Review of Proof Strategies

Logic and Proofs

Proof strategies we know are:

proof by contradiction
direct proof
contrapositive proof (same as proof by contradiction, except the negated conclusion is now in the hypothesis of the theorem)

Example

Two real numbers $a, b$ are equal iff for all $ε > 0$ it follows that $| a - b | < ε$ .

Proof
We prove the forward direction $\to$ first. Suppose $a = b$ . Then clearly $| a - b | = | a - a | = | 0 | = 0$ so then if we let $ε > 0$ be arbitrary then clearly $ε > 0 = | a - b |$ as required.

Now for the reverse direction $\leftarrow$ . Notice that we get a $\forall$ as a given, which isn't great, so we should try proof by contradiction. Thus, suppose for all $ε > 0$ that $| a - b | < ε$ . Assume for contradiction that $a \neq b$ . Then choose $ε_{o} = | a - b | > 0$ . Then:

| a - b | < ε_{o} \Rightarrow | a - b | < | a - b | \Rightarrow 0 < 0 \Rightarrow\Leftarrow

hence our assumption was incorrect, so then $a = b$ instead.
☐

Induction

The idea behind induction is to do the following:

Show the base case that $P (0)$ is true
Have an inductive hypothesis that $P (0), . . . ., P (k)$ is true
Prove that, using these hypotheses, that $P (k + 1)$ is true.

Example

Let $x_{1} = 1$ and for all $n \in N$ that $x_{n + 1} = (1 / 2) x_{n} + 1$ . Then $x_{n}$ is non-decreasing, or $x_{n} \leq x_{n + 1}$

Proof
Let's use induction:

We know $x_{1} = 1$ and calculating the next term $x_{2} = (1 / 2) 1 + 1 = 3 / 2$ so clearly $x_{1} \leq x_{2}$ .
Suppose for our inductive hypothesis that for some $k \in N$ that all $x_{1} \leq \dots \leq x_{k}$ .
Consider if $x_{k} \leq x_{k + 1}$ . We know that $x_{k - 1} \leq x_{k}$ from our inductive hypothesis. Notice that if we start from there:

\begin{aligned} x_{k - 1} & \leq x_{k} \\ \frac{1}{2} x_{k - 1} + 1 & \leq \frac{1}{2} x_{k} + 1 \\ x_{k} & \leq x_{k + 1} \end{aligned}

Hence, via the principle of mathematical induction, $x_{n}$ is a non-decreasing sequence.
☐

References

[[Abbott Real Analysis.pdf#page=21]]