Quantifiers and Predicates

Predicates and Quantifiers

A predicate is a statement with a variable, like $P(x): x^2 \ge 0$, which becomes true or false only when $x$ is specified. Quantifiers bind variables over a domain to make definite claims.

Order matters for mixed quantifiers. $\forall x \, \exists y \, P(x, y)$ means for every $x$ there is some $y$. This is weaker than $\exists y \, \forall x \, P(x, y)$, where one single $y$ works for every $x$.

Example: Over integers, "for every $x$ there is a larger $y$" is true, but "there is a $y$ larger than every $x$" is false. Swapping order can change truth value.

Negating Quantifiers

Negation of quantifiers requires pushing the negation inward, flipping the quantifier and negating the predicate:

$$\neg \forall x \, P(x) \equiv \exists x \, \neg P(x)$$ $$\neg \exists x \, P(x) \equiv \forall x \, \neg P(x)$$

The negation of "all are $P$" is "some is not $P$." This is why a single counterexample disproves a universal claim.

Common pitfall: $\neg \forall x \, P(x)$ means at least one is not $P$, not that none are $P$. Never swap $\forall x \, \exists y$ with $\exists y \, \forall x$, as order completely changes logical meaning.