A Problem of Skolem - Part 1

Welcome! This is the first part of a series of posts on a problem of Skolem’s (Yes, the mathematician and logician Thoralf Skolem!). In this post, I will introduce the problem and work through a minimal example. I will list all the books and papers at the bottom of each post. I will use and to denote the set of natural numbers and the set of non-zero natural numbers respectively.

Consider the set of functions which contains the constant function and the identity function and which is closed under addition, multiplication, and exponentiation. That is,

3. if and are in then so are , and .

For example, the set of all non-zero polynomials are in , and so are the functions etc. Of course, the mathematical operations here are done pointwise. Now that we have the set , a relation is introduced on it. Let’s define it. Let . Write if and only if there exists such that for all we have . This means that the function is eventually bigger than the function ; indeed we say that is majorized or dominated by . For example, and so on. We will write if or for each .

Alright. We now have a set and a relation on it. What now? Well, by a result of Hardy’s (Hardy 1924), and also, independently, by both Richardson (Richardson 1969) and Tarski, it follows that is a linearly ordered set. Is that the best we can say about this ordering? Actually, Ehrenfeucht (Ehrenfeucht 1973) proved that this linear ordering is in fact a well-ordering (by the way, his paper is one of the shortest papers I’ve ever seen!). He used one of Kruskal’s results (a Tree Theorem) (Kruskal 1960) to prove that is a well-ordering. Remarkarble, isn’t it?

Once we have a well-ordered set, we can ask what the order-type of that ordering is? That is, we can categorize, up to (order-)isomorphism, each well-ordered set in the class of all well-ordered sets. An isomorphism in the realm of order theory is a bijection from one ordered set to another preserving their corresponding orderings. This way we get an equivalence relation on the class of well-orderings. That means we get equivalence classes. So each equivalence class is assigned a mathematical object called an ordinal number, and we call this ordinal number the order type of that well-ordering. Let’s look at some examples. I will use the symbol for the usual ordering.

1. has order type . So does .

2. has order type . Note: is the first infinite ordinal number.

3. has order type .

Now that the stage has been set up, here’s the problem!

Skolem (Skolem 1956) showed that the order type of the subset of generated by and using the operations addition, multiplication, and is a well-ordered subset of type . Here, is the least upper bound of the set of ordinals . Later, Levitz (Levitz 1975) showed that has a subset of order type ; namely the subset of containing and for all whenever are in that subset.

The above findings suggest that the order-type of is pretty complicated! To make things a little simpler, let’s look at a new problem. But before doing that, we’ll fix some notation. Given , let’s write to denote the order type of the set . That is, instead of looking at the order-type of the entire set , we’ll just look at the order-type of the segment determined by a given in . For example, if and , then we clearly see that is in . So it follows that .

I will now quickly introduce some terminology that we’ll use in the future.

I will end this post with the following two questions.

I will answer these two questions in the next post (hope to see your answers in the comments!). There’s plenty of exciting content to come—think fascinating insights into ordinal numbers, nonstandard analysis, surreal numbers, and more. Stay tuned! See you in the next post!