Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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))$$


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)$$

share|improve this question
Can't you just take $f(x,y)=\lfloor Log(x+1)\rfloor$? –  Joseph Van Name May 23 '13 at 1:39
@Joseph: you're right! I need to reformulate my question. I still believe that under very general assumptions one still not get qa decreasing sequence. –  Wlodzimierz Holsztynski May 23 '13 at 1:44
You will need a bit more than being non-decreasing in each variable since $\lfloor Log(x+1)\rfloor$ is non-decreasing in each variable. –  Joseph Van Name May 23 '13 at 1:54
Thank you, @Joseph--I am persistently and stubbornly blind. I'll modify my question again. I hope that this time it will be finally fine :-) –  Wlodzimierz Holsztynski May 23 '13 at 5:27

2 Answers 2

up vote 10 down vote accepted

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$.

share|improve this answer
If you remove the inequality restriction in your Theorem statement, you can get some non well ordered sequences for some choices of f, e.g. floor of log of x+y+1 or a suitable modification thereof. Gerhard "Ask Me About Growing Slow" Paseman, 2013.05.23 –  Gerhard Paseman May 23 '13 at 14:46
Yes, this was also pointed out by Joseph Van Name above. –  Emil Jeřábek May 23 '13 at 14:51
Thank you, @Emil. It's a big jump (restriction) from more or less arbitrary operations to operations which are non-decreasing in each variable. I thought that it is more interesting for the purpose of a discussion not to assume right away in my question the monotone property. On the other hand, general operations form a jungle, as indicated by your and @Ramiro answers. –  Wlodzimierz Holsztynski May 23 '13 at 18:44

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.

share|improve this answer
Thank you @Ramiro. I appreciate your brief style, it sets a homework for me. The first step is to see explicitly that $g_1(n) = \tau(n\ n) = 2\cdot n^n-n = (2\cdot n^{n-1}-1)\cdot n$. (I don't know yet which form of $g_1$ is going to be the most useful). –  Wlodzimierz Holsztynski May 23 '13 at 18:53
Next, $h = 2\cdot {g_1}^{g_1} - g_1 = (2\cdot {g_1}^{g_1-1}-1)\cdot g_1$. –  Wlodzimierz Holsztynski May 23 '13 at 19:00
@Ramiro's $\tau$ is indeed decreasing where the smaller argument increases (until it reaches the greater one). –  Wlodzimierz Holsztynski May 23 '13 at 19:07
@Ramiro, your example is to me hard work :-) The example looks reasonable, I'll try to work on it still more, while now I'll up-vote your answer. –  Wlodzimierz Holsztynski May 23 '13 at 19:11
I also found the exercise nonobvious, but the point is basically that the $g_i$ functions are $n^{\Theta(n^i)}$ so that they form an increasing chain, while $h(n)=n^{\Theta(n^n)}$ grows faster than any of them, which makes $\tau(g_i,h)=2h(n)^{h(n)}-g_i(n)$ a decreasing chain. –  Emil Jeřábek May 23 '13 at 19:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.