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

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

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

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

Например, запишем число 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 какое-то произвольное число к основанию и его же отнимать от самого числа, то всегда будет получаться 0 даже в том случае, когда показатели степеней не разложены изначально по основанию 2.

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

Пример

Рассмотрим пример последовательности Гудстейна для чисел 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

Примечания

(1944), , , 9 : 33—41
; (1982), (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$ .