Universal Quantification

The Universal Quantifier

The universal quantifier $\forall$ means “for all” or “for every”.

The statement $\forall x. P(x)$ means: $P(x)$ is true for every element $x$ in the domain of discourse.

Syntax

$\forall x \in S. P(x)$

means “for all $x$ in the set $S$, $P(x)$ holds.”

Examples

• $\forall n \in \mathbb{N}. n \geq 0$ (true)
• $\forall n \in \mathbb{Z}. n^2 \geq 0$ (true)
• $\forall n \in \mathbb{Z}. n > 0$ (false: $-1$ is a counterexample)

Proof Strategy: Universal Generalisation

To prove $\forall x \in S. P(x)$:

1. Fix an arbitrary $x$: “Let $x \in S$ be arbitrary”
2. Prove $P(x)$: Show that $P(x)$ holds for this fixed $x$
3. Conclude: Since $x$ was arbitrary, the statement holds for all $x \in S$

Key Point

The $x$ you work with must be arbitrary, not a specific value. You cannot assume anything about $x$ beyond what every element of $S$ satisfies.

Example

Statement: For all integers $n$, if $n$ is even then $n + 2$ is even.

Proof:

Let $n \in \mathbb{Z}$ be arbitrary. Assume $n$ is even.

Then $n = 2k$ for some integer $k$.

We have $n + 2 = 2k + 2 = 2(k + 1)$.

Since $k + 1$ is an integer, $n + 2$ is even.

Since $n$ was arbitrary, the statement holds for all integers.

Nested Quantifiers

Multiple quantifiers can be nested. The order matters:

$\forall x. \forall y. P(x, y)$

“For all $x$ and for all $y$, $P(x, y)$ holds.”

$\forall y. \forall x. P(x, y)$

These are equivalent: $\forall x. \forall y. P(x, y) \equiv \forall y. \forall x. P(x, y)$

However, when mixing $\forall$ and $\exists$, order matters critically.

Scope and Binding

Example

In $\forall x \in \mathbb{N}. x + y > 0$:

• $x$ is bound by $\forall$
• $y$ is free (the statement depends on $y$)

In $\forall x. \forall y. x + y > 0$:

• Both $x$ and $y$ are bound

Restricted Quantification

Instead of $\forall x \in S. P(x)$, you may see:

$\forall x. (x \in S \Rightarrow P(x))$

These are logically equivalent.

Example

$\forall n \in \mathbb{N}. n \geq 0$ is equivalent to $\forall n. (n \in \mathbb{N} \Rightarrow n \geq 0)$.

Common Structures

Universal Implication

$\forall x. (P(x) \Rightarrow Q(x))$ means “for all $x$, if $P(x)$ then $Q(x)$”.

To prove:

1. Fix arbitrary $x$
2. Assume $P(x)$
3. Prove $Q(x)$

Hidden Quantifiers

Many statements hide quantifiers:

“The product of two odd integers is odd.”

Formally: $\forall m, n \in \mathbb{Z}. (\text{Odd}(m) \land \text{Odd}(n)) \Rightarrow \text{Odd}(m \cdot n)$

Common Pitfalls

Forgetting to Fix Arbitrarily

Trap: Proving for a specific value does not prove “for all”.

Proving $P(0)$, $P(1)$, $P(2)$ does not prove $\forall n. P(n)$.

Using Non-arbitrary Values

Trap: If you pick $x = 5$ and prove $P(5)$, you have not proved $\forall x. P(x)$.

You must prove it for an arbitrary, unspecified $x$.

Assuming the Consequent

Trap: When proving $\forall x. (P(x) \Rightarrow Q(x))$, you assume $P(x)$, not $Q(x)$.

---

Summary

• $\forall x. P(x)$ means ”$P(x)$ is true for all $x$”
• Proof by universal generalisation: fix arbitrary $x$, prove $P(x)$
• $\forall x. \forall y. P(x, y) \equiv \forall y. \forall x. P(x, y)$
• Hidden quantifiers must be made explicit for rigorous proof