42.03.03 · mathematical-logic / set-theory-forcing

Cardinals and the Arithmetic of the Infinite

shipped3 tiersLean: none

Anchor (Master): Kunen 2011 *Set Theory* (College Publications) Ch. I §10-13 (the aleph and beth functions, Hessenberg's theorem κ·κ = κ via the canonical well-ordering of κ×κ, cardinal exponentiation, the continuum and CH/GCH, König's theorem); Jech 2003 *Set Theory* 3e (Springer) Ch. 3 and Ch. 5 (cardinal arithmetic, cofinality, König's inequality); Cantor 1895 *Math. Ann.* 46 (Beiträge I, the original cardinal theory and the aleph notation)

Intuition Beginner

Two herders, neither of whom can count past three, want to know who owns more sheep. They line their flocks up side by side and pair them off — one of yours next to one of mine — and keep going. If every sheep finds a partner with none left over, the flocks are the same size. If one side runs out first, that side is smaller. This pairing trick decides "same size" without ever naming a number. It is the whole idea behind measuring how big a collection is.

The surprise is that this trick keeps working past every finite number, and when it does it tells us something strange: not all infinities are the same. The counting numbers $0, 1, 2, 3, \dots$ can be paired off perfectly with the even numbers, so "infinitely many counting numbers" and "infinitely many even numbers" are the same size. A part can be as big as the whole. That never happens with finite collections, and it is the first sign that infinite sizes obey their own rules.

But here is the twist that started a whole subject: the points on a line cannot be paired off with the counting numbers, no matter how cleverly you try. There are strictly more of them. So there is a smallest infinity, the size of the counting numbers, and then bigger infinities above it, climbing forever. A cardinal number is a name for one of these sizes, finite or infinite, and the arithmetic of these names is what this unit is about.

Visual Beginner

To compare two collections, draw arrows pairing each item on the left with exactly one item on the right. A pairing that uses up both sides with nothing left over means "same size."

   counting numbers        even numbers
        0  ------------------>  0
        1  ------------------>  2
        2  ------------------>  4
        3  ------------------>  6
        4  ------------------>  8
       ...                     ...
       (n maps to 2n; every even number is hit exactly once)

The pairing above sends each counting number $n$ to the even number $2 n$ . Every even number is the partner of exactly one counting number, and nothing is left over on either side. So these two infinite collections have the same size, even though one looks like only "half" of the other.

The next table records the first few sizes. The finite sizes are the ordinary counts. Then comes the smallest infinite size, written $ℵ_{0}$ ("aleph-zero"), the size of the counting numbers. Above it sits a strictly larger infinite size, the number of points on a line.

collection	size
${}$ (nothing)	$0$
${a, b, c}$	$3$
all counting numbers	$ℵ_{0}$ (smallest infinity)
all even numbers	$ℵ_{0}$ (same as above)
all points on a line	bigger than $ℵ_{0}$

The key idea: "same size" means "can be paired off exactly," and once you allow infinite collections, this gives a ladder of infinite sizes, each strictly bigger than the last.

Worked example Beginner

Let us show by hand that there are exactly as many counting numbers as there are pairs of counting numbers — a result that feels impossible, since pairs look far more plentiful.

We want to pair off each spot in an endless grid with a single counting number, missing none. Picture the pairs $(a, b)$ laid out as a grid: row $a$ , column $b$ . Instead of reading across a row (which never ends, so we would never reach the next row), we walk along the diagonals.

Step 1. The first diagonal holds just $(0, 0)$ . Give it the number $0$ .

Step 2. The next diagonal holds $(1, 0)$ and $(0, 1)$ . Give them $1$ and $2$ .

Step 3. The next diagonal holds $(2, 0), (1, 1), (0, 2)$ . Give them $3, 4, 5$ .

Step 4. The next diagonal holds four pairs. Give them $6, 7, 8, 9$ .

Because each diagonal is finite, we finish it and move on, and every pair sits on exactly one diagonal, so every pair eventually gets a number. No pair is skipped and no number is used twice.

Step 5. Count the labels handed out before reaching diagonal number $d$ : the diagonals before it hold $1 + 2 + 3 + \dots + d$ pairs. For $d = 4$ that is $1 + 2 + 3 + 4 = 10$ pairs already labelled $0$ through $9$ , so the pair $(4, 0)$ at the start of diagonal $4$ gets the number $10$ .

What this tells us: the grid of all pairs, which looks two-dimensional and far bigger, is still only $ℵ_{0}$ in size. Bundling counting numbers into pairs does not escape the smallest infinity. This is the seed of the rule that for infinite sizes, multiplying a size by itself gives back the same size.

Check your understanding Beginner

Exercise (easy, multiple-choice).

Which statement about the points on a line is correct, according to Cantor's discovery?

They can be paired off exactly with the counting numbers.
There are strictly more of them than there are counting numbers.
There are fewer of them than there are counting numbers.
There are exactly as many as there are even numbers only.

Hint

The counting numbers, the even numbers, and the pairs all have the same size $ℵ_{0}$ . The line is the odd one out.

Answer

B. The points on a line cannot be paired off with the counting numbers; there are strictly more of them. Feedback-correct: this is the first jump up the ladder of infinite sizes. Feedback-wrong: options A and D claim the line has size $ℵ_{0}$ , which Cantor's diagonal argument rules out; option C reverses the inequality.

Formal definition Intermediate+

All of the following takes place inside ZFC (cross-ref 42.03.01), and the ordinals, transfinite recursion, and the well-ordering of $On$ are as developed in 42.03.02; the Axiom of Choice is assumed throughout except where its omission is flagged.

Two sets $A, B$ are equinumerous, written $A \approx B$ , when there is a bijection $A \to B$ . Write $A ⪯ B$ when there is an injection $A \to B$ , and $A ≺ B$ when $A ⪯ B$ but $A \neq \approx B$ . The relation $\approx$ is an equivalence relation on sets, and $⪯$ is a preorder; the Cantor-Schröder-Bernstein theorem (next section) shows $⪯$ is antisymmetric up to $\approx$ .

A cardinal is an initial ordinal: an ordinal $κ$ such that no $α < κ$ satisfies $α \approx κ$ ^{[Kunen Ch. I §11]}. Every natural number is a cardinal, $ω$ is the least infinite cardinal, and under Choice every set $A$ is equinumerous with a unique cardinal $∣ A ∣$ , its cardinality — for $A$ can be well-ordered (cross-ref 42.03.02), hence is equinumerous with some ordinal, and $∣ A ∣$ is the least such ordinal. The infinite cardinals are enumerated by the aleph function, defined by transfinite recursion: $ℵ_{0} = ω$ ; $ℵ_{α + 1} = ℵ_{α}^{+}$ , the least cardinal strictly greater than $ℵ_{α}$ ; and $ℵ_{λ} = sup_{β < λ} ℵ_{β}$ at limits. One also writes $ω_{α}$ for $ℵ_{α}$ when emphasizing its role as an ordinal. The alephs are strictly increasing, and every infinite cardinal is some $ℵ_{α}$ ; the cardinals, like the ordinals, are well-ordered.

For cardinals $κ, λ$ , cardinal addition and multiplication are defined by $$ \kappa \oplus \lambda = |\kappa \sqcup \lambda|, \qquad \kappa \otimes \lambda = |\kappa \times \lambda|, $$ where $⊔$ is disjoint union; these are commutative and associative and agree with ordinary arithmetic on finite cardinals. Cardinal exponentiation is $κ^{λ} = ∣^{λ} κ ∣$ , the cardinality of the set of all functions $λ \to κ$ . The continuum is $c = 2^{ℵ_{0}} = ∣ P (ω) ∣ = ∣ R ∣$ . The beth function is $ℶ_{0} = ℵ_{0}$ , $ℶ_{α + 1} = 2^{ℶ_{α}}$ , $ℶ_{λ} = sup_{β < λ} ℶ_{β}$ .

A set is finite if equinumerous with some $n < ω$ , countable if $⪯ ω$ , countably infinite if $\approx ω$ , and uncountable otherwise. A set is Dedekind-infinite if it is equinumerous with a proper subset of itself; under Choice this coincides with being infinite.

Counterexamples to common slips Intermediate+

"Cardinal arithmetic is just ordinal arithmetic." It is not: cardinal operations record only size, ordinal operations record order type. Thus $ℵ_{0} \oplus ℵ_{0} = ℵ_{0}$ while $ω + ω \neq = ω$ , and $ℵ_{0} \otimes ℵ_{0} = ℵ_{0}$ while $ω \cdot ω \neq = ω$ . The same symbol $ω = ℵ_{0}$ names one object but carries two arithmetics.
" $2^{ℵ_{0}} = ℵ_{1}$ is a theorem." It is the Continuum Hypothesis, independent of ZFC (cross-ref 42.03.06, 42.03.08). ZFC proves $2^{ℵ_{0}} > ℵ_{0}$ (Cantor) and $cf (2^{ℵ_{0}}) > ℵ_{0}$ (König), so $2^{ℵ_{0}} \neq = ℵ_{ω}$ , but it does not pin the value.
"If $A$ is infinite then $A \approx ω$ ." Only countable infinite sets satisfy this. $R$ is infinite and uncountable; $ω ≺ R$ strictly, by Cantor's theorem.
" $⪯$ might fail to be antisymmetric, so cardinalities could be incomparable." Cantor-Schröder-Bernstein gives antisymmetry without Choice; linearity (trichotomy of cardinals) needs the well-ordering theorem (cross-ref 42.03.02, 42.03.05) and is equivalent to Choice.

Key theorem with proof Intermediate+

The organising theorem of infinite cardinal arithmetic is that addition and multiplication of infinite cardinals collapse entirely: they are governed by the single operation $max$ . Everything interesting about cardinal arithmetic is thereby pushed into exponentiation, which is where independence lives.

Theorem (Hessenberg; absorption of infinite sums and products). For an infinite cardinal $κ$ , $κ \otimes κ = κ$ . Consequently, for infinite cardinals $κ, λ$ with $λ \leq κ$ and $κ$ infinite, $$ \kappa \oplus \lambda = \kappa \otimes \lambda = \kappa = \max(\kappa, \lambda) $$ (the product requiring $λ \neq = 0$ ) ^{[Kunen Ch. I §12]}.

Proof. The core is $κ \otimes κ = κ$ , proved by transfinite induction on the infinite cardinal $κ$ . Define the canonical (Gödel) well-ordering $⊲$ of $On \times On$ by $$ (\alpha_1, \beta_1) \lhd (\alpha_2, \beta_2) \iff \begin{cases} \max(\alpha_1,\beta_1) < \max(\alpha_2,\beta_2), \text{ or}\ \max(\alpha_1,\beta_1) = \max(\alpha_2,\beta_2) \text{ and } (\alpha_1,\beta_1) <_{\text{lex}} (\alpha_2,\beta_2), \end{cases} $$ comparing first by the larger coordinate, then lexicographically. This is a well-ordering: any nonempty class has an element minimising $max$ , among which one minimises $α$ , among which one minimises $β$ .

Let $Γ (α, β)$ be the order type of the initial segment of $⊲$ below $(α, β)$ . The claim is that $Γ$ restricts to a bijection $κ \times κ \to κ$ for every infinite cardinal $κ$ , which gives $κ \otimes κ = κ$ .

Induct on $κ$ . Suppose $μ \otimes μ = μ$ for every infinite cardinal $μ < κ$ . Let $(α, β) \in κ \times κ$ and set $γ = max (α, β) + 1$ , so $γ < κ$ (as $κ$ is a limit ordinal, being an infinite cardinal). Every pair $⊲ (α, β)$ has both coordinates $< γ$ , so the segment below $(α, β)$ embeds into $γ \times γ$ , giving $Γ (α, β) \leq ∣ γ \times γ ∣ = ∣ γ ∣ \otimes ∣ γ ∣$ . Now $∣ γ ∣ < κ$ . If $γ$ is finite the product is finite $< κ$ ; if $γ$ is infinite then by the induction hypothesis $∣ γ ∣ \otimes ∣ γ ∣ = ∣ γ ∣ < κ$ . Either way $Γ (α, β) < κ$ . Hence $Γ$ maps $κ \times κ$ into $κ$ ; it is injective (order-preserving for a well-order) and its image is an initial segment of $κ$ , in fact all of $κ$ since $κ \times κ$ surjects onto $κ$ via the first coordinate (so the image has size $\geq κ$ ). Thus $Γ : κ \times κ \to κ$ is a bijection and $κ \otimes κ = κ$ .

The absorption laws follow. For $0 < λ \leq κ$ with $κ$ infinite, $$ \kappa \le \kappa \oplus \lambda \le \kappa \oplus \kappa = 2 \otimes \kappa \le \kappa \otimes \kappa = \kappa, $$ and $κ \leq κ \otimes λ \leq κ \otimes κ = κ$ , so by Cantor-Schröder-Bernstein all the displayed quantities equal $κ = max (κ, λ)$ . $□$

Bridge. The collapse $κ \oplus λ = κ \otimes λ = max (κ, λ)$ is the foundational reason cardinal arithmetic looks deceptively simple at the additive and multiplicative level: the two operations carry no information beyond which cardinal is larger, so this is exactly where ordinal arithmetic and cardinal arithmetic part ways — the order-type memory of 42.03.02 is discarded and only size remains. It builds toward exponentiation, the one operation that survives the collapse: $2^{κ} > κ$ always holds (Cantor's theorem, proved below), and the value of $2^{ℵ_{0}}$ is not decided by ZFC, which is where the Continuum Hypothesis and the independence results of 42.03.06 and 42.03.08 enter. The canonical well-ordering $⊲$ generalises the order-type machinery of 42.03.02 and is dual to the cofinality analysis of 42.03.04, where König's theorem sharpens "exponentiation is large" into " $cf (2^{κ}) > κ$ ." Putting these together, the central insight is that the entire content of cardinal arithmetic migrates into the exponential, and the alephs constructed here are exactly the cardinals consumed by Morley's categoricity theorem 42.02.06 pending, where "categorical in some uncountable power" means categorical in every $ℵ_{α}$ with $α \geq 1$ . This appears again whenever a transfinite construction must count its stages by a cardinal rather than an ordinal.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove the Cantor-Schröder-Bernstein theorem: if $A ⪯ B$ and $B ⪯ A$ then $A \approx B$ . (Do not assume Choice.)

Hint

Let $f : A \to B$ and $g : B \to A$ be injections. Partition $A$ by the chains generated by $g^{- 1}, f^{- 1}$ according to where the chain originates, and define a bijection piecewise.

Answer

Let $f : A \to B$ , $g : B \to A$ be injections. Call $a \in A$ a B-origin point if iterating $g^{- 1}, f^{- 1}, g^{- 1}, \dots$ from $a$ terminates at a point of $B ∖ f [A]$ , an A-origin point if it terminates in $A ∖ g [B]$ , and a no-origin point if the iteration never terminates. These three classes partition $A$ . Define $h : A \to B$ by $h (a) = f (a)$ on the $A$ -origin and no-origin points and $h (a) = g^{- 1} (a)$ on the $B$ -origin points (where $g^{- 1}$ is defined since such $a \in g [B]$ ). Then $h$ is a bijection: on each class the maps are injective and their images partition $B$ by the symmetric classification of $B$ . Concretely, $f$ restricted to the $A$ -origin/no-origin part lands exactly on the $A$ -origin/no-origin part of $B$ , and $g^{- 1}$ on the $B$ -origin part of $A$ lands on the $B$ -origin part of $B$ . Rubric: full credit for the chain/origin partition, the piecewise definition, and verifying bijectivity by the matched classification on $B$ .

Exercise 5 (medium, symbolic).

Prove that $∣ R ∣ = 2^{ℵ_{0}}$ , i.e. the reals are equinumerous with $P (ω)$ .

Hint

Inject $P (ω) \to R$ by binary expansions and $R \to P (ω)$ via Dedekind cuts of rationals, then apply Cantor-Schröder-Bernstein.

Answer

Inject $P (ω) \to R$ by sending $S \subseteq ω$ to the number $\sum_{n \in S} 3^{- (n + 1)}$ (base- $3$ digits in ${0, 1}$ avoids the double-counting of binary $0.0111 \dots = 0.1000 \dots$ , so the map is injective). Hence $2^{ℵ_{0}} ⪯ ∣ R ∣$ . Conversely inject $R \to P (Q)$ by $r \mapsto {q \in Q : q < r}$ , the Dedekind cut, which is injective since the rationals are dense; and $∣ P (Q) ∣ = 2^{∣ Q ∣} = 2^{ℵ_{0}}$ as $∣ Q ∣ = ℵ_{0}$ . So $∣ R ∣ ⪯ 2^{ℵ_{0}}$ . Cantor-Schröder-Bernstein gives $∣ R ∣ = 2^{ℵ_{0}}$ . Rubric: full credit for both injections (with the base- $3$ or equivalent fix for binary ambiguity) and the appeal to Cantor-Schröder-Bernstein.

Exercise 6 (hard, symbolic).

Prove König's theorem in the form $κ < κ^{cf (κ)}$ for every infinite cardinal $κ$ , and deduce $cf (2^{ℵ_{0}}) > ℵ_{0}$ , hence $2^{ℵ_{0}} \neq = ℵ_{ω}$ . (You may use the general König inequality $\sum_{i} κ_{i} < \prod_{i} λ_{i}$ when $κ_{i} < λ_{i}$ for all $i$ ; cofinality is developed in 42.03.04.)

Hint

Write $κ = \sum_{i < cf (κ)} κ_{i}$ with each $κ_{i} < κ$ , and apply the König inequality with $λ_{i} = κ$ .

Answer

Let $μ = cf (κ)$ and write $κ = sup_{i < μ} κ_{i}$ as an increasing union with each $κ_{i} < κ$ , so $κ = \sum_{i < μ} κ_{i}$ (the sum is $\geq κ$ by the sup, $\leq μ \otimes κ = κ$ by absorption). Apply the König inequality with $λ_{i} = κ$ for all $i$ : since $κ_{i} < κ = λ_{i}$ , $$ \kappa = \sum_{i<\mu} \kappa_i < \prod_{i<\mu} \kappa = \kappa^\mu = \kappa^{\operatorname{cf}(\kappa)}. $$ For the corollary, set $θ = 2^{ℵ_{0}}$ and suppose $cf (θ) = ℵ_{0}$ . Then König gives $θ < θ^{cf (θ)} = θ^{ℵ_{0}} = (2^{ℵ_{0}})^{ℵ_{0}} = 2^{ℵ_{0} \otimes ℵ_{0}} = 2^{ℵ_{0}} = θ$ , a contradiction. So $cf (2^{ℵ_{0}}) > ℵ_{0}$ . Since $cf (ℵ_{ω}) = ℵ_{0}$ , the continuum cannot be $ℵ_{ω}$ . Rubric: full credit for the sum-representation along cofinality, the König-inequality application, and the cofinality contradiction with the exponent law $(2^{ℵ_{0}})^{ℵ_{0}} = 2^{ℵ_{0}}$ .

Exercise 7 (hard, symbolic).

Prove the exponent laws $κ^{λ \oplus μ} = κ^{λ} \otimes κ^{μ}$ and $(κ^{λ})^{μ} = κ^{λ \otimes μ}$ , and use them with Cantor's theorem to show that for $2 \leq κ \leq 2^{ℵ_{0}}$ one has $κ^{ℵ_{0}} = 2^{ℵ_{0}}$ .

Hint

The first two are bijections of function sets: $^{λ ⊔ μ} κ \approx^{λ} κ \times^{μ} κ$ and $^{μ} (^{λ} κ) \approx^{λ \times μ} κ$ (currying). For the last, sandwich with monotonicity.

Answer

A function $λ ⊔ μ \to κ$ is the same datum as a pair of functions $λ \to κ$ and $μ \to κ$ (restrict to each part), giving a bijection $^{λ ⊔ μ} κ \approx^{λ} κ \times^{μ} κ$ , hence $κ^{λ \oplus μ} = κ^{λ} \otimes κ^{μ}$ . Currying gives a bijection $^{μ} (^{λ} κ) \approx^{λ \times μ} κ$ (a function of $μ$ returning a function of $λ$ is a function of $λ \times μ$ ), hence $(κ^{λ})^{μ} = κ^{λ \otimes μ}$ . Now for $2 \leq κ \leq 2^{ℵ_{0}}$ , monotonicity of exponentiation gives $$ 2^{\aleph_0} \le \kappa^{\aleph_0} \le (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 \otimes \aleph_0} = 2^{\aleph_0}, $$ so $κ^{ℵ_{0}} = 2^{ℵ_{0}}$ by Cantor-Schröder-Bernstein. Rubric: full credit for the two bijections (disjoint-union and currying), the monotone sandwich, and the use of $ℵ_{0} \otimes ℵ_{0} = ℵ_{0}$ .

Advanced results Master

The collapse of $\oplus$ and $\otimes$ leaves exponentiation as the sole carrier of arithmetic content, and the structure of $κ \mapsto 2^{κ}$ is the deep question. The alephs and beths frame it; König's theorem and cofinality constrain it; the Continuum Hypothesis names the one value ZFC refuses to decide.

Theorem 1 (Cantor's theorem and the strict tower). For every cardinal $κ$ , $κ < 2^{κ}$ ^{[Cantor 1895]}. The injection $κ \to P (κ)$ , $α \mapsto {α}$ , and the diagonal non-surjectivity of any $F : κ \to P (κ)$ via $D = {α : α \in / F (α)}$ give the strict inequality. Iterating produces the beth tower $ℶ_{0} = ℵ_{0} < ℶ_{1} = 2^{ℵ_{0}} < ℶ_{2} = 2^{2^{ℵ_{0}}} < \dots$ , and $ℶ_{α} \geq ℵ_{α}$ for all $α$ with equality for all $α$ exactly under the Generalized Continuum Hypothesis.

Theorem 2 (absorption and the arithmetic of alephs). For infinite cardinals, $ℵ_{α} \oplus ℵ_{β} = ℵ_{α} \otimes ℵ_{β} = ℵ_{m a x (α, β)}$ ^{[Kunen Ch. I §12]}, a restatement of Hessenberg's theorem. Infinite sums and products also collapse: if $κ_{i} \leq κ$ for $i < λ$ with $λ \leq κ$ infinite and some $κ_{i}$ infinite, then $\sum_{i < λ} κ_{i} = sup_{i} κ_{i} \cdot λ = max (sup_{i} κ_{i}, λ)$ . The whole additive-multiplicative theory of infinite cardinals is thereby decidable in ZFC; only exponentiation escapes.

Theorem 3 (König's theorem). If $κ_{i} < λ_{i}$ for all $i \in I$ , then $\sum_{i \in I} κ_{i} < \prod_{i \in I} λ_{i}$ ^{[Jech Ch. 5]}. The corollary $κ < κ^{cf (κ)}$ yields $cf (2^{κ}) > κ$ , the one substantive ZFC constraint on the continuum function: $2^{ℵ_{0}}$ can consistently be $ℵ_{1}, ℵ_{2}, ℵ_{17}, ℵ_{ω + 1}, \dots$ but never $ℵ_{ω}$ or any cardinal of countable cofinality. The full refinement — regular versus singular cardinals, the Singular Cardinals Hypothesis, and Easton's freedom theorem for regular cardinals — is the subject of 42.03.04.

Theorem 4 (the Continuum Hypothesis, stated). CH asserts $2^{ℵ_{0}} = ℵ_{1}$ , equivalently $ℶ_{1} = ℵ_{1}$ , equivalently every uncountable set of reals is equinumerous with $R$ . GCH asserts $2^{ℵ_{α}} = ℵ_{α + 1}$ for all $α$ , equivalently $ℶ_{α} = ℵ_{α}$ for all $α$ . Both are independent of ZFC: Gödel's constructible universe $L$ 42.03.06 models GCH (so they are consistent), and Cohen's forcing 42.03.08 produces models of $\neg$ CH (so they are not provable). Under GCH, exponentiation is completely determined: $κ^{λ}$ equals $κ^{+}$ , $κ$ , or $λ^{+}$ according to the relation of $λ$ to $κ$ and $cf (κ)$ .

Synthesis. The foundational reason cardinal arithmetic splits into a decidable part and an undecidable part is the absorption theorem: $\oplus$ and $\otimes$ on infinite cardinals are $max$ , so they retain nothing of the well-ordering data of 42.03.02, and this is exactly what concentrates all arithmetic content into exponentiation. The central insight is that ZFC pins down $2^{κ}$ only through two facts — Cantor's $2^{κ} > κ$ and König's $cf (2^{κ}) > κ$ — and these are dual: Cantor's diagonal gives strict increase, König's diagonal-across-a-cofinal-sequence gives the cofinality bar, the same argument run once versus run along a cofinal family. Putting these together, the continuum function $κ \mapsto 2^{κ}$ on regular cardinals is free up to monotonicity and the König bound (Easton), and this is the bridge to 42.03.04 (where cofinality and the singular-cardinal refinement live) and to the independence units 42.03.06 and 42.03.08 (where $L$ forces GCH and Cohen forcing breaks CH). The alephs assembled here are dual to the model-theoretic spectrum: Morley's theorem 42.02.06 pending says a countable theory categorical in one uncountable $ℵ_{α}$ is categorical in all of them, so the well-ordering of cardinals proved here is precisely what makes "uncountably categorical" a single property rather than a family indexed by $α$ . The whole edifice generalises the counting theorem of 42.03.02: there a well-order has a unique ordinal type; here a set has a unique cardinal, the least ordinal of its size, and the arithmetic of these least-ordinals is what the unit computes.

Full proof set Master

Proposition 1 (every infinite cardinal is a limit ordinal). If $κ$ is an infinite cardinal then $κ$ is a limit ordinal.

Proof. Suppose $κ = α + 1$ were a successor. The map $α + 1 \to α$ sending $0 \mapsto$ (some fixed point of $α$ , possible as $α$ is infinite) and shifting is a bijection; concretely, since $α$ is infinite there is a bijection $α \approx α + 1$ (Dedekind-infiniteness: pick an injection $ω ↪ α$ and use the shift $n \mapsto n + 1$ on the copy of $ω$ , identity elsewhere, to absorb one extra point). Then $κ = α + 1 \approx α < κ$ , contradicting that $κ$ is initial. Hence $κ$ is not a successor, and being infinite it is not $0$ , so it is a limit ordinal. $□$

Proposition 2 (Cantor-Schröder-Bernstein). If $A ⪯ B$ and $B ⪯ A$ then $A \approx B$ , provably in ZF (no Choice).

Proof. Let $f : A \to B$ , $g : B \to A$ be injections. Set $C_{0} = A ∖ g [B]$ and $C_{n + 1} = g [f [C_{n}]]$ , and $C = ⋃_{n < ω} C_{n}$ . Define $h : A \to B$ by $h (x) = f (x)$ if $x \in C$ and $h (x) = g^{- 1} (x)$ if $x \in / C$ (for $x \in / C \supseteq C_{0}$ we have $x \in g [B]$ , so $g^{- 1} (x)$ is defined). Injectivity: $f$ and $g^{- 1}$ are each injective, and their images are disjoint — if $f (x) = g^{- 1} (y)$ with $x \in C$ , $y \in / C$ , then $y = g (f (x)) \in g [f [C_{n}]] = C_{n + 1} \subseteq C$ , contradiction. Surjectivity: given $b \in B$ , if $g (b) \in C$ then $g (b) \in C_{n + 1}$ for some $n$ (it is not in $C_{0} = A ∖ g [B]$ ), so $g (b) = g (f (x))$ with $x \in C_{n}$ , whence $b = f (x) = h (x)$ ; if $g (b) \in / C$ then $b = g^{- 1} (g (b)) = h (g (b))$ . So $h$ is a bijection. $□$

Proposition 3 (Cantor's theorem). For every set $A$ , there is no surjection $A \to P (A)$ ; hence $A ≺ P (A)$ .

Proof. Let $F : A \to P (A)$ be any function and put $D = {a \in A : a \in / F (a)}$ , a subset of $A$ by Separation. If $D = F (d)$ for some $d$ , then $d \in D ⟺ d \in / F (d) = D$ , impossible. So $D$ is not in the range of $F$ and $F$ is not surjective. The singleton map $a \mapsto {a}$ injects $A$ into $P (A)$ , so $A ⪯ P (A)$ and, no surjection existing, $A \neq \approx P (A)$ , giving $A ≺ P (A)$ . $□$

Proposition 4 (uncountability of $R$ by diagonalisation). The set ${0, 1}^{ω}$ of infinite binary sequences is uncountable, and $∣ R ∣ = 2^{ℵ_{0}} > ℵ_{0}$ .

Proof. Suppose $s : ω \to {0, 1}^{ω}$ enumerated all binary sequences. Define $d \in {0, 1}^{ω}$ by $d (n) = 1 - s (n) (n)$ , flipping the $n$ -th bit of the $n$ -th listed sequence. Then $d$ differs from $s (n)$ at coordinate $n$ for every $n$ , so $d$ is not in the range of $s$ , contradicting that $s$ enumerates all sequences. Hence ${0, 1}^{ω}$ is uncountable; since $∣ {0, 1}^{ω} ∣ = 2^{ℵ_{0}}$ and (Exercise 5) $∣ R ∣ = 2^{ℵ_{0}}$ , the reals are uncountable. This is the special case of Proposition 3 at $A = ω$ , the diagonal set $D$ being read as the flipped sequence $d$ . $□$

Proposition 5 (Hessenberg, $κ \otimes κ = κ$ ). For every infinite cardinal $κ$ , the canonical well-ordering $⊲$ of $κ \times κ$ has order type $κ$ .

Proof. This is the core of the Key theorem; restated as a standalone proposition for the proof set. By transfinite induction on infinite cardinals $κ$ , assuming $μ \otimes μ = μ$ for infinite $μ < κ$ . For $(α, β) \in κ \times κ$ let $γ = max (α, β) + 1 < κ$ (Proposition 1 gives $κ$ a limit). The $⊲$ -segment below $(α, β)$ injects into $γ \times γ$ , so its order type is $\leq ∣ γ ∣ \otimes ∣ γ ∣$ , which is $< κ$ (finite if $γ$ finite; equal to $∣ γ ∣ < κ$ by the induction hypothesis if $γ$ infinite). Thus the order type $Γ$ maps $κ \times κ$ into $κ$ ; it is an order isomorphism onto an initial segment, and since the first-coordinate projection shows $∣ κ \times κ ∣ \geq κ$ , the image is all of $κ$ . Hence $κ \otimes κ = ∣ κ \times κ ∣ = κ$ . $□$

Proposition 6 (König's inequality). If $κ_{i} < λ_{i}$ for all $i \in I$ then $\sum_{i \in I} κ_{i} < \prod_{i \in I} λ_{i}$ .

Proof. That $\leq$ holds is routine. For strictness, suppose $G : ⨆_{i} κ_{i} \to \prod_{i} λ_{i}$ is given; it suffices to show $G$ is not surjective. For each $i$ , the $i$ -th coordinates ${G (x) (i) : x \in κ_{i} -block}$ form a subset of $λ_{i}$ of size $\leq ∣ κ_{i} ∣ = κ_{i} < λ_{i}$ , so there is $f (i) \in λ_{i}$ omitted by every $G (x)$ with $x$ in the $i$ -th block. (Choosing such $f (i)$ uses the Axiom of Choice across $i \in I$ .) The function $f = (f (i))_{i} \in \prod_{i} λ_{i}$ then differs from every $G (x)$ : if $x$ lies in the $i$ -th block, $G (x) (i) \neq = f (i)$ by construction. So $f \in / ran (G)$ and $G$ is not surjective. This is the diagonal argument of Proposition 3 run simultaneously in every coordinate. $□$

Connections Master

Cofinality and the Singular Cardinals Hypothesis 42.03.04 are the direct continuation of this unit's exponentiation theory: König's theorem proved here gives the bound $cf (2^{κ}) > κ$ , and 42.03.04 develops the machinery (regular versus singular cardinals, $cf (κ)$ , Easton's theorem freeing the continuum function on regular cardinals, the much harder Singular Cardinals problem) that says exactly how free the map $κ \mapsto 2^{κ}$ is. This unit owns the absorption laws and the statement of König's theorem; 42.03.04 owns the cofinality refinement and the singular-cardinal arithmetic that the absorption laws cannot reach.
The constructible universe $L$ 42.03.06 is where the Generalized Continuum Hypothesis stated here becomes a theorem: Gödel's inner model satisfies $2^{ℵ_{α}} = ℵ_{α + 1}$ for all $α$ (equivalently $ℶ_{α} = ℵ_{α}$ ), via a condensation argument that bounds the number of subsets of $ℵ_{α}$ appearing in $L$ by $ℵ_{α + 1}$ . The alephs and the beth function defined in this unit are exactly the objects whose coincidence GCH asserts, and the independence of CH from ZFC (forcing, 42.03.08) is the complementary half — $L$ shows CH is consistent, Cohen's models show $\neg$ CH is consistent.
Morley's categoricity theorem 42.02.06 pending consumes the well-ordering of the uncountable cardinals established here: its statement is that a countable first-order theory categorical in some uncountable cardinal $ℵ_{α}$ ( $α \geq 1$ ) is categorical in every uncountable cardinal. That this is a dichotomy — countable versus all-uncountable — rather than a per-cardinal phenomenon depends on the alephs being well-ordered with $ℵ_{1}$ the least uncountable one, so the transfinite induction up the cardinal ladder that drives the proof (counting types over models of each successive size) has the order type supplied by this unit.

Historical & philosophical context Master

The cardinal numbers originate with Georg Cantor, who isolated Mächtigkeit (power, cardinality) as the invariant of a set under bijection and proved in an 1874 Crelle paper that the algebraic numbers are countable while the reals are not — the first theorem distinguishing two infinite sizes. The diagonal argument in its clean form appeared in his 1891 note in the Jahresbericht der Deutschen Mathematiker-Vereinigung, yielding both the uncountability of the reals and the general theorem $∣ A ∣ < ∣ P (A) ∣$ . Cantor's 1895 Beiträge zur Begründung der transfiniten Mengenlehre I ^{[Cantor 1895]} fixed the aleph notation, defined cardinal addition, multiplication, and exponentiation through disjoint unions, products, and function sets, and conjectured the Continuum Hypothesis $2^{ℵ_{0}} = ℵ_{1}$ ; he was unable to prove the comparability of cardinals, which Zermelo's 1904 well-ordering theorem later supplied from the Axiom of Choice.

The absorption theorem $κ \otimes κ = κ$ is due to Gerhard Hessenberg in his 1906 Grundbegriffe der Mengenlehre, with the canonical well-ordering of $On \times On$ later codified by Gödel in his 1940 monograph on $L$ . Julius König's 1905 inequality $\sum κ_{i} < \prod λ_{i}$ corrected an earlier flawed attempt by König to refute the Continuum Hypothesis and remains the only substantive ZFC constraint on $2^{κ}$ . Hilbert placed the Continuum Hypothesis first among his 1900 problems; Gödel proved in 1938-1940 that CH and GCH hold in the constructible universe, hence are consistent with ZFC ^{[Kunen Ch. I §13]}, and Paul Cohen proved in 1963 that $\neg$ CH is also consistent, inventing forcing for the purpose. The standard modern developments are Kunen's ^{[Kunen Ch. I §10-13]} and Jech's ^{[Jech Ch. 3]}, from which the present treatment of cardinality, the absorption laws, and exponentiation is drawn.

Bibliography Master

@book{kunen2011set,
  author    = {Kunen, Kenneth},
  title     = {Set Theory},
  series    = {Studies in Logic},
  volume    = {34},
  publisher = {College Publications},
  year      = {2011}
}

@book{jech2003set,
  author    = {Jech, Thomas},
  title     = {Set Theory},
  edition   = {3},
  series    = {Springer Monographs in Mathematics},
  publisher = {Springer},
  year      = {2003}
}

@article{cantor1895beitraege,
  author  = {Cantor, Georg},
  title   = {Beitr{\"a}ge zur Begr{\"u}ndung der transfiniten Mengenlehre I},
  journal = {Mathematische Annalen},
  volume  = {46},
  year    = {1895},
  pages   = {481--512}
}

@article{cantor1891diagonal,
  author  = {Cantor, Georg},
  title   = {{\"U}ber eine elementare Frage der Mannigfaltigkeitslehre},
  journal = {Jahresbericht der Deutschen Mathematiker-Vereinigung},
  volume  = {1},
  year    = {1891},
  pages   = {75--78}
}

@article{koenig1905koenig,
  author  = {K{\"o}nig, Julius},
  title   = {Zum Kontinuum-Problem},
  journal = {Mathematische Annalen},
  volume  = {60},
  year    = {1905},
  pages   = {177--180}
}

@book{hessenberg1906grundbegriffe,
  author    = {Hessenberg, Gerhard},
  title     = {Grundbegriffe der Mengenlehre},
  publisher = {Vandenhoeck und Ruprecht},
  year      = {1906}
}

@book{goedel1940consistency,
  author    = {G{\"o}del, Kurt},
  title     = {The Consistency of the Continuum Hypothesis},
  series    = {Annals of Mathematics Studies},
  volume    = {3},
  publisher = {Princeton University Press},
  year      = {1940}
}

@article{cohen1963independence,
  author  = {Cohen, Paul J.},
  title   = {The Independence of the Continuum Hypothesis},
  journal = {Proceedings of the National Academy of Sciences},
  volume  = {50},
  year    = {1963},
  pages   = {1143--1148}
}

Prerequisites

42.03.02

Tier anchors

beginner: Halmos 1960 *Naive Set Theory* (Van Nostrand) §22-25 (equinumerosity, countable vs uncountable, the diagonal argument read by hand); Enderton 1977 *Elements of Set Theory* (Academic Press) Ch. 6 (cardinal numbers and the Cantor-Schröder-Bernstein theorem for the informal first pass)
intermediate: Kunen 2011 *Set Theory* (College Publications) Ch. I §10-11 (cardinality, the Cantor-Schröder-Bernstein theorem, Cantor's theorem and the uncountability of the reals, cardinals as initial ordinals, the aleph function, finite cardinal arithmetic); Enderton 1977 *Elements of Set Theory* (Academic Press) Ch. 6 (the parallel informal development)
master: Kunen 2011 *Set Theory* (College Publications) Ch. I §10-13 (the aleph and beth functions, Hessenberg's theorem κ·κ = κ via the canonical well-ordering of κ×κ, cardinal exponentiation, the continuum and CH/GCH, König's theorem); Jech 2003 *Set Theory* 3e (Springer) Ch. 3 and Ch. 5 (cardinal arithmetic, cofinality, König's inequality); Cantor 1895 *Math. Ann.* 46 (Beiträge I, the original cardinal theory and the aleph notation)

References

Kunen, K. — Set Theory · College Publications, Studies in Logic 34 (2011, revised edition). Chapter I §10-13 develops the theory of cardinality and cardinal arithmetic. §10 defines equinumerosity A ≈ B (the existence of a bijection), the partial preorder A ≼ B (an injection A → B), proves the Cantor-Schröder-Bernstein theorem that A ≼ B and B ≼ A imply A ≈ B (without Choice, by the back-and-forth/Banach decomposition), proves Cantor's theorem that A is never equinumerous with its power set P(A) by the diagonal argument, and deduces the uncountability of the reals via the binary expansion. §11 defines a cardinal as an initial ordinal — an ordinal not equinumerous with any smaller ordinal — observes that under the Axiom of Choice (well-ordering) every set is equinumerous with a unique cardinal |A|, introduces the aleph enumeration ℵ_α (ω_α) of the infinite cardinals by transfinite recursion (ℵ_0 = ω, ℵ_{α+1} the cardinal successor, ℵ_λ = sup_{β<λ} ℵ_β), and proves the alephs are well-ordered and unbounded. §12 develops cardinal addition κ ⊕ λ = |κ ⊔ λ| and multiplication κ ⊗ λ = |κ × λ|, proves Hessenberg's theorem κ ⊗ κ = κ for infinite κ via the canonical (maximum, then lexicographic) Gödel well-ordering of On × On whose order type below (κ,0) is κ, and derives the absorption law κ ⊕ λ = κ ⊗ λ = max(κ,λ) for infinite cardinals. §13 develops cardinal exponentiation κ^λ = |{}^λ κ|, identifies 2^{ℵ_0} = 𝔠 with the cardinality of the reals and of P(ω), defines the beth function ℶ_α by ℶ_0 = ℵ_0, ℶ_{α+1} = 2^{ℶ_α}, ℶ_λ = sup_{β<λ} ℶ_β, states the Continuum Hypothesis 2^{ℵ_0} = ℵ_1 and the Generalized Continuum Hypothesis 2^{ℵ_α} = ℵ_{α+1} (equivalently ℶ_α = ℵ_α), notes their independence from ZFC, and proves König's theorem that κ < κ^{cf(κ)} (so cf(2^κ) > κ), the one genuine theorem of ZFC constraining exponentiation.
Jech, T. — Set Theory · Springer Monographs in Mathematics, 3rd millennium edition (2003). Chapter 3 develops cardinal numbers: cardinality and the alephs as initial ordinals, the Cantor-Schröder-Bernstein theorem, Cantor's theorem, the well-ordering of cardinals under Choice, finite and infinite cardinal addition and multiplication with the theorem κ + λ = κ · λ = max(κ,λ) for infinite cardinals proved through the canonical well-ordering of the class of pairs (the Gödel pairing), and cardinal exponentiation. Chapter 5 develops cofinality and the arithmetic of exponentiation: regular and singular cardinals, the cofinality function cf(κ), König's theorem κ^{cf(κ)} > κ and its corollary cf(2^{ℵ_0}) > ℵ_0, the behaviour of 2^κ as a function of κ (Easton's theorem for regular κ, the harder Singular Cardinals problem), the beth function and the Generalized Continuum Hypothesis. The independence of CH (Cohen forcing, Gödel's L) is treated later (Chapters 13-15) and is the subject of the forcing units.
Cantor, G. — Beiträge zur Begründung der transfiniten Mengenlehre I · *Mathematische Annalen* 46 (1895), 481-512. Cantor's first Beiträge memoir introduces the cardinal numbers (his *Mächtigkeiten*, powers) as what is invariant under bijection, defines the order ≤ on cardinals and addition, multiplication, and exponentiation of cardinals in terms of disjoint unions, Cartesian products, and function sets, introduces the aleph notation ℵ_0 for the cardinality of the countable sets and the symbol 𝔠 = 2^{ℵ_0} for the power of the continuum, and states (without the later proof of comparability, which needs the well-ordering theorem) that the cardinals are linearly ordered; the diagonal argument and Cantor's theorem |A| < |P(A)| appear in his 1891 *Jahresbericht der DMV* note, and the Continuum Hypothesis 2^{ℵ_0} = ℵ_1 is Cantor's conjecture from this period and the first of Hilbert's 1900 problems.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m