Section 3.4 A quick visit to disproofs
Lets look a little way ahead and think about how we might prove an implication to be false. Consider
If \(n \in \mathbb{N}\) then \(2^n+1\) is prime.
How is our theorem true — the conclusion must be true every time the hypothesis is true. Hiding in this is that it must be true every single time the hypothesis is true.
So how could our theorem be false? We need the hypothesis to be true while the conclusion is false. But to be more precise — it only has to fail once. So lets explore a few values of \(n\text{:}\)
- \(n=1\) then \(2^n+1 = 2+1 = 3\) which is prime.
- \(n=2\) then \(2^n+1 = 4+1 = 5\) which is prime.
- \(n=3\) then \(2^n+1 = 8+1 = 9 = 3\times 3\) which is not prime.
So since there is a value of \(n\) that makes the hypothesis true, but the conclusion false, the implication is false. We are hiding here the idea of quantifiers
For all \(n\text{,}\) \(P(n)\)
There exists \(n\text{,}\) \(P(n)\)
We’ll come back to these in Chapter 6, but after we’ve done a little more logic.
