Predicate logic and quantifiers

A proposition is a sentence that is simply true or false. Most mathematical sentences are not like that on their own: "\( n \) is even" depends on \( n \). A predicate is such a sentence with a variable in it, written \( P(n) \), and it becomes a proposition once we substitute a value or quantify the variable. The universal quantifier \( \forall n\, P(n) \) says \( P(n) \) holds for every \( n \) in the domain; the existential quantifier \( \exists n\, P(n) \) says it holds for at least one. The domain is part of the statement: \( \exists x\,(x^2 = 2) \) is false over the rationals and true over the reals.

On a finite domain the quantifiers are just long conjunctions and disjunctions. Over the domain \( \{a, b\} \), \( \forall x\,P(x) \) means \( P(a) \land P(b) \) and \( \exists x\,P(x) \) means \( P(a) \lor P(b) \). That is why the rules for negating quantifiers are De Morgan's laws in disguise: \[ \lnot\,\forall x\,P(x) \equiv \exists x\,\lnot P(x), \qquad \lnot\,\exists x\,P(x) \equiv \forall x\,\lnot P(x). \] The example checks the two-element case, \( \lnot(p \land q) \leftrightarrow (\lnot p \lor \lnot q) \), and finds a tautology. To negate a statement with several quantifiers, push the negation inwards one quantifier at a time, flipping each one as it passes.

The order of different quantifiers changes the meaning. Over the integers, \( \forall n\,\exists m\,(m > n) \) says every integer has a larger one, which is true: the \( m \) may depend on \( n \). But \( \exists m\,\forall n\,(m > n) \) says one integer is larger than all of them, which is false. Quantifiers of the same kind commute: \( \forall x\,\forall y \) is the same as \( \forall y\,\forall x \). The definition of a limit, \( \forall \varepsilon > 0\ \exists \delta > 0\ \forall x \dots \), is the standard example of a statement whose whole content lies in its quantifier order.

Picture it: draw the domain as a row of boxes, one per element, each lit if \( P \) holds there. "For all" asks whether every box is lit; "there exists" asks whether at least one is. Negating "every box is lit" does not give "no box is lit"; it gives "some box is dark".

Think it: read \( \forall\exists \) statements as a game. An opponent picks the universally quantified value, you answer with the existential one, and the statement is true when you have a winning strategy. In \( \forall n\,\exists m\,(m > n) \) you win by answering \( m = n + 1 \). Swapping the quantifiers makes you move first, and then the opponent always wins.