Часто в разговорах о теореме Гёделя о неполноте просят привести пример. Теорема о последовательности Гудстейна является таким примером.

Теорема Гудстейна — теорема математической логики о натуральных числах, доказанная Рубеном Гудстейном. Утверждает, что все последовательности Гудстейна заканчиваются нулём. Как показали Л. Кирби и Дж. Парис, Теорема Гудстейна эквивалентна утверждению о непротиворечивости арифметики Пеано (PA), а поэтому, в силу второй теоремы Гёделя и непротиворечивости PA, теорема Гудстейна недоказуема в PA (но может быть доказана, например, в арифметике второго порядка).

In mathematical logic, Goodstein's theorem is a statement about the natural numbers, made by Reuben Goodstein, which states that every Goodstein sequence eventually terminates at 0. Kirby & Paris 1982 showed that it is unprovable in Peano arithmetic (but it can be proven in stronger systems, such as second order arithmetic). This was the third "natural" example of a true statement that is unprovable in Peano arithmetic.

Последовательность Гудстейна достаточно проста: используется представление натурального числа в виде суммы степенных членов с одинаковым основанием.

Например, запишем число 581 используя основание 2.


Разложим показатели степени по тому же принципу.


Подобное разложение можно получить для любого числа.

Будем попеременно (рекурсивно) применять к получившемуся выражению две следующие операции:

1. увеличение «основания» на 1;


2. вычитание 1.


...

Конечный предел получаемой последовательности всегда будет равен 0.