Predicate Logic and Quantifiers

Statements About Everything and Something

Propositional logic cannot express "every integer has a successor" — it has no way to talk about all or some objects. Predicate logic adds predicates — statements $P(x)$ with a variable, true or false depending on $x$ — and quantifiers that range over a domain.

The two quantifiers:

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

The order of mixed quantifiers matters enormously. $\forall x\, \exists y\, P(x,y)$ ("every $x$ has some $y$") is generally different from $\exists y\, \forall x\, P(x,y)$ ("some single $y$ works for all $x$") — the second is much stronger. "Every person has a mother" is true; "there is one mother of everyone" is false. Swapping quantifiers can silently change the meaning.

Negating quantified statements follows a clean rule that flips the quantifier and negates 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).$$ In words: the negation of "all are $P$" is "some is not $P$" (one counterexample suffices), and the negation of "some is $P$" is "none is $P$." This is why a universal claim is disproved by a single counterexample.

Common pitfall: swapping the order of quantifiers or negating them incorrectly. $\forall x\, \exists y$ is not the same as $\exists y\, \forall x$. And $\neg \forall x\, P(x)$ is $\exists x\, \neg P(x)$ — "not all" means "at least one isn't," not "none is." Negation flips $\forall$ to $\exists$ (and vice versa) while negating the inside.