(Sorry if my terminology is a bit imprecise; I'm trying to describe a rather vague notion in my head about when something "relies on" the distinction between finite/countable/uncountable, but I am finding it difficult to put into words precisely.)

There are proofs or properties that only hold when something is finite, but breaks down when it becomes infinite. For example, the finite intersection of open sets is open, but not arbitrary infinite intersections. As another example, $ a_n>0 \ \forall n \in \mathbb{N} $ does not imply $ \lim_{n \rightarrow \infty}{a_n}>0 $.

Similarly, there are also proofs or properties that only hold when something is countable. For example, normal induction can only be used if the variable takes values from a countable set.

I was wondering, are there any common proofs or properties that rely on a similar distinction between some uncountable size and another larger uncountable size? For example, property X is true iff some set S has size $\leq \aleph_n$ where $n>0$ ?

(Not sure what to tag; please edit if necessary :) )

  • 2
    $\begingroup$ Induction works over any well-ordered set. It is not the cardinality that matters but the order. $\endgroup$ – QuantumSpace May 12 '20 at 21:36
  • $\begingroup$ I see, thanks for pointing that out! $\endgroup$ – Rayna Grayson May 13 '20 at 22:33
  • 1
    $\begingroup$ One also runs into this sort of thing when dealing with category theory, too. In particular, when dealing with presentable categories, sometimes one needs to play games with cardinalities if one wants to carefully avoid set-theoretic issues. $\endgroup$ – Brian Shin May 13 '20 at 23:06

There are several relatively straightforward existence proofs in analysis that make use of $c < 2^c.$

1. "Most" Lebesgue measure zero sets are not Borel sets, because there are $2^c$ many Lebesgue measure zero sets (consider all subsets of a measure zero Cantor set) and there are only $c$ many Borel sets.

2. "Most" Riemann integrable functions are not Borel measurable, because the characteristic function of any subset of a measure zero Cantor set is Riemann integrable and there are only $c$ many Borel measurable functions.

3. "Most" complete Borel measures on $\mathbb R$ are not $\sigma$-finite. In fact, there are $2^c$ many complete Borel measures on $\mathbb R$ and only $c$ many $\sigma$-finite Borel measures (complete or not complete) on ${\mathbb R}.$ To see the first claim, let $B$ be a Borel set of cardinality $c$ (e.g. $B$ could be a Cantor set or the interval $[0,1]).$ For each $A \subseteq B,$ define ${\mu}_A(E) = \infty$ if $A \cap E \neq \emptyset$ and ${\mu}_A(E) = 0$ if $A \cap E = \emptyset.$ To see the second claim, note that every finite Borel measure on $\mathbb R$ is the Lebesgue-Stieltjes measure of some monotone function, and there are only $c$ many monotone functions (several ways to prove this). Now observe that every $\sigma$-finite Borel measure on $\mathbb R$ can be associated with a sequence of finite Borel measures on ${\mathbb R}.$ (Recall that there are only $c$ many sequences whose terms all come from a given set of cardinality $c.)$

4. "Most" convex subsets of ${\mathbb R}^2$ are not Borel sets, since removing any subset of the boundary of the unit disk results in a convex set and there are only $c$ many Borel sets. Note how badly this fails for ${\mathbb R}.$

5. "Most" functions $f:{\mathbb R} \rightarrow {\mathbb R}$ that are symmetrically continuous at each point (i.e. for each $x \in \mathbb R$ we have $\lim_\limits{h\rightarrow 0}\ [f(x+h)-f(x-h)]=0)$ are not continuous, or even Borel measurable. Miroslav Chlebík proved in this 1991 Proc. AMS paper that there are $2^c$ symmetrically continuous functions, and there are only $c$ many continuous functions (indeed, only $c$ many Borel measurable functions).

6. "Most" subsets of the boundary of the unit disk are not a divergence set for any power series with complex coefficients and radius of convergence $1,$ since there are $2^c$ many subsets of the boundary of the unit disk and only $c$ many power series with complex coefficients. For more details about the possible divergence sets of a power series with complex coefficients, see this answer. Note how different this is for power series with real coefficients, in which there are only $2^2 = 4$ possible subsets of the boundary of an interval (there are only $4$ subsets of a $2$-element set) and it is not difficult to see that any of these subsets can be a divergence set.

  • 2
    $\begingroup$ +1. Note to the OP that this answer focuses not on the $\aleph$-hierarchy but on the $\beth$-hierarchy; basically, $\beth_n$ is the cardinality of the $n$th iterated powerset of the natural numbers. So $\aleph_0=\beth_0$, $2^{\aleph_0}=c=\beth_1$, $2^c=\beth_2$, and so forth. This isn't a coincidence: besides the "countable/uncountable" divide, most natural cardinality divides live in the $\beth$ hierarchy. Essentially the issue is that while the $\beth$ numbers correspond (by definition) to reasonably concrete sets, the usual axioms of set theory don't tell us much about the $\aleph$ numbers. $\endgroup$ – Noah Schweber May 12 '20 at 19:25
  • 1
    $\begingroup$ (Re: $\beth$, see here.) For example, $c$ could be $\aleph_1$ ... or it could be $\aleph_2$, or $\aleph_{17}$, or $\aleph_{\omega^\omega+461}$, or almost anything else. A bit more snappily: I would say that the cardinalities which appear naturally in mathematics outside of set theory are almost always by definition either $\beth$-numbers (e.g. $c=\beth_1$) or successors of $\beth$-numbers (e.g. $\aleph_1=\beth_0^+$). There are occasional exceptions to this, but they're quite rare. $\endgroup$ – Noah Schweber May 12 '20 at 19:28
  • 2
    $\begingroup$ +1. A use of $c<2^c$ in topology is the Jones Lemma. E.g., to show that $U=S\times S$ is not a $T_4$ space, where $S$ is the Sorgenfrey line: $\Bbb Q\times \Bbb Q$ is a countable dense subset of $U$ so the cardinal of the set of continuous $f:U\to [0,1]$ is at most $c.$ But $Y=\{(x,-x):x\in S\}$ is a closed discrete subspace of $U.$ If $U$ were $T_4$ then for every $Z\subset Y$ there would be a continuous $f:U\to [0,1]$ with $f=1$ on $Z$ and $f=0$ on $Y\setminus Z,$ which requires $2^{|Y|}=2^c$ distinct functions. $\endgroup$ – DanielWainfleet May 13 '20 at 7:04
  • $\begingroup$ Wow, @Dave L. Renfro thanks so much! A lot of this is difficult for me to understand at my current level (I'm only starting to learn topology), but 5 I can completely understand and that is really cool - I'm still trying to wrap my head around it. I have been reading Wikipedia pages to try to better understand the other ones, which might take a while :) but I'm looking forward to understanding them eventually. $\endgroup$ – Rayna Grayson May 13 '20 at 21:52
  • 1
    $\begingroup$ @RaynaGrayson: The $\beth$ are not "parallel" to the $\aleph$ numbers. The claim that every infinite cardinal is a $\beth$ number is equivalent to GCH (Generalised Continuum Hypothesis), whereas the claim that every infinite cardinal is an $\aleph$ number is only equivalent to the axiom of choice. $\endgroup$ – Asaf Karagila May 13 '20 at 22:30

Sure. A large class of examples comes from the partition calculus. A simple result of the kind I have in mind is the following: Any infinite graph contains either a copy of the complete graph on countably many vertices or of the independent graph on countably many vertices. However, if we want to find an uncountable complete or independent graph, it is not enough that we begin with an uncountable graph. Instead, we need one of size strictly larger than the continuum.

For an encyclopedic reference on the partition calculus, including the result mentioned above, see

MR0795592 (87g:04002). Erdős, Paul; Hajnal, András; Máté, Attila; Rado, Richard. Combinatorial set theory: partition relations for cardinals. Studies in Logic and the Foundations of Mathematics, 106. North-Holland Publishing Co., Amsterdam, 1984. 347 pp. ISBN: 0-444-86157-2.

  • $\begingroup$ Thank you for the answer! This sounds really cool. I want to read more about this, but I'm having trouble finding a relevant source. Would you mind adding some links? $\endgroup$ – Rayna Grayson May 13 '20 at 22:06
  • 1
    $\begingroup$ I added the main textbook on the subject. There are also other surveys available; for instance MR2768681. Hajnal, András; Larson, Jean A. Partition relations. In Handbook of set theory. Vols. 1, 2, 3, M. Foreman and A. Kanamori, eds., pp. 129–213, Springer, Dordrecht, 2010. $\endgroup$ – Andrés E. Caicedo May 13 '20 at 22:26

It is not a trivial theorem, but $(\ell^\infty)^*$ is the $\rm ba$ space, whose cardinality is $2^{2^{\aleph_0}}$. The reason is that we can identify this space with finitely additive measures, and every ultrafilter on $\Bbb N$ induces such measure, and by a fairly straightforward argument, there are $2^{2^{\aleph_0}}$ such ultrafilters. The upper bound can be obtained by noting that the algebraic dual, which is strictly larger, has cardinality $2^{2^{\aleph_0}}$, since the dimension of $\ell^\infty$, as a linear space, is $2^{\aleph_0}$.


Now, since $\ell^1$ is a separable Banach space, its cardinality is only $2^{\aleph_0}$. This gives a "quick" proof as to why $(\ell^\infty)^*\ncong\ell^1$.

  • 1
    $\begingroup$ Note however that we can isometrically embedd one into the other! +1 $\endgroup$ – QuantumSpace May 12 '20 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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