Cardinal Arithmetic, Cofinality and the Alephs — Examples

Work in ZF; no choice principle is used anywhere below. With $\oplus$ and $\otimes$ as in Cardinal sum $\kappa \oplus \lambda$, product $\kappa \otimes \lambda$ and exponentiation ${\kappa }^{\lambda }$, and why they are written apart from the ordinal operations and the alephs as in The successor cardinal ${\kappa }^{+}$, the alephs ${\mathrm{\aleph }}_{\alpha }$, the beths ${\mathrm{\beth }}_{\alpha }$, successor and limit cardinals, and the identifications ${\mathrm{\aleph }}_0=\omega$ and ${\mathrm{\aleph }}_1={\omega }_1$:

${\mathrm{\aleph }}_0\oplus {\mathrm{\aleph }}_0={\mathrm{\aleph }}_0,{\mathrm{\aleph }}_0\otimes {\mathrm{\aleph }}_0={\mathrm{\aleph }}_0,{\mathrm{\aleph }}_1\oplus {\mathrm{\aleph }}_0={\mathrm{\aleph }}_1,5\oplus {\mathrm{\aleph }}_0={\mathrm{\aleph }}_0\mathrm{.}$

Each is an instance of absorption (Absorption: for cardinals $\kappa ,\lambda$ with $\kappa$ infinite and $\lambda \le \kappa$, $\kappa \oplus \lambda =\kappa$, and $\kappa \otimes \lambda =\kappa$ when $\lambda \mathrm{\ne }0$). The countable ones are also obtained a second way, from a bijection that was available before cardinal arithmetic existed: $\omega \times \omega \approx \omega$ ($\mathbb{N}\times \mathbb{N}\approx \mathbb{N}$), together with two inclusions and no further input.

What absorption replaces. Step 2.2 is what a reader would have had to do before Absorption: for cardinals $\kappa ,\lambda$ with $\kappa$ infinite and $\lambda \le \kappa$, $\kappa \oplus \lambda =\kappa$, and $\kappa \otimes \lambda =\kappa$ when $\lambda \mathrm{\ne }0$ existed: produce a bijection or a pair of injections for each computation separately. Step 2.1 does all four in one line, and the content of the corollary is exactly that the bookkeeping is unnecessary.

Why ${\mathrm{\aleph }}_1\oplus {\mathrm{\aleph }}_0={\mathrm{\aleph }}_1$ has no second computation here. The countable cases are witnessed by explicit maps because $\omega$ is concrete. At ${\mathrm{\aleph }}_1$ no comparable explicit bijection is written down here; the computation goes through Hessenberg: $\kappa \otimes \kappa =\kappa$ for every infinite cardinal $\kappa$, proved in ZF from the canonical well-order of $\kappa \times \kappa$, which Absorption: for cardinals $\kappa ,\lambda$ with $\kappa$ infinite and $\lambda \le \kappa$, $\kappa \oplus \lambda =\kappa$, and $\kappa \otimes \lambda =\kappa$ when $\lambda \mathrm{\ne }0$ packages. That is not a gap in this example but the reason the general theorem is worth proving.

The finite summand does not vanish for a trivial reason. $5\bigsqcup \omega$ does have more elements than $\omega$ in the naive sense: it carries a tagged copy of $\omega$ and five further points. The equality $5\oplus {\mathrm{\aleph }}_0={\mathrm{\aleph }}_0$ says only that the two sets are equinumerous, and what makes that true is that an infinite well-ordered set absorbs finitely many extra points, the same shift that makes an infinite cardinal a limit ordinal in Every natural number and $\omega$ are cardinals, every infinite cardinal is a limit ordinal, and on the natural numbers the cardinal operations are the published finite counting operations, with $\mid A\mid$ in the finite sense equal to $\mid A\mid$ in the cardinal sense.

Order does not matter here, and that is not automatic. $\oplus$ is commutative, so $5\oplus {\mathrm{\aleph }}_0$ and ${\mathrm{\aleph }}_0\oplus 5$ are the same cardinal. The ordinal $+$ on the very same objects is not commutative, which is precisely why Cardinal sum $\kappa \oplus \lambda$, product $\kappa \otimes \lambda$ and exponentiation ${\kappa }^{\lambda }$, and why they are written apart from the ordinal operations gives the cardinal operation its own symbol rather than reusing $+$.

Write ${}^{\omega }2$ for the set of functions $\omega \to 2=\{0,1\}$, the $2$ here being the von Neumann natural number, and $\mathcal{P}(\mathbb{N})$ for the power set of $\mathbb{N}=\omega$ (The natural numbers $\mathbb{N}$ (von Neumann)). Then:

(a) In ZF, with no choice principle:

$\mathbb{R}\approx {}^{\omega }2\approx \mathcal{P}(\mathbb{N})$

(Equinumerous sets, $A\approx B$ and $A⪯B$, The real numbers).

(b) Assuming the Axiom of Choice (The Axiom of Choice):

$\mid \mathbb{R}\mid =2^{{\mathrm{\aleph }}_0}=\mid \mathcal{P}(\mathbb{N})\mid$

(Cardinal sum $\kappa \oplus \lambda$, product $\kappa \otimes \lambda$ and exponentiation ${\kappa }^{\lambda }$, and why they are written apart from the ordinal operations, The successor cardinal ${\kappa }^{+}$, the alephs ${\mathrm{\aleph }}_{\alpha }$, the beths ${\mathrm{\beth }}_{\alpha }$, successor and limit cardinals, and the identifications ${\mathrm{\aleph }}_0=\omega$ and ${\mathrm{\aleph }}_1={\omega }_1$).

The two injections are the classical ones and neither uses a binary expansion. One direction is the Cantor set: The Cantor set is exactly the set of ${\sum }_{k\ge 1}{a}_k{3}^{-k}$ with every $a_k\in \{0,2\}$, and this gives a bijection with $\{0,1{\}}^{\mathbb{N}}$ already supplies a bijection from the sequences with values in $\{0,1\}$ onto the Cantor set $C\subseteq \mathbb{R}$ (The Cantor middle-thirds set as the intersection of the sets $C_n$ obtained by removing open middle thirds). The other is the cut map $x\mapsto \{q\in \mathbb{Q}:q<x\}$, injective because $\mathbb{Q}$ is dense in $\mathbb{R}$ (ℚ is dense in every Archimedean ordered field), and $\mathcal{P}(\mathbb{Q})$ is a copy of $\mathcal{P}(\mathbb{N})$ because $\mathbb{Q}$ is countable ($\mathbb{Q}$ is countably infinite). The Schröder-Bernstein theorem closes the loop, and it is choice free, which is what makes clause (a) a theorem of ZF.

Why binary expansions are avoided. The textbook proof identifies a real in $[0,1]$ with the set of positions where its binary expansion has a $1$, and then has to deal with the reals having two expansions. Neither injection above meets that difficulty: the Cantor set map is already published as a bijection, and the cut map needs only density. The cost is that the two injections go in opposite directions and The Schröder-Bernstein theorem is required to combine them, which is free, since that theorem is choice free.

Which half needs the Axiom of Choice, and why. Clause (a) is an equinumerosity statement and is a theorem of ZF. Clause (b) writes $\mid \mathbb{R}\mid$ and $2^{{\mathrm{\aleph }}_0}$ as cardinals, that is as ordinals, and in ZF alone $\mathcal{P}(\mathbb{N})$ need not be well-orderable, so those symbols need not denote anything. The hypothesis buys the notation, not the mathematics.

What is still not decided. Nothing here says which aleph $2^{{\mathrm{\aleph }}_0}$ is. The one constraint proved in this development is that its cofinality is uncountable (Assuming the Axiom of Choice: $\kappa <{\kappa }^{\mathrm{cf}(\kappa )}$ for every infinite cardinal $\kappa$, and $\mathrm{cf}(2^{\kappa })>\kappa$; in particular $\mathrm{cf}(2^{{\mathrm{\aleph }}_0})>{\mathrm{\aleph }}_0$), and the question of whether it is ${\mathrm{\aleph }}_1$ is the continuum hypothesis (What each result on this page costs in choice, and where the continuum escapes what ZFC can decide).

Assume the Axiom of Choice (The Axiom of Choice). Then

${\mathrm{\aleph }}_0<{\mathrm{\aleph }}_1\le 2^{{\mathrm{\aleph }}_0},$

and consequently ${\omega }_1$ injects into $\mathbb{R}$ (The first uncountable ordinal ${\omega }_1:=\mathrm{\aleph }(\omega )$, $\mathbb{R}\approx \mathcal{P}(\mathbb{N})$ in ZF, by the Cantor set for one injection and by the cuts $\{q\in \mathbb{Q}:q<x\}$ for the other; so $\mid \mathbb{R}\mid =2^{{\mathrm{\aleph }}_0}$ under the Axiom of Choice). Moreover $2^{{\mathrm{\aleph }}_0}={\mathrm{\aleph }}_{\alpha }$ for exactly one ordinal $\alpha$, and that $\alpha$ satisfies $1\le \alpha$ (Every infinite cardinal is ${\mathrm{\aleph }}_{\alpha }$ for exactly one ordinal $\alpha$, in ZF; and, assuming the Axiom of Choice, every infinite set is equinumerous with exactly one aleph).

The computation is one line and uses nothing about $\mathbb{R}$: $2^{{\mathrm{\aleph }}_0}$ is a cardinal strictly above ${\mathrm{\aleph }}_0$ by Cantor's theorem in cardinal form (Assuming the Axiom of Choice, $2^{\kappa }=\mid \mathcal{P}(\kappa )\mid$, and Cantor's theorem in cardinal form: $\kappa <2^{\kappa }$), and ${\mathrm{\aleph }}_1$ is by construction the least cardinal strictly above ${\mathrm{\aleph }}_0$ (For every set $A$ the Hartogs number $\mathrm{\aleph }(A)$ is a cardinal, and for every cardinal $\kappa$ it is the least cardinal strictly above $\kappa$; this is a theorem of ZF). The inequality is therefore forced, and the interest lies entirely in the fact that nothing here decides whether it is an equality.

What the inequality is not. It is not evidence for the continuum hypothesis, and it is not a partial result towards one. ${\mathrm{\aleph }}_1\le 2^{{\mathrm{\aleph }}_0}$ holds in every model of ZFC, including those where $2^{{\mathrm{\aleph }}_0}$ is very large; the inequality is a consequence of ${\mathrm{\aleph }}_1$ being defined as a least cardinal above ${\mathrm{\aleph }}_0$, so it would hold even if the continuum were enormous.

Where the real constraint lies. The one genuine restriction on $2^{{\mathrm{\aleph }}_0}$ proved in this development is on its cofinality, not on its position: Assuming the Axiom of Choice: $\kappa <{\kappa }^{\mathrm{cf}(\kappa )}$ for every infinite cardinal $\kappa$, and $\mathrm{cf}(2^{\kappa })>\kappa$; in particular $\mathrm{cf}(2^{{\mathrm{\aleph }}_0})>{\mathrm{\aleph }}_0$ gives $\mathrm{cf}(2^{{\mathrm{\aleph }}_0})>{\mathrm{\aleph }}_0$, which excludes candidate values such as ${\mathrm{\aleph }}_{\omega }$ (FALSE: $2^{{\mathrm{\aleph }}_0}={\mathrm{\aleph }}_{\omega }$) while excluding neither ${\mathrm{\aleph }}_1$ nor ${\mathrm{\aleph }}_2$, both of which are regular under choice. Whether $2^{{\mathrm{\aleph }}_0}={\mathrm{\aleph }}_1$ is the continuum hypothesis, and What each result on this page costs in choice, and where the continuum escapes what ZFC can decide records what is and is not settled about it here.

Without choice the statement is not even expressible in this form. In ZF alone $\mathcal{P}(\mathbb{N})$ need not be well-orderable, so $2^{{\mathrm{\aleph }}_0}$ need not be a cardinal and "${\mathrm{\aleph }}_1\le 2^{{\mathrm{\aleph }}_0}$" has no ordinal to compare. What is a theorem of ZF is the existence of ${\omega }_1$ itself (The first uncountable ordinal ${\omega }_1:=\mathrm{\aleph }(\omega )$, ${\omega }_1$ is uncountable, every ordinal below it is at most countable, it is a cardinal and a limit ordinal, and its existence is a theorem of ZF); the injection ${\omega }_1\to \mathbb{R}$ of step 2.1 is obtained here from the Axiom of Choice, and nothing above claims it without that hypothesis.

Work in ZF; no choice principle is used. The set

$C=\{{\mathrm{\aleph }}_n:n\in \omega \}\subseteq {\mathrm{\aleph }}_{\omega }$

(The successor cardinal ${\kappa }^{+}$, the alephs ${\mathrm{\aleph }}_{\alpha }$, the beths ${\mathrm{\beth }}_{\alpha }$, successor and limit cardinals, and the identifications ${\mathrm{\aleph }}_0=\omega$ and ${\mathrm{\aleph }}_1={\omega }_1$) is cofinal in ${\mathrm{\aleph }}_{\omega }$ (Cofinal subset of an ordinal) and satisfies $\mid C\mid ={\mathrm{\aleph }}_0$, so

$\mathrm{cf}({\mathrm{\aleph }}_{\omega })={\mathrm{\aleph }}_0<{\mathrm{\aleph }}_{\omega }$

(Cofinality $\mathrm{cf}(\alpha )$, and regular and singular cardinals) and ${\mathrm{\aleph }}_{\omega }$ is singular.

Two things make the computation work, and both are visible in the display. The upper bound is the cofinal family itself: ${\mathrm{\aleph }}_{\omega }$ is by definition the supremum of the ${\mathrm{\aleph }}_n$, so a family indexed by $\omega$ already reaches it. The lower bound is structural: ${\mathrm{\aleph }}_{\omega }$ is an infinite cardinal, hence a limit ordinal, so its cofinality is an infinite cardinal ($\mathrm{cf}(\alpha )\le \alpha$; $\mathrm{cf}(0)=0$ and $\mathrm{cf}(\alpha +1)=1$; for a limit ordinal $\lambda$ the value $\mathrm{cf}(\lambda )$ is an infinite cardinal with $\mathrm{cf}(\mathrm{cf}(\lambda ))=\mathrm{cf}(\lambda )$, so it is regular; and every cofinal subset of $\lambda$ has cardinality at least $\mathrm{cf}(\lambda )$, a value that is attained) and cannot be smaller than ${\mathrm{\aleph }}_0$.

Nothing is chosen, and that is the point. The cofinal family is the definable map $n\mapsto {\mathrm{\aleph }}_n$, and Replacement makes its range a set. So singularity of ${\mathrm{\aleph }}_{\omega }$ is a theorem of ZF, in contrast with the regularity of successor alephs, which is not (${\mathrm{\aleph }}_0$ is regular in ZF; assuming the Axiom of Choice every successor aleph ${\mathrm{\aleph }}_{\alpha +1}$ is regular; $\mathrm{cf}({\mathrm{\aleph }}_{\omega })={\mathrm{\aleph }}_0$, so ${\mathrm{\aleph }}_{\omega }$ is singular, and under choice it is the least singular infinite cardinal).

The size of ${\mathrm{\aleph }}_{\omega }$ plays no role. Only the index $\omega$ is used: it is a limit ordinal reached from below by an $\omega$-indexed family, and the aleph operation is continuous at limits, so the same computation gives $\mathrm{cf}({\mathrm{\aleph }}_{\lambda })\le \mid \lambda \mid$ for any limit $\lambda$ by exactly the argument of steps 1.2 and 1.3. What that bound is worth depends on $\lambda$, and Assuming countable choice, $\mathrm{cf}({\mathrm{\aleph }}_{{\omega }_1})={\mathrm{\aleph }}_1$, so singular does not mean of countable cofinality computes a case where it is uncountable.

Why this is not a counterexample to anything about $2^{{\mathrm{\aleph }}_0}$. It is the input to one: $\mathrm{cf}(2^{{\mathrm{\aleph }}_0})>{\mathrm{\aleph }}_0$ (Assuming the Axiom of Choice: $\kappa <{\kappa }^{\mathrm{cf}(\kappa )}$ for every infinite cardinal $\kappa$, and $\mathrm{cf}(2^{\kappa })>\kappa$; in particular $\mathrm{cf}(2^{{\mathrm{\aleph }}_0})>{\mathrm{\aleph }}_0$) together with the value computed here is what refutes $2^{{\mathrm{\aleph }}_0}={\mathrm{\aleph }}_{\omega }$ (FALSE: $2^{{\mathrm{\aleph }}_0}={\mathrm{\aleph }}_{\omega }$).

Assume the Axiom of Countable Choice ${\mathrm{A}\mathrm{C}}_{\omega }$ (The Axiom of Countable Choice (${\mathrm{A}\mathrm{C}}_{\omega }$)). Then

$\mathrm{cf}({\mathrm{\aleph }}_{{\omega }_1})={\mathrm{\aleph }}_1<{\mathrm{\aleph }}_{{\omega }_1},$

so ${\mathrm{\aleph }}_{{\omega }_1}$ is singular (Cofinality $\mathrm{cf}(\alpha )$, and regular and singular cardinals) and its cofinality is uncountable (Finite, countably infinite, countable, uncountable).

This separates two conditions that the first singular example runs together. A singular cardinal is one reachable from below by a strictly shorter family; it need not be reachable by a countable one. Here the reaching family has length ${\omega }_1$ and no shorter one will do, and what rules out a shorter one is the boundedness theorem for ${\omega }_1$ (Assuming countable choice: every at most countable subset of ${\omega }_1$ is bounded below ${\omega }_1$, so no at most countable subset of ${\omega }_1$ is cofinal in it, and a supremum of at most countably many at most countable ordinals is at most countable), which is where ${\mathrm{A}\mathrm{C}}_{\omega }$ is spent.

Why countable choice appears, and where exactly. It is used once, at [L4]: without it, ${\omega }_1$ can consistently be the supremum of an $\omega$-indexed family of countable ordinals, and then the argument of step 1.2 collapses. That dependence is inherited, not introduced here — the published boundedness theorem carries the same hypothesis, and states so in its own title.

What "singular" does and does not mean. Singular says only $\mathrm{cf}(\kappa )\mathrm{\ne }\kappa$. The singular cardinal computed in $\mathrm{cf}({\mathrm{\aleph }}_{\omega })={\mathrm{\aleph }}_0$, computed from the cofinal map $n\mapsto {\mathrm{\aleph }}_n$ has countable cofinality, and a reader who meets only that example may take the two conditions to be the same. They are not: here the cofinality is ${\mathrm{\aleph }}_1$, uncountable, while the cardinal is still singular because ${\mathrm{\aleph }}_1$ is far below ${\mathrm{\aleph }}_{{\omega }_1}$.

The pattern behind both computations. For a limit ordinal $\lambda$ the family $\alpha \mapsto {\mathrm{\aleph }}_{\alpha }$ restricted to $\lambda$ is cofinal in ${\mathrm{\aleph }}_{\lambda }$, so $\mathrm{cf}({\mathrm{\aleph }}_{\lambda })\le \mid \lambda \mid$ always. The work is entirely in the lower bound, and it is a statement about $\lambda$ rather than about ${\mathrm{\aleph }}_{\lambda }$: it asks how short a family can be and still reach $\lambda$.

Work in ZF; no choice principle is used. There is a tower of ordinals with

$T(0)={\mathrm{\aleph }}_0,T(n+1)={\mathrm{\aleph }}_{T(n)}(n\in \omega ),$

so that $T(1)={\mathrm{\aleph }}_{{\mathrm{\aleph }}_0}={\mathrm{\aleph }}_{\omega }$ and $T(2)={\mathrm{\aleph }}_{{\mathrm{\aleph }}_{\omega }}$ (The successor cardinal ${\kappa }^{+}$, the alephs ${\mathrm{\aleph }}_{\alpha }$, the beths ${\mathrm{\beth }}_{\alpha }$, successor and limit cardinals, and the identifications ${\mathrm{\aleph }}_0=\omega$ and ${\mathrm{\aleph }}_1={\omega }_1$). Put

$\alpha =\sup \{T(n):n\in \omega \}=\bigcup \{T(n):n\in \omega \}\mathrm{.}$

Then

${\mathrm{\aleph }}_{\alpha }=\alpha ,\mathrm{cf}(\alpha )={\mathrm{\aleph }}_0,$

so $\alpha$ is an infinite cardinal (Cardinal (initial ordinal) and cardinality) fixed by the aleph operation, and it is singular (Cofinality $\mathrm{cf}(\alpha )$, and regular and singular cardinals).

So the aleph operation has fixed points, even though it is strictly increasing and satisfies $\beta \le {\mathrm{\aleph }}_{\beta }$ at every ordinal (The clauses at $0$, at a successor and at a limit determine exactly one operation $\alpha \mapsto {\mathrm{\aleph }}_{\alpha }$, in ZF, and — assuming the Axiom of Choice — exactly one operation $\alpha \mapsto {\mathrm{\beth }}_{\alpha }$; each value is an infinite cardinal, each is strictly increasing and continuous at limits, and $\alpha \le {\mathrm{\aleph }}_{\alpha }$). The power operation behaves differently: assuming the Axiom of Choice, so that $2^{\kappa }$ is a cardinal at all, $\kappa <2^{\kappa }$ at every cardinal (Assuming the Axiom of Choice, $2^{\kappa }=\mid \mathcal{P}(\kappa )\mid$, and Cantor's theorem in cardinal form: $\kappa <2^{\kappa }$), so there are no fixed points there at all. That comparison is an aside; nothing below uses it, and the example itself stays in ZF.