Skolem's problem

About 1956, Skolem proposed a very simple problem which has not yet been solved (as far as I know).

Consider the smallest class Sk of one place functions over the naturals which contains

The identity function
The function with constant value 1

and whenever it contains f and g contains also the pointwise sum, product and power:

Define 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:

The order type is less that the first critical epsilon number (phi_2(0) in the Veblen hierarchy over a |-> w^a). [Levitz]
The o.t. of Sk(2^x) is w^w.
The o.t. of Sk(2^(2^x)) is w^(w^w).

These partial results are proved in various papers by Hilbert Levitz, Lou van den Dries, and Bernd I. Dahn. I will write down some references when/if I find them again.

Lou van den Dries and Hilbert Levitz, Transactions of the American Mathematical Society, 286 (1984) pp 339-349. (There is another relevant article by Dahn shortly after in the same journal).

One wonders what happens when we consider expressions in more than one variable.

Peter Hancock

Last modified: Wed Jul 26 13:59:02 BST 2000