3
$\begingroup$

So there's this false proof going around that I can't seem to find now that says that complicated numbers don't exist. So let me explain what it's about (I've added some technical details of my own, but the idea is the same).

Definition A number $a \in \mathbb{N}$ is said to be complicated if it cannot be expressed with less than 40 ASCII characters.

Statement There aren't any complicated numbers.

Proof Suppose there are. Then there is one which is the first complicated number. But we can call that one "The first complicated number", which has less than 40 ASCII characters. We get a contradiction, and this proves the statement.

So, I know this is false because I can proof the opposite in a way that seems (to me) more robust, plus intuition tells me there are complicated numbers. Here's a proof that there are complicated numbers.

Proof We assume there are 255 ASCII characters. Assume you can represent all natural numbers with a string of length 40. In particular, you have a unique representation for the $255^{40} + 1$ first natural numbers. By the pigeonhole principle, since there are $255^{40}$ possible strings of length 40, there is two numbers that have the same representation, which contradicts the statement.

Can someone point out the fallacy in the first (or in the second, if there happens to be one) proof? I just can't see why it's wrong.

$\endgroup$
  • 1
    $\begingroup$ This is Berry's paradox, which can be used to show that the complexity of a number is uncomputable in general. $\endgroup$ – Peter Dec 8 '15 at 23:36
  • 3
    $\begingroup$ If you're requiring each representation to be distinct, which you do in the second proof, then you might not be able to refer to the first complicated number as "the first complicated number" since that string may already be referring to another number. $\endgroup$ – arbitrary username Dec 8 '15 at 23:43
  • $\begingroup$ That's a good point, arbitrary username. So the proof had two fallacies then. $\endgroup$ – Martín Forsberg Conde Dec 8 '15 at 23:48
4
$\begingroup$

This paradox is called the Berry paradox. The problem is that you haven't been specific enough about what it means to express a number using ASCII characters. Once you fix the meaning of "express," the first proof becomes a proof by contradiction which shows that "the first complicated number" is not a well-defined expression.

This is a version of the diagonal argument powering Cantor's theorem, Russell's paradox, the unsolvability of the halting problem, the incompleteness theorem, etc.

$\endgroup$
  • $\begingroup$ Thanks for your help! I'm finding this more interesting than I thought. I understand that a problem may arise when using self-referencing stuff, but I can't understand the last part in your answer because my math education just isn't there yet :P . However I will try to read up on something of the sort if I find a book that I can understand. $\endgroup$ – Martín Forsberg Conde Dec 8 '15 at 23:43
  • 1
    $\begingroup$ @Martín: basically, there are a whole bunch of results in mathematics and computer science which place strong limits on meaningful self-reference (precisely because allowing too much self-reference leads to paradoxes like this). This is one of the simpler ones; there are many others (some of which are named above) that you could study to get a grip on this. For example, the liar paradox (en.wikipedia.org/wiki/Liar_paradox) places limitations on the ability of statements to self-reference their own truth values. $\endgroup$ – Qiaochu Yuan Dec 8 '15 at 23:46
  • 1
    $\begingroup$ One which I particularly like, because it doesn't appear to be about self-reference at first, is the following: say that a two-player turn-based game is "finite" if it's guaranteed to end (with a winner and a loser) in finitely many turns. For example, tic-tac-toe is finite. "Hypergame" is the following game: Player 1 picks a finite game, and Player 2 goes first. Then they play the game. The question is: is "hypergame" a finite game? $\endgroup$ – Qiaochu Yuan Dec 8 '15 at 23:48
  • 1
    $\begingroup$ (Technically tic-tac-toe is not finite because it's not guaranteed that there's a winner and loser, right?). But I get the point. I guess the problem is that if Hypergame is finite, then Player 1 can choose to play Hypergame, right? So Hypergame can't be not finite because it's a finite game plus one move, but if it is finite then player 1 can choose Hypergame, then player 2 choose Hypergame... You just blew my mind! Very interesting example :) $\endgroup$ – Martín Forsberg Conde Dec 8 '15 at 23:53
  • $\begingroup$ Oops, yeah. The condition that there's a winner and a loser isn't super important; the paradox still works as long as finite games are guaranteed to end. Yes, that's the problem exactly! $\endgroup$ – Qiaochu Yuan Dec 8 '15 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.