Ordinals and cardinals

Builds on

Required prerequisites, all the way down: 19

You will learn to

• Define ordinals as transitive sets well-ordered by ∈, and prove that every well-order is isomorphic to exactly one ordinal.
• Use transfinite induction and transfinite recursion to prove statements about, and define functions on, the ordinals.
• Prove the Schröder–Bernstein theorem and compute basic cardinal sums and products.

Definition

• An ordinal is a transitive set that is well-ordered by ∈.
• A cardinal is an ordinal that is not in bijection with any smaller ordinal; ℵ₀ = ω, and ℵ_{α+1} is the least cardinal greater than ℵ_α.
• |A| ≤ |B| means that there is an injection from A to B.

Theorem

• Schröder–Bernstein (provable in ZF): if |A| ≤ |B| and |B| ≤ |A| then |A| = |B|.
• Every well-ordered set is order-isomorphic to exactly one ordinal.
• For every infinite aleph κ, κ + κ = κ · κ = κ.
• Ordinal addition is not commutative: 1 + ω = ω, but ω + 1 ≠ ω.

Common misconceptions

• Confusing ordinal and cardinal arithmetic: ω and ω + 1 are different ordinals with the same cardinality.
• Assuming every set has an aleph as its cardinality without the axiom of choice; in ZF this holds exactly for well-orderable sets.
• Believing 2^ℵ₀ = ℵ₁ is a theorem; it is the continuum hypothesis, which ZFC neither proves nor refutes (if ZFC is consistent).

Leads to

Optional discoveries

• Forcing and independence ZFC does not decide the value of 2^ℵ₀: Cohen's forcing shows that, if ZFC is consistent, so is ZFC + 2^ℵ₀ = ℵ₂, and many other values are possible.Wonder Trail →
• Large cardinals Beyond the alephs lie inaccessible, measurable and larger cardinals whose existence ZFC cannot prove.Wonder Trail →
• ← Sets

Further reading

• Herbert B. Enderton, Elements of Set Theory (1977)
• Kenneth Kunen, Set Theory: An Introduction to Independence Proofs (1980)