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

Теорема Гудштейна — твердження математичної логіки про натуральні числа, зроблене Рубеном Гудштейном, стверджує, що всі послідовності Гудштейна закінчуються нулем. Це теорема є невиводимою із аксіом Пеано, але може бути доведена в арифметиці другого порядку.

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

Спочатку визначимо нотацію запису чисел на основі степенів одного числа (hereditary base-n notation).

Запишемо натуральне число в вигляді $a_{k}n^{k}+a_{k-1}n^{k-1}+\cdots +a_{0},\;\;0\leq a_{i}\leq (n-1).$ Потім позбудемось від коефіцієнтів, перетворимо множення в суму однакових доданків: $\ a_{k}n^{k}$ стане $n^{k}+n^{k}+\cdots +n^{k}.$

Далі запишемо всі показники степенів в нашій нотації і продовжимо це робити рекурсивно поки всі числа в запису не стануть рівними n чи 0 (записуватимемо 1 для скороченого позначення n⁰).

Наприклад, 35 на основі степенів 2 буде

\ 2^{2^{2}+1}+2+1.

Послідовність Гудштейна для числа m позначимо G(m) і визначимо так: першим елементом послідовності буде число m, наступним елементом буде запис числа m на основі степенів 2; для наступного замінимо всі 2-ки на 3-ки й віднімемо 1, переведемо число в запис на основі степенів 3; і так далі.

Приклади

Розглянемо коротку послідовність G(3):

Основа	Запис	Значення
2	2¹ + 1	3
3	(3¹ + 1) − 1 = 3¹	3
4	4¹ − 1 = 1 + 1 + 1	3
5	(1 + 1 + 1) − 1 = 1 + 1	2
6	(1 + 1) − 1 = 1	1
7	1 − 1 = 0	0

Вже послідовність G(4) буде дуже довгою.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.