Proofs with Quantifiers

“I mean the word proof not in the sense of the lawyers, who set two half proofs equal to a whole one, but in the sense of a mathematician, where half proof = 0, and it is demanded for proof that every doubt becomes impossible.”
—Carl Friedrich Gauss

Although there are many ways to structure proofs, the “default” (and most common) approach is to have the structure of the proof exactly match the structure of the formula being proved. In this section, we consider common patterns involving proofs for quantified formulas.

Universal Quantifiers

By far the most common way to prove an assertion of the form $\forall x\ P(x)$ is to present a proof that starts by assuming $x$ is completely arbitrary, and showing that we can prove $P(x)$ . If we can do so with no assumptions about $x$ , then our proof is completely general, the same argument would work for any specific value of $x$ , and so $\forall x\ P(x)$ holds.

In the more common case of restricted quantifiers like $\forall x\in S\ \ P(x)$ , we use the same idea except we assume we know nothing about $x$ except that it is an element of $S$ .

As usual, there are many possible choices of wording. Here are several examples of the pattern:

Example

Theorem: $\forall x\in S\ \ P(x)$

Proof: Let $x\in S$ be arbitrary.
⋮
Thus, $P(x)$ .

Theorem: $\forall x\in S\ \ P(x)$

Proof: Let $x\in S$ be given.
⋮
so $P(x)$ .

Theorem: $\forall x\leq N\ \ P(x)$

Proof: Assume $x\leq N$ .
⋮
so $P(x)$ .

Theorem: $\forall x\leq N\ \ P(x)$

Proof: Let $x\leq N$ be fixed but arbitrary.
⋮
so $P(x)$ .

Existential Quantifiers

The most direct to prove an assertion of the form $\exists x\ P(x)$ is to find such a value. (Or show that one of several values must work.) Here are several examples of the pattern:

Example

Theorem: $\exists x\in \mathbb{N}\ \ P(x)$

Proof:
⋮
Thus, $P(42)$ .

Theorem: $\exists x\in \mathbb{N}\ \ P(x)$

Proof: Put $x = 42$ .
⋮
and hence $P(x)$ .

Theorem: $\exists x\in \mathbb{N}\ \ P(x)$

Proof:
⋮
Therefore, $P(42)$ or $P(47)$ .

Universally Quantified Implications

Many mathematical statements are universally quantified implications. In these cases, we can combine the pattern for proving a universally quantified formula with the pattern for proving an implication.

Example

Theorem: $\forall x\in S\ \ \bigl(P(x)\to Q(x)\bigr)$

Proof: Let $x\in S$ be arbitrary.
Assume $P(x)$ .
⋮
Thus, $Q(x)$ .

Theorem: $\forall x\in S\ \ \bigl(P(x)\to Q(x)\bigr)$

Proof: Let $x\in S$ be given such that $P(x)$ .
⋮
Thus, $Q(x)$ .

Multiple Quantifiers

If a statement corresponds to a formula with multiple quantifiers, we just apply the appropriate patterns for each quantifier in order.

Example

Theorem: $\forall x{\in} \mathbb{N}\ \ \exists y{\in}\mathbb{N} \ R(x,y)$

Proof:
Let $x{\in}\mathbb{N}$ be given.
Let $y = \min\{\lfloor\sqrt{x}\rfloor, 10\}$ .
⋮
Thus, $R(x,y)$ .

Theorem: $\exists x{\in} \mathbb{N}\ \ \forall y{\in}\mathbb{N} \ R(x,y)$

Proof:
Put $x := \min\{\lfloor\sqrt{x}\rfloor, 10\}$ .
Let $y{\in}\mathbb{N}$ be given.
⋮
Thus, $R(x,y)$ .

Theorem: $\forall x{\in} \mathbb{N}\ \ \forall y{\in}\mathbb{N} \ R(x,y)$

Proof:
Let $x{\in}\mathbb{N}$ and $y{\in}\mathbb{N}$ be arbitrary.
⋮
Thus, $R(x,y)$ .

Theorem: $\exists x{\in} \mathbb{N}\ \ \exists y{\in}\mathbb{N} \ R(x,y)$

Proof:
Put $x{:=}42$ and $y:=47$ .
⋮
Thus, $R(x,y)$ .

Example

Theorem: $\forall x{\in} \mathbb{N}\ \ \forall y{\in}\mathbb{N} \ \forall z{\in}\mathbb{N}\ T(x,y,z)$

Proof:
Let $x{\in}\mathbb{N}$ and $y{\in}\mathbb{N}$ and $z{\in}\mathbb{N}$ be given.
⋮
Thus, $T(x,y,z)$ .

Theorem: $\forall x{\in} \mathbb{N}\ \ \exists y{\in}\mathbb{N} \ \exists z{\in}\mathbb{N}\ T(x,y,z)$

Proof:
Let $x{\in}\mathbb{N}$ be given.
Put $y := x+1$ and $z := 2x$ .
⋮
Thus, $T(x,y,z)$ .

Theorem: $\exists x{\in} \mathbb{N}\ \ \forall y{\in}\mathbb{N} \ \exists z{\in}\mathbb{N}\ T(x,y,z)$

Proof:
Put $x{:=}99$ .
Let $y{\in}\mathbb{N}$ be given.
Put $z := x+y-1$ .
⋮
Thus, $T(x,y,z)$ .

Using Quantified Formulas

Common strategies for proving a quantified statement mimic the Introduction rules of Natural Deduction. Similarly, strategies for applying quantified statements already known (or assumed) to be true mimic the Elimination rules of Natural Deduction.

Using Universally Quantified Statements

Once we know something is true for all $x$ , we can assert it any specific value(s) of interest.

Example

Proof:
Assume $\forall n{\in}\mathbb{N}\ Q(n)$ .
Then $Q(42)$ , so …
⋮

Proof:
Assume $\forall n{\in}\mathbb{N}\ Q(n)$ .
⋮
By assumption, $Q(0)$ and $Q(1)$ , so …

Using Existentially Quantified Statements

If we know something exists, we can give that thing a name. The name may or may not be the same as the bound variable in our existential; it doesn’t matter except that we may not use a name that we’re not already using to stand for some other specific value. (Also, as in the $\exists E$ rule, the name we choose for “the thing that exists” should not be a free variable in the conclusion of our proof.)

Example

Proof:
Assume $\exists n{\in}\mathbb{N}\ Q(n)$ .
Then $Q(k)$ for some $k{\in}\mathbb{N}$ , so … $k$ …

Proof:
Assume $\exists n{\in}\mathbb{N}\ Q(n)$ .
Then $Q(n)$ for some $n{\in}\mathbb{N}$ , so … $k$ …

Using Statements with Nested Quantifiers

Nested quantifiers work as above; we just handle each quantifier in sequence.

Example

Proof:
Assume $\forall x\in\mathbb{R}\ \forall y\in\mathbb{R}\ \exists z{\in}\mathbb{R}\ \ f(x,z)=g(y)$ .

Then there exist $z_1{\in}\mathbb{R}$ such that $f(3,z_1) = g(4)$
and $z_2{\in}\mathbb{R}$ such that $f(9, z_2) = g(7)$ .
⋮

Note: Implicit in this proof is that plugging $3$ in for $x$ in the assumption gives us

\forall y\in\mathbb{R}\ \exists z{\in}\mathbb{R}\ f(3,z)=g(y).

Plugging $4$ in for $y$ in that statement gives us

\exists z{\in}\mathbb{R}\ f(3,z)=g(4).

and we chose the name $z_1$ for this value that exists.

We called it $z_1$ rather than $z$ because we immediately doing the same thing again with $x := 9$ and $y := 7$ to get

\exists z{\in}\mathbb{R}\ f(9,z)=g(7),

and we can’t use the name for the $z$ for both numbers known to exist (since there’s no reason to believe they’ll be equal).

Proof:
Assume $\exists z\in\mathbb{R}\ \forall x\in\mathbb{R}\ \forall y{\in}\mathbb{R}\ \ f(x,z)=g(y)$ .
(Note: the order of quantifiers has changed!)
Then there exists $z{\in}\mathbb{R}$ such that $f(3,z) = g(4)$ and $f(9, z) = g(7)$ .
⋮

Note: Because we always handle quantifiers in order, we first give a name to the value $z$ such that

\forall x\in\mathbb{R}\ \forall z{\in}\mathbb{R}\ f(3,z)=g(y).

We can then plug 3 and 4 into this, and also plug in 9 and 7, and know it is the same $z$ for both.