10
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Can't you just take $f(x,y)=\lfloor Log(x+1)\rfloor$? $\endgroup$ May 23, 2013 at 1:39
  • $\begingroup$ @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. $\endgroup$ May 23, 2013 at 1:44
  • 1
    $\begingroup$ 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. $\endgroup$ May 23, 2013 at 1:54
  • $\begingroup$ 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 :-) $\endgroup$ May 23, 2013 at 5:27

2 Answers 2

10
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ May 23, 2013 at 14:46
  • $\begingroup$ Yes, this was also pointed out by Joseph Van Name above. $\endgroup$ May 23, 2013 at 14:51
  • $\begingroup$ 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. $\endgroup$ May 23, 2013 at 18:44
4
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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). $\endgroup$ May 23, 2013 at 18:53
  • $\begingroup$ Next, $h = 2\cdot {g_1}^{g_1} - g_1 = (2\cdot {g_1}^{g_1-1}-1)\cdot g_1$. $\endgroup$ May 23, 2013 at 19:00
  • $\begingroup$ @Ramiro's $\tau$ is indeed decreasing where the smaller argument increases (until it reaches the greater one). $\endgroup$ May 23, 2013 at 19:07
  • $\begingroup$ @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. $\endgroup$ May 23, 2013 at 19:11
  • 1
    $\begingroup$ 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. $\endgroup$ May 23, 2013 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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