next up previous contents
Next: Bigger sets Up: Countability Previous: Combinations   Contents

Countable sets

Definition 7.3.1   A set $ E$ is countable if there exists a bijection $ f: \; E \mapsto \mathbb{N}$.

The countable sets can be equivalently thought of as those that can be listed on a line.

Example 7.3.2       
The set $ \mathbb{N}$ is countable.
The set $ 2\mathbb{N}$ of all the even natural numbers is countable.

Lemma 7.3.3   Any subset $ S \subset \mathbb{N}$ is countable.

Proof. For: map the smallest element of $ S$ to $ 1$, the next smallest to $ 2$ and so on. $ \qedsymbol$

Lemma 7.3.4   A set $ S$ is countable iff $ \exists$ an injection $ f \colon S \mapsto \mathbb{N}$.

Proof. This is clear for finite $ S$. Hence assume $ S$ is infinite. If $ f \colon S \mapsto \mathbb{N}$ is an injection then $ f(S)$ is an infinite subset of $ \mathbb{N}$. Hence $ \exists$ a bijection $ g \colon f(S) \mapsto \mathbb{N}$. Thus $ gf \colon S \mapsto \mathbb{N}$ is a bijection. $ \qedsymbol$

The following result is obvious:

Corollary 7.3.5   Let $ A$ and $ B$ be two sets. If $ B$ is countable and if it exists an injection $ f: \; A \longrightarrow B$ then $ A$ is countable.

Proposition 7.3.6   $ \mathbb{Z}$ is countable.

Proof. Consider $ f: \; \mathbb{Z}\longrightarrow \mathbb{N}$,

$\displaystyle f: \; x \mapsto 
 2 x + 1 & \text{if $x \ge 0$} \\  
 - 2 x & \text{if $x < 0$.} 

This is clearly a bijection. $ \qedsymbol$

Proposition 7.3.7   $ \mathbb{N}^r$ is countable for any natural number $ r geq 1$.

Proof. The map $ (i_1, \dots, i_r) \mapsto 2^{i_1} 3^{i_2} \dots p_r^{i_r}$ ($ p_j$ is the $ j^{\text{th}}$ prime) is an injection by uniqueness of prime factorisation. $ \qedsymbol$

Lemma 7.3.8   If $ A_1, \dots, A_n$ are countable sets with $ n \in \mathbb{N}$, then so is $ A_1 \times \dots \times A_n$.

Proof. Since $ A_i$ is countable there exists an injection $ f_i: \; A_i
\longrightarrow \mathbb{N}$. Hence the function $ g: \; A_1 \times \dots
\times A_n \longrightarrow \mathbb{N}^k$ defined by $ g(a_1,\dots,a_n) =
(f_1(a_1),\dots,f_n(a_n))$ is an injection. $ \qedsymbol$

Proposition 7.3.9   $ \mathbb{Q}$ is countable.

Proof. Define $ f: \; \mathbb{Q}\longrightarrow \mathbb{N}$ by

$\displaystyle f: \; \frac{a}{b} \mapsto 2^{\lvert a\rvert } 3^b 5^{1+\sign a},$    

where $ (a,b) = 1$ and $ b > 0$. $ \qedsymbol$

Theorem 7.3.10   A countable union of countable sets is countable. That is, if $ I$ is a countable indexing set and $ A_i$ is countable $ \forall i \in I$ then $ \bigcup_{i \in I} A_i$ is countable.

Proof. Identify first $ I$ with the subset $ f(I) \subseteq \mathbb{N}$. Define $ F \colon A \mapsto \mathbb{N}$ by $ a \mapsto 2^n 3^m$ where $ n$ is the smallest index $ i$ with $ a \in A_i$, and $ m = f_n(a)$. This is well-defined and injective (stop to think about it for a bit). $ \qedsymbol$

Definition 7.3.11   An algebraic number is a root of a polynomial, whose coefficients are rational. If a number is not algebraic, it is called transcendental.

For example, $ \sqrt{2}$ is an algebraic number as it is a root of the polynomial $ X^2-$. The number $ \pi$ and the number $ e$ (basis of the natural logarithm) are transcendental.

Theorem 7.3.12   The set of all algebraic numbers is countable.

Proof. Let $ P_n$ be the set of all polynomials of degree at most $ n$ with integral coefficients. Then the map $ c_n x^n + \dots + c_1 x + c_0
\mapsto (c_n, \dots, c_1, c_0)$ is an injection from $ P_n$ to $ \mathbb{Z}^{n+1}$. Hence each $ P_n$ is countable. It follows that the set of all polynomials with integral coefficients is countable. Each polynomial has finitely many roots, so the set of algebraic numbers is countable. $ \qedsymbol$

Theorem 7.3.13 (Cantor's diagonal argument)   $ \mathbb{R}$ is uncountable.

Proof. Assume $ \mathbb{R}$ is countable, then the elements can be listed as

$\displaystyle x_1$ $\displaystyle = n_1 . d_{11} d_{12} d_{13} \dots$    
$\displaystyle x_2$ $\displaystyle = n_2 . d_{21} d_{22} d_{13} \dots$    
$\displaystyle x_3$ $\displaystyle = n_3 . d_{31} d_{32} d_{33} \dots$    
$\displaystyle \dots$ $\displaystyle \dots$    

(in decimal notation). Now define the real $ b = 0.b_1 b_2 b_3 \dots$ by $ b_i = 0$ if $ d_{ii} \neq 0$ and $ b_i
= 1$ if $ d_{ii} = 0$. This is a real number, but it differs from $ x_i$ in the $ i^{\text{th}}$ decimal place. So the list is incomplete. This shows that the set of all the reals is uncountable. $ \qedsymbol$

Exercise: use a similiar proof to show that $ \mathcal{P}(\mathbb{N})$ is uncountable.

Theorem 7.3.14   The set of all transcendental numbers is uncountable. (And therefore at least non-empty!)

Proof. Let $ A$ be the set of algebraic numbers and $ T$ the set of transcendentals. Then $ \mathbb{R}= A \cup T$, so if $ T$ was countable then so would $ \mathbb{R}$ be. Thus $ T$ is uncountable. $ \qedsymbol$

next up previous contents
Next: Bigger sets Up: Countability Previous: Combinations   Contents
root 2002-06-10