Problem: Show that all horses are of the same color.
“Solution”: We will show, by induction, that for any set of horses, every horse in that set has the same color. Suppose , this is obviously true. Now suppose for all sets of horses, every horse in the set has the same color. Consider any set of horses. We may pick a horse at random, , and remove it from the set, getting a set of horses. By the inductive hypothesis, all of the remaining horses are the same color.
On the other hand, if we remove a different horse , we again get a set of horses which are all the same color. Let us call this color “brown,” just to give it a name. In particular, is brown. But when we removed , we got that all the remaining horses had the same color as . So must also be brown. Hence, all horses in are brown.
Explanation: The argument here is valid for almost all . For large , it is a very natural argument that follows from the inductive hypothesis. However, it fails for (and this is the only time it fails). By having only two horses, we cannot conclude that the removed horses have the same color, because there aren’t any horses remaining in to apply the transitivity of “having the same color as.”
This false proof highlights the danger of neglecting the base case of an inductive argument. Here the true base case was not , but rather . Since the base case is false, we should have prudently stopped our argument there before embarrassing ourselves.
Problem: Show 31.5 = 32.5.
Explanation: It appears that by shifting around the pieces of one triangle, we have constructed a second figure which covers less area! Since the first triangle has base length 13 and height 5, its area is 32.5. Clearly, the second figure has the same area minus a square of area 1, giving the second figure area 31.5.
In fact, by counting up the squares in each component, we do see that it is simply a shifting of pieces, so the areas of the two figures must be the same. Therefore, the fault lies in our first assumption: that the first figure is actually a triangle. Looking more closely, we see that the slope of the hypotenuse of the red component is , while the blue triangle as slope . If the first figure were a triangle, then the slope of the hypotenuse would be uniform. Since , the first figure is not a triangle, and hence its area is not 32.5. In fact, counting up the area of each component, the areas of both figures are actually 32.
This false proof accentuates the need to question one’s intuition. In fact, nothing false was said by the picture alone. The two figures do truly have the same area. The falsity is entirely in the viewer’s interpretation of what the picture says (and the questionably moral intent of a trickster mathematician). So the lesson is: while intuition can be a useful and essential guide, it is often not rigorous enough to be proof, and it can create very dangerous false positives.
Problem: Show there are finitely many primes.
“Solution”: Suppose to the contrary there are infinitely many primes. Let be the set of primes, and the set of square-free natural numbers (numbers whose prime factorization has no repeated factors). To each square-free number there corresponds a subset of primes, specifically the primes which make up ‘s prime factorization. Similarly, any subset of primes corresponds to a number in , since we can simply multiply all numbers in together to get a square-free number.
Thus we have shown a bijection between and the power set of , but the power set of an infinite set is uncountable. Hence, there are uncountably many square-free natural numbers, a contradiction. Hence there are only finitely many primes.
Explanation: The problem here lies in the bijection. Take any subset of primes which is infinitely large. Assuming there are infinitely primes to begin with, this is a valid step, since we may consider the subset of all primes, . However, the product of all primes in an infinite subset of positive numbers is infinitely large, and hence cannot correspond to a square-free (finite) number. In other words, the set of finite subsets of an infinite set is countable.
This illuminates why the power set of an infinite set is interesting. Specifically, the only things which make it “big” are the infinite subsets. So these should be our primary concern.
This is the first in a series of “false proofs.” Despite their falsity, they will be part of the Proof Gallery. The reason for putting them there is that often times a false proof gives insight into the nature of the problem domain. We will be careful to choose problems which do so.
Problem: Show 1 = 2.
“Solution”: Let . Then , and . Factoring gives us . Canceling both sides, we have , but remember that , so . Since is nonzero, we may divide both sides to obtain , as desired.
Explanation: This statement, had we actually proved it, would imply that all numbers are equal, since subtracting 1 from both sides gives and hence for all real numbers . Obviously this is ridiculous.
Digging into the algebraic mess, we see that the division by is invalid, because and hence .
Division by zero, although meaningless, is nevertheless interesting to think about. Much advanced mathematics deals with it on a very deep and fundamental level, either by extending the number system to include such values as (which still gives rise to other problems, such as and ), or by sidestepping the problem by inventing “pseudo” operations (linear algebra) and limiting calculations (calculus).