How many orders of infinity are there?

Question

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.

Answer 1

For asymptotic domination, commonly denoted ${\leq^*}$ and often called eventual domination, this has been answered by Stephen Hechler, On the existence of certain cofinal subsets of ${}^{\omega }\omega$, MR360266. What you call a complete set is usually called a dominating family.

As a poset under eventual domination, a dominating family $\mathcal{F}$ must have the following three properties:

1. $\mathcal{F}$ has no maximal element.
2. Every countable subset of $\mathcal{F}$ has an upper bound in $\mathcal{F}$.
3. $|\mathcal{F}| \leq 2^{\aleph_0}$

Hechler showed that for any abstract poset $(P,{\leq})$ with these three properties, there is a forcing extension where all cardinals and cardinal powers are preserved, and there is a dominating family isomorphic to $(P,{\leq})$.

In particular, one can have a wellordered dominating family whose length is any cardinal $\delta$ with uncountable cofinality. In this case, the restriction $\delta \leq 2^{\aleph_0}$ is inessential since one can always add $\delta$ Cohen reals without affecting conditions (1) and (2). However, for arbitrary posets, condition (2) could be destroyed by adding reals.

The total domination order is more complex. One can always get a totally dominating family $\mathcal{F}'$ from a dominating family $\mathcal{F}$ by adding $\max(f,n) \in \mathcal{F}'$ for every $f \in \mathcal{F}$ and $n < \omega$. Since $\mathcal{F}$ is infinite, the resulting family $\mathcal{F}'$ has the same size as $\mathcal{F}$. Howerver, there does not appear to be a simple combinatorial characterization of the possibilities for the posets that arise in this way.

Answer 2

François has given an excellent answer to this question.

What you call a cofinal collection, a family $\cal F$ such that every function is dominated by a function in $\cal F$, is known as a dominating family. This is different, for example, from the similar concept of an unbounded family, a family $\cal F$ such that no function dominates every function in $\cal F$, since in partial orders as opposed to linear orders the notions of dominating and unbounded are not the same. As there are several inequivalent but similar-sounding notions here, it seems worthwhile to use the established terminology.

As Kristal mentions, I mention in this MO answer, which is also a direct answer to this question, that the dominating number d is the size of the smallest dominating family of function, the smallest family of functions such that every function is dominated by something in the family. As you point out, this number is always uncountable and at most the continuum, but as François mentioned, the particular value of d can be exactly controlled by forcing. In particular, it can achieve desired intermediate values, when CH fails.

The similar-sounding but actually inequivalent bounding number b, in contrast, is the size of the smallest unbounded family $\cal F$, a family such that no function dominates every function in $\cal F$. Since every dominating family is unbounded, it follows that b $\leq$ d. Remarkably, however, it is consistent that b $\lt$ d, and this is proved again by forcing.

There are dozens of other similar cardinal characteristics of the continuum, some of which I mention in this MO answer. For examples, researchers consider the additivity of the Lebesgue-measure, the additivity of the meager ideal, the cofinality of the symmetric group $S_\omega$ (the smallest number of proper subgroups forming a chain whose union is the whole group), the covering number (fewest number of measure zero sets to cover the reals) and variations, and so on. Researchers in this area classify and separate these different cardinals into hierarchies, and some prominent relationships are expressed by Cichon's diagram. It is often particularly desired to control some of the cardinal characteristics by forcing, while leaving others fixed, and some of the most valuable results here are general theorems that make such a conclusion. Andreas Blass, now here on MO, is one of the world experts in this area.

Answer 3

Francois Dorais cited the paper of Stephen Hechler that (more than) completely answers the first part of the question. For the second part, concerning other ways to view $\mathfrak d$, two other papers of Hechler are relevant; here are the MathSciNet citations:

MR0369078 (51 #5314) Hechler, Stephen H., A dozen small uncountable cardinals. TOPO 72---general topology and its applications (Proc. Second Pittsburgh Internat. Conf., Pittsburgh, Pa., 1972; dedicated to the memory of Johannes H. de Groot), pp. 207--218. Lecture Notes in Math., Vol. 378, Springer, Berlin, 1974.

MR0380705 (52 #1602) Hechler, Stephen H., On a ubiquitous cardinal. Proc. Amer. Math. Soc. 52 (1975), 348--352.

Four (if I remember correctly) of the 12 cardinals in the first paper turn out to equal $\mathfrak d$, which is also the "ubiquitous cardinal" of the second paper.

Let me also mention that, if one just wants to answer the first part of the question, one doesn't need the very detailed information given by Hechler's theorem. In order to get a model of set theory with prescribed values for $\mathfrak d$ and for the cardinality $\mathfrak c$ of the continuum (subject to the necessary restrictions that both have uncountable cofinality and that $\mathfrak d\leq\mathfrak c$), it suffices to start with a model of the generalized continuum hypothesis (e.g., G\"odel's constructible universe), adjoin as many Cohen reals as the cardinal you want to be $\mathfrak d$, and then adjoin enough random reals to bring $\mathfrak c$ up to the desired value.

The forcing method introduced by Hechler in the paper that Francois cited has become one of the standard tools in the study of cardinal characteristics of the continuum. For just one example, see

MR0780528 (86i:03064) Baumgartner, James E.; Dordal, Peter, Adjoining dominating functions. J. Symbolic Logic 50 (1985), no. 1, 94--101.

Finally, let me indulge in a bit of self-promotion. On the set theory page of my web site,

http://www.math.lsa.umich.edu/~ablass/set.html ,

the first two papers are about cardinal characteristics of the continuum. The first is a short (6 pages), general-audience introduction (based on a talk at a conference for Ryll-Nardzewski's 70th birthday), and the second is a long chapter which (contrary to the "to appear" on the web site) has now appeared in the Handbook of Set Theory.

Answer 4

Yes, this is possible, if you define the order to be dominance with finitely many exceptions. So f < g iff the set of n with f(n) > g(n) is finite. What you call a complete system of growth functions is called a dominating subset of $\omega^\omega$ (and a scale if it is well-ordered). See van Douwen's paper "The integers and topology" in the Handbook of Set Theoretic Topology. The minimal cardinality of such a dominating family is called $\mathfrak{d}$ in the set-theoretic literature and it's one of the so-called cardinal invariants of the continuum. What is known is that its cofinality is at least $\mathfrak{b}$ where the latter is the minimal size of an unbounded set in $\omega^\omega$ in the partial order of eventual dominance. Also, $\mathfrak{d}$ is equal to the minimal size of a cofinal subset of $\omega^\omega$ in the total dominance order that you defined. So indeed, the problem is the same for both orders, and both have minimal size $\mathfrak{d}$. The eventual dominance is more commonly used though, and that's how I knew it at first.

This cardinal can assume almost any value (under said restriction on the cofinality at least) and there has been a lot of study on this and similar cardinal invariants and their interrelations. We can have $\omega_1 = \mathfrak{d} < \mathfrak{c}$, $\omega_1 < \mathfrak{d} < \mathfrak{c}$ and $\omega_1 < \mathfrak{d} = \mathfrak{c}$, in different models of ZFC.

Answer 5

If instead of looking at all functions you just look at the computable ones, then in some sense you can find a cofinal subset corresponding to large cardinal axioms. The idea is roughly that if you have a large cardinal axiom you can define a computable fast growing function f as follows. Take all Turing machines of size at most n such that ZFC with the large cardinal axiom can prove in less than n symbols that the Truing machine eventually halts. Then f(n) is the maximum number of steps it takes any of these machines to halt.

Answer 6

I think that there is a complete set of growth functions of intermediate cardinality. This is based a earlier discussion on a related subject here. In particular Joel David Hamkins answer seems to answer the question in the affirmative.

Answer 7

I would like to make two points addressing the topological aspect of the OP by Terence Tao. The cardinals $\frak b$ and $\frak d$, although defined "arithmetically," are in fact equivalent to some incompleteness parameters of the Boolean Algebra $P (\omega) / fin$, equivalently of the space $\omega^* = \beta\omega \setminus \omega$.

1A) Indeed: $\frak b$ is the smallest cardinal of a family $\mathcal B$ of clopen subsets of $\omega^*$ such that, for some countable family $\mathcal A$ "disjointed" from $\mathcal B$ (and this means that for all $A$ in $\mathcal A$ and all $B$ in $\mathcal B$ the meet $A \wedge B = 0$), $\mathcal A$ and $\mathcal B$ cannot be separated by a clopen set. This is well-defined because $P (\omega) / fin$ is not countably complete, i.e. countable subsets need not have the least upper bound.

On the other hand, it is well-known that $P (\omega) / fin$ possesses the so called the du Bois-Reymond separation property (this means that disjointed $\mathcal B$, $\mathcal A$ can be separated when both families are countable). A compact space with this property is called an $F$-space (even if it is not Boolean, i.e. zero-dimensional), and the Boolean Algebra is called (by Eric van Douwen) weakly countably complete.

1B) Now, regarding the cardinal $\frak d$, which is our main concern: $\frak d$ is the smallest cardinal for a $\mathcal B$ so that, for some countable $\mathcal A$ disjointed from $\mathcal B$, $\mathcal A$ and $\mathcal B$ cannot be "weakly left-separated." This means that there is no clopen set $C$ such that $\forall \ A \in \mathcal A$, $A \leq C$ and $\forall \ B \in \mathcal B$, $B - C \neq 0$.

These facts are, practically, obvious (so that I could not find a formal reference even in the excellent monograph of Andreas Blass he mentions in his answer).

2) My second remark is that the $\frak b$ and $\frak d$ so re-defined for $P (\omega) / fin$ are (despite their "arithmetical" origin) perfectly applicable to any Boolean Algebra/Boolean space which is not countably complete, and that they measure the rough cardinal degree of such an incompleteness.

(3) I also have some mild puzzlement about the a-symmetricity in the (revised) definition of $\frak d$.