Section 13.2 Properties
The following facts outline some relationships countability and the set operations. They can be used to more easily prove that a set is countable or uncountable using the already-known countability or uncountability of a related set.
Proposition 13.2.1. Countability properties.
Every subset of \(\N\) is countable.
If there exists an injection \(A \ifuncto \N\text{,}\) then the set \(A\) is countable.
Suppose \(A \subseteq B\text{.}\) If \(B\) is countable, then so is \(A\text{.}\)
Suppose \(A \subseteq B\text{.}\) If \(A\) is uncountable, then so is \(B\text{.}\)
If \(A\) and \(B\) are countable, then \(A\cup B\) and \(A\cap B\) are both countable.
Proof outline.
Assume
\(A \subseteq \N\text{.}\) If
\(A\) is finite, then it is countable by definition. So assume that
\(\card{A} = \infty\text{.}\) We can construct a sequence
\(\{a_k\}\) that contains each element of
\(A\) exactly once as follows.
\begin{align*}
a_0 \amp = \text{ smallest number in } A, \\
a_1 \amp = \text{ next smallest number in } A, \\
a_2 \amp = \text{ next smallest number in } A, \\
\amp \phantom{=} \; \vdots
\end{align*}
Therefore,
\(A\) is countable.
If
\(\ifuncdef{f}{A}{\N}\) is injective, then
\(\funcdef{f}{A}{f(A)}\) is a bijection, so that
\(A\) and its image
\(f(A)\) have the same size. But
\(f(A)\) is countable by
Statement 1, so using the definition of countable along with
Fact 12.3.2, conclude that
\(A\) is countable.
If
\(B\) is countable, then by definition there exists a bijection
\(\funcdef{f}{B}{\N}\text{.}\) Then
\(\funcdef{\funcres{f}{A}}{A}{\N}\) is an injection. Apply
Statement 2.
This is the contrapositive of
Statement 3, under the common assumption
\(A \subseteq B\text{.}\)
-
For
\(A \cap B\text{,}\) consider
\(A \cap B \subseteq A\) and apply
Statement 3.
Now consider \(A \cup B\text{.}\) For simplicity, we will assume \(A \cap B = \emptyset\text{,}\) so that \(A \cup B = A \sqcup B\text{.}\) Since \(A\) and \(B\) are countable, we can write their elements as sequences:
\begin{align*}
A \amp = \{ \, a_0, \, a_1, \, a_2, \, \dotsc \, \}, \amp B \amp = \{ \, b_0, \, b_1, \, b_2, \, \dotsc \, \} \text{.}
\end{align*}
We can then write the elements of \(A \sqcup B\) in a sequence by interleaving these two sequences:
\begin{equation*}
A \sqcup B = \{ \, a_0, \, b_0, \, a_1, \, b_1, \, a_2, \, b_2, \, \dotsc \, \} \text{.}
\end{equation*}
Checkpoint 13.2.2.
Prove \(A \cup B\) is countable even in the case \(A \cap B \ne \emptyset\text{.}\)
Hint.
Consider the sets
\begin{align*}
A' \amp = A \smallsetminus (A\cap B), \amp
B' \amp = B \smallsetminus (A\cap B), \amp
C \amp = A' \sqcup B'.
\end{align*}
Then \(A\cup B\) is the disjoint union of \(C\) and \(A\cap B\text{.}\)
Example 13.2.3. Primes are countable.
The set of prime numbers is countable, since it is a subset of \(\N\text{.}\)
Example 13.2.4. Unit interval is uncountable.
The unit interval
\((0,1)\) on the real number line is uncountable because it contains the uncountable subset
\(\mathscr{C}\) from
Lemma 13.1.7.
Theorem 13.2.5.
Set \(\R\) is uncountable.
Proof.
Example 13.2.6.
The Cartesian product set \(\R^2 = \R \times \R\) is uncountable because it has an uncountable subset: the \(x\)-axis has the same size as \(\R\text{.}\)
