Quantifiers

Predicates: sentences with holes

Last lesson we kept tripping over sentences like "$x > 3$" or "$n$ is even." These aren't propositions — they have no truth value until you say what $x$ or $n$ is. We call them predicates: declarative templates with one or more free variables. Write a predicate as $P(x)$, a function from objects to truth values. $P(5)$ might be true, $P(2)$ false.

To forge a predicate into an honest proposition, you do one of two things: claim it holds for everything, or claim it holds for something. Those are the quantifiers.

For all, there exists

The universal quantifier $\forall$ means "for all" / "for every." The statement $\forall x \in \mathbb{Z},\ P(x)$ reads "for every integer $x$, $P(x)$ holds." It's true only if $P(x)$ is true for every single $x$ in the domain — no exceptions allowed.

The existential quantifier $\exists$ means "there exists" / "for some." The statement $\exists x \in \mathbb{Z},\ P(x)$ reads "there is at least one integer $x$ with $P(x)$." It's true if even one $x$ works.

Always nail down the domain — the set $x$ ranges over. "$\exists x,\ x^2 = 2$" is false over $\mathbb{Q}$ (we proved no fraction squares to $2$ informally back in Irrationals & the Real Line) but true over $\mathbb{R}$. Same predicate, different universe, different truth value. Quantifying without a domain is like firing the particle accelerator without a target — loud, useless, and someone loses an eyebrow.

The asymmetry of proof burden

Here's a structural truth that decides how you'll prove things for the rest of your life. The two quantifiers have opposite economics:

• To prove $\forall x,\ P(x)$: you must handle every $x$ — usually by arguing about an arbitrary, unnamed element (next lesson's whole technique). To disprove it: a single counterexample suffices. One purple swan and "all swans are white" is dead.
• To prove $\exists x,\ P(x)$: a single example suffices — just exhibit one $x$ that works. To disprove it: you must rule out every $x$, which is the hard universal job in disguise.

So $\forall$ is expensive to prove, cheap to refute; $\exists$ is cheap to prove, expensive to refute. One counterexample kills a universal; one witness proves an existential. This asymmetry is not some quirk to be memorized and forgotten — it's the fucking load-bearing beam of mathematical argument. Internalize it now and proofs stop feeling like guesswork.

Negation: push the not through, flip the quantifier

This is the mechanical move that makes quantifiers a tool rather than a vibe. What does it mean for "$\forall x,\ P(x)$" to be false? It means not everything satisfies $P$ — i.e., something fails it. In symbols: $\neg \big(\forall x,\ P(x)\big) \equiv \exists x,\ \neg P(x).$

And dually, "$\exists x,\ P(x)$" is false when nothing satisfies $P$ — i.e., everything fails it: $\neg \big(\exists x,\ P(x)\big) \equiv \forall x,\ \neg P(x).$

Look at what happened: the negation slid inward past the quantifier and flipped it — $\forall$ became $\exists$, $\exists$ became $\forall$ — landing on the predicate. This is De Morgan's law (from Propositions & Connectives) scaled up to infinite collections: $\forall$ is a giant AND, $\exists$ is a giant OR, and negating a giant AND gives a giant OR of negations. Same move, bigger stage.

To negate a whole chain of quantifiers, you just walk left to right flipping each one and finally negate the innermost predicate. "$\forall x\, \exists y,\ P(x,y)$" negates to "$\exists x\, \forall y,\ \neg P(x,y)$." Mechanical. Boring. Powerful. The Federation of Boring Textbook Authors makes students guess negations — actual guessing, in a mathematics class, god help them — while in my lab you compute them. No guessing. Ever. This is a lab, not a seance.

Order matters: everyone has a mother

Now the trap that sounds like philosophy but is pure logic. When you nest two different quantifiers, their order changes the meaning. Compare:

$\forall x\, \exists y,\ \text{Mother}(y, x) \qquad\text{vs}\qquad \exists y\, \forall x,\ \text{Mother}(y, x).$

The first: "for every person $x$, there exists a person $y$ who is $x$'s mother." True — everyone has a mother. Crucially, the $y$ is allowed to depend on $x$; different people get different mothers.

The second: "there exists a person $y$ such that for every person $x$, $y$ is $x$'s mother." This says one single person is the mother of everybody — a universal mom. Wildly false. Here $y$ must be chosen first, before $x$, so the same $y$ has to work for all $x$ at once.

That's the rule: in $\forall x\, \exists y$, the witness $y$ may vary with $x$. In $\exists y\, \forall x$, the witness $y$ is fixed up front and must serve every $x$. Swapping $\forall$ and $\exists$ is not free — it can turn a true statement into a catastrophic falsehood. This exact distinction is the soul of the epsilon-delta definitions you'll meet far down the line; getting it wrong there is precisely how otherwise intelligent people fail analysis and end up resenting mathematics forever, and I will not let that happen to you.

Translate until it's boring

The only way to own this is reps — boring, unglamorous, infallible reps. Take "every positive real has a square root" and grind it both directions: $\forall x \in \mathbb{R},\ \big(x > 0 \to \exists y \in \mathbb{R},\ y^2 = x\big).$ Notice the hidden implication from last lesson is still in there — "every positive $A$" gives a $\forall$ guarding a $\to$. Read symbols into crisp English, read English into airtight symbols, back and forth, until it's so automatic it's dull. Dull is the goal. Now go.