Goldstein sequence

From Exampleproblems

Jump to: navigation, search

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

Definition

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

Given any positive integer k, let a1 = k. Now, write k as a sum over its binary expansion. For example, for k = 10, we have a1 = 10 = 23 + 21. Then write each exponents in the binary expansion as a binary expansions as well. Continuing with the previous example:

a_1 = 2^3 + 2^1 = 2^{2^1+1} + 2^1

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

a_2 = (3^{3^1+1} + 3^1) - 1 = 83

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

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.

Properties

Intuitively, it seems that the sequence an 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 ak 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 σ(ak) with σ(ak + 1), we see that the rule for transforming ak with ak + 1 by replacing k+1 does not change the value of σ, 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 σ(an) is decreased by 1 with each step.

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

Personal tools

Flash!
A Free Fun Game!
For Android 4.0

Get A Wifi Network
Switcher Widget for
Android