home

# Proofs

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

## Terminology

Term Description
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.

To show $$p$$ is true, demonstrate that $$\lnot p \rightarrow (r \land \lnot r)$$.
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}$