- Теорема Гудстейна
-
Теорема Гудстейна — теорема математической логики о натуральных числах, доказанная Рубеном Гудстейном.[1] Утверждает, что все последовательности Гудстейна заканчиваются нулём. Как показали Л. Кирби и Дж. Парис (англ.),[2][3] Теорема Гудстейна эквивалентна утверждению о непротиворечивости арифметики Пеано , а поэтому, в силу второй теоремы Гёделя и непротиворечивости теорема Гудстейна недоказуема в (но может быть доказана, например, в арифметике второго порядка).
Последовательность Гудстейна
Рассмотрим представление целых положительных чисел в виде суммы степенных членов с одинаковым основанием.
Например, запишем число 581 используя основание 2.
Разложим показатели степени по тому же принципу.
Подобное разложение можно получить для любого числа.
Будем попеременно (рекурсивно) применять к получившемуся выражению две следующие операции:
- увеличение «основания» на 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 Примечания
- ↑ Goodstein, R. (1944), "«On the restricted ordinal theorem»", Journal of Symbolic Logic Т. 9: 33–41, <http://www.jstor.org/pss/2268019>
- ↑ 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>
- ↑ Роджер Пенроуз. Большое малое и человеческий разум. Приложение 1.
Категории:- Теоремы
- Теория множеств
Wikimedia Foundation. 2010.