A concrete piece of evidence for incompleteness

On Thursday, the 25th of March 2015, Venanzio Capretta gave a Theory Lunch talk about Goodstein’s theorem. Later, on the 9th of March, Wolfgang Jeltsch talked about ordinal numbers, which are at the base of Goodstein’s proof. Here, I am writing down a small recollection of their arguments.

Given a base $b \geq 2$ , consider the base- $b$ writing of the nonnegative integer

$n = b^m \cdot a_m + b^{m-1} \cdot a_{m-1} + \ldots + b \cdot a_1 + a_0$

where each $a_i$ is an integer between $0$ and $b-1$ . The Cantor base- $b$ writing of $n$ is obtained by iteratively applying the base- $b$ writing to the exponents as well, until the only values appearing are integers between $0$ and $b$ . For example, for $b = 2$ and $n = 49$ , we have

$49 = 32 + 16 + 1 = 2^{2^2 + 1} + 2^{2^2} + 1$

and also

$49 = 27 + 9 \cdot 2 + 3 + 1 = 3^3 + 3^2 \cdot 2 + 3 + 1$

Given a nonnegative integer $n$ , consider the Goodstein sequence defined for $i \geq 2$ by putting $x_2 = n$ , and by constructing $x_{i+1}$ from $x_i$ as follows:

Take the Cantor base- $i$ representation of $x_i$ .
Convert each $i$ into $i+1$ , getting a new number.
If the value obtained at the previous point is positive, then subtract $1$ from it.
(This is called the woodworm’s trick.)

Goodstein’s theorem. Whatever the initial value $x_2$ , the Goodstein sequence ultimately reaches the value $0$ in finitely many steps.

Goodstein’s proof relies on the use of ordinal arithmetic. Recall the definition: an ordinal number is an equivalence class of well-ordered sets modulo order isomorphisms, i.e., order-preserving bijections.Observe that such order isomorphism between well-ordered sets, if it exists, is unique: if $(X, \leq_X)$ and $(Y, \leq_Y)$ are well-ordered sets, and $f, g : X \to Y$ are two distinct order isomorphisms, then either $U = \{ x \in X \mid f(x) <_Y g(x) \}$ or $V = \{ x \in X \mid g(x) <_Y f(x) \}$ has a minimum $m$ , which cannot correspond to any element of $Y$ .

An interval in a well-ordered set $(X, \leq)$ is a subset of the form $[0, y) = \{ x \in \alpha \mid x < y \}$ .

Fact 1. Given any two well-ordered sets, either they are order-isomorphic, or one of them is order-isomorphic to an initial interval of the other.

In particular, every ordinal $\alpha$ is order-isomorphic to the interval $[0, \alpha)$ .

All ordinal numbers can be obtained via von Neumann’s classification:

The zero ordinal is $0 = \emptyset$ , which is trivially well-ordered as it has no nonempty subsets.
A successor ordinal is an ordinal of the form $\alpha + 1 = \alpha \sqcup \{\alpha\}$ , with every object in $\alpha$ being smaller than $\{\alpha\}$ in $\alpha + 1$ .
For instance, $N + 1$ can be seen as $N \sqcup \{N\}$ .
A limit ordinal is a nonzero ordinal which is not a successor. Such ordinal must be the least upper bound of the collection of all the ordinals below it.
For instance, the smallest transfinite ordinal $\omega$ is the limit of the collection of the finite ordinals.

Observe that, with this convention, each ordinal is an element of every ordinal strictly greater than itself.

Fact 2. Every set of ordinal numbers is well-ordered with respect to the relation: $\alpha < \beta$ if and only if $\alpha \in \beta$ .

Operations between ordinal numbers are defined as follows: (up to order isomorphisms)

$\alpha + \beta$ is a copy of $\alpha$ followed by a copy of $\beta$ , with every object in $\alpha$ being strictly smaller than any object in $\beta$ .
If $M$ and $N$ are finite ordinals, then $M+N$ has the intuitive meaning. On the other hand, $1 + \omega = \omega$ , as a copy of $1$ followed by a copy of $\omega$ is order-isomorphic to $\omega$ : but $\omega + 1$ is strictly larger than $\omega$ , as the latter is an initial interval of the former.
$\alpha \cdot \beta$ is a stack of $\beta$ copies of $\alpha$ , with each object in each layer being strictly smaller than any object of any layer above.
If $M$ and $N$ are finite ordinals, then $M \cdot N$ has the intuitive meaning. On the other hand, $2 \cdot \omega$ is a stack of $\omega$ copies of $2$ , which is order-isomorphic to $\omega$ : but $\omega \cdot 2$ is a stack of $2$ copies of $\omega$ , which is order-isomorphic to $\omega + \omega$ .
$\alpha^\beta$ is $1$ if $\beta = 0$ , $\alpha^\gamma \cdot \alpha$ if $\beta$ is the successor of $\gamma$ , and the least upper bound of the ordinals of the form $\alpha^x$ with $x < \beta$ if $\beta$ is a limit ordinal.
If $M$ and $N$ are finite ordinals, then $M^N$ has the intuitive meaning. On the other hand, $2^\omega$ is the least upper bound of all the ordinals of the form $2^N$ where $N$ is a finite ordinal, which is precisely $\omega$ : but $\omega^2 = \omega \cdot \omega$ .

Proof of Goodstein’s theorem: To each integer value $x_i$ we associate an ordinal number $y_i$ by replacing each $i$ (which, let’s not forget, is the base $x_i$ is written in) with $\omega$ . For example, if $x_2 = 49 = 2^{2^2 + 1} + 2^{2^2} + 1$ , then

$y_2 = \omega^{\omega^\omega + 1} + \omega^{\omega^\omega} + 1$

and $x_3 = 3^{3^3 + 1} + 3^{3^3}$ (which, incidentally, equals $30,502,389,939,948$ ) so that

$y_3 = \omega^{\omega^\omega + 1} + \omega^{\omega^\omega}$

We notice that, in our example, $x_3 > x_2$ , but $y_3 < y_2$ : why is it so?, and is it just a case, or is there a rule behind this?

At each step $i \geq 2$ where $x_i > 0$ , consider the writing $x_i = i^m \cdot a_m + \ldots + i \cdot a_1 + a_0$ . Three cases are possible:

$m = 0$ .
Then $y_i = a_0$ , $x_{i+1} = a_0 - 1$ as $a_0 < i$ , and $y_{i+1} = a_0 - 1 < y_i$ .
$m > 0$ and $a_0 > 0$ .
Then $y_i = \alpha + a_0$ for a transfinite ordinal $\alpha$ , and $y_{i+1} = \alpha + (a_0 - 1) < y_i$ .
$m > 0$ and $a_0 = 0$ .
Then $x_i = i^m \cdot a_m + \ldots + i^p \cdot a_p$ for some $p > 0$ , and $x_{i+1} = (i+1)^m \cdot a_m + \ldots + (i+1)^p \cdot a_p - 1$ is a number whose $p$ th digit in base $i+1$ is zero: correspondingly, the rightmost term in $y_i$ will be replaced by a smaller ordinal in $y_{i+1}$ .

It is then clear that the sequence $y_i$ is strictly decreasing. But the collection of all ordinals not larger than $y_2$ is a well-ordered set, and every nonincreasing sequence in a well-ordered set is ultimately constant: hence, there must be a value $i$ such that $y_i = y_{i+1}$ . But the only way it can be so is when $y_i = 0$ : in turn, the only option for $y_i$ to be zero, is that $x_i$ is zero as well. This proves the theorem. $\Box$

So why is it that Goodstein’s theorem is not provable in the first order Peano arithmetics? The intuitive reason, is that the exponentiations can be arbitrarily many, which requires having available all the ordinals up to

$\varepsilon_0 = \left. \omega^{\omega^{\omega^{\omega \vdots}}} \right\}$ , $\omega$ times $= \sup_{n < \omega} \left. \omega^{\omega^{\vdots^\omega}} \right\}$ , $n$ times:

this, however, is impossible if induction only allows finitely many steps, as it is the case for first-order Peano arithmetics. A full discussion of a counterexample, however, would greatly exceed the scope of this post.

Theory Lunch

Institute of Cybernetics, Tallinn

A concrete piece of evidence for incompleteness

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply