example of false implies true

A common mistake in writing proofs is to overlook that false can imply true. Consider the following example:

Claim 1.

$2=5$.

False proof..

$2=5\Rightarrow 0\cdot 2=0\cdot 5\Rightarrow 0=0$. Clearly $0=0$ so $2=5$. ∎

Of course this is wrong and $2\ne 5$. The mistake is that we start from a false premise, that of $2=5$, and then use completely correct methods (multiply an equation on both sides by the same number) to arrive a true statement, that $0=0$. That process is logical: false can imply true. However, the mistake in the “proof” is to think that only true can imply true, as then we are lead to believe that $0=0$ makes $2=5$.

This line of argument is absurd in the example just given, but it is often hard to spot and many times a good looking proof is hiding such a mistake. For example:

Claim 2.

${\displaystyle \sum _{k=1}^n}k={\displaystyle \frac{n(n+1)}{2}}$ for all integers $n\mathrm{\ge }\mathrm{1}$.

Incorrect proof..

We proceed by induction. In the base case $n=1$:

${\displaystyle \sum _{k=1}^1}k$ $={\displaystyle \frac{1(1+1)}{2}}$

$1$ $=1.$

Therefore the base case is true.

Induction hypothesis: suppose that for some $n\ge 1$, ${\displaystyle \sum _{k=1}^n}k={\displaystyle \frac{n(n+1)}{2}}$. Now consider the case $n+1$.

${\displaystyle \sum _{k=1}^{n+1}}k$ $={\displaystyle \frac{(n+1)((n+1)+1)}{2}}$

$(n+1)+{\displaystyle \sum _{k=1}^n}k$ $={\displaystyle \frac{(n+1)(n+2)}{2}}$

$(n+1)+{\displaystyle \frac{n(n+1)}{2}}$ $={\displaystyle \frac{n^2+3n+2}{2}}$

${\displaystyle \frac{2n+2}{2}}+{\displaystyle \frac{n^2+n}{2}}$ $={\displaystyle \frac{n^2+3n+2}{2}}$

${\displaystyle \frac{n^2+3n+2}{2}}$ $={\displaystyle \frac{n^2+3n+2}{2}}.$

So by induction the theorem is true for all $n\ge 1$. ∎

Notice both the base case and the inductive step assume what is to be proved and then using only logical implications arrive at a place where something is obviously true, such as $1=1$ or $\frac{n^2+3n+2}{2}=\frac{n^2+3n+2}{2}$. What makes these both incorrect is that:

We may arrive at truth by starting with either truth or fiction!

That is the way we define implication (at least in logic).

Some common signs of this mistake include:

1. The proof begins by assuming what is to be proved.

   The exception to this is a proof by contradiction. Then the proof will end with something false. Implications do not allow this: true must imply only true. Hence it is accurate to then conclude that the assumption at the start was false.

   Because of the possible confusion, it is almost always necessary to start a proof by contradiction with a phrase of the form ”Suppose not” or ”We proceed by contradiction”.

2. The proof ends with something that is always true, such as $1=1$ or $0=0$ or $x=x$.

3. The proof cannot be read aloud.

   This is an often overlooked tool in writing good proofs. Try to insert words like “implies” or “ from this it follows that ” for symbols like $\to$ or $\Rightarrow$ or (even just new lines). If it sounds silly when read aloud in this way the chances are high that something is wrong. For example, the base case in the inductive proof above could be read as:

   The sum from $k=1$ to $1$ of $k$ equals $\frac{1(1+1)}{2}$ implies that $1=1$.

   Think: isn’t $1=1$ obvious? Why would that need to be implied by some ugly formula? Ah, it would not need to be. Perhaps the implication is not meaningful.

Correcting the mistake

For many problems the mistaken proof is nevertheless a good way to begin thinking about a correct proof. This is because by assuming what is to be proved one has something to begin with. By simplifying the problem down to something recognizably true, for example $1=1$, it then seems certain that the equation is correct. To prove the result it is often a matter of only reversing the scratch work. To see this we use the ingredients of the incorrect proof of ${\sum }_{k=1}^{n}k=\frac{n(n+1)}{2}$ in the following correct proof. Notice also that we have included many more words and punctuation to the proof which makes it both readable and also helps us to understand the logic of the proof more easily.

Proof.

We proceed by induction. In the base case $n=1$ and so on the left hand side of our equation we find that ${\sum }_{k=1}^{n}k=1$. On the right hand side we have $\frac{1(1+1)}{2}=1$. As the left hand side equals the right hand side, the base case is settled.

Now suppose for induction that ${\sum }_{k=1}^{n}k=\frac{n(n+1)}{2}$ for some integer $n\ge 1$. We then consider the case of the equation for $n+1$. On the left hand side we have: ${\sum }_{k=1}^{n+1}k=(n+1)+{\sum }_{k=1}^{n}k=n+1+\frac{n(n+1)}{2}$ with that last step applying the induction hypothesis. From here we use basic algebra to see that $n+1+\frac{n(n+1)}{2}=\frac{(n+1)(n+2)}{2}=\frac{(n+1)((n+1)+1)}{2}$. Hence, by induction the equation holds for all $n\ge 1$. ∎

Title	example of false implies true
Canonical name	ExampleOfFalseImpliesTrue
Date of creation	2013-03-22 18:49:52
Last modified on	2013-03-22 18:49:52
Owner	Algeboy (12884)
Last modified by	Algeboy (12884)
Numerical id	9
Author	Algeboy (12884)
Entry type	Example
Classification	msc 03B05