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

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

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

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

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

Подобное разложение можно получить для любого числа.

Будем попеременно (рекурсивно) применять к получившемуся выражению две следующие операции:

1. увеличение «основания» на 1;
2. вычитание 1.

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

После применения второй операции будет:

После третьей:

После четвёртой:

После пятой:

Конечный предел получаемой последовательности всегда будет равен 0.

Пример

Рассмотрим последовательности для числа 3.

Примечания