Русская Википедия:Теорема Гудстейна
Теорема Гудстейна — теорема математической логики о натуральных числах, доказанная Рубеном Гудстейном в 1944 году[1]. Утверждает, что все последовательности Гудстейна заканчиваются нулём. В 1982 году Л. Кирби и Джефф Парис показали, что теорема Гудстейна недоказуема в арифметике первого порядка[2][3]. Тем не менее она может быть (и была) доказана, например, в арифметике второго порядка.
Последовательность Гудстейна
Рассмотрим представление целых положительных чисел в виде суммы степенных членов с одинаковым основанием.
Например, запишем число 581, используя основание 2:
- <math>581 = 512 + 64 + 4 + 1 = 2^9 + 2^6 + 2^2 + 2^0.</math>
Разложим показатели степени по тому же принципу:
- <math>581 = 2^{2^3+1} + 2^{2^2+2} + 2^2 + 1 = 2^{2^{2+1}+1} + 2^{2^2+2} + 2^2 + 1.</math>
Подобное разложение можно получить для любого числа.
Будем рекурсивно применять к получившемуся выражению следующую операцию:
- увеличение «основания» на 1 и вычитание 1 из самого числа.
Таким образом, после применения первой операции (меняем 2 на 3 и вычитаем единицу из числа) будет получено выражение
- <math>3^{3^{3+1}+1} + 3^{3^3+3} + 3^3.</math>
После второй (меняем 3 на 4 и вычитаем единицу из числа):
- <math>4^{4^{4+1}+1} + 4^{4^4+4} + 3 \times 4^3 + 3 \times 4^2 + 3 \times 4 + 3.</math>
После третьей (меняем 4 на 5 и вычитаем единицу из числа):
- <math>5^{5^{5+1}+1} + 5^{5^5+5} + 3 \times 5^3 + 3 \times 5^2 + 3 \times 5 + 2.</math>
Теорема Гудстейна утверждает, что в конце концов всегда будет получен 0.
Верно и более сильное утверждение: Если прибавлять вместо 1 какое-то произвольное число к основанию и его же отнимать от самого числа, то всегда будет получаться 0 даже в том случае, когда показатели степеней не разложены изначально по основанию 2.
Последнее основание в качестве дискретной функции от исходного числа растёт очень быстро, и уже при <math>n = 4</math> оно достигает значения <math>3\times 2^{27}\times 2^{3 \times 2^{27}} - 1 = 3\times 2^{402653211}-1</math>. При <math>n > 3</math> оно всегда будет числом Вудала[4].
Пример
Рассмотрим пример последовательности Гудстейна для чисел 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 |
Примечания
- ↑ Шаблон:Citation
- ↑ Шаблон:Citation Шаблон:Wayback
- ↑ Роджер Пенроуз. Большое малое и человеческий разум. Приложение 1.
- ↑ Рассмотрим представление числа в виде <math> \sum a_ik^{\sum b_{ij} k^{\dots}}</math>, где <math>k</math> -- наше основание. Когда останется только коэффициент при <math>k^2</math>, равный единице, обозначим значение этого <math>k</math> <math>k_2</math>. После этого при <math>k=k_2+1</math> число превращается в <math>k_2k+k_2.</math> Нетрудно показать, что в ходе дальнейшей эволюции каждое снижение коэффициента при <math>k</math> на 1 удваивает k. Последним значением основания станет <math>k_2\cdot 2^{k_2} -1</math>.
