Proof Techniques

Before studying this section, you may want to review:

An identity is a mathematical sentence that is always true. For example, ‘$\,x+x=2x\,$’ is an identity.

A contradiction is a mathematical sentence that is always false. For example, ‘$\,x=1\text{ and }x\ne 1\,$’ is a contradiction.

Given any mathematical statement $\,S\,,$

$S\text{ or } (\text{not }S)\,$
is an identity, and

$S\text{ and }(\text{not }S)\,$
is a contradiction,

as the truth table below shows:

$\,S\,$	$\,\text{not }S\,$	$\,S\text{ or }(\text{not }S)\,$	$\,S\text{ and }(\text{not }S)\,$
T	F	T	F
F	T	T	F

Here's the intuition for ‘$S\text{ or } (\text{not }S)\,$’: you're either true, or you're not true.

Here's the intuition for ‘$S\text{ and }(\text{not }S)\,$’: you can't be true and not true at the same time.

Proof by Contradiction

The proof by contradiction technique can be applied to any type of mathematical sentence:

PROOF BY CONTRADICTION a widely-applicable proof technique

To prove that a sentence is true, you can assume that it is false, and then reach a contradiction.

This approach is justified by the truth table below, where it is shown that a statement $\,S\,$ is equivalent to:

$\,(\text{not }S)\Rightarrow \text{(a contradiction)}$

$S$	$\text{not }S$	a contradiction	$(\text{not }S)\Rightarrow \text{(a contradiction)}$
T	F	F	T
F	T	F	F

Three Standard Approaches for Proving Implications

There are three standard approaches for proving an implication, $\,A\Rightarrow B\,$:

DIRECT PROOF a proof technique for implications

To prove that an implication $\,A\Rightarrow B\,$ is true, we can assume that $\,A\,$ is true, and show that $\,B\,$ is also true.

Recall from ‘If... Then...’ Sentences that the only time an implication is false is when the hypothesis is true, and the conclusion is false. In a direct proof, we show that this line of the truth table can never occur.

The next method is based on the fact that an implication is equivalent to its contrapositive.

PROOF BY CONTRAPOSITION a proof technique for implications

To prove that an implication $\,A\Rightarrow B\,$ is true, we can alternatively prove that its contrapositive $\,(\text{not }B)\Rightarrow (\text{not }A)\,$ is true: Assume that $\,B\,$ is false, and show that $\,A\,$ is also false.

Observe that ‘proof by contraposition’ is just a direct proof of the contrapositive.

Applying ‘proof by contradiction’ to an implication leads to a proof technique that is called an ‘indirect proof’. By the way, don't mix up ‘proof by contraposition’ and ‘proof by contradiction’. The words sound similar, but they're different proof techniques.

INDIRECT PROOF a proof technique for implications

To prove that an implication $\,A\Rightarrow B\,$ is true, we can assume that $\,A\,$ is true, but $\,B\,$ is false, and then reach a contradiction.

What's the only time that an implication ‘$\,A\Rightarrow B\,$’ is false? When $\,A\,$ is true, and $\,B\,$ is false. In an indirect proof, we assume these conditions, and then reach a contradiction.

In Introduction to the Two-Column Proof, you'll get lots of practice with direct and indirect proofs, and proof by contraposition. However, there are some skills you'll probably want to develop first—so keep moving forward!