week 1 · day 3

Predicates & Quantifiers

'for all' and 'there exists', the reach of a claim

Easy 35 min 180 xp

After this you can

› Distinguish a proposition from a predicate (a statement with a variable)
› Use the quantifiers ∀ ('for all') and ∃ ('there exists') precisely
› Negate quantified statements correctly — the single most useful proof skill
› See why the order of quantifiers changes the meaning entirely

From fixed statements to statements about variables

Propositional logic (yesterday) handled statements that are simply true or false: "7 is prime." But real mathematics says things like "every even number greater than 2 is a sum of two primes" or "there is a smallest prime." These are claims about *many objects at once*, and to express them we need two more tools: predicates and quantifiers. This is where logic gets its reach — and where you learn to negate claims correctly, which is quietly the most useful proof skill there is.

A predicate is a statement with a blank

A predicate is a statement containing a variable, whose truth *depends* on what you plug in. Write P(n) for "n is prime." On its own, P(n) is neither true nor false — it depends on n. P(7) is true; P(8) is false. A predicate is like a sentence with a blank: "___ is prime." It becomes a genuine proposition only once the blank is filled — or once you say *how much* of the possible values it holds for. That "how much" is a quantifier.

The two quantifiers

∀ ("for all"): ∀n, P(n) means "for every n, P(n) is true." A universal claim. It's false
the instant a *single* n makes P(n) false — that n is a counterexample (day 1).
∃ ("there exists"): ∃n, P(n) means "there is at least one n for which P(n) is true." An
existence claim. It's true the instant you find *one* such n (a witness); it's false only if
*no* n works.

Key idea

Notice the beautiful asymmetry in how you *settle* each. To prove ∀ you must argue for every case (you can't check them all, so you reason about an arbitrary one — exactly the "let a be any even number" move from day 1). To disprove ∀, one counterexample suffices. To prove ∃, one example (a witness) suffices. To disprove ∃, you must rule out every case. Universal and existential claims are, in this sense, mirror images — and that mirror is the next idea.

Negation: the skill that pays off daily

Here is the rule that will serve you in nearly every proof, and it's elegant: to negate a quantified statement, swap the quantifier and negate the inside.

¬(∀n, P(n)) is (∃n, ¬P(n)) — "not everything has P" means "something lacks P."
¬(∃n, P(n)) is (∀n, ¬P(n)) — "nothing has P" means "everything lacks P."

flipping quantifiers under negation

   "All swans are white."            ¬ ->  "Some swan is NOT white."
    ∀ swan, white(swan)                     ∃ swan, ¬white(swan)

   "Some student passed."            ¬ ->  "Every student did NOT pass."
    ∃ student, passed(student)              ∀ student, ¬passed(student)

  Rule: ∀ <-> ∃ flip, and the inner statement gets negated.

Read those aloud until they feel obvious. The negation of "all swans are white" is not "all swans are non-white" — it's "*some* swan is non-white" (you only need one black swan to break "all"). The negation of "some student passed" is "*every* student failed" (for "some passed" to be false, not a single one passed). Getting this flip right is the difference between a correct proof and a subtly broken one — and it's the same skill as De Morgan (yesterday), extended to quantifiers.

Order matters — a lot

When you stack quantifiers, their order changes the meaning entirely. Compare, over the whole numbers:

∀x, ∃y, (y > x): "for every x, there exists a y bigger than it." True — pick any x, then
y = x+1 works. The y is allowed to *depend on* x (a different y for each x).
∃y, ∀x, (y > x): "there exists a y bigger than every x." False — this demands a *single* y
that beats *all* x at once, i.e. a largest number, which doesn't exist.

Note

Same symbols, opposite truth, purely from order. ∀x ∃y lets y adapt to each x; ∃y ∀x demands one y that works for all x — a far stronger, often impossible claim. Whenever you read or write nested quantifiers, ask "is the second one allowed to depend on the first?" This exact distinction underlies rigorous definitions you'll meet later (like limits: "for all ε, there exists δ..."), so building the instinct now pays off for months.

Predict first

Negate this statement completely (push the negation all the way in, flipping quantifiers and negating the inside): "For every integer n, there exists an integer m such that m > n." Then say whether the ORIGINAL statement is true.

finished reading?

Your task, you write the code

Quantify and negate

On paper, no code: (1) Translate into symbols using ∀, ∃, and a predicate: 'every positive integer has a prime factor' and 'there is an even prime.' (2) Negate each of the following correctly by flipping quantifiers and negating the inside, then state in plain English what the negation says and whether the ORIGINAL was true: (a) 'for all real x, x² ≥ 0'; (b) 'there exists an integer between 3 and 4'; (c) 'for every person there is a person taller than them.' (3) Explain, with the y=x+1 idea, why ∀x∃y differs from ∃y∀x. Everything is in this lesson.

deliverable: your symbolic translations, negations, and explanations

self-review before running

› Your negations flip ∀↔∃ AND negate the inner statement
› For each, you stated in plain English what the negation means
› You correctly judged whether each original statement is true or false
› You can explain why ∀x∃y and ∃y∀x can have opposite truth values

stretchThe rigorous definition of 'the sequence a_n converges to L' is: ∀ε>0, ∃N, ∀n>N, |a_n − L| < ε. Just READ it and identify what each quantifier is doing and why the order matters (ε first, then an N allowed to depend on ε). You don't need to use it yet — recognizing this three-quantifier structure now is a head start on calculus later.

Self-check

01What is a predicate?

02To DISPROVE a 'for all' statement (∀n, P(n)), you need:

03The negation of 'all swans are white' is:

04Over the integers, '∀x ∃y (y > x)' and '∃y ∀x (y > x)' — what's true?

0/4 correct · 0/4 checked