Goldstein sequence

From Example Problems
Jump to: navigation, search

In mathematics, Goldstein sequences are an interesting example of the power of ordinal arithmetic.


A Goldstein sequence \{a_{n}\}_{{n=1}}^{\infty } may be defined in the following way:

Given any positive integer k, let a_{1}=k. Now, write k as a sum over its binary expansion. For example, for k=10, we have a_{1}=10=2^{3}+2^{1}. Then write each exponents in the binary expansion as a binary expansions as well. Continuing with the previous example:


Now, define a_{2} to be the number obtained in from this expansion for a_{1} by first replacing all the 2s with 3s, and then subtracting 1 from the result. So, for our example,


We generalize this recurrence: given each a_{k}, write it in its base-k+1 representation, and write each of the exponents in their base-k+1 representation. Then we define a_{{k+1}} by replacing all instances of k+1 in the expanded expression with k+2, and subtracting 1 from the result. For example, for a_{3}:

a_{2}=83=(3^{{3^{1}+1}}+2 a_{3}=(4^{{4^{1}+1}}+2)-1=1026

This is well-defined because the base expansion is guaranteed to be unique, and we will never encounter any b as a coefficient in the base-b expansion.


Intuitively, it seems that the sequence a_{n} is increasing very quickly: for our example, in the first two steps the sequence goes from 10 to 1026, and each step adds to both the base and the exponent. One might expect that the sequence will proceed to infinity.

However, it can be shown that the limit of every such sequence is 0. The secret here is the fact that we subtract 1 in each step. This surprising result can be proven by defining a 'size function' σ which, given any a_{k} in its expanded form, maps the base k+1 to ω (the first transfinite ordinal) but leaves the rest of the expression intact. For example:

\sigma (a_{1})=\sigma (2^{{2^{1}+1}}+2^{1}+1)=\omega ^{{\omega ^{1}+1}}+\omega ^{1}
\sigma (a_{2})=\sigma (3^{{3^{1}+1}}+2)=\omega ^{{\omega ^{1}+1}}+2
\sigma (a_{3})=\sigma (4^{{4^{1}+1}}+1)=\omega ^{{\omega ^{1}+1}}+1
\sigma (a_{4})=\sigma (5^{{5^{1}+1}})=\omega ^{{\omega ^{1}+1}}

When we compare \sigma (a_{k}) with \sigma (a_{{k+1}}), we see that the rule for transforming a_{k} with a_{{k+1}} by replacing k+1 does not change the value of \sigma , because the k+1 is mapped to ω. However, we can see from the above example that the fact that we are subtracting 1 does affect σ: the ordinal value of \sigma (a_{n}) is decreased by 1 with each step.

Since the nonnegative integers are totally ordered, and the value of \sigma (a_{n}) is a infinite strictly decreasing sequence with respect to this order, then its limit is the lower bound of the set, namely 0.