Existential Quantification

The Existential Quantifier

The existential quantifier $\exists$ means “there exists” or “there is”.

The statement $\exists x. P(x)$ means: there is at least one element $x$ (in the domain) such that $P(x)$ holds.

Syntax

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

means “there exists an $x$ in the set $S$ such that $P(x)$ holds.”

Examples

• $\exists n \in \mathbb{N}. n > 10$ (true: $n = 11$ works)
• $\exists n \in \mathbb{Z}. n^2 = 4$ (true: $n = 2$ or $n = -2$)
• $\exists n \in \mathbb{Z}. n^2 = 2$ (false: no integer squared equals 2)

Proof Strategy: Constructive Existence

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

1. Exhibit a witness: Find a specific value $x_0 \in S$
2. Verify: Prove that $P(x_0)$ holds

This is called a constructive proof of existence.

Example

Statement: There exists an even prime number.

Proof:

Take $x_0 = 2$.

We verify: $2$ is even (since $2 = 2 \cdot 1$) and $2$ is prime (its only divisors are $1$ and $2$).

Therefore, $\exists n \in \mathbb{N}$ such that $n$ is even and prime.

Non-constructive Existence

Sometimes we can prove $\exists x. P(x)$ without exhibiting a specific witness.

Example: “There exist irrational numbers $a, b$ such that $a^b$ is rational.”

Non-constructive proof: Consider $\sqrt{2}^{\sqrt{2}}$.

• If it’s rational, take $a = \sqrt{2}$, $b = \sqrt{2}$
• If it’s irrational, take $a = \sqrt{2}^{\sqrt{2}}$, $b = \sqrt{2}$, and note $a^b = (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^2 = 2$

In either case, such $a, b$ exist.

Nested Quantifiers

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

“There exists an $x$ such that for all $y$, $P(x, y)$ holds.”

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

“For all $y$, there exists an $x$ such that $P(x, y)$ holds.”

Order Matters!

These are NOT equivalent:

$\exists x. \forall y. P(x, y) \not\equiv \forall y. \exists x. P(x, y)$

Example

Consider $P(x, y) : \equiv$ ”$x$ loves $y$” over people.

• $\exists x. \forall y. P(x, y)$: There is someone who loves everyone.
• $\forall y. \exists x. P(x, y)$: Everyone is loved by someone.

The second is much weaker.

Example over $\mathbb{R}$

• $\exists x. \forall y. x \leq y$: False (no smallest real)
• $\forall y. \exists x. x \leq y$: True (take $x = y - 1$)

De Morgan’s Laws for Quantifiers

Negation of Universal

$\neg(\forall x. P(x)) \equiv \exists x. \neg P(x)$

“It is not the case that all $x$ satisfy $P$” means “there exists an $x$ that does not satisfy $P$.”

Negation of Existential

$\neg(\exists x. P(x)) \equiv \forall x. \neg P(x)$

“It is not the case that some $x$ satisfes $P$” means “all $x$ fail to satisfy $P$.”

Example

$\neg(\forall n \in \mathbb{N}. n > 0) \equiv \exists n \in \mathbb{N}. n \leq 0$

The witness is $n = 0$.

Common Structures

Existential Implication

$\exists x. (P(x) \Rightarrow Q(x))$ is tricky.

Note: $P(x) \Rightarrow Q(x)$ is equivalent to $\neg P(x) \lor Q(x)$.

So $\exists x. (P(x) \Rightarrow Q(x))$ is equivalent to $\exists x. (\neg P(x) \lor Q(x))$.

Example

$\exists x \in \mathbb{R}. (x < 0 \Rightarrow x^2 < 0)$

This is true: take $x = 1$. Then $x < 0$ is false, so the implication is vacuously true.

Common Pitfalls

Unverified Witness

Trap: Claiming $\exists x. P(x)$ without verifying $P(x)$ for your candidate.

Example: To prove $\exists n. n^2 + n + 41$ is prime, you cannot just say “take $n = 40$” without checking.

Wrong Quantifier Order

Trap: Confusing $\exists x. \forall y$ with $\forall y. \exists x$.

They are NOT equivalent.

Using a Variable Without Introduction

Trap: Using $x$ in a proof without specifying where it comes from.

When proving $\forall x. \exists y. P(x, y)$, for each $x$ you must say how to find $y$.

---

Summary

• $\exists x. P(x)$ means “there exists an $x$ such that $P(x)$”
• Prove constructively: exhibit a witness $x_0$ and verify $P(x_0)$
• Quantifier order matters: $\exists x. \forall y \not\equiv \forall y. \exists x$
• De Morgan: $\neg\forall x. P(x) \equiv \exists x. \neg P(x)$ and $\neg\exists x. P(x) \equiv \forall x. \neg P(x)$