A Problem of Skolem - Part 01

Created in February 03, 2025

2025   ·   notes   ·   order-theory

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 $\mathbb{N}$ and $\mathbb{N}^>$ to denote the set of natural numbers and the set of non-zero natural numbers respectively.

Consider the set $\mathcal{S}$ of functions $f:\mathbb{N}\to \mathbb{N}$ which contains the constant function $\mathbf{1}$ and the identity function $\mathbf{x}$ and which is closed under addition, multiplication, and exponentiation. That is,

  1. $\mathbf{1} \in \mathcal{S}$
  2. $\mathbf{x} \in \mathcal{S}$
  3. If $f$ and $g$ are in $\mathcal{S}$ then so are $f+g$, $fg$, and $f^g$.

For example, the set of all non-zero polynomials are in $\mathcal{S}$, and so are the functions $\mathbf{x}^{\mathbf{x}^\mathbf{x}}$, $(3+5\mathbf{x})^{7\mathbf{x}^{\mathbf{x}^2}}$, etc. Of course, the mathematical operations here are done pointwise. Now that we have the set $\mathcal{S}$, a relation is introduced on it. Let's define it. Let $f, g \in \mathcal{S}$. Write $f \prec g$ if and only if there exists $n_0 \in \mathbb{N}$ such that for all $n \geq n_0$, we have $f(n) < g(n)$. This means that the function $g$ is eventually bigger than the function $f$; indeed, we say that $f$ is majorized or dominated by $g$. For example, $\mathbf{x} \prec \mathbf{x^2} \prec \mathbf{x^3}$ and so on. We will write $f \preceq g$ if $f \prec g$ or $f = g$ for each $f, g \in \mathcal{S}$.

Alright. We now have a set and a relation on it. What now? Well, by a result of Hardy's [1], and also, independently, by both Richardson \cite{richardson1969solution} and Tarski, it follows that $(\mathcal{S}, \prec)$ is a linearly ordered set. Is that the best we can say about this ordering? Ehrenfeucht [2] 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) [3] to prove that $(\mathcal{S}, \prec)$ is a well-ordering. Remarkable, 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 \textit{order type} of that well-ordering. Let's look at some examples. I will use the symbol $\leq$ for the usual ordering.

  1. $(\{0,1,2\}, \leq)$ has order type $3$. So does $(\{3,5,7\}, \leq)$.
  2. $(\mathbb{N}, \leq)$ has order type $\omega$. Note: $\omega$ is the first infinite ordinal number.
  3. $(\{0,1,2,3,\ldots,\omega\}, \leq)$ has order type $\omega + 1$.

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

Problem 1: What is the order type of $(\mathcal{S}, \prec)$?

Skolem [4] showed that the order type of the subset of $\mathcal{S}$ generated by $1$ and $\mathbf{x}$ using the operations addition, multiplication, and $g \mapsto \mathbf{x}^g$ is a well-ordered subset of type $\epsilon_0$. Here, $\epsilon_0$ is the least upper bound of the set of ordinals $\{\omega, \omega^{\omega}, \omega^{\omega^{\omega}}, \ldots\}$. Later, Levitz [5] showed that $\mathcal{S}$ has a subset of order type $\epsilon_0$; namely the subset of $\mathcal{S}$ containing $1$, $f+g$, $fg$, $\mathbf{x}^f$, and $n^f$ for all $n \in \mathbb{N}^>$ whenever $f, g$ are in that subset.

The above findings suggest that the order-type of $(\mathcal{S},\prec)$ 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 $f \in \mathcal{S}$, let's write $\mathcal{S}(f)$ to denote the order type of the set $\{ g\in \mathcal{S} : g \prec f \}$. That is, instead of looking at the order-type of the entire set $\mathcal{S}$, we'll just look at the order-type of the segment determined by a given $f$ in $\mathcal{S}$. For example, if $f\in \mathcal{S}$ and $f\prec \mathbf{x}$, then we clearly see that $f$ is in $\mathbb{N}^>$. So it follows that $\mathcal{S}(\mathbf{x})=\omega$.

Problem 2: Given a fixed $f\in \mathcal{S}$, what is $\mathcal{S}(f)$?

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

Definition 1: Let $f\in\mathcal{S}$.

  1. $f$ is an additive prime if $f$ cannot be written as $f=g+h$ with $g,h$ in $\mathcal{S}$.
  2. $f$ is a multiplicative prime if $f$ cannot be written as $f=gh$ where $g,h\neq 1$ are in $\mathcal{S}$.
  3. $f$ is an exponential prime if $f$ cannot be written as $f=g^h$ where $g,h\neq 1$ are in $\mathcal{S}$.

I will end this post with the following two questions.

Question 1: Determine all the functions $f\in \mathcal{S}$ that are primes according to all three definitions.

Question 2: Show that each $f\in \mathcal{S}$ can be written as $f=p_1+\cdots+p_k$ with $p_1,\ldots,p_k$ additive primes in $\mathcal{S}$ and $p_k\preceq\cdots\preceq p_1$ for some $k\in \mathbb{N}^>$.

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!

References

  1. Hurwitz, W.A., 1915. GH Hardy, Orders of Infinity. The “Infinitärcalcül” of Paul Du Bois-Reymond.
  2. Ehrenfeucht, A., 1973. Polynomial functions with exponentiation are well ordered. Algebra universalis, 3, pp.261-262.
  3. Kruskal, J.B., 1960. Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture. Transactions of the American Mathematical Society, 95(2), pp.210-225.
  4. Skolem, T., 1956. An ordered set of arithmetic functions representing the least $\epsilon$-number. Det Konigelige Norske Videnskabers Selskab Fordhandlinger, 29, pp.54-59.
  5. Levitz, H., 1975. An ordered set of arithmetic functions representing the least $\epsilon$-number. Mathematical Logic Quarterly, 21(1), pp.115-120.