11.2 The Burali-Forti Paradox and ordinal numbers

The Burali-Forti Paradox highlights a contradiction in naive set theory when considering the set of all ordinal numbers. It shows that assuming such a set exists leads to a logical impossibility, emphasizing the need for restrictions on set formation.

Ordinal numbers extend natural numbers to the transfinite, representing well-ordered sets. They play a crucial role in set theory, allowing for comparisons and operations beyond finite numbers, but require careful handling to avoid paradoxes.

The Burali-Forti Paradox

Overview of the Paradox

Top images from around the web for Overview of the Paradox

• 

  elementary set theory - In a Venn diagram, where are other number sets located? - Mathematics ... View original

  Is this image relevant?

• 

  Set theory - Wikipedia View original

  Is this image relevant?

• 

  elementary set theory - In a Venn diagram, where are other number sets located? - Mathematics ... View original

  Is this image relevant?

• 

  Set theory - Wikipedia View original

  Is this image relevant?

1 of 2

Top images from around the web for Overview of the Paradox

• 

  elementary set theory - In a Venn diagram, where are other number sets located? - Mathematics ... View original

  Is this image relevant?

• 

  Set theory - Wikipedia View original

  Is this image relevant?

• 

  elementary set theory - In a Venn diagram, where are other number sets located? - Mathematics ... View original

  Is this image relevant?

• 

  Set theory - Wikipedia View original

  Is this image relevant?

1 of 2

• Burali-Forti Paradox demonstrates a contradiction in naive set theory when considering the set of all ordinal numbers
• Arises from the assumption that there exists a set containing all ordinal numbers
• Leads to a contradiction where the set of all ordinals would have to be both an element of itself and strictly greater than itself

Set Theory Concepts Involved

• Set of all ordinals refers to a hypothetical set that contains every ordinal number
  • Ordinal numbers represent the order type of well-ordered sets
  • Assuming the existence of a set containing all ordinals leads to the paradox
• Limitation of size principle states that no set can contain all the ordinals
  • The paradox demonstrates that the set of all ordinals cannot exist without contradiction
  • Highlights the need for restrictions on set formation to avoid paradoxes in set theory

Resolving the Paradox

• The paradox is resolved by recognizing that the set of all ordinals cannot exist as a well-defined set
• Axiom of Regularity in Zermelo-Fraenkel set theory prevents sets from being elements of themselves
  • Prevents the formation of the set of all ordinals, which would have to contain itself
• Limitation of size principle is accepted as a fundamental concept in modern set theory
  • Avoids the contradictions arising from assuming the existence of sets that are "too large"

Ordinal Numbers and Well-Ordering

Definition and Properties of Ordinal Numbers

• Ordinal numbers extend the concept of natural numbers to transfinite numbers
  • Represent the order type of well-ordered sets
  • Denoted by Greek letters $\alpha$, $\beta$, $\gamma$, etc.
• Each ordinal number corresponds to a unique well-ordered set up to isomorphism
  • Two well-ordered sets have the same ordinal number if they are order-isomorphic
• Ordinal numbers are transitive sets that are well-ordered by the membership relation $\in$
  • Every element of an ordinal is also a subset of that ordinal

Well-Ordering and Order Types

• Well-ordering is a total order on a set where every non-empty subset has a least element
  • Ensures that the set can be traversed in a specific order without infinite descending chains
  • Examples: natural numbers, integers, rationals with standard ordering
• Order type refers to the abstract structure of a well-ordered set
  • Determined by the order relations between elements, disregarding their specific nature
  • Sets with the same order type are order-isomorphic and have the same ordinal number
• Ordinal numbers capture the essential properties of well-ordered sets and their order types
  • Allow for the comparison and classification of well-ordered sets based on their structure

Operations on Ordinal Numbers

• Ordinal arithmetic extends the operations of addition, multiplication, and exponentiation to transfinite ordinals
  • Defined recursively using the properties of well-ordered sets
  • Preserves the well-ordering of the resulting ordinals
• Successor ordinal $\alpha+1$ is the smallest ordinal greater than $\alpha$
  • Obtained by adding a new element greater than all elements in $\alpha$
• Limit ordinal is an ordinal that is not a successor ordinal
  • Has no immediate predecessor and is the supremum of all smaller ordinals
  • Examples: $\omega$ (smallest infinite ordinal), $\omega+\omega$, $\omega^2$

Transfinite Induction

Principle of Transfinite Induction

• Transfinite induction extends the principle of mathematical induction to well-ordered sets and ordinal numbers
• Allows proving statements about all ordinals or elements of a well-ordered set
• Induction hypothesis: If a property holds for all ordinals less than $\alpha$, then it also holds for $\alpha$
  • Base case: Prove the property holds for the smallest ordinal (usually 0 or $\omega$)
  • Successor case: Assume the property holds for an ordinal $\alpha$ and prove it holds for its successor $\alpha+1$
  • Limit case: If $\alpha$ is a limit ordinal, prove the property holds for $\alpha$ assuming it holds for all smaller ordinals

Applications and Examples

• Transfinite induction is used to prove properties of ordinal numbers and well-ordered sets
  • Example: Proving that every ordinal is either a successor ordinal or a limit ordinal
  • Example: Proving the well-ordering theorem, which states that every set can be well-ordered
• Transfinite recursion is a related concept that defines functions on ordinal numbers
  • Allows defining a function recursively on all ordinals, using the values of the function on smaller ordinals
  • Example: Defining the ordinal exponentiation function $\alpha^\beta$ using transfinite recursion

Limitations and Considerations

• Transfinite induction requires the set to be well-ordered
  • Not applicable to sets with different order types or without a well-ordering
• The induction hypothesis must be carefully formulated to handle limit ordinals
  • Ensuring the property holds for all smaller ordinals is crucial for the limit case
• Transfinite induction can lead to non-constructive proofs
  • Proving the existence of an object without explicitly constructing it
  • Example: The well-ordering theorem proves the existence of a well-ordering without specifying the actual ordering