Quantifiers

There are two quantifiers:

• $\forall x$ reads "for all $x$"

• $\exists x$ reads "there exists $x$ such that..."

Example 1

Consider the statement $(\forall x \neq 0) (\exists y) (xy = 1)$ says that every $x$ other than zero has a multiplicative inverse. This statement is valid over $\mathbb{R}$ and $\mathbb{Q}$ but not $\mathbb{Z}$. Therefore, the validity of a statement depends crucially on the universe we are working in. We often make the universe explicit by writing $(\forall x \in U)$ where $U$ is the universe.

Example 2

The statement "there exists an integer between $5$ and $8$" can be written mathematically as $(\exists x \in \mathbb{Z})(5 \le x \le 8)$.

Notice that the statement "$(5 ≤ x ≤ 8)$" is not a proposition. We call it a propositional formula P(x) (or a predicate).

Example 3

The ordering of the quantifier matters. Consider the following two statements:

• $(\exists x \in \mathbb{Z}) (\forall y \in \mathbb{Z}) (y\le x)$. This statement reads "there exists a largest integer".
• $(\forall y \in \mathbb{Z}) (\exists x\in \mathbb{Z}) (y \le x)$. This statement can be read as "given an integer, there is a larger (or equal) one".

Obviously, the first statement is false, while the second is true.

Negation: Let $P$ and $Q$ be propositions. The negation of conjunction $\neg (P \land Q)$ is the same as $(\neg P \lor \neg Q)$. Similarly for the negation of disjunction $\neg(P \lor Q) \equiv \neg P \land \neg Q$. These simple rules are known as De Morgan’s Laws. Since we can view $(\exists x \in U) P(x)$ as $\bigvee_{a\in U} P(a)$ (read as the conjunction of $P(a)$ with a over $U$), it should be intuitive to believe that $\neg (\exists x \in U) P(x)$ is the same as $(\forall x \in U) \neg P(x)$. Similar rules apply to the universal quantifier, i.e., $\neg(\forall x \in U)P(x) \equiv (\exists x \in U) \neg P(x)$.

Example 4 (Distinct solutions)

How to write a statement "there are at least two distinct integers that satisfy $P(x)$"? One way to do it is $(\exists x \in \mathbb{Z}) (\exists y \in \mathbb{Z}) ((x \neq y) \land P(x) \land P(y))$. What about the statement "there are at most two distinct integers that satisfy P(x)"? Here it is:

$$(\exists x)(\exists y)(\forall q)[P(q) \Rightarrow (q = x \lor q = y)]$$

Example 5 (Two-player game)

In a two-player game (like chess), the statement "Black will checkmate in two turns" can also be written using alternating quantifiers. Let us try to understand this. Let $B(x, y)$ be the predicate indicating that if White uses strategy y and Black uses x, then Black wins. So we can write $(\forall y)(\exists x)B(x, y)$ to say that no matter how White plays the current turn, Black has a strategy to win.