Chapter 3: Countable and Uncountable Sets
In set theory and topology, distinguishing the sizes of infinite sets (i.e., "cardinality" or "power") is extremely important. Not all "infinities" are equal. This chapter strictly defines countability, explores the operational properties of countable sets, reveals the existence of uncountable sets through Cantor's diagonal argument, and finally introduces cardinality and the Continuum Hypothesis.
1. Basic Definition of Countable Sets
First, we need to strictly define the categories of set "size," specifically for classifying infinite sets.
Definition 3.1 (Finite, Infinite, and Countable)
-
Finite Set: A set \(S\) is called finite if it is the empty set \(\emptyset\), or if there exists a natural number \(n \in \mathbb{N}_{\ge 1}\) and a bijection \(f: S \to \{1, 2, \dots, n\}\).
-
Infinite Set: A set \(S\) is called infinite if it is not finite.
-
Countably Infinite Set: A set \(S\) is called countably infinite if there exists a bijection \(f: S \to \mathbb{N}\) (where \(\mathbb{N}\) is the set of natural numbers).
-
Countable Set: A set is called countable if it is either finite or countably infinite.
As a fundamental example, the set of integers \(\mathbb{Z}\) is countably infinite. We can explicitly construct a bijection \(f: \mathbb{Z} \to \mathbb{N}\) as follows:
This mapping maps the integer sequence \(0, 1, -1, 2, -2, \dots\) one-to-one onto the natural number sequence \(1, 2, 3, 4, 5, \dots\).
2. Equivalent Characterizations of Countable Sets
To make it easier to determine whether a set is countable in practical applications, we have the following equivalent conditions.
Theorem 3.1 (Equivalent Conditions for Countable Sets)
Let \(B\) be any non-empty set. Then the following three propositions are equivalent (TFAE):
-
(1) \(B\) is a countable set.
-
(2) There exists a surjection \(f: \mathbb{N} \to B\) from the set of natural numbers \(\mathbb{N}\) to \(B\).
-
(3) There exists an injection \(g: B \to \mathbb{N}\) from \(B\) to the set of natural numbers \(\mathbb{N}\).
Proof of Theorem 3.1
(1) \(\implies\) (2): If \(B\) is countable, it is either finite or countably infinite. If \(B\) is countably infinite, by definition there exists a bijection \(h: B \to \mathbb{N}\), and its inverse \(h^{-1}: \mathbb{N} \to B\) is clearly a surjection. If \(B\) is finite, let \(B = \{b_1, b_2, \dots, b_k\}\). We can construct a surjection \(f: \mathbb{N} \to B\) as follows:
(2) \(\implies\) (3): Given a surjection \(f: \mathbb{N} \to B\). For every \(b \in B\), its preimage set \(f^{-1}(\{b\}) \subseteq \mathbb{N}\) must be non-empty. According to the Well-Ordering Principle of natural numbers, any non-empty subset of natural numbers must have a least element. Therefore, we can define the mapping \(g: B \to \mathbb{N}\) as:
If \(b_1 \neq b_2\), then because the function \(f\) is single-valued, the corresponding minimum preimages must be different; thus \(g\) is an injection.
(3) \(\implies\) (1): Given an injection \(g: B \to \mathbb{N}\). This means \(g\) is a bijection from \(B\) to its image set \(S = g(B) \subseteq \mathbb{N}\). Therefore, we only need to prove that any subset \(S \subseteq \mathbb{N}\) of natural numbers must be countable.
Suppose \(S\) is not finite. We wish to construct a bijection \(\varphi: \mathbb{N} \to S\). We use the Well-Ordering Principle for a recursive definition:
Let \(S_0 = S\).
Define \(\varphi(0) = \min S_0\).
For \(i \ge 1\), let \(S_i = S \setminus \{\varphi(0), \varphi(1), \dots, \varphi(i-1)\}\).
Since \(S\) is an infinite set, \(S_i\) is always non-empty. Define \(\varphi(i) = \min S_i\).
Clearly, the \(\varphi\) constructed in this way maps \(\mathbb{N}\) one-to-one onto \(S\); therefore \(S\) is countably infinite. \(\square\)
3. Operational Properties of Countable Sets
Countable sets exhibit strong closure properties under basic set operations (such as taking subsets, finite Cartesian products, and countable unions).
Theorem 3.2 (Closure of Countable Sets)
-
(i) Any subset of a countable set is still countable.
-
(ii) The union of countably many countable sets is still countable.
-
(iii) The Cartesian product of finitely many countable sets is still countable.
Proof of Operational Properties
(i) Proof: Let \(A\) be a countable set and \(S \subseteq A\). Since \(A\) is countable, there exists an injection \(g: A \to \mathbb{N}\). Restricting \(g\) to \(S\) yields \(g|_S: S \to \mathbb{N}\), which is clearly also an injection. By Theorem 3.1, \(S\) is countable.
(ii) Proof: Let \(I\) be a countable index set, and for each \(i \in I\), \(A_i\) is a countable set. We need to prove that \(\bigcup_{i \in I} A_i\) is countable. Since \(I\) is countable, there exists a surjection \(g: \mathbb{N} \to I\). For each \(i \in I\), since \(A_i\) is countable, there exists a surjection \(f_i: \mathbb{N} \to A_i\). Define a new mapping \(\Phi: \mathbb{N} \times \mathbb{N} \to \bigcup_{i \in I} A_i\) as follows:
Clearly, since \(g\) traverses all indices and \(f_{g(m)}\) traverses all elements in the sets, \(\Phi\) must be a surjection. As long as we can prove that \(\mathbb{N} \times \mathbb{N}\) is countable (there exists a surjection from \(\mathbb{N}\) to \(\mathbb{N} \times \mathbb{N}\)), the composite mapping proves the countability of the union.
Lemma: \(\mathbb{N} \times \mathbb{N}\) is countable. Construct a mapping \(H: \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) defined as:
By the Fundamental Theorem of Arithmetic (uniqueness of prime factorization), if \((m, n) \neq (m', n')\), then \(2^m \cdot 3^n \neq 2^{m'} \cdot 3^{n'}\). Therefore \(H\) is an injection. By Theorem 3.1, \(\mathbb{N} \times \mathbb{N}\) is countable. This completes the proof of (ii).
(iii) Proof: By induction, we only need to prove that the Cartesian product \(A \times B\) of two countable sets \(A\) and \(B\) is countable. Given surjections \(f_A: \mathbb{N} \to A\) and \(f_B: \mathbb{N} \to B\). Construct a mapping \(F: \mathbb{N} \times \mathbb{N} \to A \times B\) as \(F(m, n) = (f_A(m), f_B(n))\). This is clearly a surjection. Since \(\mathbb{N} \times \mathbb{N}\) is countable, \(A \times B\) is also countable. \(\square\)
Typical Application: The set of positive rational numbers \(\mathbb{Q}^+\) is countable. This is because we can construct a surjection \(f: \mathbb{N}_{\ge 1} \times \mathbb{N}_{\ge 1} \to \mathbb{Q}^+\) defined as \((a, b) \mapsto \frac{a}{b}\). Since \(\mathbb{Q}^+\) is countable, it follows that the entire set of rational numbers \(\mathbb{Q}\) is also countable.
4. Uncountable Sets and Cantor's Diagonal Argument
Not all infinite sets are countable. The Cartesian product of infinitely many countable sets often leads to an "uncountable" explosion.
Consider the set \(S = \{0, 1\}\). Define \(S^{\mathbb{N}}\) as the set of all functions from \(\mathbb{N}\) to \(\{0, 1\}\), which is equivalent to the set of all infinite sequences composed of 0s and 1s.
Theorem 3.3 (Cantor's Diagonal Argument)
The space of infinite sequences \(S^{\mathbb{N}} = \{0, 1\}^{\mathbb{N}}\) is an uncountable set.
Proof of Cantor's Diagonal Argument
We proceed by contradiction. Suppose \(S^{\mathbb{N}}\) is countable. Then there exists a bijection \(\varphi: \mathbb{N} \to S^{\mathbb{N}}\). This means we can arrange all infinite sequences of 0s and 1s into a list:
where all \(x_{ij} \in \{0, 1\}\).
Now, we construct a new sequence \(y = (y_1, y_2, y_3, \dots) \in S^{\mathbb{N}}\) such that \(y\) does not appear in any of the above positions. The construction rule is as follows (i.e., negating the diagonal elements):
Since \(y\) is an infinite sequence of 0s and 1s, it must be that \(y \in S^{\mathbb{N}}\). However, for any integer \(n \in \mathbb{N}\), the element of sequence \(y\) at the \(n\)-th position is different from the element of sequence \(\varphi(n)\) at the same position (because \(y_n = 1 - x_{nn} \neq x_{nn}\)).
This means \(y \neq \varphi(n)\) holds for all \(n\). This breaks the assumption that \(\varphi\) is a surjection. Contradiction! Therefore, \(S^{\mathbb{N}}\) must be uncountable. \(\square\)
Note: Through binary expansion, one can establish a mapping from \(\{0, 1\}^{\mathbb{N}}\) to the real interval \([0, 1]\), thus strictly proving that the set of real numbers \(\mathbb{R}\) is an uncountable set.
5. Cantor's Theorem and Cardinality Theory
Abstracting further, we can compare the sizes of any set and its power set (the set of all its subsets). For a set \(A\), its power set is denoted as \(\mathcal{P}(A)\). For the set of natural numbers, it is not difficult to find that there is a one-to-one correspondence between \(\mathcal{P}(\mathbb{N})\) and \(\{0, 1\}^{\mathbb{N}}\) (via characteristic functions).
Theorem 3.4 (Cantor's Theorem)
For any set \(A\), there exists no surjection from \(A\) to its power set \(\mathcal{P}(A)\), and consequently, there exists no injection from \(\mathcal{P}(A)\) to \(A\).
Proof of Cantor's Theorem
We proceed by contradiction. Suppose there exists a surjection \(g: A \to \mathcal{P}(A)\). For any element \(a \in A\), \(g(a)\) is an element of \(\mathcal{P}(A)\), i.e., a subset of \(A\). We construct a "pathological" set \(B\):
Clearly \(B \subseteq A\), so \(B \in \mathcal{P}(A)\). Since \(g\) is a surjection, there must exist some element \(b \in A\) such that \(g(b) = B\).
Now we ask a question: does the element \(b\) belong to the set \(B\)?
-
If \(b \in B\): According to the definition of \(B\), we must have \(b \notin g(b)\). But \(g(b) = B\), meaning \(b \notin B\). Contradiction!
-
If \(b \notin B\): That is, \(b \in g(b)\). Again, according to the definition of \(B\), an element satisfying this condition must be in \(B\), meaning \(b \in B\). Contradiction!
Either case leads to a logical breakdown (this is similar to the construction of Russell's paradox). Therefore, no such surjection exists. \(\square\)
5.1 Cardinality and the Continuum Hypothesis
Based on injections and bijections, we define the cardinality relationship of sets:
- Equal: If there exists a bijection \(A \to B\), we write \(\text{Card}(A) = \text{Card}(B)\) or \(|A| = |B|\).
- Strictly Less Than: If there exists an injection \(A \to B\) and no bijection \(A \to B\) exists, we write \(\text{Card}(A) < \text{Card}(B)\).
We use \(\aleph_0\) (aleph-null) to denote the cardinality of a countably infinite set (i.e., \(\text{Card}(\mathbb{N})\)). By Cantor's Theorem, we can construct an endless sequence of increasingly large cardinalities:
The cardinality of the set of real numbers is called the continuum cardinality \(\mathfrak{c}\), and it is known that \(\mathfrak{c} = \text{Card}(\mathcal{P}(\mathbb{N})) = 2^{\aleph_0}\). Thus \(\aleph_0 < 2^{\aleph_0}\).
Continuum Hypothesis (CH): Cantor proposed a famous question: Does there exist a set \(X\) whose cardinality is strictly between those of the natural numbers and the real numbers? That is, does there exist \(X\) such that:
The Continuum Hypothesis conjectures that "no such set exists." Modern set theory has proven that the Continuum Hypothesis can neither be proven nor disproven within the standard ZFC axiom system (i.e., it is independent of the ZFC system).