Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 37 · Predicate Logic

Nested Quantifiers and Negating Quantified Statements

Understand why the order of nested quantifiers matters, how to negate ∀ and ∃ statements correctly, and how to check them with Python loops over finite domains.

Real statements usually involve more than one quantifier. "Everybody loves somebody" and "somebody is loved by everybody" use the same words but say very different things. This lesson teaches you to read nested quantifiers, to see why order matters, and to negate quantified statements without error.

Reading nested quantifiers

Read left to right, as a game between two players. For ∀x ∃y P(x, y): an opponent picks any x; then you must produce a y that works for that x. For ∃y ∀x P(x, y): you must first commit to a single y that then works against every x the opponent might pick.

Example with P(x, y) meaning "x < y" over the integers:

  • ∀x ∃y (x < y): for every integer there is a larger one. True (take y = x + 1).
  • ∃y ∀x (x < y): some single integer is larger than all integers. False.

Swapping ∀ and ∃ changes the meaning. Swapping two quantifiers of the same kind (∀x ∀y to ∀y ∀x) does not.

Python Order of quantifiers matters

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the first world everyone loves Ben, so both statements hold. In the cycle, everybody loves somebody, but nobody is loved by everyone: only the first (weaker) statement is true. In general ∃y ∀x P implies ∀x ∃y P, never the reverse.

Quantifier order

∀x ∃y y may depend on x
∃y ∀x One y works for all x
∃∀ implies ∀∃ Never the other way

Swap different quantifiers and the meaning changes

1 / 2

Negating quantifiers

The negation rules are the quantifier version of De Morgan's laws:

  • ¬∀x P(x) ≡ ∃x ¬P(x): "not everyone passed" means "someone did not pass".
  • ¬∃x P(x) ≡ ∀x ¬P(x): "nobody passed" means "everyone failed".

To negate a longer statement, push the negation inward, flipping each quantifier and finally negating the predicate:

¬∀x ∃y (x < y) becomes ∃x ∀y ¬(x < y), that is ∃x ∀y (y ≤ x): "there is a largest element".

Also remember the propositional rules: ¬(A → B) ≡ A ∧ ¬B. Negating ∀x (Even(x) → Div2(x)) gives ∃x (Even(x) ∧ ¬Div2(x)): "some even number is not divisible by 2".

Python Check the negation laws

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Patterns you will meet again

Many famous definitions have the shape ∀ … ∃ … or ∃ … ∀ …:

  • Limit of a sequence: ∀ε>0 ∃N ∀n>N |aₙ − L| < ε. Negating it (swap every quantifier) tells you what "does not converge to L" means: ∃ε>0 ∀N ∃n>N |aₙ − L| ≥ ε.
  • Surjective function f:A→B: ∀b ∃a f(a) = b.
  • Upper bound: ∃M ∀x x ≤ M.
  • Uniform continuity vs continuity: differ only by where the ∃δ sits.
Python Surjective, injective and an upper bound on finite sets

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Translating nested statements carefully

  1. Identify each variable and its domain.
  2. Read the English left to right; each "every", "some", "no" introduces a quantifier in that order.
  3. Decide whether later quantifiers may depend on earlier variables.
  4. Add restrictions with → (for ∀) and ∧ (for ∃).
  5. Test with a tiny model you can enumerate.

"No" is a quantifier too: "no student failed" is ∀s ¬Failed(s), equivalently ¬∃s Failed(s).

Common mistakes

  • Negating ∀x P(x) as ∀x ¬P(x) ("everything fails") instead of ∃x ¬P(x).
  • Treating ∀x ∃y and ∃y ∀x as interchangeable.
  • Forgetting to negate the predicate at the end.
  • Leaving implications unnegated: the negation of A → B is A ∧ ¬B.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is the negation of ∀x P(x)?

    Not everything satisfies P exactly when something fails P.
  2. 2. Over the integers with P(x,y) = 'x < y', which is true?

    Every integer has a larger one, but no single integer exceeds all integers.
  3. 3. Negate ∀x (Even(x) → Div2(x)).

    Flip ∀ to ∃ and negate the implication, which gives a conjunction.
  4. 4. Which implication between quantifier orders always holds?

    If one y works for all x, then each x has a y that works; the converse can fail.

Summary

  • Read nested quantifiers left to right: later variables may depend on earlier ones.
  • ∀x ∃y and ∃y ∀x differ; ∃∀ implies ∀∃ but not conversely.
  • ¬∀ becomes ∃¬ and ¬∃ becomes ∀¬; push negation inward and negate the predicate.
  • Epsilon-delta style definitions are alternating quantifier chains.
  • Test translations on tiny finite models.

Next: Models and Interpretations