How many orders of infinity are there? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T20:59:00Z http://mathoverflow.net/feeds/question/29624 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29624/how-many-orders-of-infinity-are-there How many orders of infinity are there? Terry Tao 2010-06-26T17:40:55Z 2013-05-19T21:19:16Z <p>Define a <em>growth function</em> 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$ <em>dominates</em> another $G$ if one has $F(n) \geq G(n)$ for all $n$. (One could instead ask for <em>eventual domination</em>, in which one works with sufficiently large $n$ only, or <em>asymptotic domination</em>, 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.) </p> <p>Let's call a collection ${\mathcal F}$ of growth functions <strike>complete</strike> <em>cofinal</em> if every growth function is dominated by at least one growth function in ${\mathcal F}$. </p> <p>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.</p> <p>My first question is: what happens without the continuum hypothesis? Is it possible to have a cofinal set of growth functions of intermediate cardinality?</p> <p>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).</p> <p>EDIT: notation updated in view of responses.</p> http://mathoverflow.net/questions/29624/how-many-orders-of-infinity-are-there/29625#29625 Answer by Henno Brandsma for How many orders of infinity are there? Henno Brandsma 2010-06-26T17:59:46Z 2011-02-23T19:53:28Z <p>Yes, this is possible, if you define the order to be dominance with finitely many exceptions. So f &lt; 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.</p> <p>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} &lt; \mathfrak{c}$, $\omega_1 &lt; \mathfrak{d} &lt; \mathfrak{c}$ and $\omega_1 &lt; \mathfrak{d} = \mathfrak{c}$, in different models of ZFC.</p> http://mathoverflow.net/questions/29624/how-many-orders-of-infinity-are-there/29626#29626 Answer by François G. Dorais for How many orders of infinity are there? François G. Dorais 2010-06-26T18:00:11Z 2010-06-26T18:24:22Z <p>For asymptotic domination, commonly denoted <code>${\leq^*}$</code> and often called <em>eventual domination</em>, this has been answered by Stephen Hechler, <em>On the existence of certain cofinal subsets of ${}^{\omega }\omega$</em>, <a href="http://www.ams.org/mathscinet-getitem?mr=360266" rel="nofollow">MR360266</a>. What you call a <em>complete set</em> is usually called a <em>dominating family</em>. </p> <p>As a poset under eventual domination, a dominating family $\mathcal{F}$ must have the following three properties:</p> <ol> <li>$\mathcal{F}$ has no maximal element.</li> <li>Every countable subset of $\mathcal{F}$ has an upper bound in $\mathcal{F}$.</li> <li>$|\mathcal{F}| \leq 2^{\aleph_0}$</li> </ol> <p>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})$. </p> <p>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.</p> <p>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 &lt; \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.</p> http://mathoverflow.net/questions/29624/how-many-orders-of-infinity-are-there/29627#29627 Answer by Kristal Cantwell for How many orders of infinity are there? Kristal Cantwell 2010-06-26T18:00:51Z 2010-06-26T18:00:51Z <p>I think that there a complete set of growth functions of intermediate cardinality. This is based a earlier discussion on a related subject <a href="http://mathoverflow.net/questions/3057/is-there-a-topology-on-growth-rates-of-functions" rel="nofollow">here</a>. In particular Joel David Hamkins answer seems to answer the question in the affirmative.</p> http://mathoverflow.net/questions/29624/how-many-orders-of-infinity-are-there/29630#29630 Answer by reb for How many orders of infinity are there? reb 2010-06-26T18:30:04Z 2010-06-26T18:30:04Z <p>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. </p> http://mathoverflow.net/questions/29624/how-many-orders-of-infinity-are-there/29659#29659 Answer by Joel David Hamkins for How many orders of infinity are there? Joel David Hamkins 2010-06-27T01:44:23Z 2010-06-27T01:44:23Z <p>François has given an excellent answer to this question. </p> <p>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 <em>dominating</em> family. This is different, for example, from the similar concept of an <em>unbounded</em> 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.</p> <p>As Kristal mentions, I mention in <a href="http://mathoverflow.net/questions/3057/is-there-a-topology-on-growth-rates-of-functions/13780#13780" rel="nofollow">this MO answer</a>, which is also a direct answer to this question, that the <em>dominating number</em> <strong>d</strong> 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 <strong>d</strong> can be exactly controlled by forcing. In particular, it can achieve desired intermediate values, when CH fails.</p> <p>The similar-sounding but actually inequivalent <em>bounding number</em> <strong>b</strong>, 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 <strong>b</strong> $\leq$ <strong>d</strong>. Remarkably, however, it is consistent that <strong>b</strong> $\lt$ <strong>d</strong>, and this is proved again by forcing. </p> <p>There are dozens of other similar cardinal characteristics of the continuum, some of which I mention in <a href="http://mathoverflow.net/questions/8972#9027" rel="nofollow">this MO answer</a>. 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 <a href="http://en.wikipedia.org/wiki/Cicho%C5%84%27s_diagram" rel="nofollow">Cichon's diagram</a>. 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. <a href="http://mathoverflow.net/users/6794/andreas-blass" rel="nofollow">Andreas Blass</a>, now here on MO, is one of the world experts in this area.</p> http://mathoverflow.net/questions/29624/how-many-orders-of-infinity-are-there/29746#29746 Answer by Andreas Blass for How many orders of infinity are there? Andreas Blass 2010-06-28T03:31:47Z 2010-06-28T03:31:47Z <p>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:</p> <p>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. </p> <p>MR0380705 (52 #1602) Hechler, Stephen H., On a ubiquitous cardinal. Proc. Amer. Math. Soc. 52 (1975), 348--352. </p> <p>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.</p> <p>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. </p> <p>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</p> <p>MR0780528 (86i:03064) Baumgartner, James E.; Dordal, Peter, Adjoining dominating functions. J. Symbolic Logic 50 (1985), no. 1, 94--101.</p> <p>Finally, let me indulge in a bit of self-promotion. On the set theory page of my web site, </p> <p><a href="http://www.math.lsa.umich.edu/~ablass/set.html" rel="nofollow">http://www.math.lsa.umich.edu/~ablass/set.html</a> ,</p> <p>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. </p>