Consider the smallest class Sk
of one place functions over the naturals which contains
1
f
and g
contains also the pointwise sum, product
and power:
f < g
to mean that g
majorises f
; ie. that there is some
n
such that f(m) < g(m)
for all m
> n
.
For example, the majorisation order between polynomials (in the form
x^n1 + x^n2 + .. x^nk
with n1 >= n2 >= .. >= nk
) is the
same as the lexicographic (dictionary) order of their exponent sequences (n1,n2,...,nk)
.
Given f : Sk
, define Sk(f)
to be the class of g : Sk
such that g <
f
.
By a result of Hardy (1924) [or was it Richardson?], this order
is linear. By a result of Ehrenfeucht (1973, using Kruskal's
theorem), Sk
is wellordered. Skolem's
problem/conjecture is that the order-type of Sk
is
epsilon_0
. (He showed that it is at least
epsilon_0
.)
One might think that there should be a simple solution to this problem. However, all we know so far is that:
epsilon
number
(phi_2(0)
in the Veblen hierarchy
over a |-> w^a
). [Levitz]Sk(2^x)
is w^w
.Sk(2^(2^x))
is
w^(w^w)
.