Cardinal Arithmetic — Mathematics Knowledge System

Overview

Cardinal arithmetic defines addition, multiplication, and exponentiation on cardinal numbers — the sizes of sets, including infinite ones — via operations on disjoint unions, Cartesian products, and function sets. For finite cardinals these operations reduce to ordinary arithmetic, but for infinite cardinals the rules become strikingly different: adding or multiplying two infinite cardinals (assuming choice) simply returns the LARGER of the two, so ℵ₀+ℵ₀ = ℵ₀ and ℵ₀·ℵ₀ = ℵ₀, collapsing operations that would blow up in the finite world. Exponentiation is the one operation that still grows: Cantor's theorem guarantees 2^κ > κ for every cardinal κ, which is exactly why the reals (of cardinality 2^{ℵ₀}) form a strictly larger infinity than the naturals. This 'flattening' of addition/multiplication alongside genuine growth under exponentiation is the central, counterintuitive fact that makes infinite cardinal arithmetic behave so differently from arithmetic on finite numbers.

Intuition

With finite numbers, adding, multiplying, and exponentiating all make numbers bigger (for numbers > 1). With infinite cardinals, addition and multiplication essentially stall: combining two infinite collections, or pairing up every element of one with every element of another, doesn't actually get you MORE infinity than you started with — it's still just the size of the larger piece. Think of ℵ₀·ℵ₀: you might expect an infinite grid (ℕ×ℕ) to be 'more infinite' than a single row, but Cantor's classic zig-zag enumeration snakes through the whole grid hitting every cell exactly once, proving the grid is still only countably infinite. Exponentiation is different in kind: 2^κ counts all SUBSETS of a κ-sized set (via characteristic functions), and Cantor's diagonal argument shows you can never list all of them using only κ many labels — so exponentiation is the one operation that reliably manufactures a strictly bigger infinity every time.

Formal Definition

Definition

For cardinals κ = |A| and λ = |B| (with A, B disjoint where needed), define κ+λ = |A ⊔ B| (disjoint union), κ·λ = |A × B| (Cartesian product), and κ^λ = |A^B| (the set of functions from B to A). For infinite cardinals, the Absorption Law (provable from AC via well-ordering) states that if κ and λ are cardinals with at least one infinite and κ ≥ λ > 0, then κ+λ = κ·λ = κ. Cantor's theorem gives strict growth under exponentiation: κ < 2^κ for every cardinal κ, infinite or finite.

\kappa + \lambda = |A \sqcup B|,\quad \kappa \cdot \lambda = |A \times B|,\quad \kappa^{\lambda} = |A^{B}|

Definitions via disjoint union, product, and function sets

\kappa,\lambda \text{ infinite}, \; \kappa \ge \lambda \implies \kappa + \lambda = \kappa \cdot \lambda = \kappa

Absorption law (requires the Axiom of Choice)

\aleph_0 + \aleph_0 = \aleph_0, \qquad \aleph_0 \cdot \aleph_0 = \aleph_0

The countable case: ℵ₀ absorbs itself under + and ·

\kappa < 2^{\kappa}

Cantor's theorem: exponentiation always strictly increases cardinality

2^{\aleph_0} = |\mathbb{R}|

The continuum as 2 to the power ℵ₀

Derivation

Cantor's pairing argument: showing ℵ₀ · ℵ₀ = ℵ₀ by explicitly enumerating ℕ × ℕ.

\text{Arrange pairs } (m,n) \in \mathbb{N}\times\mathbb{N} \text{ in an infinite grid, indexed by row } m \text{ and column } n

Set up the grid to be counted

\text{Enumerate along successive anti-diagonals } m+n = 0, 1, 2, \ldots \text{, each of which is finite}

Each diagonal m+n=k contains exactly k+1 pairs — a finite batch

f(m,n) = \frac{(m+n)(m+n+1)}{2} + n

The Cantor pairing function: an explicit bijection ℕ×ℕ → ℕ

f \text{ is a bijection} \implies |\mathbb{N}\times\mathbb{N}| = |\mathbb{N}| \implies \aleph_0 \cdot \aleph_0 = \aleph_0

Since a bijection exists, the product has the same cardinality as ℕ itself

Properties

Absorption for addition

\aleph_0 + n = \aleph_0 \text{ for any finite } n, \text{ and } \aleph_0 + \aleph_0 = \aleph_0

Absorption for multiplication

\aleph_0 \cdot \aleph_0 = \aleph_0

Cantor's theorem

\kappa < 2^{\kappa} \text{ for every cardinal } \kappa

Continuum cardinality

2^{\aleph_0} = \mathfrak{c} \text{ (the cardinality of } \mathbb{R}\text{)}

Monotonicity

\kappa \le \lambda \implies \kappa + \mu \le \lambda + \mu \;\land\; \kappa \cdot \mu \le \lambda \cdot \mu

Applications

Cardinal arithmetic explains why the set of all possible infinite binary strings (2^ℵ₀) is strictly larger than the set of all finite programs (ℵ₀), the counting basis of uncomputability results.

Worked Examples

Take two disjoint copies of ℕ, say A = {a₀,a₁,...} and B = {b₀,b₁,...}; we want a bijection from A⊔B to ℕ.
$A \sqcup B, \quad |A|=|B|=\aleph_0$
Send even naturals to A's elements and odd naturals to B's elements: f(2n)=aₙ, f(2n+1)=bₙ. Every element of A⊔B is hit exactly once.
$f(2n) = a_n, \quad f(2n+1) = b_n$
f is a bijection ℕ → A⊔B, so |A⊔B| = ℵ₀.
$|A \sqcup B| = \aleph_0$

Answer: ℵ₀ + ℵ₀ = ℵ₀ — the union of two countably infinite disjoint sets is still only countably infinite.

Practice Problems

Difficulty 6/10

What is ℵ₀ · 7 (seven disjoint copies of a countably infinite set, combined)?

Difficulty 7/10

Which of the following equals ℵ₀?

2^{ℵ₀}ℵ₀ · ℵ₀ℵ₀^{ℵ₀}ℵ₁

Difficulty 8/10

Explain why 'ℵ₀^{ℵ₀}' (functions ℕ→ℕ) equals 2^{ℵ₀} rather than something strictly larger, even though both the base and the exponent are infinite.

Common Mistakes

Common Mistake

Assuming ℵ₀+ℵ₀ or ℵ₀·ℵ₀ should be 'bigger than ℵ₀,' by analogy with finite arithmetic.

For infinite cardinals, addition and multiplication of two cardinals (at least one infinite) just return the larger cardinal — the absorption law. ℵ₀+ℵ₀=ℵ₀ and ℵ₀·ℵ₀=ℵ₀; only exponentiation (2^κ) reliably increases cardinality (Cantor's theorem).

Common Mistake

Believing 2^{ℵ₀} must equal ℵ₁ (the very next cardinal after ℵ₀).

Cantor's theorem only guarantees 2^{ℵ₀} > ℵ₀, not that it equals the immediate successor ℵ₁ — that additional claim is exactly the (independent, unprovable-from-ZFC) Continuum Hypothesis.

Quiz

Summary

Cardinal arithmetic defines κ+λ, κ·λ, κ^λ via disjoint unions, products, and function sets.
Absorption law: for infinite cardinals, κ+λ=κ·λ= the larger of κ,λ — addition and multiplication 'flatten.'
ℵ₀+ℵ₀=ℵ₀ and ℵ₀·ℵ₀=ℵ₀, provable via explicit bijections (e.g. Cantor's pairing function).
Cantor's theorem: κ<2^κ always — exponentiation is the operation that genuinely grows cardinality.
2^{ℵ₀} equals the cardinality of the continuum; whether it equals ℵ₁ exactly is the independent Continuum Hypothesis.

References

WebsiteWikipedia — Cardinal number
BookJech, T. Set Theory, 3rd ed., Ch. 3.