title: "Quantifier"

Quantifier

Definition. A quantifier turns a statement about one object into a statement about many: "for all $x$, $P(x)$" asserts $P$ of every $x$, and "there exists $x$ with $P(x)$" asserts $P$ of at least one. Negation flips each quantifier and pushes inward: not "for all $x$, $P(x)$" is "there exists $x$ with not $P(x)$", and not "there exists $x$ with $P(x)$" is "for all $x$, not $P(x)$". Negating an implication is the third rule you need: not "if $P$ then $Q$" is "$P$ and not $Q$". Quantifier order matters: "every lock has a key" and "some key opens every lock" are different claims.

Introduced in Lecture 1; negating quantifiers correctly is the entire mechanism of disproving Big-O claims and of the pumping lemma arguments in Lecture 4.