Mathematical logic and foundations Arithmetic and incompleteness Theorem

Goodstein's theorem

Statement

Let $b \ge 2$ be an integer. The hereditary base- $b$ notation of $n \ge 1$ writes $n$ as a sum $b^{e_1} c_1 + \cdots + b^{e_r} c_r$ with $e_1 > \cdots > e_r$ and $0 < c_i < b$ . Then it writes each exponent $e_i$ in hereditary base- $b$ notation again. Let $B_b(n)$ be the number obtained by replacing every $b$ in this notation by $b + 1$ , with $B_b(0) = 0$ . The Goodstein sequence of $m \in \N$ is $G_1 = m$ and $G_{k+1} = B_{k+1}(G_k) - 1$ while $G_k > 0$ .

For every $m \in \N$ the Goodstein sequence of $m$ reaches $0$ .
Statement 1, written as a sentence of first-order arithmetic, is not provable in Peano arithmetic $\mathsf{PA}$ .

Remarks

Proof idea for 1: replace each base in the hereditary notation of $G_k$ by the ordinal $\omega$ . This gives an ordinal $o_k < \varepsilon_0$ , and the change of base does not change it while subtracting $1$ makes it strictly smaller. A strictly decreasing sequence of ordinals is finite, so the sequence reaches $0$ . Goodstein proved part 1 in 1944; Kirby and Paris proved part 2 in 1982, by showing that $\mathsf{PA}$ plus statement 1 proves the consistency of $\mathsf{PA}$ .

Example: for $m = 3$ , the sequence is $3 = 2 + 1$ , then $3 + 1 - 1 = 3$ , then in base $3$ , $3 = 3^1$ becomes $4 - 1 = 3$ , then $2$ , $1$ , $0$ . For $m = 4$ the sequence also reaches $0$ , but only after more than $10^{100{,}000{,}000}$ steps.

Going deeper

For a student

The theorem shows how ordinals below $\varepsilon_0$ measure the strength of $\mathsf{PA}$ : transfinite induction up to epsilon nought proves it, while $\mathsf{PA}$ does not. This ties it to Gentzen's consistency proof and to ordinal analysis. Like the Paris–Harrington theorem, it is a natural true statement independent of $\mathsf{PA}$ .

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Ordinal number concept
Peano axioms concept
Goodstein's theorem statement

Tag	`XQMNJF241J`
URI	`m2://XQMNJF241J`
Kind	statement, theorem
Writing	W0 stub
MSC	03F30, 03F15
Status	This copy of the site has no build data. Run `m2 status XQMNJF241J`.
About	Peano axioms
Uses	Peano axioms, Ordinal number
Same as	Wikidata Q1149185 Wikipedia Goodstein's theorem