An uncountable well-ordered subordering of asymptotic growth rates?

Question

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?

Answer 1

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

Answer 2

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.