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

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

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

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

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

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

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

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

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

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

Ця стаття не містить посилань на джерела. Ви можете допомогти поліпшити цю статтю, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (серпень 2018)