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

It seems that in most theorems outside of set theory where the size of some set is used in the proof, there are three possibilities: either the set is finite, countably infinite, or uncountably infinite. Are there any well known results within say, algebra or analysis that require some given set to be of cardinality strictly greater than $2^{\aleph_{0}}$? Perhaps in a similar vein, are any objects encountered that must have size larger than $2^{\aleph_{0}}$ in order for certain properties to hold?

share|improve this question
One famous folklore example is the automorphism group of the field of complex numbers, which has cardinality $2^{2^{\aleph_0}}$. –  Evan Jenkins Nov 3 '10 at 17:35
@Evan On the other hand, there are only 2 continuous (or even "reasonably definable") such automorphisms. –  Andres Caicedo Nov 3 '10 at 17:44
Given the title of this question, isn't it an oxymoron to tag this question "set-theory"? –  Willie Wong Nov 3 '10 at 19:09
@Andres: the automorphism group of the complex numbers is used as a tool in the theory of canonical models of Shimura varieties. Even though I can only think of two explicit automorphisms, the full group is needed. –  Kevin Buzzard Nov 3 '10 at 20:38
@Kevin Buzzard: I haven't seen the email, but in general, it's often possible to avoid a complex construction by talking around it. For example, we could skip all abstract group theory and only work with groups of permutations. For a more historical example, I read once that topologists understood the concept of homology groups long before they began using that terminology in papers. In principle we still "could" avoid homology groups for many results by talking around them. My personal opinion is that ''if'' something is commonly used, that's all that matters - not whether it "must" be used. –  Carl Mummert Nov 4 '10 at 12:59
show 4 more comments

13 Answers

up vote 35 down vote accepted

The Zariski tangent space at any point of a positive dimensional $C^1$-manifold $X$ has dimension $2^{2^{\aleph_0}}= 2^{\frak c}$. Let me explain in the case when $X=\mathbb R$.

Consider the ring $C^1_0$ of germs of $C^1$- functions at $0\in \mathbb R$ and its maximal ideal $\frak m $ of germs of functions vanishing at zero. The cotangent space at zero of $\mathbb R $ is $Cot_0=\frak m /\frak m ^2$ and the Zariski tangent space is $T_0=(Cot_0)^{\ast}$ (dual $\mathbb R$-vector space). Now the germs of the functions $x^\alpha $ are linearly independent modulo $\frak m ^2$ for $\; \alpha\in(1,2)$ . Hence $dim_{\mathbb R} (Cot_0)=\frak c$ and so indeed the Zariski tangent space at zero of $\mathbb R$ is $dim_{\mathbb R} (T_0)=2^{\frak c}$.

It is noteworthy that many textbooks erroneously claim that for an $n$-dimensional manifold of class $C^1$ the Zariski tangent space defined above has dimension $n$. Or they make some equivalent mistake like claiming that the vector space of derivations of $C^1_0$ has dimension $n$ . An example of such an error is on page 42 in Claire Voisin's (excellent!) book Hodge Theory And Complex Algebraic Geometry I published by Cambridge University Press.

To end on a positive note, the phenomenon I am describing only raises its ugly head for $C^k$-manifolds with $k<\infty$. For $n$-dimensional $C^\infty$-manifolds the Zariski tangent space at any point has dimension $n$, as it should. The heart of the matter is that a $C^\infty$ function $f$ , on $\mathbb R$ say, which vanishes at zero can be written $f=xg$ for some function $g$ which is also of class $C^\infty$, whereas $g$ would only be of class $C^{k-1}$ if $f$ were of class $C^k$.

share|improve this answer
Holy moly! That's incredible! –  Ravi Vakil Jul 29 '11 at 16:58
A bit late, but: finally, a gripping example of the difference between $C^k$ and $C^\infty$ manifolds! (Not that I was really looking.) –  Ryan Reich Aug 8 '13 at 5:10
add comment

Here is an example from group theory.

The automorphism tower of a group G is obtained by iteratively computing the automorphism group:

$$G\to \text{Aut}(G)\to \text{Aut}(\text{Aut}(G))\to\cdots$$

Each groups maps homomorphically into the next by mapping an element $g$ to conjugation by that element. One may therefore continue the iteration transfinitely by taking a direct limit to get the group $G_\omega$ at $\omega$, and continue the process. At successor stages, take the automorphism group; at limit stages, take the direct limit of the resulting system. The question is whether the process ever terminates, whether one ever arrives at a group that is isomorphic to its automorphism group by that natural map. Such a group is complete, having trivial center and no outer automorphisms.

Wielandt (1939) proved that the automorphism tower of every finite centerless group terminates in finitely many steps. Hulse (1970) proved that the automorphism tower of any centerless polycyclic group terminates in a countable ordinal number of steps.

Simon Thomas (here at MO) proved (1985) in general that the automorphism tower of any centerless group $G$ terminates before stage $(2^{|G|})^+$ many steps.

This bound on the height of the automorphism tower is strictly larger than the continuum, even when the size of the group is not, and so it seems to be an example of the desired phenomenon. (There is a set-theoretic sense (Just, Shelah and Thomas) in which one cannot expect to prove a better bound.)

Thomas' papers are available on his web page.

Meanwhile, in the case of non-centerless groups, I proved that every group has a terminating transfinite automorphism tower (see Proceedings AMS 126 (1998)). The proof proceeds by showing that every automorphism tower leads eventually to a centerless group, and then appeals to Thomas' theorem. There is also an easy survey article available.

For general groups, the best known upper bound for the height of the automorphism tower is essentially the next inaccessible cardinal. Even for finite groups, no reasonable upper bound is known in the general (non-centerless) case.

The topic was also discussed at this MO question.

share|improve this answer
add comment

One of the quickest ways to demonstrate that there exist Lebesgue measurable subsets of the real line that are not Borel measurable is to compute the cardinality of the Lebesgue $\sigma$-algebra and the Borel $\sigma$-algebra. The former has cardinality $2^{2^{\aleph_0}}$ (it contains the power set of the Cantor set), whereas the latter has cardinality $2^{\aleph_0}$ (by the transfinite induction construction of the Borel $\sigma$-algebra).

EDIT: Another potential place for larger cardinality sets to appear (though one which is still currently somewhat rare) is in nonstandard analysis. The usual construction of nonstandard models requires only countable ultraproducts, which do not increase cardinality that much. On the other hand, as a consequence, the models that one gets are only countably saturated. One can ask for more saturation by taking larger ultraproducts. In fact, if one iterates this process out to an inaccessible cardinal, one eventually obtains a monstrously large model which has saturation at all cardinalities smaller than that of the model. Such models have occasionally been used in analysis (e.g. in a recent paper of Hrushovski to attack the "noncommutative Freiman theorem" conjecture) but one can take the position that these tools are largely a convenience, and that one could work with a much less saturated model and still get the same applications at the end of the day (but perhaps with a lengthier argument).

I gather that something analogous happens in arithmetic geometry, in which it is convenient to work with Grothendieck universes which are again the size of inaccessible cardinals in order to obtain saturation-like properties, but that this is not absolutely necessary. (Though, I believe that the only extant proofs of Fermat's last theorem, for instance, still ultimately use Grothendieck universes, though perhaps not in a particularly essential fashion.)

share|improve this answer
I thought we needed axiom of choice to show that there are non-measurable sets? (unless the axiom was used in counting the size of the algebras and I missed it) –  muad Nov 3 '10 at 18:37
The axiom of choice is needed to exhibit sets that are not Lebesgue measurable. However, it is not required in order to exhibit sets that are Lebesgue measurable but not Borel measurable. (An explicit example of such a set is given for instance at en.wikipedia.org/wiki/Borel_set ). –  Terry Tao Nov 3 '10 at 18:45
Terry, you still need some AC (in the form of DC) to exhibit non-Borel sets of reals, because it is consistent with ZF that the reals are a countable union of countable sets, in which case every set of reals is Borel. (This issue arose at another MO question a few months back.) –  Joel David Hamkins Nov 3 '10 at 23:20
"(This issue arose at another MO question a few months back.)" I found it! mathoverflow.net/questions/32720/… –  Andres Caicedo Nov 4 '10 at 2:09
Hmm, that was a subtlety I was not aware of, though in retrospect it is clear that some weak form of choice is still used in the above cardinality argument. OK, I stand corrected! –  Terry Tao Nov 4 '10 at 3:05
show 1 more comment

The $\sigma$-algebra of all Lebesgue measurable subsets of $\mathbb{R}$ (i.e. the completion of the Borel $\sigma$-algebra) has cardinality $2^{2^{\aleph_0}}$.

I think there are lots of familiar objects of cardinality $2^{2^{\aleph_0}}$, so it might be interesting to concentrate on the ones that are larger.

share|improve this answer
Aww, beaten by 20 seconds. –  Nate Eldredge Nov 3 '10 at 18:18
But if you identify Lebesgue measurable sets that differ by a set of measure 0 (which is what we usually do), then there is only a continuum of such sets. –  Dmitri Pavlov Nov 4 '10 at 11:28
add comment

In his paper Higher set theory and mathematical practice MR0284327, Harvey Friedman shows how sets of higher rank are necessary to prove Borel determinacy.

Another instance is the Erdős–Rado Theorem, which says in particular that any graph on a set of size $(2^{\aleph_0})^+$ either has an uncountable clique or an uncountable anticlique (this result is best possible).

share|improve this answer
What's the plus? –  Mariano Suárez-Alvarez Nov 3 '10 at 19:07
Btw, I remember reading a statement of a theorem of Erdős claiming that if a graph has a sufficiently large chromatic number (some $\aleph$ or another...) then it has a cycle of some specific length (four?)... Maybe you can point me to a precise statement? –  Mariano Suárez-Alvarez Nov 3 '10 at 19:09
$(2^{\aleph_0})^+$ is the smallest cardinal larger than $2^{\aleph_0}$. –  François G. Dorais Nov 3 '10 at 19:38
These two examples surely belong to set theory. –  Andres Caicedo Nov 3 '10 at 20:45
@Andres: Yes and no. In any case, the two examples were in answer to the second question more than the first. –  François G. Dorais Nov 4 '10 at 2:34
show 2 more comments

This is close to alephomega's answer, but looks less set theoretic. $\beta\mathbb N$, the Stone-Cech compactification of the natural numbers is the spectrum of the commutative $C^*$-algebra $\ell^\infty$. As pointed out above, the set is of size $2^{2^{\aleph_0}}$.

For several results on the Ramsey theory of $\mathbb N$ (Hindman's theorem, Hales-Jewett theorem, even van der Waerden's theorem) it is very useful to consider compact semigroups that are Stone-Cech compactifications of countable discrete semigroups. As topological spaces these are homeomorphic to $\beta\mathbb N$.

In the same direction, the OP mentions "uncountable" sets, which often means sets of size $2^{\aleph_0}$. In Furstenberg's structure theorem which is used in his proof of Szemeredi's theorem, the cardinal (or rather, the ordinal) $\aleph_1$ figures prominently.

I have difficulties coming up with a set of size larger than $2^{2^{\aleph_0}}$ that comes up in ordinary mathematics, though.

It seems that real "large cardinals" show up more often in this context:

The statement that there is a non-trivial, $\sigma$-additive measure on $\mathbb R$ (i.e., one that measures every set) is equiconsistent with the existence of a measurable cardinal.
A measurable cardinal is a large cardinal in the set-theoretic sense of the word. In particular, it cannot be reached from $\aleph_0$ by iterating exponentials finitely often.

The existence of a Grothendieck universe is equivalent to the existence of an inaccessible cardinal, another notion of large cardinal.

share|improve this answer
Inductions of length $\omega_1$ are not that uncommon in complex analysis, actually. –  Andres Caicedo Nov 3 '10 at 20:55
Let me elaborate: Typically these inductions appear when there is some sort of ''topological derivative'' in the background, although there are of courses other settings. For a pretty example, look at the paper "Fixed Points, Koebe Uniformization and Circle Packings" by Zheng-Xu He and Oded Schramm, The Annals of Mathematics, Second Series, Vol. 137, No. 2, (Mar., 1993), pp. 369-406. –  Andres Caicedo Nov 3 '10 at 21:18
"The existence of a Grothendieck universe is equivalent to the existence of an inaccessible cardinal." This sounds something you might read in a <a href="amazon.com/Angels-Demons-ebook/dp/B000FBJFSM/… Brown book</a>, about nefarious plots high up in the Catholic Church... :-) –  Ravi Vakil Jul 29 '11 at 17:14
add comment

For $X$ a countable $T_{3_{1/2}}$ space then the Stone-Cech compatification $\beta(X)$ has size $2^{2^{\aleph_0}}$.

Also Shelah has written things about Dowker spaces of size $\aleph_{\omega+1}$.

Still in topology, $\mathbb{N}^{\aleph_1}$ is not a Cech-complete space. Recall that a Cech-complete space is space where the remainder $\beta(X) \backslash X$ is a $G_\delta$ set.

share|improve this answer
Only the first has size provably greater than the continuum (and you probably mean $2^{2^{|X|}}$. Since Daniel asked for analysis applications, it may be worth pointing out that nonstandard analysis calls for ultrapowers, which in turn calls for a set of nonprincipal ultrafilters such as $\beta(\mathbb{N})$. –  Todd Trimble Nov 3 '10 at 18:32
You're right I mean $X$ not $\aleph_0$, let me edit that. –  Carlo Von Schnitzel Nov 3 '10 at 18:39
The discrete countable space has Stone–Čech compactification of size $2^{2^{\aleph_0}}$. However, there are many countable spaces whose $\beta$ is much smaller. For the extreme case, if $X$ is a countable compact space, then $\beta X=X$ is countable. –  Emil Jeřábek Jun 2 '11 at 14:05
add comment

Let $k$ be an algebraically closed field. The Lefschetz principle states that, as far as "algebraic" statements are concerned, any algebraically closed extension of $k$ is "the same" as $k$. For instance, if $A$ is a finitely generated $k$-algebra and $K$ is an algebraically closed extension of $k$, then $A$ is a domain (or reduced, irreducible, normal,...) if and only if $A \otimes_k K$ is.

There is a precise version of this using model theory that can be used to prove the statements above (and a number of others), and hence is interesting to algebraists. It states that the theory of algebraically closed extensions of $k$ is complete. The standard way to prove this involves showing that for a sufficiently large cardinal $\kappa$, there is a unique isomorphism class of algebraically closed $k$-algebras of cardinality $\kappa$.

In particular, for this to be relevant, we must consider $\kappa > \lvert k \rvert$. If, e.g., $k = \mathbb{C}$, then we are using cardinalities greater than that of the continuum. Moreover, the fact that this cardinality is "large" is used in an essential way--it's not just a side effect of something else we're trying to do.

share|improve this answer
Dear Charles: Entirely precise versions of this principle are given in extraordinary generality in EGA IV$_3$, sections 8, 9, 11, 12, 17 without ever needing anything remotely model-theoretic, and the added generality is extremely useful in practice. If one only cares about the framework you describe, it can all be done in an elegant manner using nothing deeper than the Nullstellensatz and generic flatness results; this is a very instructive (and perhaps challenging) exercise to figure out. –  BCnrd Nov 4 '10 at 5:40
What's wrong with using model theory? You make it sound like it's cheating. –  arsmath Nov 4 '10 at 7:22
Dear arsmath: There's nothing wrong with using model theory. My points are: (i) in practice one needs results like what Charles describes but with way more general ring extensions than those of algebraically closed fields, for which it seems unlikely that model theory is applicable, and (ii) he says the intervention of "large" extension fields is essential in some model-theoretic approaches, and it is an instructive exercise in basic scheme methods to see that one can make simple proofs of all such things without "large" field extns. So my emphasis is on alternative useful techniques. –  BCnrd Nov 4 '10 at 7:45
Dear arsmath: Here is a specific example of what I have in mind. Let $R$ be the direct limit of a direct system of rings $R_i$, and let $X_i$ be a corresponding system of finitely presented schemes (compatible with base change along the directed system). Let $X$ be the corresponding $R$-scheme. Prove that if $X$ is $R$-flat (resp. $R$-proper) then so is $X_i \rightarrow {\rm{Spec}}(R_i)$ for large $i$. Can model-theoretic methods provide proofs? –  BCnrd Nov 4 '10 at 7:50
Dear Charles: These statements going from $\mathbf{C}$ to $\overline{\mathbf{F}}_p$ for sufficiently large $p$ are amenable to simple geometric proofs without model theory by using nothing much more than the Nullstellensatz and elementary flatness stuff, and such methods are extremely useful: for example, it's exactly what's needed to justify that various results at the geometric generic fiber in are equivalent to results on geometric fibers over a Zariski-dense open locus in the base (can then be applied over Spec($\mathbf{Z}$)!) –  BCnrd Nov 4 '10 at 18:04
show 1 more comment

For each $n$, there is a unique binary operation $*$ on $\{1,\ldots,2^n\}$ which satisfies $$a * 1 \equiv a+1 \mod 2^n$$ $$a * (b * c) = (a * b) * (a * c)$$ This is the $n$th Laver table $A_n$. The Laver tables have a purely number-theoretic definition (although see my other post concerning computation in them). These naturally project down to the smaller tables in such a way to give rise to an inverse limit. In this inverse limit, there is a copy of the generator and one can use it to generate an algebra $A_\infty$.

Here is the interesting part: the freeness of $A_\infty$ has been established from the assumption that, for each $n$, there is an $n$-huge cardinal (these are among the strongest of the large cardinal hypotheses). No proof is known in ZFC. See Laver's articles in Advances in Mathematics or Dehornoy's book "Braids and self distributivity" for more information. In my opinion this is the greatest problem in reverse mathematics.

These tables did originate in set theory, but they have natural connections to the study of braids (Dehornoy's book is testimony to this).

share|improve this answer
Is the history of the appearance of the tables (this sounds so biblical!) written down somewhere? –  Mariano Suárez-Alvarez Mar 10 '11 at 2:56
Laver discovered them in the course of studying the algebra of elementary embeddings. See the above references for a discussion. Dehornoy's book gives a fairly exhaustive account and development of the tables. –  Justin Moore Mar 10 '11 at 3:40
Thanks! ${}{}{}$ –  Mariano Suárez-Alvarez Mar 10 '11 at 3:48
add comment

Denote by $H^\infty$ the Banach algebra of all bounded analytic functions on the unit disc. Then the maximal ideal space of $H^\infty$, (i.e., the set of all norm continuous, multiplicative linear functionals on $H^\infty$) has cardinality $2^{2^{\aleph_0}}$. SInce maximal ideal spaces are used all the time in Banach algebra theory, this is an example of a naturally occuring ``large cardinal".

This is also an example of how knowing the (large) cardinality of a set may help direct us in research, even if this knowledge does not lead to a proof of anything. In this example, since the maximal ideal space is so wild, one realizes that it is ``hopeless" to find a nice analytic or geometric description of the maximal ideal space, and one is led to look for a suitable replacement. In algebras such as $H^\infty$ it is often the weak-$*$ continuous multiplicative linear functionals which are more useful (there are only $2^{\aleph_0}$ such functionals).

share|improve this answer
Hi Orr. Without disputing your main point, I'd like to just mention that some people have continued to try and get some handle on the full maximal ideal space, see for instance work of Brudnyi arxiv.org/abs/math/9908168 although I have not actually looked properly at the work itself –  Yemon Choi Nov 4 '10 at 3:09
add comment

I have some other examples: tha cardinality of the family of dense non denumerable subsets of $\mathbb{R}^{n}$ (n=1,2...) is $2^{2^{\aleph_{0}}}$, the dimension of $\mathbb{R}$ like a $\mathbb{Q}$-vector space is $2^{2^{\aleph_{0}}}$, the cardinalitiy of the family of lebesgue non mesurable (and mesurables, mesurables with measure r (r a given real number), with infinite measure) sets is $2^{2^{\aleph_{0}}}$, the cardinality of the family of riemann integrable functions (in $\mathbb{R}^{n}$, n=1,2...)is $2^{2^{\aleph_{0}}}$, and so on...

share|improve this answer
The dimension of $\mathbb{R}$ over $\mathbb{Q}$ is certainly not bigger than the cardinality of $\mathbb{R}$ itself. Perhaps you meant the number of bases? –  Ori Gurel-Gurevich Nov 3 '10 at 23:29
Thanks, that was a mistake. The number ob bases is $2^{2^{\aleph_{0}}}$ –  Paul Marcelo Nov 3 '10 at 23:49
add comment

Extending the answer by Stefan Geschke, another example is the enveloping semigroup of a compact dynamical system. Let $G$ be a topological group that acts continuously on a compact Hausdorff space $X$. Then each element of $G$ can be identified with an element of the function space $X^X$. The closure of $G$ in this space (under the product topology) is the enveloping semigroup of $(X,G)$. These are well studied in the theory of dynamical systems, for example they can be used to prove the Auslander-Ellis theorem.

The paper "On metrizable enveloping semigroups" by Glasner, Megrelishvili, and Uspenski (Israel J. Math 2008) gives some background and restates an explicit cardinality dichotomy between $2^{\aleph_0}$ and $2^{2^{\aleph_0}}$ in Theorem 6.1. That result is related to the group $\beta\mathbb{N}$ mentioned by Stefan Geschke and by alephomega. Their preprint is at http://www.math.tau.ac.il/~glasner/papers/metr.pdf .

share|improve this answer
add comment

For a discrete infinite amenable group $G$ the family of left-invariant means on $G$ is quite large having cardinality $2^{2^{|G|}}$. See Chapter 7 of

A. L. T. Paterson, Amenability, Mathematical Surveys and Monographs, 29, American Math. Soc., Providence, Rhode Island, 1988.

Although I am not sure how natural it is, there is a recent result of Farah and Katsura concerning the number of non-isomorphic hyperfinie $II_1$-factors with preduals having density character $\kappa>\omega$. This number is precisely $2^\kappa$. Since $2^\kappa$ is much bigger than 1, it is a pretty good reason to stick with separably acting von Neumann algebras. (Of course it may still happen that $2^\kappa = \mathfrak{c}$.)

share|improve this answer
add comment

Your Answer


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.