Quantifiers and Predicates

Statements About Many Objects

A predicate is a statement with a variable, like $P(x): \text{"}x^2 \ge 0\text{"}$ — it becomes true or false only once $x$ is specified. To make definite statements about all or some values, mathematics uses quantifiers, which bind the variable and range over a domain.

The two quantifiers:

• Universal $\forall x\, P(x)$ — "for all $x$, $P(x)$": true when $P$ holds for every element of the domain.
• Existential $\exists x\, P(x)$ — "there exists $x$ with $P(x)$": true when at least one element satisfies $P$.

Order matters when quantifiers mix. $\forall x\, \exists y\, P(x, y)$ ("for every $x$ there is some $y$") is generally weaker than $\exists y\, \forall x\, P(x, y)$ ("there is one $y$ that works for every $x$"). Over the integers, "for every $x$ there is a larger $y$" is true, but "there is a $y$ larger than every $x$" is false. Swapping quantifier order can change a true statement into a false one.

Negation follows a precise rule — push the negation inward, flipping each quantifier and negating the predicate: $$\neg \forall x\, P(x) \;\equiv\; \exists x\, \neg P(x), \qquad \neg \exists x\, P(x) \;\equiv\; \forall x\, \neg P(x).$$ So the negation of "all are $P$" is "some is not $P$" — which is why a single counterexample disproves a universal claim, and why "there is no $x$ with $P$" means "every $x$ fails $P$."

Common pitfall: swapping the order of mixed quantifiers or negating them incorrectly. $\forall x\, \exists y$ is not interchangeable with $\exists y\, \forall x$. And $\neg \forall x\, P(x)$ is $\exists x\, \neg P(x)$ — "not all are $P$" means "at least one is not," not "none is $P$." Negation flips $\forall \leftrightarrow \exists$ while negating the inside.