У интуиции есть своя логика. Гёдель. Теоремы о неполноте.

Возьмем любое натуральное число, например 25. На его основе построим последовательность чисел, называемую последовательностью Гудстейна для числа 25 (названа в честь Рубена Луиса Гудстейна (1912-1985), английского математика, который впервые ее определил). Для получения второго числа последовательности запишем 25 как сумму степеней числа 2 так, чтобы каждая степень появлялась ровно один раз (1 — это тоже степень числа 2, поскольку 2⁰ = 1):

25 = 2⁴+2³+1.

И запишем также каждый показатель степени как сумму степеней числа 2:

25 = 2^{2^2} +2²⁺¹ + 1.

Второй член последовательности получается, если заменить каждое 2 на 3 в выражении 222 + 2²⁺¹ +1 и затем вычесть 1:

(З^{3^3} + З³⁺¹ +1) - 1 = З^{3^3} + З³⁺¹ = 7625597485068

Второе число последовательности Гудстейна для числа 25 — это 7625597485068. Для получения третьего числа заменяем каждое 3 на 4 в З^{3^3} + З³⁺¹ и вычитаем 1. Получается 4⁴ + 4⁴⁺¹ - 1, операция, которая в результате дает число из 155 цифр. Прежде чем перейти к следующему шагу, надо записать 4⁴ + 4⁴⁺¹ - 1 как сумму степеней числа 4, в которой каждая степень появляется самое большое 3 раза и в которой показатели степени также являются суммой степеней числа 4. Заметьте, что 4⁴ + 4⁴⁺¹ - 1 не записано таким образом, поскольку присутствует вычитание. Правильная запись:

4⁴ + 4⁴ + 4⁴ + 4⁴ + 4¹⁺¹⁺¹ + 4¹⁺¹⁺¹ + 4¹⁺¹⁺¹ + 4¹⁺¹ + 4¹⁺¹ + 4¹⁺¹ + 4 + 4 + 4 + 1 + 1 + 1.

Чтобы получить четвертое число, заменим каждое 4 на 5 и вычтем 1. То есть:

5⁵ + 5⁵ + 5⁵ + 5⁵ + 5¹⁺¹⁺¹ + 5¹⁺¹⁺¹ + 5¹⁺¹⁺¹ + 5¹⁺¹ + 5¹⁺¹ + 5¹⁺¹ + 5 + 5 + 5 + 1 + 1.

Результат последнего вычисления состоит из более чем 2000 цифр. Для получения следующего числа заменим каждое 5 на 6 и вычтем 1, и так далее. Кажется, что последовательность растет до бесконечности. Однако в теореме Гудстейна, доказанной им около 1950 года, утверждается, что вне зависимости от исходного числа последовательность всегда за конечное количество шагов достигнет 0. В доказательстве Гудстейна были использованы понятия теории множеств и оставалась открытой возможность того, что оно неосуществимо на основе аксиом Пеано. Это было подтверждено в 1982 году Лори Кирби и Джеффом Пэрисом, которые доказали, что теорема Гудстейна действительно недоказуема на основе аксиом Пеано с помощью рассуждений, проверяемых алгоритмически.

Посмотрим внимательно на последний шаг: d(423) — это код "d(423) — четное". То есть "d(423) — четное число" может читаться как самореферентное высказывание, говорящее о своем собственном коде следующее: "мой код — четное число". Если бы у "d(423) — четное число" кодом было 503, то высказывание можно было бы записать как "503 — четное число" и в нем бы ложно утверждалось, что его собственный код — четное число.