Proof that 1 = 0 using a common logical fallacy
Wednesday, March 17, 2010 Math 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:
- y = y (identity axiom)
- y - y = 0 (arithmetic)
- x*(y - y) = 0 (substitution)
- x*y - x*y = 0 (distributive)
- 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 = 0 (hypothesis)
- 0 * 1 = 0 * 0 (multiply each side by same amount maintains equality)
- 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:
| A | B |
|---|---|
| false | false |
| false | true |
| true | true |
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:
| A | B | A -> B | ~B -> ~A | true? |
|---|---|---|---|---|
| false | false | false -> false | true -> true | true |
| false | true | false -> true | false -> true | true |
| true | false | true -> false | true -> false | false |
| true | true | true -> true | false -> false | true |
In a proof by contradiction, we can prove the truthfulness of B by proving the following two things:
- ~B -> ~A
- 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.
- Assume x*0 != 0
- y = y (identity)
- y - y = 0 (arithmetic)
- x*(y - y) != 0 (substitution)
- x*y - x*y != 0 (distributive)
- x*y != x*y (contradiction of identity axiom)
- 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:
- Assume 1 != 0
- 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.
Reader Comments (11)
Cool!
Why does A -> B
A B
false true
Good question. It means that it's valid to derive something true from something false (as we did going from 1 = 0 to 0 = 0). It is not a statement that something false means something else is true. After all, (false -> true) and (false -> false) are both true statements.
The opposite statement "true -> false" is invalid, as its never possible to derive something false from something that is true.
Sorry, but this is a terrible post. First, his proof isn't wrong because it reduces to an axiom, it's wrong because in the third line he uses his unproven hypothesis. To get from y - y = 0 to x*(y-y) = 0, you must multiply both sides by x to maintain the equality, making the RHS x*0, as opposed to 0 (because it would only be 0 if his hypothesis was true). Further, the proof itself results in proving that x*y = x*y assuming x*0 = 0 (i.e., not that x*0 = 0, but that x*0 = x*0).
Your fallacious proof seems only to rely on the same principles by accident, as you begin the proof by asserting your hypothesis as truth... a tautology.
Your "correct" proof is incorrect for the same reason his is. On line four, you say x*(y-y) != 0, however, you must multiply both sides by x to maintain correctness, yielding
x*(y-y) != x*0
x*0 != x*0
where your contradiction *should* occur. Please fix this.
A correct and short proof using the field axioms for addition and multiplication would be:
Lemma 1. If x + y = x, then y = 0.
Proof. y = x - x = 0. QED.
Theorem 1. 0x = 0.
Proof. 0x + 0x = (0 + 0)x = 0x. By Lemma 1, 0x = 0. QED.
--ABM
My correct proof doesn't use multiplication on line 4, it uses substitution by combining (1) and (3). In x*0=0, it substitutes y - y for 0. My intent was to use the same "axioms" (substitution, identity, distributive, etc.) as in the original proof, but structured correctly to show implication in the correct direction.
My correct proof doesn't have full mathematical rigor. Again, the point of the post is to illustrate correct usage of implication, not to give an exposition on extremely rigorous mathematics. That would have just clouded the OP.
You write "What we have actually shown is that 1 = 0 implies 0 = 0". But why does this proof rely on implication? I would have thought it would be equivalence. The error in your proof would be multiplying both sides by zero, which you can't do to prove equality (because anything multiplied by zero is zero). This is equivalent to the "division by zero" fallacy.
I think I understand the point of the post: if you start with a falsity and then create a long chain of implication, then you can't say what people who would interpret "implies" in the standard (non-logic) way would think you can imply. But you demonstrate this by including a fallacious step in the proof.
What I mean is that my "proof" (not actually a proof) for 1=0 shows that (1=0) -> (0=0) is true and *does not* show that 1=0 is true. Each step of a proof is an implication, not an equivalence. Multiplying by 0 there is *not* fallacious, what's fallacious is thinking that showing (1=0) -> (0=0) shows the truthfulness of 1=0.
Another way to do the x*0=0 proof correctly is to reverse the order of the steps to go from y=y ->...-> x*0 = 0. If you were to try to go from 0=0 -> ... -> 1 = 0, you would run into a wall because the multiplying by 0 step in the bad proof is not reversible.
My bad. I do think using multiplication would make the proofs shorter, though.
So is your argument equivalent to this one?
Axiom 1: Any integer whose absolute value is less than 3 is equal to 0.
1. 1 = 0 (assumption)
2. 0 = 0 (axiom 1)
In other words, since the point is that "a is false; b is true; a implies b is true" doesn't mean "b implies a is true", it doesn't matter how useful the actual proof stages are?
You're right on the main point: A -> B being true doesn't mean that B -> A is true.
Your write-up is fantastic. It is essentially extraordinary to me. I like it greatly and I hope to determine you additional content articles. yqzfmm yqzfmm - The North Face Outlet.
I smell the taste of wine. see you! "We do not talk more that day. We stood up, shook his hand and eye lookedeach and so on. Bees were shut out, but came to backhesitatingly. bmsxjr bmsxjr - yves saint laurent sandales.