\(\newcommand{\N}{\mathbb N}\)Consider the set \(\N^\N\) of all functions from \(\N\) to itself. We impose a partial order of eventual domination on this set: we say that \(f\) eventually dominates \(g\) if for large enough \(n\) we have \(f(n)< g(n)\). In this poset, we consider chains, in particular the well-ordered ones. One question we can ask is, how long can such chains be? Here we establish a lower bound \(\omega_2\) for the supremum of possible lengths.

All background necessary for this post is some basic knowledge about ordinals, in particular cofinalities.


The question above can be asked for arbitrary partial order – what is the supremum of lengths of well-ordered chains in a given poset? Before we tackle \(\N^\N\), let’s look at a few simpler ones, the ideas from resolution of which will be useful later.

Chains of rationals

If we consider the set of rational numbers with their standard ordering, the resolution is not too difficult – clearly no uncountable ordinal can be embedded in this order, so we get an upper bound \(\omega_1\) (it’s a nice exercise to show the same is true for the set of real numbers). This turns out to be the right answer, and to see that we have to show that any countable ordinal can be embedded in \(\mathbb Q\).

We proceed by transfinite induction, and we prove the following statement: For any countable ordinal \(\alpha\) and rational numbers \(a<b\), there is a subset of an open interval \((a,b)\) of length \(\alpha\).

Proof: This is obvious for \(\alpha=0\). Given a successor ordinal \(\alpha=\beta+1\), take some \(c\in (a,b)\) and a subset \(A\subseteq(a,c)\) of length \(\beta\), then \(A\cup\left\{c\right\}\subseteq(a,b)\) has length \(\alpha\).

If \(\alpha\) is a limit ordinal, it can be written as a countable sum \(\alpha_0+\alpha_1+\alpha_2+\dots\). Pick a sequence of rationals \(a=a_0<a_1<a_2<\dots<b\) (for example by taking successive midpoints) and subsets \(A_i\subseteq (a_i,a_{i+1})\) of length \(\alpha_i\). The union of these sets will have length \(\alpha\). Hence such a subset exists for all countable ordinals. \(\square\)

Mentioning the intervals in the statement might look a bit artificial, but it helps in the last step when “gluing together” the subsets; note that if we talked about arbitrary subsets, it would not be so clear how to add them.

Chains of computable functions

We now introduce the terminology properly. Consider two functions \(f,g:\N\to\N\). We say that \(f\) eventually dominates \(g\), denoted \(f>^*g\), if there is an \(n_0\) such that \(f(n)>g(n)\) for \(n\geq n_0\). This is a (strict) partial order on \(\N^\N\). In this poset we consider well-ordered chains, i.e. subsets of the form \(\{f_\beta:\beta<\alpha\}\) for some ordinal \(\alpha\) such that if \(\beta<\gamma\), then \(f_\beta<^*f_\gamma\). We call \(\alpha\) the length of this chain. The question is, what is the supremum of lengths of well-ordered chains?

The question which sparked these considerations dealt with computable functions, relating to the fast-growing hierarchy (FGH). Using FGH (or rather some variant which guarantees we get a chain) it’s not hard to show there are chains of length being any recursive ordinal, so the supremum is at least \(\omega_1^\mathrm{CK}\), the Church-Kleene ordinal. Given the context it’s a natural guess that this ordinal is the right answer, but it turns out that it’s not.

Indeed, the answer is the same as in the case of rationals, and for a good reason: we can find a subset of computable functions which is order-isomorphic to positive rationals. The embedding is simple: given a rational number \(q>0\), we take the function \(f_q(n)=\lfloor qn\rfloor\). Using the results of the previous section, we can find chains of any countable ordinal length. Since there are countably many computable functions, we can’t do any better, so \(\omega_1\) is the desired supremum.

(Short) chains of arbitrary functions

Using above arguments we can show that there are chains of any countable ordinal length in \(\N^\N\). However, for the first time we are are not constrained by the cardinality issues. Indeed, it is possible to embed all of \(\omega_1\) into this poset, for example using the fast-growing hierarchy (note that we need to agree on fundamental sequences for all countable limit ordinals, which will require some amount of choice, which is unfortunately unavoidable).

It’s not clear, however, how to continue. In order to embed \(\omega_1+1\), we need to construct a hierarchy like above, but making sure that there is another function which will eventually dominate the whole hierarchy, i.e. we need to construct a bounded hierarchy (note: here and below we require all bounds to be strict). While I’m not sure if this can be done with FGH itself, using a similar, just more careful, diagonalization it can be achieved.

Bounded chains of length \(\omega_1\)

When we construct a chain, going from one function to its successor is most easily achieved by simply adding \(1\). We wouldn’t like the new function to exceed the bound we have put on our hierarchy. For this reason we introduce a stricter relation between functions: we say that \(f\) properly dominates \(g\), denoted \(f>^pg\), if \(f\) eventually dominates \(g+k\) for any \(k\in\N\) (equivalently, \(f-g\) tends to infinity). It’s easy show that \(f>^pg\) is a necessary condition for existence of an infinite chain between \(f\) and \(g\), and it turns out to be sufficient for existence of not only infinite, but even uncountable chains.

The following result is a key to constructing bounded hierarchies:

Lemma: Let \(f_1<^*f_2<^*\dots\) be a countable chain of functions, all properly dominated by some function \(F\). There is a function \(g\) eventually dominating every \(f_k\) and properly dominated by \(F\).

Proof: By assumption, we can take, for every \(k\), an integer \(n_k\) such that, for \(n\geq n_k\), \(f_k(n)>f_i(n)\) for all \(i\leq k\) and \(f_k(n)+k< F(n)\). We may take \(\dots\). Define \[g(n)=\begin{cases} 0 & \text{for}\,n < n_1,\\ f_k(n) & \text{for}\,n_k\leq n<n_{k+1}.\end{cases}\] Now, if \(n\geq n_k\), then \(n_l\leq n<n_{l+1}\) for some \(l\geq k\), so we have \(g(n)=f_l(n)>f_k(n)\), so \(g>^*f_k\), and \(g(n)=f_l(n)< F(n)-l\leq F(n)-k\), so \(g+k<^*F\), hence \(F>^pg\). Thus \(g\) is our desired function. \(\square\)

We can now show not only that there are bounded chains of length \(\omega_1\), but there are such chains below any (sensible) such bound:

Proposition: If \(F>^p0\), then there is a chain under eventual domination of length \(\omega_1\) bounded by \(F\). Indeed, we can take this chain to be a chain under proper domination.

Proof: We construct this chain by transfinite recursion on \(\alpha<\omega_1\). Take \(f_0=0\). Given \(\alpha=\beta+1\), if we already have \(f_\beta\), let \(f_\alpha=f_\beta+1\). For \(\alpha\) a limit ordinal, take a sequence \(\alpha_1<\alpha_2<\dots\) converging to \(\alpha\) and apply the previous lemma to the sequence \(f_{\alpha_1}<^*f_{\alpha_2}<^*\dots\). We let \(f_\alpha\) be the resulting function \(g\). It follows immediately that this gives a chain of length \(\omega_1\) under eventual domination properly dominated by \(F\). For proper domination, take the above chain and consider \(f_{\omega\alpha},\alpha<\omega_1\). If \(\alpha>\beta\), then \(\alpha\geq \beta+1\), so \(\omega\alpha>\omega\beta+k\) for all \(k\in\N\), hence \(f_{\omega\alpha}>^*f_{\omega\beta+k}=f_{\omega\beta}+k\). This means \(f_{\omega\alpha}>^pf_{\omega\beta}\), so we get a chain under proper domination. \(\square\) Given \(f>^pg\), applying the proposition to the function \(f-g\) (let's say we take it equal to zero if the result would've been negative, which happens only finitely many times anyways), or just using a similar argument, we get: Corollary: If \(f>^pg\), there is a chain of length \(\omega_1\) under proper domination bounded between \(f\) and \(g\).

Construction of long chains

In this section we give the proof of the main result. The method bears a lot of resemblance to the construction of chains in the rationals.

Proposition: For any functions \(f<^pg\) and an ordinal \(\alpha<\omega_2\) there is a chain under eventual domination of length \(\alpha\) bounded between \(f\) and \(g\).

Proof: As usual, we proceed by induction on \(\alpha\). We note that every ordinal below \(\omega_2\) is either \(0\), a successor, or is limit of cofinality at most \(\omega_1\). The case \(\alpha=0\) is trivial. If \(\alpha=\beta+1\), then take a function \(h\) such that \(f<^ph<^pg\) (for example, \(h=\left\lfloor\frac{f+g}{2}\right\rfloor\)). There is a chain between \(f\) and \(h\) of length \(\beta\), and taking its union with \(\{h\}\) gives a desired chain of length \(\alpha\).

If \(\alpha\) is a limit ordinal, it can be written as a sum of \(\omega_1\) summands smaller than \(\alpha\) (we allow them to be zero, to account for cofinality \(\omega\)), say \(\alpha=\sum_{\gamma<\omega_1}\alpha_\gamma\). Using previous proposition, there is a chain \(\{f_\gamma:\gamma<\omega_1\}\) under proper domination bounded between \(f\) and \(g\). There is a chain \(A_\gamma\) of length \(\alpha_\gamma\) bounded between \(f_\gamma\) and \(f_{\gamma+1}\). Their union, \(A=\bigcup_{\gamma<\omega_1}A_\gamma\), is a chain bounded between \(f\) and \(g\) of length \(\alpha\). \(\square\)

Hence the supremum of lengths of well-ordered chains of functions is at least \(\omega_2\).

Possible extensions

\(\omega_2\) shown above is only a lower bound for this supremum, I do not claim it’s the precise value. However, we can say with certainty that it sometimes is tight – namely, when the continuum hypothesis holds. For under CH there clearly can’t be a chain of length \(\omega_2\) or longer, so the supremum must be exactly \(\omega_2\).

On the flipside, there are instances where this bound is not tight, for example if the bounding number is sufficiently large. Indeed, if \(\frak b>\aleph_2\) (which is consistent with ZFC, as \(\frak b\) can be any uncountable, regular cardinal), then any chain of length smaller than \(\omega_3\) can be extended.

The same argument shows that we can always find a chain of length \(\frak b\). This bound, however, is quite trivial. A friend of mine has suggested that it might be possible to reach \(\frak b^+\) (the next initial ordinal), i.e. every ordinal of cardinality \(\frak b\) is a length of a chain in \(\N^\N\). While we did not succeed at proving that (it’s not even clear how to reach \(\frak{b}+1\)!), I propose the following conjecture, which implies the supremum is at least \(\frak b^+\) by the reasoning similar to what I’ve described in this post:

Conjecture: If \(f>^p0\), then there is a chain bounded by \(f\) of length \(\frak b\).

Regarding upper bounds, the only one I know is a trivial one, namely \(\frak c^+\) (by cardinality reasons), and to the best of my knowledge this could always be the right answer. With this in mind, let me end the blog post with a

Question: Is it consistent that the supremum of well-ordered chains is smaller than \(\frak c^+\)?