🤔Mathematical Logic Unit 8 – Cardinality and Transfinite Numbers

Key Concepts and Definitions

• Cardinality measures the size of a set, the number of elements it contains
  • Two sets have the same cardinality if there exists a bijection (one-to-one correspondence) between them
• Infinite sets are sets that contain an endless number of elements
  • Examples include the set of natural numbers $\mathbb{N}$, integers $\mathbb{Z}$, and real numbers $\mathbb{R}$
• Transfinite numbers extend the concept of infinity, allowing for the comparison and arithmetic of infinite sets
• Ordinal numbers represent the order type of well-ordered sets
  • They describe the position of an element in a well-ordered set (first, second, third, etc.)
• Cardinal numbers represent the cardinality of sets, the size of the set
  • They describe the number of elements in a set, whether finite or infinite
• The continuum hypothesis states that there is no set with a cardinality between that of the integers and the real numbers
  • It is independent of the standard axioms of set theory (ZFC)

Set Theory Foundations

• Set theory is the branch of mathematics that studies collections of objects called sets
  • It provides a framework for understanding and comparing different types of infinity
• The concept of a set is an undefined primitive notion in set theory
  • Sets are described by their elements or by a property that characterizes the elements
• The axioms of set theory, such as the Zermelo-Fraenkel axioms with the Axiom of Choice (ZFC), provide a consistent foundation for mathematics
  • These axioms define the properties and operations of sets, such as union, intersection, and power sets
• The principle of extensionality states that two sets are equal if and only if they have the same elements
  • This allows for the comparison of sets based on their contents rather than their descriptions
• The axiom of infinity guarantees the existence of an infinite set, typically the set of natural numbers $\mathbb{N}$
  • This axiom is crucial for the study of transfinite numbers and the properties of infinite sets

Comparing Infinite Sets

• Two sets $A$ and $B$ have the same cardinality, denoted $|A| = |B|$, if there exists a bijection between them
  • A bijection is a one-to-one correspondence that maps each element of $A$ to a unique element of $B$ and vice versa
• Cantor's diagonalization argument proves that the set of real numbers $\mathbb{R}$ has a higher cardinality than the set of natural numbers $\mathbb{N}$
  • This demonstrates the existence of different sizes of infinity
• The power set of a set $A$, denoted $\mathcal{P}(A)$, is the set of all subsets of $A$
  • Cantor's theorem proves that the power set of any set has a higher cardinality than the original set
• The continuum hypothesis states that there is no set with a cardinality between that of the integers $\mathbb{Z}$ and the real numbers $\mathbb{R}$
  • The hypothesis is independent of the standard axioms of set theory (ZFC), meaning it can neither be proved nor disproved using these axioms

Types of Infinity

• Countable infinity refers to the cardinality of sets that can be put into a one-to-one correspondence with the natural numbers $\mathbb{N}$
  • Examples of countably infinite sets include the integers $\mathbb{Z}$, rational numbers $\mathbb{Q}$, and algebraic numbers
• Uncountable infinity refers to the cardinality of sets that cannot be put into a one-to-one correspondence with the natural numbers
  • The set of real numbers $\mathbb{R}$ is an example of an uncountably infinite set
• The smallest infinite cardinal number is $\aleph_0$ (aleph-null), which represents the cardinality of the natural numbers $\mathbb{N}$
  • All countably infinite sets have cardinality $\aleph_0$
• The cardinality of the continuum, the set of real numbers $\mathbb{R}$, is denoted by $\mathfrak{c}$ or $2^{\aleph_0}$
  • The continuum hypothesis states that there is no cardinal number between $\aleph_0$ and $\mathfrak{c}$
• Higher levels of infinity, such as $\aleph_1$, $\aleph_2$, etc., represent the cardinalities of even larger infinite sets
  • These are studied using the tools of transfinite arithmetic and the theory of ordinal and cardinal numbers

Ordinal Numbers

• Ordinal numbers extend the concept of natural numbers to infinite sets, representing the order type of well-ordered sets
  • A well-ordered set is a totally ordered set in which every non-empty subset has a least element
• The first infinite ordinal number is $\omega$, which represents the order type of the natural numbers $\mathbb{N}$
  • Ordinal arithmetic allows for the addition, multiplication, and exponentiation of ordinal numbers
• Successor ordinals are obtained by adding one to a given ordinal, representing the next element in the order
  • For example, the successor of $\omega$ is $\omega + 1$, which represents the order type of $\mathbb{N} \cup \{\infty\}$
• Limit ordinals are ordinals that are not successor ordinals, representing the supremum (least upper bound) of a sequence of smaller ordinals
  • The first limit ordinal is $\omega$, and other examples include $\omega + \omega$, $\omega \cdot 2$, and $\omega^2$
• The Burali-Forti paradox demonstrates that the collection of all ordinal numbers is not a set, as it would lead to a contradiction
  • This highlights the need for a careful treatment of transfinite numbers within the framework of set theory

Cardinal Numbers

• Cardinal numbers represent the cardinality of sets, the number of elements in a set
  • They are used to compare the sizes of infinite sets and to perform arithmetic operations on them
• The first infinite cardinal number is $\aleph_0$, which represents the cardinality of the natural numbers $\mathbb{N}$
  • All sets with cardinality $\aleph_0$ are countably infinite
• The next larger cardinal number is $\aleph_1$, which is the smallest uncountable cardinal
  • The continuum hypothesis states that $\aleph_1$ is equal to the cardinality of the continuum $\mathfrak{c}$
• Cardinal arithmetic allows for the addition, multiplication, and exponentiation of cardinal numbers
  • For infinite cardinals, the sum and product of two cardinals is always the larger of the two
• The Cantor-Bernstein-Schroeder theorem states that if there are injections (one-to-one functions) between two sets $A$ and $B$ in both directions, then $|A| = |B|$
  • This theorem is useful for comparing the cardinalities of infinite sets without explicitly finding a bijection

Cantor's Theorem and Continuum Hypothesis

• Cantor's theorem states that the power set of any set $A$, denoted $\mathcal{P}(A)$, always has a higher cardinality than $A$ itself
  • In other words, $|A| < |\mathcal{P}(A)|$ for any set $A$
• The proof of Cantor's theorem uses a diagonalization argument, showing that there cannot be a surjection (onto function) from $A$ to $\mathcal{P}(A)$
  • This demonstrates the existence of an infinite hierarchy of increasing cardinalities
• The generalized continuum hypothesis (GCH) states that for any infinite set $A$, there is no set with a cardinality between $|A|$ and $|\mathcal{P}(A)|$
  • The standard continuum hypothesis is a special case of GCH, asserting that there is no set with a cardinality between $\aleph_0$ and $\mathfrak{c}$
• The independence of the continuum hypothesis from the standard axioms of set theory (ZFC) was proven by Kurt Gödel and Paul Cohen
  • Gödel showed that the continuum hypothesis is consistent with ZFC, while Cohen demonstrated that its negation is also consistent

Applications and Implications

• Transfinite numbers and the study of different types of infinity have important applications in various branches of mathematics
  • They are used in topology to classify different types of spaces and to study their properties
• In analysis, the concept of cardinality is used to compare the sizes of function spaces and to investigate the properties of sets of real numbers
  • The Lebesgue measure, which assigns a size to subsets of the real line, is based on the concept of cardinality
• In logic and foundations of mathematics, transfinite numbers are used to study the properties of formal systems and to investigate the limits of mathematical reasoning
  • The independence of the continuum hypothesis has important implications for the nature of mathematical truth and the role of axioms in mathematics
• The study of transfinite numbers has also led to the development of new branches of mathematics, such as descriptive set theory and infinitary combinatorics
  • These fields investigate the properties of infinite sets and their subsets, as well as the combinatorial properties of infinite structures
• Understanding the nature of infinity and the different sizes of infinite sets is crucial for a deep understanding of the foundations of mathematics
  • It provides insight into the limits of mathematical reasoning and the role of axioms in shaping mathematical knowledge