Proof Techniques

Donovan D Chang

10 Proof Techniques

So far we have seen the power and utility of a truth table. However, it might be inconvenient and even inefficient to lay out all possible cases every time we attempt to prove certain claims. Thus there is a need for theorems, rules, and techniques to save time as well as organize our ideas.

The modus ponens rule is the most fundamental rule of our deductive reasoning, based on the tautology

$\left[P \wedge \left(P \Rightarrow Q\right)\right]\Rightarrow Q$

In other words, whenever we have $P$ and $P \Rightarrow Q$ , then we can conclude $Q$ is true.

The details of such techniques are mentioned in the following subsections.

Direct Proofs

The structure of direct proof [14] of $P \Rightarrow Q$ is simple, and takes the following form:

Direct Proof.
Assume $P$ .
$\cdots$
Therefore, $Q$ .
Therefore, $P \Rightarrow Q$ .

Let us clarify with an example.

Example. Prove if $x$ is even, then $x+1$ is odd.

Proof.
Let $x$ be an even integer.
Then, there exists $k\in \mathbb{Z}$ such that $x=2k$ .
Then, $x+1=2k+1$ .
Therefore, $x+1$ is odd for all $k\in \mathbb{Z}$ .
Therefore, if $x$ is even, then $x+1$ is odd.

Above is the typical example of a direct proof – we began with the assumption
$P$ : $x$ is even

and with an elementary arithmetic operation we deduced
$Q$ : $x+1$ is even

Indeed, this is quite simple an example, but illustrative of the direct proof method. Let us have a look at another.

Example. Let $x,y>0$ . Prove that if $x>y$ , then $y^2-x^2<0$

Proof.
Let $x>y>0$ .
Then, $x-y>0$ and $x+y>0$ .
Therefore, $(x-y)(x+y)=x^2-y^2>0$ .
Therefore, $y^2-x^2<0$ , where $x>y>0$ .
Therefore, if $x>y$ , then $y^2-x^2<0$ .

To analyze, again, we began with the assumption
$P: x>y>0$

and with an elementary arithmetic operation we deduced
$Q: x^2-y^2>0$ and thus $y^2-x^2<0$

Contraposition

Reasoning with the contrapositive or contraposition is also a well-known proof technique. Let us revisit the theorem of contraposition.

$(P\Rightarrow Q) \Leftrightarrow \, (\sim Q \Rightarrow \,\sim P)$

The proof by contrapositive takes the following form:

Proof by Contrapositive/Contraposition.
Assume $\sim Q$ .
$\cdots$
Therefore, $\sim P$ .
Therefore, $\sim Q \Rightarrow \sim P$ .
If and only if $P \Rightarrow Q$ .

Let us illustrate with examples.

Example. Prove that if $m^2$ is odd, then $m$ is odd.

Following our usual strategy, we might as well begin our proof by denoting an odd number $m^2=2k+1$ for $k \in \mathbb{Z}$ . However, this form does not really help, and we are not really sure how to proceed to show $m$ is odd.

Instead, the consequent that $m$ is odd, and the converse of the consequent that $m$ is even, fit the format we usually denote an odd/even number. Therefore, we strategize to prove the contrapositive, i.e. if $m$ is even, then $m^2$ is even.

Proof.
Suppose $m$ is even.
That is, there exists $k\in \mathbb{Z}$ such that $m=2k$ .
Then,

$m^2 = \left( 2k \right)^2 = 4k^2 = 2\left( 2k^2\right)$

Therefore, $m^2$ is even for all $k\in \mathbb{Z}$ .
Therefore, if $m$ is even, then $m^2$ is even.
Therefore, if $m^2$ is odd, then $m$ is odd.

Indirect Proofs

Indirect proofs are proofs based on tautologies, the statements that are always true, irrespective of the truth values of the propositions involved. Proof by contraposition was a motivating example of indirect proofs. In this section, we introduce another indirect proof technique, proof by contradiction. Following is the typical form of proof by contradiction:

Proof by Contradiction.
Assume $P \wedge \sim Q$ .
$\cdots$
Therefore, $R$ .
$\cdots$
Also, $\sim R$ .
This is contradiction, both $R$ and $\sim R$ cannot be true at the same time. And therefore, we conclude it must be the case our assumption was wrong, i.e. $\sim \left( P \wedge \sim Q \right)$ , equivalent to $\sim P \vee Q$ , equivalent to $P\Rightarrow Q$ , is true.

Let us illustrate with an example.

Example. Prove $\sqrt{6}$ is irrational.

Our proof is divided into several parts. To prove by contradiction, first, we shall assume the negation, $\sqrt{6}$ is not irrational, and thus rational. Then, we express this “rational number” as a fraction. While proceeding, we shall inevitably face a contradiction, since our assumption $\sqrt{6}$ is rational is incorrect.

Proof.
First, assume the converse is true.
Suppose $\sqrt{6}$ is rational.
Then, there exist integers $p,q$ such that $\sqrt{6}=\frac{p}{q}$ , where $q \neq 0$ and $gcd(p,q)=1$ .
Then,

$\begin{align*} \left(\sqrt{6}\right)^2 &= \left(\frac{p}{q}\right)^2\\ 6 &= \frac{p^2}{q^2}\\ 2\left( 3q^2\right) &= p^2 \end{align*}$

Therefore, $p^2$ is even.

Show $p^2$ is even $\Rightarrow$ $p$ is even
This part, let us prove the contrapositive.

Suppose $p$ is odd.
Then, there exists $k\in \mathbb{Z}$ such that $p=2k+1$ .
Then,

$\begin{align*} p^2 &= (2k+1)^2\\ &= 4k^2+4k+1\\ &= 2\left( 2k^2+2k\right)+1 \end{align*}$

Therefore, $p^2$ is odd for all $k\in \mathbb{Z}$ .
Therefore, if $p$ is odd, then $p^2$ is odd.
Then, if $p^2$ is even, then $p$ is even.

Finally, show $p$ is even $\Rightarrow$ $q^2$ is even $\Rightarrow$ $q$ is even.

$\begin{align*} 6 &= \frac{p^2}{q^2}\\ q^2 &= \frac{p^2}{6}\\ &= \frac{(2k)^2}{6}\\ &= \frac{4k^2}{6}\\ &= 2\left( \frac{k^2}{3}\right) \end{align*}$

Therefore, $q^2$ is even.
Then, likewise, $q$ is even.

In fact, it was our part of assumption $gcd(p,q)=1$ . However, since both $p$ and $q$ are even $gcd(p,q) \neq 1$ . This is contradiction – it must be the case our assumption was wrong, i.e. $\sqrt{6}$ is not rational, and thus irrational. Therefore, we conclude $\sqrt{6}$ is irrational.

Proof by Exhaustion

Proof by exhaustion is a technique to examine every possible case. Let us illustrate with an example.

Example. Prove $|ab|=|a||b|$ for $a,b\in \mathbb{R}$ .

Proof.
1. $a \geq 0$ and $b \geq 0$
Then, $|a|=a$ , $|b|=b$ , and $|ab|=ab$ .
Therefore, $|ab|=ab=|a||b|$ .

2. $a \geq 0$ and $b < 0$
Then, $|a|=a$ , $|b|=-b$ , and $|ab|=-ab$ .
Therefore, $|ab|=-ab=|a||b|$ .

3. $a < 0$ and $b \geq 0$
Then, $|a|=-a$ , $|b|=b$ , and $|ab|=-ab$ .
Therefore, $|ab|=-ab=|a||b|$ .

4. $a < 0$ and $b < 0$
Then, $|a|=-a$ , $|b|=-b$ , and $|ab| =\left\vert (-a)(-b) \right\vert =ab$ .
Therefore, $|ab|=ab=|a||b|=(-a)(-b)$ .

Therefore, $|ab|=|a||b|$ for $a,b\in \mathbb{R}$ .

Mathematical Induction

Our discussion so far has been focused on deductive reasoning. Yes, deduction is our primary method of unfolding our logic, yet we also have briefly mentioned the existence of the principles of mathematical induction (PMI). Following is the basic scheme of the proof using the PMI:

Proof using the Principles of Mathematical Induction.
Let $P(n)$ for $n\in \mathbb{N}$ be the collection of propositions.
1. (Basis Step) Show that $P(1)$ is true.
2. (Inductive Step) Show that, for all $n\in \mathbb{N}$ , if $P(n)$ is true, then $P(n+1)$ is true.
3. Therefore, we conclude $P(n)$ is true for all $n\in \mathbb{N}$ by the principles of mathematical induction.

Let us illustrate with a famous example, well-known as the problem of the Tower of Hanoi.

Example. The Tower of Hanoi

The Tower of Hanoi, also called the Tower of Brahma or Lucas’ Tower, is a famous mathematical puzzle. It is consisted of 3 rods and $n$ number of disks with differing radii (Figure ??). At the initial state, the disks are placed in a single rod with diameters increasing from top to bottom. The goal is to move the disks to another rod in the same order with the following rules:

1. Only one disk at the top of the rod can be moved to another rod in each turn.
2. Larger disk cannot be placed on top of a smaller disk.

It is known the fewest number of movements to solve the puzzle is $2^n-1$ . Prove this using the PMI.

Proof of the Tower of Hanoi.
1. (Basis Step) Show that $P(1)$ is true.
Let $P(n)=2^n-1$ .
Then, $P(1)=2^1-1=1$ is true, since we only need a single movement to migrate a single piece of disk.

2. (Inductive Step) Show that, for all $n\in \mathbb{N}$ , if $P(n)$ is true, then $P(n+1)$ is true.
Suppose $P(n)=2^n-1$ .
Then, to completely migrate a stack of $n+1$ pieces placed in one rod, we first need to move $n$ pieces from the top, except the last piece; move the last piece; and then on top of the last piece place the first $n$ pieces that were moved. Therefore,

$\begin{align*} 2P(n)+1 &= 2\left( 2^n-1\right)+1\\ &= 2^{n+1}-2+1\\ &= 2^{n+1}-1\\ &= P(n+1) \end{align*}$

Therefore the statement, the puzzle with $n$ disks can be solved in $2^n-1$ moves, is true for $n+1$ .

3. Therefore, we conclude $P(n)$ is true for all $n\in \mathbb{N}$ by the principles of mathematical induction.