Mathematics.

predicate logic

Quantifiers

Mathematical Logic20 minDifficulty3 out of 10

You should know: predicate logic

Overview

A quantifier specifies how many members of a domain satisfy a given property, turning an open statement with a free variable ('x is even') into a statement with a definite truth value ('for all x, x is even' — false; 'there exists an x that is even' — true). The two quantifiers of first-order logic, universal (∀) and existential (∃), are the backbone of how mathematics states general laws and existence claims precisely.

Intuition

Compare 'every student passed the exam' (a claim about ALL students — false if even one failed) with 'some student passed the exam' (a claim about AT LEAST ONE student — true if just one did). These are exactly the universal and existential quantifiers. Getting the order of nested quantifiers right matters enormously: 'for every door there exists a key that opens it' is very different from 'there exists a key that opens every door'.

Formal Definition

Definition

The two quantifiers of first-order logic:

∀x P(x)\forall x\, P(x)

P(x) is true for every x in the domain

Universal
∃x P(x)\exists x\, P(x)

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

Existential
¬∀x P(x)≡∃x ¬P(x),¬∃x P(x)≡∀x ¬P(x)\neg \forall x\, P(x) \equiv \exists x\, \neg P(x), \qquad \neg \exists x\, P(x) \equiv \forall x\, \neg P(x)
Quantifier duality (De Morgan for quantifiers)

Notation

NotationMeaning
∀\forall'for all' — the universal quantifier
∃\exists'there exists' — the existential quantifier
∃!\exists!'there exists exactly one' — the unique existential quantifier

Properties

Quantifier order matters

∀x ∃y P(x,y)≢∃y ∀x P(x,y)\forall x\, \exists y\, P(x,y) \not\equiv \exists y\, \forall x\, P(x,y)

Example: 'Everyone has a mother' (∀x∃y) vs. 'someone is the mother of everyone' (∃y∀x) — very different claims.

Vacuous truth

∀x∈∅ P(x) is always true\forall x \in \emptyset\, P(x) \text{ is always true}

Condition: A universal statement over an empty domain is vacuously true

Applications

Formal specification languages (used in program verification) rely entirely on nested ∀/∃ statements to precisely state correctness properties.

Worked Examples

  1. For all integers x, there exists a y that is x's successor.

    ∀x∈Z ∃y∈Z (y=x+1)\forall x \in \mathbb{Z}\, \exists y \in \mathbb{Z}\, (y = x+1)

Answer: ∀x∈ℤ ∃y∈ℤ (y=x+1)

Practice Problems

Difficulty 3/10

Is the statement ∀x∈ℝ ∃y∈ℝ (y² = x) true?

Common Mistakes

Common Mistake

Assuming ∀x∃y P(x,y) and ∃y∀x P(x,y) mean the same thing.

They don't — in ∃y∀x, the SAME y must work for every x; in ∀x∃y, each x may get its own different y. The second is a strictly stronger claim.

Summary

  • ∀ ('for all') and ∃ ('there exists') convert open statements into statements with a definite truth value.
  • Negating a quantified statement flips ∀↔∃ and negates the inner predicate (quantifier duality).
  • The order of nested quantifiers changes meaning — ∀∃ and ∃∀ are generally NOT equivalent.
  • A universal statement over an empty domain is vacuously true.

References

  1. WebsiteWikipedia — Quantifier (logic)