WikiSort.ru - Не сортированное

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

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

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

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

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

Пример

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

Примечания