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.
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.