Skip to main content
4 of 5
edited tags
Taras Banakh
  • 41.8k
  • 3
  • 74
  • 183

How many orders of infinity are there?

Define a growth function to be a monotone increasing function $F: {\bf N} \to {\bf N}$, thus for instance $n \mapsto n^2$, $n \mapsto 2^n$, $n \mapsto 2^{2^n}$ are examples of growth functions. Let's say that one growth function $F$ dominates another $G$ if one has $F(n) \geq G(n)$ for all $n$. (One could instead ask for eventual domination, in which one works with sufficiently large $n$ only, or asymptotic domination, in which one allows a multiplicative constant $C$, but it seems the answers to the questions below are basically the same in both cases, so I'll stick with the simpler formulation.)

Let's call a collection ${\mathcal F}$ of growth functions complete cofinal if every growth function is dominated by at least one growth function in ${\mathcal F}$.

Cantor's diagonalisation argument tells us that a cofinal set of growth functions cannot be countable. On the other hand, the set of all growth functions has the cardinality of the continuum. So, on the continuum hypothesis, a cofinal set of growth functions must necessarily have the cardinality of the continuum.

My first question is: what happens without the continuum hypothesis? Is it possible to have a cofinal set of growth functions of intermediate cardinality?

My second question is more vague: is there some simpler way to view the poset of growth functions under domination (or asymptotic domination) that makes it easier to answer questions like this? Ideally I would like to "control" this poset in some sense by some other, better understood object (e.g. the first uncountable ordinal, the nonstandard natural numbers, or the Stone-Cech compactification of the natural numbers).

EDIT: notation updated in view of responses.

Terry Tao
  • 114.1k
  • 33
  • 462
  • 539