# How this set of functions is ordered?

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.

-
I think it's obvious what would count as a nontrivial upper bound, but what counts as a nontrivial lower bound? – Harry Altman Dec 3 '11 at 21:26
Harry, I would think that for a lower bound of $\alpha$ Vladimir would simply want us to exhibit a collection of functions having order type $\alpha$ under eventual domination. And the bigger the $\alpha$, the more nontrivial the bound. – Joel David Hamkins Dec 3 '11 at 23:49
Hm... the obvious way to contradict well-ordering would be to construct the predecessor function, but this is impossible; for any $f\in S$, $\mathbb{N}$ can be split into two sets A and B such that f is bounded on A and satisfies $f(n)\ge n$ on B. (Omitting proof because once you think to make the statement, it's straightforward.) – Harry Altman Dec 4 '11 at 0:51
Yikes -- not certain my proof of the above comment is correct, or that the comment is correct. Same applies where I stated the same in my answer below, of course. Of course, since I've since solved the problem (as stated), it's kind of irrelevant... – Harry Altman Dec 7 '11 at 21:18

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≤n≤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≤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≥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≤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≤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≥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.

-
Do you get examples like this if you take $\mathbb N = \{1,2,3,\dots\}$ and make appropriate changes? – Gerald Edgar Dec 3 '11 at 23:52
@Gerald: Depends on what you mean by "like this". Making that change definitely does get rid of this sort of boolean test function: You can prove that if 0 is excluded from $\mathbb{N}$, any function f in the new S has to either: 1. be constant 2. be the identity function or 3. satisfy f(n)≥n+1 for all n. So the direct analogs of these are impossible. But perhaps it would be possible to accomplish a "piecewise" function in some weirder way? Seems unlikely but I don't know how you'd rule that out. – Harry Altman Dec 4 '11 at 22:21
@Gerald: Also in that case they would have to be monotonic -- in fact, either constant or strictly monotonic -- so that would make things harder too. Makes it seem very unlikely. – Harry Altman Dec 4 '11 at 22:38