A proof is a valid argument that establishes the truth of a mathematical statement.

## Terminology

theorem |
A formal statement that can be shown to be true. |

axiom |
A statement we assume to be true to serve as the premise for further arguments. |

lemma |
A proven statement used as a step to a larger result. |

corollary |
A theorem that can be established by a short proof from a theorem. |

## Types of proofs

### Direct

A direct proof is structured to show \(p \rightarrow q\) based on the assumption that \(p\) is true.

Assume p, show q.

### Indirect

Not all statements may be expressed through direct establishment that \(\forall x(P(x) \rightarrow Q(x))\). Indirect proof technique provide the tools for these cases.

#### Contraposition

Contrapositives make use of \(p \rightarrow q \equiv \lnot q \rightarrow \lnot p\). In this case \(\lnot q\) is taken as a premise the it is shown that \(\lnot p\) must follow.

#### Contradiction

To show \(p\) is true, demonstrate that \(\lnot p \rightarrow (r \land \lnot r)\).

#### Induction

Show that the statement holds in a base case where \(n = 0\) or \(1\).
Prove that for every \(n\) the statement holds for \(n + 1\).
\[
\begin{array}{rl}
& P(1)\ \text{is true} \\
& \forall k \; P(k) \rightarrow P(k+1) \\
\hline
\therefore & \forall n \; P(n)
\end{array}
\]