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

From ProofWiki
Jump to navigation Jump to search


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

Formulation 1

$\neg \paren {\forall x: \map P x} \dashv \vdash \exists x: \neg \map P x$

Formulation 2

$\vdash \neg \paren {\forall x: \map P x} \iff \paren{ \exists x: \neg \map P x }$

In text, this can be summarised as:

If not everything is, there exists something that is not.


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.