De Morgan's Laws (Predicate Logic)/Denial of Universality

From ProofWiki
Jump to: navigation, search

Theorem

Let $\forall$ and $\exists$ denote the universal quantifier and existential quantifier respectively.

Then:

$\neg \forall x: P \paren x \dashv \vdash \exists x: \neg P \paren x$
If not everything is, there exists something that is not.


Proof


$[\forall x.P \paren x]^1$
$[P \paren y]^2$ $\neg P \paren y$
$\bot$ $ _1$
$\neg \forall x.P \paren x$ $\exists x. \neg P \paren x _2$
$\neg \forall x.P \paren x$

So $\exists x. \neg P \paren x \vdash \neg \forall x.P \paren x$

$\blacksquare$


Examples

Example: $\forall x \in S: x \le 3$

Let $S \subseteq \R$ be a subset of the real numbers.

Let $P$ be the statement:

$\forall x \in S: x \le 3$

The negation of $P$ is the statement written in its simplest form as:

$\exists x \in S: x > 3$


Source of Name

This entry was named for Augustus De Morgan.


Sources