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:

  1. Take the Cantor base-i representation of x_i.
  2. Convert each i into i+1, getting a new number.
  3. 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:

  1. 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.
  2. 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.
  3. 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 pth 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s