∞Intro to the Theory of Sets Unit 9 – Ordinal Numbers & Transfinite Induction

Key Concepts and Definitions

• Ordinal numbers extend the concept of natural numbers to include infinite sets while preserving the notion of order
• Well-ordered sets are totally ordered sets where every non-empty subset has a least element
• Transfinite induction is a proof technique that extends mathematical induction to well-ordered sets, including infinite sets
• Ordinal arithmetic defines operations (addition, multiplication, and exponentiation) on ordinal numbers
• Order types describe the structure of well-ordered sets up to isomorphism
• Isomorphisms are bijective functions between well-ordered sets that preserve the order relation
• Limit ordinals are ordinal numbers that are not succeeded by any smaller ordinal (e.g., $\omega$, the smallest infinite ordinal)
• Successor ordinals are ordinal numbers that have an immediate predecessor (e.g., $\omega+1$, the successor of $\omega$)

Ordinal Numbers: Basics and Properties

• Ordinal numbers are a generalization of natural numbers that include both finite and infinite numbers
• Every ordinal number corresponds to a well-ordered set, and every well-ordered set corresponds to a unique ordinal number
• The smallest infinite ordinal is denoted by $\omega$ and represents the order type of the natural numbers
• Ordinal numbers are transitive sets, meaning that if $\alpha$ is an ordinal, then $\alpha = \{\beta : \beta < \alpha\}$
• The class of all ordinal numbers is denoted by $\mathbf{ON}$ and is a proper class, not a set
• Ordinal numbers are linearly ordered by the membership relation $\in$, which coincides with the subset relation $\subset$ for ordinals
• The Burali-Forti paradox demonstrates that $\mathbf{ON}$ cannot be a set to avoid contradictions in set theory
• The Axiom of Regularity ensures that there are no infinite descending chains of ordinal numbers, preventing circular membership

Well-Ordered Sets and Their Significance

• A well-ordered set is a totally ordered set in which every non-empty subset has a least element
• Well-ordered sets are crucial for defining ordinal numbers and enabling transfinite induction
• The natural numbers $\mathbb{N}$ form a well-ordered set under the usual order relation $\leq$
• Every well-ordered set is order-isomorphic to a unique ordinal number
• The Axiom of Choice is equivalent to the Well-Ordering Theorem, which states that every set can be well-ordered
  • This equivalence highlights the importance of well-ordered sets in set theory and the foundations of mathematics
• Well-ordered sets satisfy the least upper bound property, ensuring that every bounded subset has a supremum
• The order topology on a well-ordered set is discrete, as every point is an isolated point

Transfinite Induction: Principles and Applications

• Transfinite induction is a proof technique that extends the principle of mathematical induction to well-ordered sets, including infinite sets
• The principle of transfinite induction states that if a property $P$ holds for the least element of a well-ordered set and, whenever $P$ holds for all elements less than some element $\alpha$, it also holds for $\alpha$, then $P$ holds for all elements of the set
• Transfinite induction can be used to prove statements about ordinal numbers and well-ordered sets
• The base case of transfinite induction proves the property for the least element of the well-ordered set (often 0 or $\omega$)
• The successor case proves that if the property holds for an ordinal $\alpha$, it also holds for its successor $\alpha+1$
• The limit case proves that if the property holds for all ordinals less than a limit ordinal $\lambda$, it also holds for $\lambda$
• Transfinite induction has applications in various areas of mathematics, such as topology, algebra, and analysis

Ordinal Arithmetic and Operations

• Ordinal arithmetic extends the arithmetic operations of addition, multiplication, and exponentiation to ordinal numbers
• Ordinal addition is defined by transfinite recursion:
  • $\alpha + 0 = \alpha$
  • $\alpha + (\beta + 1) = (\alpha + \beta) + 1$
  • $\alpha + \lambda = \sup\{\alpha + \xi : \xi < \lambda\}$ for limit ordinals $\lambda$
• Ordinal multiplication is defined by transfinite recursion:
  • $\alpha \cdot 0 = 0$
  • $\alpha \cdot (\beta + 1) = (\alpha \cdot \beta) + \alpha$
  • $\alpha \cdot \lambda = \sup\{\alpha \cdot \xi : \xi < \lambda\}$ for limit ordinals $\lambda$
• Ordinal exponentiation is defined by transfinite recursion:
  • $\alpha^0 = 1$
  • $\alpha^{\beta+1} = \alpha^\beta \cdot \alpha$
  • $\alpha^\lambda = \sup\{\alpha^\xi : \xi < \lambda\}$ for limit ordinals $\lambda$
• Ordinal arithmetic is left-distributive but not right-distributive, meaning $\alpha \cdot (\beta + \gamma) = \alpha \cdot \beta + \alpha \cdot \gamma$, but $(\alpha + \beta) \cdot \gamma \neq \alpha \cdot \gamma + \beta \cdot \gamma$ in general
• Ordinal arithmetic is associative but not commutative, so $\alpha + (\beta + \gamma) = (\alpha + \beta) + \gamma$, but $\alpha + \beta \neq \beta + \alpha$ in general

Comparing Ordinals: Order Types and Isomorphisms

• Order types describe the structure of well-ordered sets up to isomorphism
• Two well-ordered sets have the same order type if and only if there exists an order-preserving bijection (isomorphism) between them
• Ordinal numbers represent the order types of well-ordered sets
• The order type of the natural numbers $\mathbb{N}$ is $\omega$, the smallest infinite ordinal
• The order type of the integers $\mathbb{Z}$ is $\omega + \omega^*$, where $\omega^*$ represents the reverse order of $\omega$
• The order type of the rational numbers $\mathbb{Q}$ is $\eta$, the order type of the rationals in their usual order
• Isomorphisms between well-ordered sets are unique, as they preserve the least element and the successor relation
• The comparison of ordinal numbers is determined by the existence of an isomorphism between their corresponding well-ordered sets

Examples and Problem-Solving Strategies

• To prove a statement for all ordinal numbers, use transfinite induction by proving the base case, successor case, and limit case
• Example: Prove that every ordinal number is either a successor ordinal or a limit ordinal
  • Base case: 0 is a limit ordinal by definition
  • Successor case: If $\alpha$ is a successor or limit ordinal, then $\alpha+1$ is a successor ordinal
  • Limit case: If $\lambda$ is a limit ordinal and all $\xi < \lambda$ are successor or limit ordinals, then $\lambda$ is a limit ordinal by definition
• To compare ordinal numbers, look for an isomorphism between their corresponding well-ordered sets
• Example: Show that $\omega + 1 \neq 1 + \omega$
  • $\omega + 1$ has a greatest element, while $1 + \omega$ does not, so they cannot be isomorphic
• To perform ordinal arithmetic, use the recursive definitions of addition, multiplication, and exponentiation
• Example: Calculate $\omega \cdot 2 + 1$
  • $\omega \cdot 2 = \omega + \omega$ (by the definition of ordinal multiplication)
  • $\omega + \omega + 1 = \omega \cdot 2 + 1$ (by the definition of ordinal addition)

Real-World Applications and Connections

• Ordinal numbers and well-ordered sets have applications in computer science, particularly in the theory of computation and algorithm analysis
• The ordinal $\omega$ represents the order type of the natural numbers, which is used to define the concept of computability and the halting problem
• Ordinal numbers are used to measure the complexity of algorithms and the growth rates of functions in computational complexity theory
• In topology, ordinal numbers are used to define the transfinite induction principle for constructing topological spaces and studying their properties
• The long line is a topological space constructed using ordinal numbers, serving as a counterexample to various topological properties
• In algebra, ordinal numbers are used to define transfinite versions of algebraic structures, such as transfinite groups and transfinite fields
• Ordinal numbers have connections to the foundations of mathematics, particularly in the study of set theory and logic
• The theory of ordinal numbers is closely related to the axiomatization of set theory, such as the Zermelo-Fraenkel axioms (ZF) and the axiom of choice (AC)
• Ordinal numbers play a crucial role in the study of large cardinals and the consistency strength of various axioms in set theory