Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
9  
I'm pretty sure the correct terminology here would be cofinal. en.wikipedia.org/wiki/Cofinal_(mathematics) –  Harry Gindi Jun 26 '10 at 17:46
1  
Thanks for the correction! –  Terry Tao Jun 26 '10 at 17:58
4  
Let me mention Scott Aaronson post about growth functions scottaaronson.com/blog/?p=263 and a somewhat related MO question mathoverflow.net/questions/4347/… –  Gil Kalai Jun 26 '10 at 18:26
1  
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. –  François G. Dorais Jun 26 '10 at 18:35
    
@Dorais: indeed the minimal covering number of the irrationals (Baire space) by compact sets. –  Henno Brandsma Jun 26 '10 at 19:36

6 Answers 6

up vote 46 down vote accepted

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.

share|improve this answer
3  
Excellent answer! –  Gil Kalai Jun 26 '10 at 18:23

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.

share|improve this answer
    
@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. –  Andrew L Jun 27 '10 at 7:09
    
Thanks for the vote of confidence, Andrew, although there are several expert answers here, notably François' and Henno's. –  Joel David Hamkins Jun 27 '10 at 11:44
    
And of course Andreas's! (He had added his answer after I had posted my comment.) –  Joel David Hamkins Jun 23 '13 at 17:24

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
6  
Could you provide any reference work that explores this idea further? –  Joel David Hamkins Jun 27 '10 at 12:07
    
This is the busy beaver function, and has an excellent Wikipedia article at en.wikipedia.org/wiki/Busy_beaver. –  Eric Tressler May 23 '13 at 5:15
    
Scott Aaronson also mentions it in "Who Can Name the Bigger Number"(scottaaronson.com/writings/bignumbers.html) –  Eric Tressler May 23 '13 at 5:22

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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