1.3 Methods of Proof

Definition

A proof is a logical argument that establishes the truth of a mathematical statement by a sequence of deductive steps from agreed-upon axioms and previously proven statements.

Direct Proof

To prove a statement of the form $P\to Q$, assume $P$ is true and use logical deductions to show $Q$ holds.

1. Assume $P$

2. logical deductions

3. Therefore, $Q$

Proof by Contrapositive

To prove $P\to Q$, prove its contrapositive $\neg Q\to \neg P$

1. Assume $\neg Q$

2. logical deductions

3. Therefore, $\neg P$, hence $P\to Q$

Proof by Contradiction

To prove a statement $S$, assume the negation $\neg S$ and derive a contradiction e.g., $R$ and $\neg R$ for some $R$.

1. Assume $\neg S$

2. logical deductions

3. Derive a contradiction

4. Therefore, $S$

The Mathematical Induction Principle

To prove a statement $P\left(n\right)$ is true for all natural numbers $n$:

Base Case: Show $P\left(0\right)$ is true.

Inductive Step: Assume $P\left(k\right)$ is true (the inductive hypothesis) for an arbitrary $k\geqq 1$ and prove $P(k+1)$ is true.

Conclusion: If both steps are verified, then $P\left(n\right)$ holds for all $n\in \mathbb{N}$

The Strong Induction Principle

To prove a statement $P\left(n\right)$ is true for all natural numbers 𝑛:

Base Case: Prove $P\left(0\right)$ is true.

Inductive Step: Assume $P\left(1\right)$, $P\left(2\right),\cdots$, $P\left(k\right)$ are all true (the strong inductive hypothesis) and then prove $P(k+1)$ is true.

Note: Strong induction is logically equivalent to ordinary induction but is especially useful when the proof of $P(k+1)$ relies on multiple previous cases rather than just the immediate predecessor.

The only difference between regular induction and strong induction is that in strong induction you assume that every number up to k satisfies the condition that you wish to prove whereas in regular induction you only assume that some integer k satisfies this condition.

The Least Number Principle

Every non-empty subset of $\mathbb{N}$ has a least element.

Equivalently, in the language of a property $P\left(n\right)$:

1. Let $P\left(n\right)$ be a statement about natural numbers. Suppose, toward a contradiction, that $P\left(n\right)$ fails for at least one $n$.

   Define $S=\{n\in \mathbb{N}:\neg P\left(n\right)\}$.

   By hypothesis, $S\ne \varnothing$.

2. Application of the LNP

   Then $S$ has a least element; call it $m=\min \left(S\right)$

3. Derive the contradiction

   If $m=1$, you show directly that $\neg P\left(1\right)$ is impossible (i.e. you show $P\left(1\right)$ holds.)

   If $m>1$, then by minimality of $m$ every $k<m$ satisfies $P\left(k\right)$.

   Use that fact to prove $P\left(m\right)\to$again contradicting $\neg P\left(m\right)$.

4. Conclusion

   Since assuming “there is some $n$ with $\neg P\left(n\right)$” led to a contradiction, it must be that $S$ is empty. Hence $\neg P\left(n\right)$ never occurs, and so $P\left(n\right)\forall n\in \mathbb{N}$