Теорема Гудстейна

Теорема Гудстейна — теорема математической логики о натуральных числах, доказанная Рубеном Гудстейном. Утверждает, что все последовательности Гудстейна заканчиваются нулём. Как показали Л. Кирби и Дж. Парис (англ.), теорема Гудстейна эквивалентна утверждению о непротиворечивости арифметики Пеано $(PA)$, а поэтому, в силу второй теоремы Гёделя и непротиворечивости $PA,$ теорема Гудстейна недоказуема в $PA$ (но может быть доказана, например, в арифметике второго порядка).

Последовательность Гудстейна

Рассмотрим представление целых положительных чисел в виде суммы степенных членов с одинаковым основанием.

Например, запишем число 581, используя основание 2.

$\ 581 = 512 + 64 + 4 + 1 = 2^9 + 2^6 + 2^2 + 2^0.$

Разложим показатели степени по тому же принципу.

$\ 581 = 2^{2^3+1} + 2^{2^2+2} + 2^2 + 1 = 2^{2^{2+1}+1} + 2^{2^2+2} + 2^2 + 1$

Подобное разложение можно получить для любого числа.

Будем попеременно (рекурсивно) применять к получившемуся выражению две следующие операции:

1. увеличение «основания» на 1;
2. вычитание 1.

Таким образом, после применения первой операции будет получено выражение:

$\ 3^{3^{3+1}+1} + 3^{3^3+3} + 3^3 + 1$

После применения второй операции будет:

$\ 3^{3^{3+1}+1} + 3^{3^3+3} + 3^3$

После третьей:

$\ 4^{4^{4+1}+1} + 4^{4^4+4} + 4^4$

После четвёртой:

$\ 4^{4^{4+1}+1} + 4^{4^4+4} + 3 \times 4^3 + 3 \times 4^2 + 3 \times 4 + 3$

После пятой:

$\ 5^{5^{5+1}+1} + 5^{5^5+5} + 3 \times 5^3 + 3 \times 5^2 + 3 \times 5 + 3$

Теорема Гудстейна утверждает, что в конце концов всегда будет получен 0.

Пример

Рассмотрим пример последовательности Гудстейна для числа 3.

Основание	Запись	Значение
2	21 + 1	3
3	(31 + 1) − 1 = 31	3
4	41 − 1 = 1 + 1 + 1	3
5	(1 + 1 + 1) − 1 = 1 + 1	2
6	(1 + 1) − 1 = 1	1
7	1 − 1 = 0	0