Cantor's diagonal argument

Definition

Cantor's diagonal argument is a mathematical proof that demonstrates the existence of uncountable sets, specifically showing that the set of all real numbers is larger than the set of natural numbers. This argument constructs a new real number by changing the digits along the diagonal of a hypothetical list of all real numbers, proving that no complete list can include every real number. This highlights the concept of different sizes of infinity and is a foundational result in set theory.

5 Must Know Facts For Your Next Test

1. Cantor's diagonal argument shows that there are more real numbers between 0 and 1 than there are natural numbers, making the set of real numbers uncountable.
2. The proof begins by assuming that all real numbers can be listed, leading to a contradiction when constructing a new number by altering the diagonal digits.
3. This argument established that not all infinities are equal; specifically, it demonstrated that the infinity of real numbers is strictly larger than that of natural numbers.
4. Cantor's diagonal argument has implications beyond just real numbers; it applies to any set that can be expressed in similar terms, leading to a broader understanding of infinity.
5. This concept laid the groundwork for further developments in set theory and mathematics, influencing various fields such as topology and mathematical logic.

Review Questions

• How does Cantor's diagonal argument demonstrate that not all infinities are equal?
  • Cantor's diagonal argument illustrates that not all infinities are equal by showing that the set of real numbers is uncountable while the set of natural numbers is countable. The proof assumes that all real numbers can be listed and then constructs a new number by changing digits along the diagonal of this list. Since this new number cannot be found in the original list, it proves that no complete list can exist, highlighting that the infinity of real numbers surpasses that of natural numbers.
• What role does the construction of a new number play in Cantor's diagonal argument, and what does this reveal about lists of real numbers?
  • The construction of a new number in Cantor's diagonal argument is central to demonstrating that any assumed complete list of real numbers is incomplete. By altering the digits along the diagonal of this hypothetical list, Cantor reveals that this new number differs from every entry in the list. This process shows that for any attempt to list all real numbers, there will always be at least one number missing, underscoring the uncountability of real numbers.
• Evaluate the significance of Cantor's diagonal argument in relation to other concepts in mathematics and its impact on understanding infinity.
  • Cantor's diagonal argument significantly impacts mathematics by reshaping our understanding of infinity and establishing different levels or cardinalities of infinite sets. Its implications extend beyond just uncountability; it influences areas such as topology, logic, and even computer science by illustrating fundamental limits regarding what can be systematically listed or counted. By proving that some infinities are larger than others, it challenges preconceived notions about size and completeness in mathematical frameworks.

Related terms

Countable set: A set is countable if its elements can be put into a one-to-one correspondence with the natural numbers, meaning it can be listed in a sequence.

Uncountable set: An uncountable set is a set that cannot be matched one-to-one with the natural numbers, meaning it has a greater cardinality than any countable set.

Cardinality: Cardinality refers to the measure of the 'size' of a set, which can be finite or infinite, and is used to compare the sizes of different sets.