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.



How this set of functions is ordered?
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. :) )


