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

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

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

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

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

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

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

${\displaystyle 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 и вычитание 1 из самого числа.

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

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

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

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

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

${\displaystyle 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	21	2
	3	31 − 1	2
	4	2 - 1	1
	5	1 − 1	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 какое-то произвольное число к основанию и его же отнимать от самого числа, то всегда будет получаться 0 даже в том случае, когда показатели степеней не разложены изначально по основанию 2.

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

Примечания

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