Negation of Quantified Statements

Negation of universal quantifier

Assume the statement $\forall x P(x)$, for some domain $D$. This statement asserts that every element of $D$ has the property $P$. By negation, we mean that it is not the case. If it is not the case that every element of $D$ has the property $P$, then there must be at least one element in $D$ that does not have the property $P$. That is,

$$\neg (\forall_{x\in D} P(x)) \equiv \exists_{y \in D} \neg P(y).$$

Similarly, the negation has the same effect for more than one universal quantifier. Again, with a generic domain $D$, assume the following statement:

$$\forall_{x\in D} \forall_{y\in D} \forall_{z\in D} P(x,y,z).$$

This statement asserts that for every selection of three elements $a,b,$ and $c$, from $D$, the predicate $P(a,b,c)$ is true. The negation of this statement means that it is not the case. This means there must be at least one selection of three elements $e,f,$ and $g$, such that $P(e,f,g)$ is not true. We can state this fact as follows:

$$\neg\left(\forall_{x\in D} \forall_{y\in D} \forall_{z\in D} P(x,y,z)\right) \equiv \exists_{x\in D} \exists_{y\in D} \exists_{z\in D} \neg P(x,y,z).$$

Let’s look at a few examples.

Examples

Let’s look at a few examples:

---

Assume the domain to be $M$, which is the set of all mammals. That is,

$M = \{x | x$ is a mammal.$\}$

---

Make a predicate as follows:

• $P(x)$: $x$ has four legs.

Quantify this predicate to make the following statement:

• $\forall x P(x)$: Every mammal has four legs.

The negation of this statement is as follows:

• $\neg\left(\forall x P(x)\right)$: It is not the case that every mammal has four legs.

The logical equivalent of this statement is as follows:

• $\exists x \neg P(x)$: There exists a mammal that does not have four legs.