Открыть главное меню

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

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

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

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

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

 

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

 

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

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

  1. увеличение «основания» на 1 и вычитание 1 из самого числа.

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

 

После второй (меняем 3 на 4 и вычитаем единицу из числа):

 

После третьей (меняем 4 на 5 и вычитаем единицу из числа):

 

Теорема Гудстейна утверждает, что в конце концов всегда будет получен 0.

Верно и более сильное утверждение: Если прибавлять вместо 1 какое-то произвольное число к основанию и его же отнимать от самого числа, то всегда будет получаться 0 даже в том случае, когда показатели степеней не разложены изначально по основанию 2.

Последнее основание в качестве дискретной функции от исходного числа растёт очень быстро, и уже при   оно достигает значения  . При   оно всегда будет числом Сабита и числом Вудала[источник не указан 413 дней].

ПримерПравить

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

ПримечанияПравить

  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.