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 \(\PageIndex{1}\)

1. Every subset of \(\mathbb{N}\) is countable.
2. If there exists an injection \(A \hookrightarrow \mathbb{N}\text{,}\) then the set \(A\) is countable.
3. Suppose \(A \subseteq B\text{.}\) If \(B\) is countable, then so is \(A\text{.}\)
4. Suppose \(A \subseteq B\text{.}\) If \(A\) is uncountable, then so is \(B\text{.}\)
5. If \(A\) and \(B\) are countable, then \(A\cup B\) and \(A\cap B\) are both countable.

Proof outline.

1. Assume \(A \subseteq \mathbb{N}\text{.}\) If \(A\) is finite, then it is countable by definition. So assume that \(\vert A \vert = \infty\text{.}\) We can construct a sequence \(\{a_k\}\) that contains each element of \(A\) exactly once as follows.

\begin{align*} a_0 & = \text{ smallest number in } A, \\ a_1 & = \text{ next smallest number in } A, \\ a_2 & = \text{ next smallest number in } A, \\ & \; \vdots \end{align*}
Therefore, \(A\) is countable.

2. If \(f: A \hookrightarrow \mathbb{N}\) is injective, then \(f: A \rightarrow 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.
3. If \(B\) is countable, then by definition there exists a bijection \(f: B \rightarrow \mathbb{N}\text{.}\) Then \(f\vert _A: A \rightarrow \mathbb{N}\) is an injection. Apply Statement 2.
4. This is the contrapositive of Statement 3, under the common assumption \(A \subseteq B\text{.}\)
5. 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 & = \{ \, a_0, \, a_1, \, a_2, \, \ldots \, \}, & B & = \{ \, b_0, \, b_1, \, b_2, \, \ldots \, \} \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, \, \ldots \, \} \text{.} \end{equation*}

Checkpoint \(\PageIndex{1}\)

Prove \(A \cup B\) is countable even in the case \(A \cap B \ne \emptyset\text{.}\)

Hint.

Consider the sets

\begin{align*} A' & = A \smallsetminus (A\cap B), & B' & = B \smallsetminus (A\cap B), & C & = A' \sqcup B'. \end{align*}
Then \(A\cup B\) is the disjoint union of \(C\) and \(A\cap B\text{.}\)

Example \(\PageIndex{1}\): Primes are countable.

The set of prime numbers is countable, since it is a subset of \(\mathbb{N}\text{.}\)

Example \(\PageIndex{2}\): Unit interval is uncountable.

The unit interval \((0,1)\) on the real number line is uncountable because it contains the uncountable subset \(\scr{C}\) from Lemma 13.1.1.

Theorem \(\PageIndex{1}\)

Set \(\mathbb{R}\) is uncountable.

Proof

This follows from Lemma 13.1.1 and Statement 4 of Proposition \(\PageIndex{1}\).

Example \(\PageIndex{3}\)

The Cartesian product set \(\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}\) is uncountable because it has an uncountable subset: the \(x\)-axis has the same size as \(\mathbb{R}\text{.}\)