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. Properties of countability.

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 for Statement 1.

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.

Proof outline for Statement 2.

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.

Proof outline for Statement 3.

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.

Proof outline for Statement 4.

This is the contrapositive of Statement 3, under the common assumption \(A \subseteq B \text{.}\)

Proof outline for Statement 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 \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.

This follows from Lemma 13.1.7 and Statement 4 of Proposition 13.2.1.

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{.}\)

Prev Top Next