Do operations generate well-ordered sets only?

Question

I've read   @TauMu's question   about the set of functions   $\mathbb N\rightarrow\mathbb N$   generated from the identity map by repeatedly applying exponentiation of two already accepted functions. @TauMu asks if such a set is well-ordered with respect to eventual domination.

It seems to me that it would be hard, perhaps impossible, to obtain a set which is not well-ordered regardless of the choice of a binary operation   $\mathbb N\times\mathbb N\rightarrow\mathbb N$.   Here is a patient formulation of my more general question:

Given an operation   $\tau : \mathbb N^2\rightarrow\mathbb N$,   let   $\bigcirc^{\tau}\subseteq\mathbb N^{\mathbb N}$   be the smallest set such that it has the identity map   $I_{\mathbb N}$   as its element,   $I_\mathbb N\in\bigcirc^\tau$,   and   $h:=\tau\circ(f\triangle g)\in\bigcirc^{\tau}$   for every   $f\ g\in\bigcirc^{\tau}$.

REMARK (an explanation of the notation above) $$\forall_{n\in\mathbb N}\quad h(n) := \tau(f(n)\ g(n))$$

Finally,

QUESTION (edited twice after the 1st and 2nd comment by @Joseph Van Name)   Does there exists an operation   $\tau:\mathbb N^2\rightarrow \mathbb N$   dominating the identity in each variable (see below), and such that   $\bigcirc^{\tau}$   contains an infinite strictly decreasing sequence with respect to the relation of eventual domination?

By   $\tau$   dominating the identity in each variable I mean that:

$$\forall_{k\ n\in\mathbb N}\quad \tau(k\ \ n)\ \ \ge\ \ \max(k\ \ \ n)$$

Answer 1

If we further require that the operation is nondecreasing in all arguments, the answer is negative. In fact, something more general holds:

Theorem: Let $L$ be a finite set of operations $f\colon\mathbb N^k\to\mathbb N$ (where the arity $k$ is finite, but not necessarily the same for all operations). Assume that every $f\in L$ is nondecreasing in each argument, and $f(n_1,\dots,n_k)\ge\max\{n_1,\dots,n_k\}$. Then the set $F$ of all functions $\mathbb N\to\mathbb N$ representable by a unary term over $L$ is well-quasi-ordered (hence well-founded) under domination (hence under eventual domination).

This is an easy consequence of Kruskal’s theorem for labelled ordered rooted trees. We can identify a unary $L$-term $t$ with a rooted tree whose vertices correspond to subterms of $t$, each non-leaf vertex is labelled with its head operation $f\in L$, and its children are ordered according to their order as arguments of $f$ in $t$. By Kruskal’s theorem, the set of such trees is a wqo under homeomorphic embedding, and a straightforward induction on the size of a term shows that if $t$ homeomorphically embeds into $t'$, and $h,h'\colon\mathbb N\to\mathbb N$ are the functions represented by $t,t'$, then $h(n)\le h'(n)$ for every $n\in\mathbb N$.

Let me stress that I’m answering the question as given in the body of the question. The title asks for well order, i.e., that additionally any two functions generated by the operation are comparable wrt eventual domination. This can easily fail: for example, take $$\tau(n,m)=n+m+[n\text{ even}],$$ where $[\dots]$ denotes the Iverson bracket. Then $\tau(\tau(n,n),n)=3n+[n\text{ odd}]$ and $\tau(n,\tau(n,n))=3n+2[n\text{ even}]$ do not eventually dominate each other. One way of ensuring that any two functions are comparable is to require all the operations to be restrictions to $\mathbb N$ of functions coming from an o-minimal expansion of the real field, see e.g. Real functions with finitely many zeroes . Note that this covers the motivating example of $\tau(n,m)=n^m$.

Answer 2

I think the following example shows that the extra condition (nondecreasing in all arguments) proposed in Emil Jeřábek´s answer is necessary.

Consider the operation $$\tau(m,n)=2 \max(m,n)^n -\min(m,n).$$ It is clear that $\tau(m,n) \geq \max(m,n)$. Now let $g_0=I_\mathbb{N}$, $g_{i+1}=\tau\circ(g_i \triangle g_0)$, $h=\tau\circ(g_1 \triangle g_1)$ and $f_i=\tau\circ(g_i \triangle h)$. Then $\{f_i: i \in \mathbb{N} \}$ is a strictly decreasing sequence with respect to eventual domination.