3.2: Countable and Uncountable Sets
- Page ID
- 22651
A function \(\varphi: A \rightarrow B\) is said to be a one-to-one correspondence if \(\varphi\) is both one-to-one and onto.
We say sets \(A\) and \(B\) have the same cardinality if there exists a one-to-one correspondence \(\varphi: A \rightarrow B\).
We denote the fact \(A\) and \(B\) have the same cardinality by writing \(|A|=|B| .\)
Define a relation on sets by setting \(A \sim B\) if and only if \(|A|=|B| .\) Show that this relation is an equivalence relation.
Let \(A\) be a set. If, for \(n \in \mathbb{Z}^{+}, A\) has the cardinality of the set \(\{1,2,3, \ldots, n\},\) we say \(A\) is finite and write \(|A|=n .\) If \(A\) has the cardinality of \(\mathbb{Z}^{+},\) we say \(A\) is countable and write \(|A|=\aleph_{0} .\)
If we define \(\varphi: \mathbb{Z}^{+} \rightarrow \mathbb{Z}\) by
\[\varphi(n)=\left\{\begin{array}{ll}{\frac{n-1}{2},} & {\text { if } n \text { is odd, }} \\ {-\frac{n}{2},} & {\text { if } n \text { is even, }}\end{array}\right.\]
then \(\varphi\) is a one-to-one correspondence. Thus \(|\mathbb{Z}|=\aleph_{0}\).
Let \(A\) be the set of even integers. Show that \(|A|=\aleph_{0}\).
Verify each of the following:
a. If \(A\) is a nonempty subset of \(\mathbb{Z}^{+},\) then \(A\) is either finite or countable.
b. If \(A\) is a nonempty subset of a countable set \(B,\) then \(A\) is either finite or countable.
Suppose \(A\) and \(B\) are countable sets. Then the set \(C=\) \(A \cup B\) is countable.
- Proof
-
Suppose \(A\) and \(B\) are disjoint, that is, \(A \cap B=\emptyset .\) Let \(\varphi: \mathbb{Z}^{+} \rightarrow A\) and \(\psi: \mathbb{Z}^{+} \rightarrow B\) be one-to-one correspondences. Define \(\tau: \mathbb{Z}^{+} \rightarrow C\) by
\[\tau(n)=\left\{\begin{array}{ll}{\varphi\left(\frac{n+1}{2}\right),} & {\text { if } n \text { is odd, }} \\ {\psi\left(\frac{n}{2}\right),} & {\text { if } n \text { is even. }}\end{array}\right.\]
Then \(\tau\) is a one-to-one correspondence, showing that \(C\) is countable.
If \(A\) and \(B\) are not disjoint, then \(\tau\) is onto but not one-to-one. However, in that case \(C\) has the cardinality of an infinite subset of \(\mathbb{Z}^{+},\) and so is countable. \(\quad\) Q.E.D.
A nonempty set which is not finite is said to be infinite. An infinite set which is not countable is said to be uncountable.
Suppose \(A\) is uncountable and \(B \subset A\) is countable. Show that \(A \backslash B\) is uncountable.
Suppose \(A\) and \(B\) are countable. Then \(C=A \times B\) is countable.
- Proof
-
Let \(\varphi: \mathbb{Z}^{+} \rightarrow A\) and \(\psi: \mathbb{Z}^{+} \rightarrow B\) be one-to-one correspondences. Let \(a_{i}=\varphi(i)\) and \(b_{i}=\psi(i) .\) Define \(\tau: \mathbb{Z}^{+} \rightarrow C\) by letting
\[\tau(1)=\left(a_{1}, b_{1}\right),\]
\[\tau(2)=\left(a_{1}, b_{2}\right),\]
\[\tau(3)=\left(a_{2}, b_{1}\right),\]
\[\tau(4)=\left(a_{1}, b_{3}\right),\]
\[\tau(5)=\left(a_{2}, b_{2}\right),\]
\[\tau(6)=\left(a_{3}, b_{1}\right),\]
\[\tau(7)=\left(a_{1}, b_{4}\right),\]
\[\vdots = \vdots\]
That is, form the infinite matrix with \(\left(a_{i}, b_{j}\right)\) in the \(i\)th row and \(j\)th column, and then count the entries by reading down the diagonals from right to left. Then \(\tau\) is a one-to-one correspondence and \(C\) is countable.
\(\mathbb{Q}\) is countable.
- Proof
-
By the previous proposition, \(\mathbb{Z} \times \mathbb{Z}\) is countable. Let
\[A=\{(p, q): p, q \in \mathbb{Z}, q>0, p \text { and } q \text { relatively prime }.\}\]
Then \(A\) is infinite and \(A \subset \mathbb{Z} \times \mathbb{Z},\) so \(A\) is countable. But clearly \(|\mathbb{Q}|=|A|,\) so \(\mathbb{Q}\) is countable. \(\quad\) Q.E.D.
Suppose for each \(i \in \mathbb{Z}^{+}, A_{i}\) is countable. Then
\[B=\bigcup_{i=1}^{\infty} A_{i}\]
is countable.
- Proof
-
Suppose the sets \(A_{i}, i \in \mathbb{Z}^{+},\) are pairwise disjoint, that is, \(A_{i} \cap A_{j}=\emptyset\) for all \(i, j \in \mathbb{Z}^{+} .\) For each \(i \in \mathbb{Z}^{+},\) let \(\varphi_{i}: \mathbb{Z}^{+} \rightarrow A_{i}\) be a one-to-one correspondence. Then \(\psi: \mathbb{Z}^{+} \times \mathbb{Z}^{+} \rightarrow B\) defined by
\[\psi(i, j)=\varphi_{i}(j)\]
is a one-to-one correspondence, and so \(|B|=\left|\mathbb{Z}^{+} \times \mathbb{Z}^{+}\right|=\aleph_{0}\).
If the sets \(A_{i}, i \in \mathbb{Z}^{+},\) are not disjoint, then \(\psi\) is onto but not one-to-one. But then there exists a subset \(P\) of \(\mathbb{Z}^{+} \times \mathbb{Z}^{+}\) such that \(\psi: P \rightarrow B\) is a one-to-one correspondence. Since \(P\) is an infinite subset of a countable set, \(P\) is countable and so \(|B|=\aleph_{0} .\) \(\quad\) Q.E.D.
If in the previous proposition we allow that, for each \(i \in \mathbb{Z}^{+}, A_{i}\) is either finite or countable, then \(B=\bigcup_{i=1}^{\infty} A_{i}\) will be either finite or countable.