How this set of functions is ordered?

Question

Notation:

• $k, m, n$ are non-negative integers
• $f, g, h$ are functions $\mathbb{N} \to \mathbb{N}$
• $f^k$ is $k$-th iterate of the function $f$: $f^0(n)=n, f^{k+1}(n)=f^k(f(n))$
• $f \prec g$ means eventual domination: $\exists_m \forall_{n>m} f(n) < g(n)$.

Let $S$ be the minimal set of functions $\mathbb{N} \to \mathbb{N}$ such that

• $n \mapsto 0, n \mapsto 1, n \mapsto n, n \mapsto n+1 \in S$, and
• If $f, g, h \in S$ then $n \mapsto f^{g(n)}(h(n)) \in S$.

Is $S$ well-ordered by $\prec$? If yes, then what is the corresponding ordinal? Otherwise, what is the supremum of ordinals corresponding to well-ordered subsets of $S$? Can you suggest an algorithm implementing $\prec$?

Update: nontrivial lower and upper bounds on the ordinal would be also appreciated.

Answer 1

Here is a trivial way in which it is not well-ordered: the ordering used is not total (we have a preorder, rather than a total order). This is because we can construct a function $Z(n)$ given by $Z(0)=1$ and $Z(n)=0$ for $n>0$. Simply take, in the combination law, $f(n)=0$, $g(n)=n$, and $h(n)=1$. Then $Z$ and $0$ are distinct but equivalent.

Edit: Actually, here's a further (but more problematic) way in which it's not totally-ordered. We can construct $E(n)$ where $E(n)=0$ if $n$ is even and $E(n)=1$ if $n$ is odd. Simply take, in the combination law, $f=Z$, $g(n)=n$, and $h(n)=0$. If we instead take $h(n)=1$, we get $D(n)$ where $D(n)=1$ if $n$ is even and $E(n)=0$ if $n$ is odd. But then neither of $E$ and $D$ eventually dominates the other, in the stronger sense that they are not eventually equal, either.

So even if we take equivalence classes (two functions being equivalent if they're eventually equal), we will still only have a partial order. I suppose we could ask if it's a well-founded partial order... (it's certainly not a well-partial order in the stronger sense of that term, I will post a proof here later).

Edit again: OK, here is an example of an infinite antichain. Note that this still might be a well-founded partial order. (Later: It isn't, see below.)

I will show that all periodic functions are in $S$; then for primes $p$, we can take $E_p(n)=1$ if $p\mid n$ and $E(n)=0$ otherwise, and these will form an infinite antichain. I will do this by inductively showing that for any $m\ge 1$, all functions of period $m$ are in $S$.

First observe that $S$ is closed under pointwise addition, since given $g,h\in S$ we can apply the combination law with $f(n)=n+1$ and the given $g$ and $h$. Thus all constant functions are in $S$ and so the case $m=1$ is proved. So suppose it is true for $m$, and we want to prove it for $m+1$.

Again, since $S$ is closed under pointwise addition, it suffices to construct each of the functions $E_{m+1,k}$ given by $E_{m+1,k}(n)=1$ if $n\equiv k \pmod{m+1}$ and $E_{m+1,k}(n)=0$ otherwise. Actually, it suffices to construct a function $M$ such that:

1. $M$ is periodic with period $m+1$
2. There is a unique congruence class $a$ mod $m+1$ which is mapped to $0$ by $M$.

Once we have this, since $S$ is closed under compostion (take $g=1$ in the combination law), and contains all functions of the form $n\mapsto n+k$ (either by addition or composition), we can make $E_{m+1,a-k}$ by taking $E_{m+1,a-k}(n)=Z(M(n+k))$.

It remains to construct $M$. By the inductive hypothesis, we may construct $L$ given by $L(n)=(n-1) \bmod{m}$. Then we can construct $L'$ given by $L'(n)=L(n)$ for $n>0$ and $L(0)=m$ by taking $f(n)=m$, $g=Z$, and $h=L$ in the combination law. Now we just take $f=L'$, $g(n)=n$, $h=0$ in the combination law to get $M$: $L'(0)=m$, and for $0\lt n\le m$, $L'(n)=n-1$, meaning that iterating $L'$ starting from $0$ yields an $m+1$-cycle, with $1$ serving the role of $a$ above.

Section below updated to now include an explicit construction

Edit yet again: Using the above and a similar construction, you can also get that eventually periodic functions are in $S$, and using that, you can get that taking a function in $S$ and modifying it at only finitely many places yields another function in $S$ (just take, in the combination law, $h$ is your old function, $f$ is a function containing your replacement values at the appropriate spots, and $g$ is a function that is $1$ on the appropriate spots and $0$ elsewhere).

Proof: It suffices to show that for each $k$, the function $Z_k$ given by $Z_k(n)=1$ if $n=k$ and $Z_k(n)=0$ otherwise lies in $S$. So take a periodic function $J$ such that $J(0)=k+1$, $J(n)=n-1$ for $1\le n\le k$, and $J(k+1)=k+1$. Then construct $Y(n)$ by taking in the combination law, $f=J$, $g(n)=n$, and $h(n)=k$. Then for $n\le k$, $Y(n)=n-k$, and for $n>k$, $Y(n)=k+1$. In particular, $Y(n)=0$ iff $n=k$, so we can take $Z_k=Z\circ Y\in S$.

Actually, the above provides an example of -- well, it's not actually an infinite descending sequence in the order he actually defined, but it is an infinite descending sequence in the obvious nonstrict modification (which is what I have really been implicitly using all along -- otherwise the distinction between "equivalent" and "incomparable" doesn't really make sense!). Simply take $E_m$ as above and observe that $E_{2^{k+1}}\lt E_{2^k}$. Of course, this is a slightly different notion of "less than", so the question of whether one can find an infinite descending sequence with the original notion of "less than" remains unanswered.

Final edit: Here I will construct an infinite descending sequence that works even with Vladimir's original, stricter, ordering, showing that it does not, in any way, well-order this set. (However, it seems to me to be plausible that Vladimir's idea is correct if $0$ is excluded from $\mathbb{N}$; as Gerald points out, everything I'm doing is based around trickery with $0$, and indeed you can prove that in the absence of zero, every function constructible this way must be either constant, the identity, or strictly monotonic and satisfing $f(n)\gt n$.)

I will show that for all $k\ge 1$, the function $F_k(n)=\max(0,2(n-k))$ lies in S. (Of course, we already know it's in $S$ for $k\le 0$ by other means!) Then $F_1 \succ F_2 \succ \ldots$ forms an infinite descending chain. First, define $A_k(n)$ by $A_k(n)=0$ if $n=2k-1$ and $A_k(n)=n+2$ otherwise; then $A_k\in S$ by applying the combination rule with $f(n)=0$, $g=Z_{2k+1}$, and $h(n)=n+2$ (since $n=2k-1$ iff $n+2=2k+1$). Then construct a function $G_k(n)$ by applying the combination rule with $f=A_k$, $g(n)=n$, and $h(n)=1$. Then for $n\le k-1$, $G_k(n)=2n+1$, $G_k(k-1)=2k+1$, $G_k(k)=0$, and $G_k(n)=2(n-k)$ for $n\ge k$. This is really enough, but for completeness, define $E'(n)=n$ for n even and $E'(n)=0$ for n odd; this lies in $S$ by applying the combination rule with $f(n)=0$, $g=D$ from above, and $h(n)=n$. Then $F_k=E'\circ G_k\in S$, and we are done.

And now I really better not edit this anymore or I think it'll become CW! But I think I've answered the $0$-included case pretty thoroughly now; if I figure out anything about the case when $0$ is excluded, I'll make that a separate answer.

(Edit many years later: Now that automatic CW is no longer a thing, I'm going back and editing this post to be slightly more readable. :) )

Answer 2

So I wanted to return to this and add another answer about some of what happens when we exclude $0$ from the natural numbers (and $n\mapsto 0$ from the starting functions).

In this case, this set of functions, ordered under $\preceq$, is in fact a well-quasi-order! I don't know how to show it's a total order, which would require showing both antisymmetry and totality. But we can show it's at least a well-quasi-order, and get an upper bound on its maximum linearization, aka type (which if it is well-ordered would then be a bound on its order type), without a lot of difficulty, by applying Kruskal's tree theorem and the habilitation thesis of Diana Schmidt.

Specifically, we can think of function specifications here as being encoded by ternary trees; each vertex either has degree 3 or degree 0, the degree 3 leaves are unlabeled, and the degree 0 leaves are labeled with one of $1$, $\mathrm{id}$, or $S$. Actually, to make the argument work, we'll allow labeling leaves with any constant, not just $1$; I'm hopeful there's a way to make it work without that, but at the moment I don't see how to. I'll order the labels by $\preceq$, so they form an $\omega+2$.

We then want to, using the order on trees from Kruskal's tree theorem, map this set of trees onto this set of functions in a monotonic way. If we can do so, then the set of functions will be a well-quasi-order, and its type will be at most that of our set of trees. The type of the latter, meanwhile, can be upper bounded using Schmidt's thesis. Specifically -- just applying the results directly in the most naïve way -- we get an upper bound of $f^+ \left(\begin{array}{cc}\omega+2 & 1 \\0 & 3\end{array}\right)$ (in Klammersymbol notation), which I think offhand is equal to the ordinal $\phi_{1,0,0}(\omega+2)$ but I'm doing this quickly so I'm not certain of that. In reality I suspect this bound is overly large and one can do better, but I'm going with the easy bound for now!

The problem, of course, is showing that the mapping is monotonic -- and this is a problem because in fact it isn't. However, we can restrict to a subset on which it is, and which will still get us all of our functions. I claim that we can do that in a way that makes the restricted mapping monotonic.

In order to verify this, we'll first need to prove some basic facts about the functions we can get. Specifically:

1. Every function we in this set is monotonic.
2. Every function in this set is either constant, or satisfies $f(n)\ge n$ everywhere. Moreover, in the second case, either $f$ is the identity, or it satisfies $f(n)>n$ everywhere.

Both these statements are of course true of our starting functions $1$ (or any constant), $\mathrm{id}$, and $S$. Now, if we have three such functions in our set $f$, $g$, and $h$, we can check that they're true for $x\mapsto f^{g(x)}(h(x))$.

Specifically: If $f$ is constant, then (because $g(x)\ge 1$!) we just get $f$ back, so we get back a constant, which satisfies both constraints. So assume $f(n)\ge n$. Then, since $f$ is monotonic, $h$ is monotonic, and $g$ is monotonic and $f(n)\ge n$, we can conclude that our new function is monotonic. Now we need to check the second constraint.

We get the following cases:

1. $f$ is constant -- already checked above, we get back $f$ (using the fact that $g(n)\ge 1$).
2. $g$ and $h$ both constant -- we get another constant.
3. $f=\mathrm{id}$, $h$ is constant -- we get back $h$, again a constant.
4. $f(n)>n$, $g(n)\ge n$ -- Since $f$ is monotonic, if we use the fact that $h(n)\ge 1$, we get $f^{g(n)}(h(n))\ge S^n(1)=n+1>n$.
5. $f(n)\ge n$, $h(n)\ge n$ -- Since $f$ is monotonic, we get $f^{g(n)}(h(n))\ge n$. If $f=h=\mathrm{id}$ we get the identity function; if either $f(n)>n$ or $h(n)>n$ we get $f^{g(n)}(h(n))>n$.

You can check that these are exhaustive, and that therefore the two constraints above always hold.

OK! So now let's restrict our construction by disallowing the following cases:

1. $f$ is a constant. In this case we just get back $f$, which we already had.
2. $f$ is the identity. In this case we just get back $h$, which we already had.
3. $g$ and $h$ are constants. In this case we will just get back another constant, though it may be different from $g$ and $h$. This case is why I allowed arbitrary constants... if we only have $1$, and we bar this case, we can't make any other constants!

So these restrictions haven't cost us any surjectivity. And, I claim, we make our map monotonic!

So, let's check the monotonicity of our map. There are two things we have to check. The first is that replacing $f$, $g$, or $h$ by a larger function (under $\preceq$) will make our function larger (under $\preceq$). This holds without any restrictions. For $h$ this holds because $f$ is monotonic; for $g$ this holds because $f$ is monotonic and $f(n)\ge n$ (and if we allow $f$ constant, it still holds because we just get $f$); and for $f$ this holds because $h$ is monotonic and all our allowed $f$ are monotonic as well.

The more problematic thing is that we need to check that $f^{g(x)}(h(x))\succeq f, g, h$. But our restrictions will make this true.

First off, since $f(n)\ge n$, $f$ is monotonic, and $g(n)\ge 1$, we see that $f^{g(x)}(h(x))\ge h(x)$. Also, since $h(n)\ge 1$ and $f(n)>n$, we have $f^{g(n)}(h(n))\ge S^{g(n)}(1)=g(n)+1>g(n)$.

Finally we need to check that $f^{g(x)}(h(x))\succeq f$. Since $g$ and $h$ are not both constant, either $h(n)\ge n$, or $g(n)\ge n$. If $h(n)\ge n$, then the claim follows by the monotonicity of $h$ and $f$ (and the fact that $g(n)\ge 1$). If $g(n)\ge n$, meanwhile, then (applying monotonicity of $f$, etc) $f^{g(n)}(h(n))\ge f^n(1)$, so it suffices to show that $f^n(1)\ge f(n)$. But $f^n(1) = f(f^{n-1}(1)) \ge f(S^{n-1}(1)) = f(n)$, as required.

That completes the proof.

So:

1. This set of functions is at least well-quasi-ordered under $\preceq$; whether it is antisymmetric or total I do not know, but it is at least well-quasi-ordered.
2. The type (maximum linearization), and therefore the order type if it is well-ordered, is at most $f^+ \left(\begin{array}{cc}\omega+2 & 1 \\0 & 3\end{array}\right)$; this is probably a substantial overestimate, but I prioritized putting someting up here rather than optimizing the bound.

I realize this is many years later, but I hope this is helpful! :)