Cardinal Arithmetic and the Power Set

Cardinal arithmetic underlies the modern classification of infinite structures throughout mathematics. In measure theory and analysis, the fact that $|\mathbb{R}| = 2^{\aleph_0}$ while the collection of Lebesgue measurable sets has cardinality $2^{2^{\aleph_0}}$ (strictly larger, by Cantor's theorem applied twice) explains why "almost all" subsets of $\mathbb{R}$ are non-measurable — there are simply too many subsets for a countably-additive measure to assign consistent values to each. In topology, cardinal invariants (density, weight, character of a space) are defined and compared using exactly this arithmetic, and theorems about compactness and metrizability often hinge on inequalities between such cardinals. In mathematical logic and model theory, the Löwenheim–Skolem theorems and the classification of models by cardinality (categoricity, stability theory) are stated entirely in the language of cardinal arithmetic developed here. In theoretical computer science, the fact that the set of all languages over a finite alphabet has cardinality $2^{\aleph_0}$ while the set of Turing machines (hence of decidable/recognizable languages) is only countable — a direct instance of Cantor's theorem — is the foundational argument proving that undecidable problems must exist. In statistics and probability, cardinal comparisons underlie the distinction between countable and uncountable sample spaces, dictating whether sums or integrals are the correct tool. Finally, in set-theoretic foundations, the independence of the Continuum Hypothesis, foreshadowed here, motivates entire research programs (forcing, inner model theory, large cardinal axioms) aimed at understanding just how much freedom exists in choosing the value of $2^{\aleph_0}$.

Ask the tutor: How does the independence of the Continuum Hypothesis actually get proved — what is "forcing," and why can't ZFC decide the value of $2^{\aleph_0}$?

For finite sets, these definitions recover ordinary arithmetic exactly: if $|A|=3$ and $|B|=2$, then $|A\cup B|=5$ when the union is disjoint, $|A\times B|=6$, and the number of functions from a 3-element set to a 2-element set is $2^3=8$, matching $\lambda^\kappa = 2^3$. The definitions are literally generalizations of grade-school counting, phrased in a way that makes sense even when $A$ or $B$ is infinite. The surprise begins with infinite cardinals: $\aleph_0 + \aleph_0 = \aleph_0$ (interleave two copies of $\mathbb{N}$), and even $\aleph_0 \cdot \aleph_0 = \aleph_0$ (Cantor's classical pairing of $\mathbb{N}\times\mathbb{N}$ with $\mathbb{N}$ via diagonals). Addition and multiplication of infinite cardinals turn out to be almost trivial — they just return the larger of the two cardinals. The real richness is in exponentiation: $2^{\aleph_0}$ is not $\aleph_0$, by Cantor's theorem, and pinning down exactly which cardinal it equals is one of the deepest open-ended questions in set theory. Below, a number-line-style picture contrasts the "flat" behavior of sums and products with the sudden jump caused by taking a power set.

Example 1: Computing $\aleph_0^{\aleph_0}$ and comparing it to $2^{\aleph_0}$. We compute $|{}^{\mathbb{N}}\mathbb{N}|$, the cardinality of the set of all functions $\mathbb{N} \to \mathbb{N}$ (equivalently, all infinite sequences of natural numbers), and show it equals $2^{\aleph_0}$, not something larger. Lower bound: $2^{\aleph_0} \le \aleph_0^{\aleph_0}$. Since $\{0,1\} \subseteq \mathbb{N}$, any function $\mathbb{N} \to \{0,1\}$ is in particular a function $\mathbb{N} \to \mathbb{N}$, giving an injection ${}^{\mathbb{N}}\{0,1\} \hookrightarrow {}^{\mathbb{N}}\mathbb{N}$ (inclusion of codomain). So $2^{\aleph_0} \le \aleph_0^{\aleph_0}$. Upper bound: $\aleph_0^{\aleph_0} \le 2^{\aleph_0}$. Encode a function $f: \mathbb{N} \to \mathbb{N}$ by its graph $G_f = \{(n, f(n)) : n \in \mathbb{N}\} \subseteq \mathbb{N} \times \mathbb{N}$. This is injective as a map $f \mapsto G_f$ from ${}^{\mathbb{N}}\mathbb{N}$ into $\mathcal{P}(\mathbb{N}\times\mathbb{N})$, since $f$ is recoverable from its graph. Because $\mathbb{N}\times\mathbb{N}$ is countable (a standard fact from Countable Sets, via the Cantor pairing function), fix a bijection $\mathbb{N}\times\mathbb{N} \leftrightarrow \mathbb{N}$; this induces $|\mathcal{P}(\mathbb{N}\times\mathbb{N})| = |\mathcal{P}(\mathbb{N})| = 2^{\aleph_0}$. Composing the two injections gives ${}^{\mathbb{N}}\mathbb{N} \hookrightarrow \mathcal{P}(\mathbb{N})$, so $\aleph_0^{\aleph_0} \le 2^{\aleph_0}$. By Schroeder-Bernstein Theorem, $\aleph_0^{\aleph_0} = 2^{\aleph_0}$. Concretely: even though $\mathbb{N}$ has "more room" than $\{0,1\}$ per coordinate, the countably-infinite number of coordinates makes the total no larger than the binary case — the exponent, not the base, controls growth once the base is infinite but at most $2^{\aleph_0}$.

Example 2: An asymmetric sum-product-power computation. Let $\kappa = 5$ (finite), $\lambda = \aleph_0$, $\mu = 2^{\aleph_0}$. Compute $\kappa + \lambda$, $\lambda \cdot \mu$, and $\kappa^{\mu}$, and compare to $\mu^\mu$. Computing $\kappa + \lambda = 5 + \aleph_0$. By the Lemma above (one cardinal infinite, both nonzero), $5 + \aleph_0 = \max(5,\aleph_0) = \aleph_0$. Concretely: take $\{0,1,2,3,4\}$ disjoint from $\mathbb{N}\times\{1\}$; a bijection with $\mathbb{N}$ sends $0,\dots,4$ to $0,\dots,4$ and shifts the copy of $\mathbb{N}$ up by $5$. So finite pieces are absorbed without changing the cardinality. Computing $\lambda \cdot \mu = \aleph_0 \cdot 2^{\aleph_0}$. By the Lemma, since $2^{\aleph_0}$ is infinite (it's $\ge \aleph_0$ by Cantor's theorem applied iteratively, or directly since $2^{\aleph_0} > \aleph_0$), $\aleph_0 \cdot 2^{\aleph_0} = \max(\aleph_0, 2^{\aleph_0}) = 2^{\aleph_0}$. Computing $\kappa^{\mu} = 5^{2^{\aleph_0}}$. We claim this equals $2^{2^{\aleph_0}}$. Indeed $2 \le 5 \le 2^5$ (as cardinals, since finite), so applying the (order-preserving in the base, for fixed exponent) monotonicity of exponentiation — if $\lambda_1 \le \lambda_2$ then $\lambda_1^\kappa \le \lambda_2^\kappa$, via post-composing functions $A \to B_1 \hookrightarrow B_2$ — we get

using the exponent law $(\lambda^{\kappa_1})^{\kappa_2} = \lambda^{\kappa_1 \cdot \kappa_2}$ (currying: a function $A_2 \to {}^{A_1}B$ corresponds bijectively to a function $A_1\times A_2 \to B$) and $5 \cdot 2^{\aleph_0} = 2^{\aleph_0}$ from the previous computation with the roles relabeled. Squeezing between equal ends, $5^{2^{\aleph_0}} = 2^{2^{\aleph_0}}$ by Schroeder-Bernstein. Comparing to $\mu^\mu = (2^{\aleph_0})^{2^{\aleph_0}}$. Using the exponent law again,

using $\aleph_0 \cdot 2^{\aleph_0} = 2^{\aleph_0}$ computed above. So remarkably $5^{2^{\aleph_0}} = \mu^\mu = 2^{2^{\aleph_0}}$: raising $2^{\aleph_0}$ to itself gives the same cardinal as raising any finite number $\ge 2$ to that power. This illustrates the general fact that for infinite $\mu$ and $2 \le \kappa \le \mu$, $\kappa^\mu = 2^\mu$, so the base becomes irrelevant once it's between $2$ and $\mu$.