# An uncountable well-ordered subordering of asymptotic growth rates?

Define the following relation $\le$ between arithmetic functions $f$ and $g$ (mappings from $\mathbb{N} \rightarrow \mathbb{N}$):

$f \le g := \exists n_0, k: \forall n: n \gt n_0 \implies f(n) \lt k \cdot g(n)$

So for example we have $(n \rightarrow n) \lt (n \rightarrow n^2)$ and also $(n \rightarrow n + 1) \le (n \rightarrow n)$.

Does there exist an uncountable set of arithmetic functions that is well-ordered under this relation, assuming the axiom of choice?

• I assume that the functions are from $\Bbb N$ to itself? – Asaf Karagila Aug 10 '13 at 23:36
• You might want to add this to the question. – Asaf Karagila Aug 10 '13 at 23:38
• Also I understand that there is no such uncountable well-ordering for suborderings of $P(\mathbb{N})$ under inclusion, but I am not sure about this case. – Dan Brumleve Aug 10 '13 at 23:39
• Oh I thought that was implied by "arithmetic" I guess that doesn't constrain the range though... – Dan Brumleve Aug 10 '13 at 23:40
• Under $\subseteq$ it's easy to show that there is no uncountable well-ordered chain. Suppose $\cal C$ is a well ordered chain, map $C_{\alpha+1}$ to $\min C_{\alpha+1}\setminus C_\alpha$. It's easy to see there are only countably many successors and therefore $C$ is countable. Note, however, that your ordering is very different, and in fact it is a preorder rather than a partial order. – Asaf Karagila Aug 10 '13 at 23:41

## 2 Answers

$f_\alpha,$ where $\alpha$ ranges over $\omega_1$ the least uncountable ordinal, is such an uncountable sub-well-order under the following definition. Let $f_0$ be any computable function. Let $f_1$ be the Busy Beaver function, which grows strictly faster than any choice of $f_0.$

Now we proceed by transfinite induction. For $\alpha$ a successor ordinal, let $f_\alpha$ be a "super-Busy Beaver function" for Turing machines equipped with an oracle for $f_{\alpha-1}$. For $\alpha$ a limit ordinal, do the same thing but let your Turing machines have an oracle for all the $f_\beta,\beta<\alpha$.

Of course, this sequence grows much faster than necessary. It's no trouble to find $\omega^2$ levels in between each jump to a new oracle: before the first BB function, for instance, we could use $n,n^2,...,2^n,2^{n^2},...,2^{2^n},2^{2^{n^2}},...,...$. And we could get more by bringing in tetration, pentation, and the like...I think this'll do at least $\omega^\omega$. But since again there are only countably many computable functions we'll have to make uncountably many oracle jumps regardless.

• Can you spot the use of the axiom of choice in your answer? :-) – Asaf Karagila Aug 12 '13 at 20:10
• Ah, I was considering asking about that! I think AC must come up in my machines with oracles to countably many functions lower in the definition, but I don't see exactly how-I guess in needing to be able to compute the smaller ordinals in order to consult my oracle? – Kevin Carlson Aug 13 '13 at 2:47
• Well, one point I spot choice is where you do your transfinite induction. In order to end up with an $\omega_1$ sequence, you need to have "enough" choice functions. In particular, as I remarked in my answer, it is consistent that there are no $\aleph_1$ such functions, and in that case no such sequence can be defined (the induction will have to stop before $\omega_1$). – Asaf Karagila Aug 13 '13 at 3:25

Assuming the axiom of choice we can find a sequence of $\omega_1$ (infinite) sets of natural numbers $A_\alpha$ such that whenever $\alpha<\beta$ we have $|A_\alpha\setminus A_\beta|<\infty$. The axiom of choice is essential here, because it might be the case that there are no $\omega_1$ sets of integers (regardless to inclusion relation and whatnot).

Now let $f_\alpha(n)=0$ if $n\notin A_\alpha$ and $1$ otherwise. Then this sequence is $\leq$-increasing.

Easily we have $f_\alpha\leq f_\beta$ for $\alpha<\beta$, since for some $n_0$ we have $A_\alpha\setminus A_\beta\subseteq\{0,\ldots,n_0\}$. But on the other hand, given $k\in\Bbb N$ and $n>n_0$ we have that $f_\beta(n)<k\cdot f_\alpha(n)$ if and only if $n\in A_\alpha$. However there are infinitely many $n\in A_\beta\setminus A_\alpha$, so we don't have everywhere dominance.

• How do you show existence of the $A_\alpha$'s ? – Denis Aug 11 '13 at 0:14
• Asaf, you may want to add a few words about the bounding and dominating numbers. The study of these questions began very early on, actually, with Du Bois-Reymond, and was first developed seriously by Hausdorff. – Andrés E. Caicedo Aug 11 '13 at 0:19
• @dkuper: One example is a Hausdorff gap. – Asaf Karagila Aug 11 '13 at 0:34