Теорема Гудстейна — теорема математической логики о натуральных числах, доказанная Рубеном Гудстейном в 1944 году. Утверждает, что так называемые последовательности Гудстейна заканчиваются нулём. В 1982 году Лори Кирби и Джефф Парис показали, что теорема Гудстейна недоказуема в арифметике первого порядкаРоджер Пенроуз. Большое малое и человеческий разум. Приложение 1.. Тем не менее она может быть (и была) доказана, например, в арифметике второго порядка.
Наследственная запись по основанию n
Рассмотрим представление целых положительных чисел в виде суммы степенных членов с одинаковым основанием. Это представление аналогично представлению чисел в позиционной системе счисления Чтобы получить запись по основанию n (где n — натуральное число больше 1), произвольное натуральное число m представляют в виде суммы кратных степеней числа n.
где каждый коэффициент ai удовлетворяет условиям , и .
Например, запишем число 581, используя основание 2:
Здесь все коэффициенты равны 1.
При разложении по бо́льшим основаниям коэффициенты могут различаться. Например разложение числа 100 по основанию 3 имеет вид
Разложим показатели степени для числа 581 по основани 2 по тому же принципу:
что является наследственной записью по основанию 2. Подобное разложение можно получить для любого числа по любому основанию.
Формулировка
Будем рекурсивно применять к наследственной записи некоторого числа, начиная с основания 2, следующую операцию: увеличение «основания» на 1 и вычитание 1 из самого числа. Таким образом, после применения первой операции для разложения числа 581 (меняем 2 на 3 и вычитаем единицу из числа) будет получено выражение
После второй (меняем основание 3 на 4 и вычитаем единицу из числа):
После третьей (меняем основание 4 на 5 и вычитаем единицу из числа):
Теорема Гудстейна утверждает, что в конце концов всегда будет получен 0.
Примеры Рассмотрим пример последовательности Гудстейна для чисел 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 какое-то произвольное число к основанию и его же отнимать от самого числа, то всегда будет получаться 0 даже в том случае, когда показатели степеней не разложены изначально по основанию 2.
Последнее основание в качестве дискретной функции от исходного числа растёт очень быстро, и уже при оно достигает значения . При оно всегда будет числом ВудалаРассмотрим представление числа в виде , где — наше основание. Когда останется только коэффициент при , равный единице, обозначим значение этого . После этого при число превращается в Нетрудно показать, что в ходе дальнейшей эволюции каждое снижение коэффициента при на 1 удваивает k. Последним значением основания станет . .
Примечания
Гудстейна Категория:Теоремы теории множеств Гудстейна