Mathematics Foundations/1.4 Cardinality

Introduction to Cardinality Cardinality is a fundamental concept in set theory that allows us to compare the sizes of sets, even infinite ones. Intuitively, the cardinality of a set is the number of elements it contains. For finite sets, this is straightforward, but the concept becomes more nuanced when dealing with infinite sets. Finite and Infinite Sets A set S is finite if it contains exactly n elements for some natural number n. In this case, we write . A set that is not finite is called infinite. Example: The set {1, 2, 3, 4, 5} has cardinality 5. Comparing Set Sizes Bijections and Equivalent Sets Two sets A and B have the same cardinality if there exists a bijection (a one-to-one and onto function) . We write or . Definition: A bijection between sets A and B is a function that is: Injective (one-to-one): For all , if , then Surjective (onto): For every , there exists an such that Countable Sets A set S is countable if , where is the set of natural numbers. In other words, S is countable if it is finite or if there exists a bijection between S and . Example: The set of integers is countable. We can establish a bijection with as follows: This gives the sequence: 0, −1, 1, −2, 2, −3, 3, ... Uncountable Sets A set that is not countable is called uncountable. Theorem (Cantor): The set of real numbers is uncountable. Proof Sketch: Cantor's diagonal argument shows that any attempt to list all real numbers between 0 and 1 will always miss some numbers, proving that is uncountable. Cantor's Theorem and Cardinal Arithmetic Cantor's Theorem Theorem: For any set S, , where is the power set of S. This theorem establishes that there is no "largest" infinity and that there exists an infinite hierarchy of infinite cardinalities. Cardinal Numbers Cardinal numbers formalize the concept of the "size" of a set: (aleph-null): The cardinality of : The next larger infinity after : The cardinality of (the continuum) The Continuum Hypothesis The Continuum Hypothesis states that there is no cardinal number between and , or equivalently, that . This hypothesis was proven by Kurt Gödel and Paul Cohen to be independent of the standard axioms of set theory (ZFC), meaning it can neither be proved nor disproved within this axiomatic system. Schröder-Bernstein Theorem Theorem: If and , then . In other words, if there exists an injection from A to B and an injection from B to A, then there exists a bijection between A and B. Examples and Applications Example 1: Countability of Rational Numbers The set of rational numbers is countable. This can be shown by arranging the positive rationals in a grid and traversing it diagonally. Example 2: Uncountability of Irrational Numbers Since is uncountable and is countable, the set of irrational numbers must be uncountable. Example 3: Hilbert's Hotel Hilbert's Hotel is a thought experiment that illustrates properties of infinite sets. It describes a hotel with infinitely many rooms, all occupied, that can still accommodate new guests through clever reassignment of rooms. Exercises 1. Prove that the set of all finite subsets of is countable. 2. Show that the set of all functions is uncountable. 3. Prove that . 4. Show that . 5. Prove that the set of all sequences of natural numbers is uncountable.