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

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

Пример

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

Примечания

Goodstein, R. (1944), On the restricted ordinal theorem, Journal of Symbolic Logic Т. 9: 33–41, <https://www.jstor.org/pss/2268019>
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> Архивная копия от 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$ .

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Goodstein, R. (1944), On the restricted ordinal theorem, Journal of Symbolic Logic Т. 9: 33–41, <https://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> Архивная копия от 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$ .