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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Послідовності Гудштейна[ред.ред. код]

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

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

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

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

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

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

Приклади[ред.ред. код]

Розглянемо коротку послідовність G(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

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