Consider the smallest class `Sk`

of one place functions over the naturals which contains

- The identity function
- The function with constant value
`1`

`f`

and `g`

contains also the pointwise sum, product
and power:
- f+g
- f.g
- f^g

`f < g `

to mean that `g`

`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)`

.

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

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