Proofs

A logical, step-by-step argument that demonstrates a mathematical statement is absolutely true. It begins with universally accepted truths (axioms) and definitions, uses rules of logic, and ends by confirming the claim.

Proving Conditional Statements

For proving conditional statements (‘If $P$, then $Q$’ or '$P\to Q$'), there are three main methods.

Direct Proof

Proposition If $P$, then $Q$.
Proof. Suppose $P$.
Therefore $Q$.

Nothing more to it.

Contrapositive Proof

Proposition If $P$, then $Q$.
Proof. Suppose $\neg Q$.
Therefore $\neg P$.

$P\to Q$ is logically equivalent to $\neg Q\to \neg P$.

To setup a contrapositive proof, first suppose $Q$ is not true. Then prove that $P$ is not true.

Proof by Contradiction

Proposition If $P$, then $Q$.
Proof. Suppose $P$ and $\neg Q$.
Therefore $C\wedge \neg C$.

Where $C\wedge \neg C$ is a contradiction.

This is logically sound because to prove a statement $P$, it suffices to instead prove the conditional statement $(\neg P)\to (C\wedge \neg C)$. So assume $\neg P$ and deduce $C\wedge \neg C$.

To use this for a conditional statement $P\to Q$, begin with the assumption that $\neg (P\to Q)$ is true, that is, $P\to Q$ is false. $P\to Q$ being false means that it is possible that $P$ can be true while $Q$ is false. Thus the first step is to assume $P$ and $\neg Q$. Then deduce a contradiction, which will in turn prove $P\to Q$.

Proving If-and-Only-If Statements

Proposition $P$ if and only if $Q$.
Proof.
Prove $P\to Q$ using direct, contrapositive or contradiction proof.
Prove $Q\to P$ using direct, contrapositive or contradiction proof.

Proof by Induction

Proposition The statements $S_1,S_2,S_3,S_4,...$ are all true.
Proof. (Induction)
(1) Prove that the first statement $S_1$ is true.
(2) Given any integer $k\ge 1$, prove that the statement $S_k\Rightarrow S_{k+1}$ is true.
It follows by mathematical induction that every $S_n$ is true.

The first step (1) is called the basis step. The second step (2) is called the inductive step. In the inductive step direct proof is most often used to prove $S_k\Rightarrow S_{k+1}$, so this step is usually carried out by assuming $S_k$ is true and showing this forces $S_{k+1}$ to be true. The assumption that $S_k$ is true is called the inductive hypothesis.

Proof by Strong Induction

Proposition The statements $S_1,S_2,S_3,S_4,...$ are all true.
Proof. (Strong Induction)
(1) Prove that the first statement $S_1$. (Or the first several $S_n$, if needed.)
(2) Given any integer $k\ge 1$, prove $(S_1\wedge S_2\wedge S_3\wedge \cdot \cdot \cdot \wedge S_k)\Rightarrow S_{k+1}$.

This is useful when $S_k$ does not easily imply $S_{k+1}$. It may be easier to show some earlier statement ($S_{k-1}$ or $S_{k-2}$, for instance) implies $S_{k+1}$.

Proof by Smallest Counterexample

Proposition The statements $S_1,S_2,S_3,S_4,...$ are all true.
Proof. (Smallest counterexample)
(1) Check that the first statement $S_1$ is true.
(2) For the sake of contradiction, suppose not every $S_n$ is true.
(3) Let $k>1$ be the smallest integer for which $S_k$ is false.
(4) Then $S_{k-1}$ is true and $S_k$ is false. Use this to get a contradiction.