86
$\begingroup$

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.

$\endgroup$
8
  • 10
    $\begingroup$ I'm pretty sure the correct terminology here would be cofinal. en.wikipedia.org/wiki/Cofinal_(mathematics) $\endgroup$ Jun 26, 2010 at 17:46
  • 4
    $\begingroup$ Let me mention Scott Aaronson post about growth functions scottaaronson.com/blog/?p=263 and a somewhat related MO question mathoverflow.net/questions/4347/… $\endgroup$
    – Gil Kalai
    Jun 26, 2010 at 18:26
  • 1
    $\begingroup$ I don't know if this helps you or not, but the posets $({}^\omega\omega,{\leq})$ and $({}^\omega\omega,{\leq^*})$ are very closely related to the compact and $\sigma$-compact subsets of Baire space, respectively. $\endgroup$ Jun 26, 2010 at 18:35
  • $\begingroup$ @Dorais: indeed the minimal covering number of the irrationals (Baire space) by compact sets. $\endgroup$ Jun 26, 2010 at 19:36
  • $\begingroup$ @Taras You really should stop adding the tag until there is agreement within the users. $\endgroup$ Mar 26, 2019 at 22:54

7 Answers 7

72
$\begingroup$

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.

$\endgroup$
0
29
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ @Joel Leave questions about foundations to the experts-this is why. Good response,Joel. Would love to have Blass chime in on this and see what insights he has. $\endgroup$ Jun 27, 2010 at 7:09
  • $\begingroup$ Thanks for the vote of confidence, Andrew, although there are several expert answers here, notably François' and Henno's. $\endgroup$ Jun 27, 2010 at 11:44
  • $\begingroup$ And of course Andreas's! (He had added his answer after I had posted my comment.) $\endgroup$ Jun 23, 2013 at 17:24
29
$\begingroup$

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.

$\endgroup$
17
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ In view of Bourbaki's treatment of orders of infinity (in Functions of a Real Variable), your domination order is defined w.r.t the filter of complements of finite subsets (called there Fréchet filter) which is strictly coarser than the filter of neighbourhoods of infinity. Is there any study comparing the cardinality results w.r.t. any filter ? $\endgroup$ Mar 6, 2015 at 10:01
9
$\begingroup$

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.

$\endgroup$
4
  • 6
    $\begingroup$ Could you provide any reference work that explores this idea further? $\endgroup$ Jun 27, 2010 at 12:07
  • $\begingroup$ This is the busy beaver function, and has an excellent Wikipedia article at en.wikipedia.org/wiki/Busy_beaver. $\endgroup$ May 23, 2013 at 5:15
  • $\begingroup$ Scott Aaronson also mentions it in "Who Can Name the Bigger Number"(scottaaronson.com/writings/bignumbers.html) $\endgroup$ May 23, 2013 at 5:22
  • 2
    $\begingroup$ There doesn't appear to be any evidence in those references supporting the claim in the answer that the resulting large-cardinal busy-beaver-like functions are cofinal in the computable functions. $\endgroup$ Sep 26, 2016 at 23:15
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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