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

Теорема Гудстейна — теорема математической логики о натуральных числах, доказанная Рубеном Гудстейном в 1944 году^[1]. Утверждает, что так называемые последовательности Гудстейна заканчиваются нулём. В 1982 году Л. Кирби и Джефф Парис показали, что теорема Гудстейна недоказуема в арифметике первого порядка^[2]^[3]. Тем не менее она может быть (и была) доказана, например, в арифметике второго порядка.

Формулировка

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

Например, запишем число 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 на 3 и вычитаем единицу из числа) будет получено выражение

3^{3^{3+1}+1}+3^{3^{3}+3}+3^{3}.

После второй (меняем 3 на 4 и вычитаем единицу из числа):

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

После третьей (меняем 4 на 5 и вычитаем единицу из числа):

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

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

Примеры

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

Число	Основание	Запись	Значение
1	2	1	1
	3	1 - 1	0
2	2	2¹	2
	3	3¹ − 1	2
	4	2 - 1	1
	5	1 − 1	0
3	2	2¹ + 1	3
	3	(3¹ + 1) − 1 = 3¹	3
	4	4¹ − 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 какое-то произвольное число к основанию и его же отнимать от самого числа, то всегда будет получаться 0 даже в том случае, когда показатели степеней не разложены изначально по основанию 2.

Последнее основание в качестве дискретной функции от исходного числа растёт очень быстро, и уже при $n=4$ оно достигает значения $3\times 2^{27}\times 2^{3\times 2^{27}}-1=3\times 2^{402653211}-1$ . При $n>3$ оно всегда будет числом Вудала^[4].

Примечания

↑ Goodstein, R. (1944), "On the restricted ordinal theorem", Journal of Symbolic Logic, 9: 33—41
↑ Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic" (PDF), Bulletin London Mathematical Society, 14: 285—293, Архивировано из оригинала (PDF) 25 августа 2011 Архивная копия от 25 августа 2011 на Wayback Machine
↑ Роджер Пенроуз. Большое малое и человеческий разум. Приложение 1.
↑ Рассмотрим представление числа в виде $\sum a_{i}k^{\sum b_{ij}k^{\dots }}$ , где $k$ — наше основание. Когда останется только коэффициент при $k^{2}$ , равный единице, обозначим значение этого $k$ $k_{2}$ . После этого при $k=k_{2}+1$ число превращается в $k_{2}k+k_{2}.$ Нетрудно показать, что в ходе дальнейшей эволюции каждое снижение коэффициента при $k$ на 1 удваивает k. Последним значением основания станет $k_{2}\cdot 2^{k_{2}}-1$ .

[1] Goodstein, R. (1944), "On the restricted ordinal theorem", Journal of Symbolic Logic, 9: 33—41

[2] Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic" (PDF), Bulletin London Mathematical Society, 14: 285—293, Архивировано из оригинала (PDF) 25 августа 2011 Архивная копия от 25 августа 2011 на Wayback Machine

[3] Роджер Пенроуз. Большое малое и человеческий разум. Приложение 1.

[4] Рассмотрим представление числа в виде $\sum a_{i}k^{\sum b_{ij}k^{\dots }}$ , где $k$ — наше основание. Когда останется только коэффициент при $k^{2}$ , равный единице, обозначим значение этого $k$ $k_{2}$ . После этого при $k=k_{2}+1$ число превращается в $k_{2}k+k_{2}.$ Нетрудно показать, что в ходе дальнейшей эволюции каждое снижение коэффициента при $k$ на 1 удваивает k. Последним значением основания станет $k_{2}\cdot 2^{k_{2}}-1$ .

[1]

[2]

[3]

[4]