Section 11.1 Structure of a proof by contradiction
Say we wish to prove a statement \(P\) to be true. Since
\begin{equation*}
(P \lor (\neg P)) \text{ is a tautology,}
\end{equation*}
either we must have \(P\) is true or \((\neg P)\) is true.
- Tell the reader something like “We will prove this by contradiction” otherwise the next step looks like a mistake.
- We assume that \((\neg P)\) is true, and then show that this leads to a falsehood — a contradiction — garbage.
- That is, we will construct a change of implications like:\begin{align*} (\neg{P}) & \implies P_1 & \text{ and}\\ P_1 & \implies P_2 & \text{and}\\ P_2 & \implies P_3 & \text{and}\\ & \vdots\\ P_{n-1} & \implies P_n & \text{and}\\ P_n & \implies \text{CONTRADICTION} \end{align*}
- The contradiction is a statement that is always false — for example\begin{equation*} R \land (\neg R)\text{.} \end{equation*}But which contradiction do we aim for? Let’s discuss that shortly.
- Since the contradiction is false, and all of those implications are true, we must have \(P_n\) is false (modus tollens).
- Similarly, since \(P_n\) is false, we know \(P_{n-1}\) is false (again, modus tollens).
- Keep on moving back up the chain of implications, and we see that \((\neg P)\) must be false.
- Thus 154 \(P\) is true.
When when we write this up neatly for the reader we arrive at a proof that looks like the following:
We prove this result by contradiction. So assume, to the contrary \((\neg{P})\text{.}\)
- A chain of implications showing that “\((\neg P) \implies\) contradiction”.
Thus we conclude that \((\neg P)\) is false, and so \(P\) is true.
Warning 11.1.1. What contradiction should we aim for?
As we warned earlier, once you are comfortable with the logic of proof by contradiction, it becomes tempting to use it everywhere. However, we caution the reader to use this method after first trying a direct or contrapositive proof. One very good reason for this caution is that a direct or contrapositive proof has a well defined starting point:
- the hypothesis is true,
and a well defined end point:
- the conclusion is true.
By exploring the conclusion in our scratch work we can work out how to make the proof work.
Proof by contradiction starts clearly enough
- the statement is false,
but in contrast with direct and contrapositive proofs, it is not clear what statement we need to generate the contradiction. We know we need some contradiction, but which contradiction we should reach? How do we know where to aim? This can make it much harder.
We can generate a contradiction for our proof by contradiction is to show that one of our assumptions is both true and false. For example, when we start a proof by contradiction, we assume that the result is actually false and this, in turn, requires us to make an assumption, say, \(Q\text{.}\) One way we can generate a contradiction is to reach a conclusion \((\neg Q)\text{.}\) However this is not the only way to generate a contradiction.
Let us do a small example, in which the contradiction is quite easy to find.
Result 11.1.2.
There is no smallest positive real number.
Proof by contradiction can work very nicely for results of this form “There is no smallest \(X\)” or “There is no largest \(X\)” (where \(X\) is some interesting mathematical object). We can construct the proof by
- assume that there is a smallest \(X\text{,}\) call it \(X_1\text{,}\) then
- use \(X_1\) to construct an even smaller \(X\text{,}\) call it \(X_2\)
but then we have
- \(X_1\) is the smallest possible \(X\text{,}\) and at the same time
- \(X_2\) is smaller that \(X_1\)
This gives us a contradiction of the form
\begin{equation*}
Q \land \neg Q.
\end{equation*}
Let’s apply this approach to the above result.
Our scratch work should look something like this:
- We’ll try a proof by contradiction
- The negation of the result is “There is a smallest positive real number”.
- Hence we assume there is a smallest positive real number — call it \(r\text{.}\)
- But now the number \(r/2\) is a positive real number and \(r/2 \lt r\text{.}\)
- Contradiction!
Proof of Result 11.1.2.
We prove this result by contradiction. Assume the result is false, so there is some smallest positive real number \(r\text{.}\) But then \(0 \lt r/2 \lt r\text{,}\) making \(r/2\) is a smaller positive real number. This contradicts our assumption that \(r\) was the smallest positive real number. Hence the result must be true.
By the law of the excluded middle
