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

Теорема Гудстейна — теорема математической логики о натуральных числах, доказанная Рубеном Гудстейном.^[1] Утверждает, что все последовательности Гудстейна заканчиваются нулём. Как показали Л. Кирби и Дж. Парис (англ.),^[2][3] Теорема Гудстейна эквивалентна утверждению о непротиворечивости арифметики Пеано $(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

Примечания

1. ↑ Goodstein, R. (1944), "«On the restricted ordinal theorem»", Journal of Symbolic Logic Т. 9: 33–41, <http://www.jstor.org/pss/2268019> 
2. ↑ Kirby, L. & Paris, J. (1982), "«Accessible independence results for Peano arithmetic»", Bulletin London Mathematical Society Т. 14: 285–293, <http://reference.kfupm.edu.sa/content/a/c/accessible_independence_results_for_pean_59864.pdf> 
3. ↑ Роджер Пенроуз. Большое малое и человеческий разум. Приложение 1.