Home / Courses / Intro to Proofs / Unit 2

Intro to Proofs Unit 2: Quantifiers

Quantifiers say how many objects a statement is about: all of them or at least one. Reading, writing and negating quantified statements is what lets you know exactly what a proof must show.

Covers: Open sentences and domains, Universal and existential quantifiers, Translating English into symbols, Negating quantified statements, Nested quantifiers and their order, Counterexamples, Unique existence

Study guide

An open sentence, or predicate, such as P(x): 'x² > 4', has a variable and no truth value until the variable is fixed. A quantifier turns it into a proposition. The universal quantifier ∀x P(x) claims P(x) is true for every x in the domain. The existential quantifier ∃x P(x) claims at least one x in the domain makes P(x) true. The domain matters: ∃x (x² = 2) is false over the integers but true over the reals. Always ask what set the variable ranges over, and write it explicitly, as in ∀x ∈ ℝ or ∃n ∈ ℤ, whenever there is any doubt.

Negation swaps the quantifiers. ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x). So the negation of 'every student passed' is 'some student did not pass', not 'no student passed'. Universal statements are often conditionals in disguise: 'every prime is odd' means ∀n (n prime → n odd), and its negation is ∃n (n prime ∧ n not odd). That is why a single counterexample, one object satisfying the hypothesis but not the conclusion, disproves a universal claim. By contrast, checking examples never proves a universal statement over an infinite domain, no matter how many you try.

When quantifiers are nested, their order matters. ∀x ∃y (x < y) says each x has some larger y, and y may depend on x, so it is true over the reals. ∃y ∀x (x < y) says one y beats every x, which is false. Read nested statements left to right as a game: for each ∀, an opponent picks the value; for each ∃, you pick, knowing the earlier choices. To negate a nested statement, flip every quantifier from left to right and then negate the innermost predicate, converting any inner conditional A → B into A ∧ ¬B.

Unique existence ∃! x P(x) means exactly one x satisfies P. It combines existence, ∃x P(x), with uniqueness: if P(x) and P(y) then x = y. Proving a ∃! statement takes two parts: exhibit a witness, then show any two witnesses are equal. When translating English, 'every', 'all' and 'any' usually signal ∀; 'some', 'there is' and 'at least one' signal ∃; and 'no' signals ¬∃. Definitions such as bounded, continuous and onto are quantified statements, so learning to negate them precisely is how you find out what a counterexample must look like.

Key ideas

• A quantifier's truth value depends on the domain it ranges over.
• ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x).
• One counterexample disproves a universal statement; examples never prove one over an infinite domain.
• Swapping ∀ and ∃ in a nested statement usually changes its meaning.
• In ∀x ∃y, the choice of y may depend on x.
• To negate a nested statement, flip every quantifier and negate the inner predicate.
• ∃! requires both existence and uniqueness.

Formulas and rules

Common mistakes

• Negating 'all are' as 'none are' instead of 'some are not'.
• Swapping the order of ∀ and ∃ when translating, which changes the meaning.
• Forgetting to negate the inner predicate after flipping the quantifiers.
• Leaving an inner conditional as a conditional in a negation instead of writing A ∧ ¬B.
• Treating a few confirming examples as a proof of a universal claim.

Before the test, make sure you can

• Translate English sentences with 'every', 'some', 'no' and 'only' into quantified symbols.
• Determine the truth value of a quantified statement over a given domain.
• Negate statements with one or more quantifiers, including inner conditionals.
• Explain how changing the order of ∀ and ∃ changes meaning, with an example.
• Produce a counterexample to a false universal statement.
• State and prove what ∃! requires: existence and uniqueness.
• Write the negation of a definition such as bounded or continuous.

Words to know

Predicate (open sentence)

A sentence with variables, such as 'x > 3', whose truth depends on the values substituted.

Domain

The set of values a quantified variable ranges over.

Universal quantifier

∀x P(x): P(x) is true for every x in the domain.

Existential quantifier

∃x P(x): P(x) is true for at least one x in the domain.

Unique existence

∃! x P(x): exactly one x in the domain makes P(x) true.

Counterexample

An element that makes the hypothesis of a universal statement true and its conclusion false.

Witness

A specific element that shows an existential statement is true.

Nested quantifiers

Quantifiers applied in sequence, such as ∀x ∃y P(x, y); order matters.

Bound variable

A variable governed by a quantifier, which cannot be replaced by a value from outside.

Free variable

A variable not governed by any quantifier, so the sentence is still open.

Negating ∀

¬∀x P(x) ≡ ∃x ¬P(x).

Negating ∃

¬∃x P(x) ≡ ∀x ¬P(x).

Vacuous universal

∀x ∈ ∅ P(x) is true, since there is nothing to check.

Bounded function

∃M ∀x (|f(x)| ≤ M): one bound works for all inputs.

Sample practice questions

30 more questions like these, from level 1 to 5, are in the practice set.