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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

\ 3^{3^{3+1}+1} + 3^{3^3+3} + 3^3 + 1

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

\ 3^{3^{3+1}+1} + 3^{3^3+3} + 3^3

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

\ 4^{4^{4+1}+1} + 4^{4^4+4} + 4^4

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

\ 4^{4^{4+1}+1} + 4^{4^4+4} + 3 \times 4^3 + 3 \times 4^2 + 3 \times 4 + 3

После пятой:

\ 5^{5^{5+1}+1} + 5^{5^5+5} + 3 \times 5^3 + 3 \times 5^2 + 3 \times 5 + 3

Теорема Гудстейна утверждает, что в конце концов всегда будет получен 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, <http://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> 
  3. Роджер Пенроуз. Большое малое и человеческий разум. Приложение 1.