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

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:

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. 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