Tag Archives: false proof

False Proof – 2 = 4, As the Limit of an Infinite Power Tower

Posted on by

Problem: Prove that 2 = 4.

Solution: Consider the value of the following infinitely iterated exponent:

\displaystyle \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\cdot^{\cdot^{\cdot}}}}}

Let a_n = \sqrt{2} \uparrow \uparrow n, that is, the above power tower where we stop at the n-th term. Then a_n is clearly an increasing sequence, and moreover a_n \leq 4 by a trivial induction argument: \sqrt{2} \leq 4 and if a_n \leq 4 then a_{n+1} = (\sqrt{2})^{a_n} \leq (\sqrt{2})^{4} = 4.

So by basic results in analysis, the sequence of a_n converges to a limit. Let’s call this limit x, and try to solve for it.

It is not hard to see that x is defined by the equation:

\displaystyle (\sqrt{2})^x = x,

simply because the infinite power tower starting at the second level is the same as the infinite power tower starting at the first level. However, we notice that x=2 and x=4 both satisfy this relationship. Hence,

\displaystyle 2 = \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\cdot^{\cdot^{\cdot}}}}} = 4

And hence 2=4, as desired. \square

Explanation: The issue here is relatively subtle, but one trained in real analysis should have no trouble spotting the problem.

The first alarm is that we are claiming that the limit of a sequence is not unique, which is always false. Inspecting this argument more closely, we corner the flaw to our claim that x is defined by the equation (\sqrt{2})^x = x. It does, in fact, satisfy this equation, but there is a world of difference between satisfying an equation and being defined by satisfying an equation. One might say that this only makes sense when there is a unique solution to the equation. But as we just saw, there are multiple valid solutions here: 2 and 4 (I don’t immediately see any others; it’s clear no other powers of two will work).

Analogously, one might erroneously say that i is defined by satisfying the equation x^2 = -1, but this does not imply i = -i, since the equation has two differing complex roots. This is a slightly murky analogy, as complex conjugation gives an automorphism of \mathbb{C}. One would reasonably argue that i and -i “play the same role” in this field, while 2 and 4 play wildly different roles as real numbers. But nevertheless, they are not equal simply by virtue of satisfying the same equation.

Moreover, while we said the sequence was bounded from above by 4, an identical argument shows it’s bounded from above by 2. And so one can immediately conclude that the limit of the sequence cannot be 4.

In fact, this infinite tower power x^{x^{\cdot^{\cdot^{\cdot}}}} is continuous as a function, whose domain is the interval [e^{-e}, \sqrt[e]{e}] and whose range is [e^{-1},e]. For more information about interesting number-theoretic properties of infinite power towers, see this paper.

False Proof: 1 = 2 (with Calculus)

Posted on by

Problem: Show 1 = 2 (with calculus)

“Solution”: Consider the following:

1^2 = 1
2^2 = 2 + 2
3^2 = 3 + 3 + 3
\vdots
x^2 = x + x + \dots + x (x times)

And since this is true for all values of x, we may take the derivative of both sides, and the equality remains true. In other words:

2x = 1 + 1 + \dots + 1 (x times)

Which simplifies to x=2x, and plugging in x=1 we have 1 = 2, as desired.

Explanation: Though there are some considerations about the continuity of adding something to itself a variable number of times, the true error is as follows. If we are taking the derivative of a function with respect to x, then we need to take into account all parts of that function which involve the variable. In this case, we ignored that the number of times we add x to itself depends on x. In other words, x + x + \dots + x (x times) is a function of two variables in disguise:

f(u,v) = u + u + \dots + u (v times)

And our mistake was to only take the derivative with respect to the first variable, and ignore the second variable. Unsurprisingly, we made miracles happen after that.

Addendum: Continuing with this logic, we could go on to say:

x = 1 + 1 + \dots + 1 (x times)

But certainly the right hand side is not constant with respect to x, even though each term is.

False Proof – All Numbers are Describable in at Most Twenty Words

Posted on by

Problem: Show that every natural number can be unambiguously described in fewer than twenty words.

“Solution”: Suppose to the contrary that not every natural number can be so described. Let S be the set of all natural numbers which are describable in fewer than twenty words. Consider R = \mathbb{N}-S, the set of all words which cannot be described in fewer than twenty words.

Since R is a subset of the natural numbers, which is well-ordered, it has a unique smallest element which we call r. Now, we may describe r unambiguously with the sentence: “the smallest natural number which cannot be unambiguously described in fewer than twenty words.” Since this description uses only fourteen words, we see that r \in S, a contradiction. Hence, R must be the empty set. \square

Explanation: Let’s analyze this a bit further. Suppose that every number were indeed unambiguously describable in fewer than twenty words. It should be obvious that this admits only finitely many descriptions of infinitely many numbers!

In particular, let there be n words in the English language, which we for the sake of argument say is the number of words in the Oxford English Dictionary. Then there are \displaystyle \sum \limits_{k=1}^{20} n^k different phrases. This is a large number, but it is indeed finite. Even if every phrase describes a natural number, there’s no way that we could get them all! This proof is clearly nonsense.

This apparent paradox is in the same vein as Russell’s paradox, which we cover at the end of our set theory primer. Indeed, in its paradox form, this problem is sometimes called the Richard-Berry paradox. The problem is with what kinds of sets we construct. While with Russell’s paradox, the problem was with elements of our set, here it is with the propositions used to determine membership. This proof gives evidence that the English language (and any human language, really), is not rigorous enough for the purposes of mathematics. It also convinces us that naive set theory is problematic.

We find the meat of the problem when we finally get down to the definition of a description. In short (and I don’t want to spoil upcoming content on this blog), a description of a number is a program which computes the number (on some fixed universal Turing machine U). Note that this assumes that whatever a human can compute a computer can too, which is a controversial statement better known as the Church-Turing Thesis. If we further define a number’s “definition” as the shortest program which computes it, then this statement transforms into “x is the smallest integer whose definition has fewer than 100 characters.” As it turns out, when this English description is appropriately reformulated on a Turing machine, it is not an effective description: the statement is undeciable. In fact, once we get into the theory of Kolmogorov complexity, we will find that Berry’s paradox can be used to prove Gödel’s incompleteness theorem!

The problem of description is a very deep and historically debated one. The various approaches and sub-fields are encapsulated in the study of information theory. One such framework for descriptions is provided by Kolmogorov complexity, which we are diligently working toward understanding. Keep an eye out for our future primer on the subject, which we will write as extra background for the already-written post on low-complexity art and unknown future topics.

False Proof – The Reals are Countable

Posted on by

It seems that false proofs are quickly becoming some of the most popular posts on Math ∩ Programming. I have been preparing exciting posts on applications of graph coloring, deck stacking, and serial killers. Unfortunately, each requires resources which exist solely on my home desktop, which is currently dismantled in California while I am on vacation in Costa Rica. Until I return from the tropics, I will continue with more of the ever -popular false proofs.

Problem: Show the real numbers \mathbb{R} are countable. [For a primer on set theory and countability, see our post on the subject].

“Solution”: Recall from our post on well-orderings that every set has a well-order (assuming the axiom of choice). So \mathbb{R} has a well-ordering. Call it <. Recall additionally that by the definition of a well-order, every nonempty subset of \mathbb{R} has a least element with respect to <. We construct a sequence x_i \in \mathbb{R} that uses this well-order in the following way:

Let x_1 be the smallest element of \mathbb{R} with respect to <. Let x_2 be the smallest element of \mathbb{R} - \left \{ x_1 \right \}. Let x_i be the smallest element of \mathbb{R} - \left \{ x_1, x_2, \dots, x_{i-1} \right \}.

Define f: \mathbb{N} \to \mathbb{R} by f(i)=x_i. Clearly this map is injective, and we argue that it is surjective because any element y \in \mathbb{R} is the smallest element of the subset of \mathbb{R} that contains strictly greater elements with respect to <. So this map is a bijection, and the reals are countable.

Explanation: The reader should be extremely wary of this argument, because it does not only claim that the reals are countable. If the argument above held, then we could apply it to any set (since every set has a well-order!). So something is definitely fishy here.

The problem with analyzing this argument is that the well-order of the reals is not known explicitly. However, our noses point us to recognize that the only place a flaw could exist is in the claim of surjectivity.  We prove the falsity of the above argument now, by proving that the same argument fails to show the integers \mathbb{Z} are countable with respect to a well-order of our choosing.

Define a well-order <_{\xi} on \mathbb{Z} by letting non-positive numbers be larger than all positive numbers, and ordering negative numbers by increasing absolute value. In other words, we order the integers like 1,2, \dots, n, \dots, 0, -1, -2, \dots, -n, \dots. We leave it as an exercise to the reader to prove <_{\xi} is a well-order.

Notice that with the argument above, we never choose -1, or any negative number, as an x_i. Specifically, the sequence of x_i is precisely the natural numbers. Hence, we cannot enumerate all of \mathbb{Z} in this fashion. Clearly the argument fails for \mathbb{R} as well.

This false proof is significant in that we get some intuition about well-orders. In particular, a function from the natural numbers to a set S is also a way to “order” S. However, a well-order is more general and more expressive than a bijection from \mathbb{N} \to S, in that we can construct such an order on any set. As we have seen, with a well-order we don’t have to worry about a contiguous sequence of elements from smallest to greatest. We are allowed the power to say “all of these guys are bigger than all of these guys,” regardless of how many are in each group.

And, as always, with more power comes the responsibility to manage counter-intuitive results, either by accepting them through rigorous proof or rejecting false constructions like the one above.