Así que hay una prueba falsa por ahí que parece que no puedo encontrar ahora que dice que los números complicados no existen. Así que déjame explicar de qué se trata (he añadido algunos detalles técnicos propios, pero la idea es la misma).
Definición Un número $a \in \mathbb{N}$ se dice que complicado si no puede expresarse con menos de 40 caracteres ASCII.
Declaración No hay números complicados.
Prueba Supongamos que hay. Entonces hay uno que es el primer número complicado. Pero podemos llamar a ese "El primer número complicado", que tiene menos de 40 caracteres ASCII. Obtenemos una contradicción, y esto demuestra la afirmación.
Entonces, sé que esto es falso porque puedo probar lo contrario de una manera que me parece (a mí) más sólida, además la intuición me dice que hay son números complicados. Aquí hay una prueba de que hay números complicados.
Prueba Suponemos que hay 255 caracteres ASCII. Supongamos que se pueden representar todos los números naturales con una cadena de longitud 40. En particular, tiene una representación única para el $255^{40} + 1$ primeros números naturales. Por el principio de encasillamiento, ya que hay $255^{40}$ posibles cadenas de longitud 40, hay dos números que tienen la misma representación, lo que contradice la afirmación.
¿Puede alguien señalar la falacia en la primera prueba (o en la segunda, si es que la hay)? Es que no veo por qué es errónea.
