# Proof Techniques

Before studying this section, you may want to review:

- Practice with the mathematical words ‘and’, ‘or’, and ‘is equivalent to’
- ‘If... Then...’ Sentences
- Contrapositive and Converse

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:

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\,$:

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.

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.

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!