Proof that 1 = 0 using a common logical fallacy - thoughts from the red planet - thoughts from the red planet (2024)

Awhile ago I read a post by Daniel Levine that shows a formal proof of x*0 = 0. Here's a reprint of the proof:

1. y = y (identity axiom)
2. y - y = 0 (arithmetic)
3. x*(y - y) = 0 (substitution)
4. x*y - x*y = 0 (distributive)
5. x*y = x*y (arithmetic)

The logic of this proof is that since we can reduce x*0 = 0 to the identity axiom, x*0 = 0 is true. Unfortunately, this is not logically sound.

Now I don't mean to pick on Daniel Levine. He's a really smart guy. I've made this same mistake, and only when I lost points on problem sets a number of times did I really understand the fallacy of this logic.

To show why this logic is unsound, here's a "proof" that 1 = 0:

1. 1 = 0 (hypothesis)
2. 0 * 1 = 0 * 0 (multiply each side by same amount maintains equality)
3. 0 = 0 (arithmetic)

According to the logic of the previous proof, we have reduced 1 = 0 to 0 = 0, a known true statement, so 1 = 0 is true. Obviously this is incorrect.

What we have actually shown is that 1 = 0 implies 0 = 0. You would write this out formally as:

(1 = 0) -> (0 = 0)

Let's take a quick detour to discuss the implication operator. The implication operator is a funny creature. Showing that A -> B is true doesn't mean that either A or B themselves are true. Instead, it shows that one of the following combinations of A and B is valid:

The only combination missing is true -> false, since something true can never imply something false.

As you can see above, when B is true, A can be either true or false. However, when A is true, B must be true. So, if you can show A -> B to be true and also show that A is true, you can combine A and A -> B to show that B is true. This is called modus ponens in formal logic.

Back to 1 = 0. We showed that (1 = 0) -> (0 = 0) and we know that 0 = 0 is true. As we just saw, this says nothing about the truthfulness of 1 = 0 and our proof is invalid. Likewise, the x*0 = 0 proof just showed that (x*0 = 0) -> (x*y = x*y) which doesn't prove the truthfulness of x*0 = 0.

There's an easy fix to the proof by making use of proof by contradiction.

Proof by contradiction makes use of the fact that A -> B and ~B -> ~A ("~" meaning "boolean negation") are logically equivalent. We can see this by writing out all the combinations of variables:

In a proof by contradiction, we can prove the truthfulness of B by proving the following two things:

1. ~B -> ~A
2. A

By proving ~B -> ~A, we also prove A -> B because of logical equivalence. By proving A to be true, we can combine A with A -> B using modus ponens to prove that B is true. This technique is called "proof by contradiction" because by assuming ~B to be true, we are able to show that both A and ~A are true which is a logical contradiction.

Let's use proof by contradiction to fix the proof of x*0 = 0.

1. Assume x*0 != 0
2. y = y (identity)
3. y - y = 0 (arithmetic)
4. x*(y - y) != 0 (substitution)
5. x*y - x*y != 0 (distributive)
6. x*y != x*y (contradiction of identity axiom)
7. x*0 = 0 (by contradiction)

There's only a few changes, but now the logic is sound.

Let's see what happens when we try to use proof by contradiction to prove that 1 = 0:

1. Assume 1 != 0
2. 0 * 1 != 0 * 0

The proof immediately breaks down. Multiplying each side of an equation by the same amount will maintain an equality relationship but does not necessarily maintain an inequality relationship. That is, "(x = y) -> (x*z = y*z)" is true, but "(x != y) -> (x*z != y*z)" is false.

You may be thinking "this is well and good, but how is any of this useful??". I've only had to do a formal proof one time in the past two years, but the proof was for an algorithm whose correctness was absolutely critical for my company. More generally though, I find the rigorous, disciplined approach to thinking about problems to be really valuable.

You should follow me on Twitter here.