A proof is a valid argument that establishes the truth of a mathematical statement.
| 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. |
A direct proof is structured to show \(p \rightarrow q\) based on the assumption that \(p\) is true.
Assume p, show q.
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.
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} \]