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?

  • $\begingroup$ I assume that the functions are from $\Bbb N$ to itself? $\endgroup$ – Asaf Karagila Aug 10 '13 at 23:36
  • $\begingroup$ You might want to add this to the question. $\endgroup$ – Asaf Karagila Aug 10 '13 at 23:38
  • $\begingroup$ 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. $\endgroup$ – Dan Brumleve Aug 10 '13 at 23:39
  • 1
    $\begingroup$ Oh I thought that was implied by "arithmetic" I guess that doesn't constrain the range though... $\endgroup$ – Dan Brumleve Aug 10 '13 at 23:40
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Aug 10 '13 at 23:41

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

  • 2
    $\begingroup$ Can you spot the use of the axiom of choice in your answer? :-) $\endgroup$ – Asaf Karagila Aug 12 '13 at 20:10
  • $\begingroup$ 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? $\endgroup$ – Kevin Carlson Aug 13 '13 at 2:47
  • 1
    $\begingroup$ 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$). $\endgroup$ – 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.

  • $\begingroup$ How do you show existence of the $A_\alpha$'s ? $\endgroup$ – Denis Aug 11 '13 at 0:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Andrés E. Caicedo Aug 11 '13 at 0:19
  • $\begingroup$ @dkuper: One example is a Hausdorff gap. $\endgroup$ – Asaf Karagila Aug 11 '13 at 0:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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