Skip to main content
1 of 5
Terry Tao
  • 114.1k
  • 33
  • 462
  • 539

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 asymptotic domination, in which one works with sufficiently large $n$ only, 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 if every growth function is dominated by at least one growth function in ${\mathcal F}$. (There may be a better terminology to use here; I am making this one up.)

Cantor's diagonalisation argument tells us that a complete 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 complete 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 complete 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?

Terry Tao
  • 114.1k
  • 33
  • 462
  • 539