0.5 Countable Sets and Set of Real Numbers

We begin by defining countable sets.

A set $X$ is countable if $|X| \leq |\mathbb{N}|$. For finite sets, we denote $$ |X| = n \iff |X| = |\left\{ 1, 2, ..., n \right\}|$$

Since $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|$ by this theorem, power set of natural numbers is uncountable.

1. Finite product of countable sets are countable.
2. Countable union of countable sets is countable.
3. If $X$ is countably infinite, then $|X| = |\mathbb{N}|$.

1. It is sufficient to show that $\mathbb{N} \times \mathbb{N}$ is countable. Define a function $$ h: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N},\ h(n, m) = \frac{(n+m)(n+m-1)}{2} + 1- n $$ This is clearly injection (check it!). So $\mathbb{N} \times \mathbb{N}$ is countable. Using induction, we can deduce that finite product of countable sets are countable.
2. Let $\left\{ X_{\alpha} \right\}_{\alpha \in A}$ be countable collection of countable sets. First for each $X_{\alpha}$, there exist surjection $$ g_{\alpha}: \mathbb{N} \rightarrow X_{\alpha}$$ Also there exist surjection $$ f: \mathbb{N} \rightarrow A$$ Define $$ h: \mathbb{N} \times \mathbb{N} \rightarrow \bigcup_{\alpha \in A} X_{\alpha},\ h(n, m) = g_{f(n)}(m) $$ then $h$ is surjection. This implies that $\cup_{\alpha} X_{\alpha}$ is countable.
3. It is sufficient to show that there exist injection from $\mathbb{N}$ to $X$. First, well order $X$ by some relation $\leq$. Then define $$ f: \mathbb{N} \rightarrow X,\ f(n) =\begin{cases} \leq\text{-smallest element on }X & (n = 1) \\ \leq\text{-smallest element on }X\setminus \left\{ f(1), f(2), ..., f(n-1) \right\} & (n > 1) \end{cases} $$ Clearly $f$ is injection. By Schröoder-Bernstein theorem, $|X| = |\mathbb{N}|$.

$\mathbb{Z}$ and $\mathbb{Q}$ are countable.

Since $\mathbb{Z}$ is union of countable sets; namely $\mathbb{N} \cup \left\{ -n: n \in \mathbb{N} \right\} \cup \left\{ 0 \right\}$, it is countable. The function $$ f: \mathbb{Z} \times \mathbb{Z}\setminus \left\{ 0 \right\} \rightarrow \mathbb{Q},\ f(p,q) = \frac{p}{q} $$ is surjection; so $\mathbb{Q}$ is countable.

Now we come to set of real numbers, $\mathbb{R}$.

A set $X$ is said to have the cardinality of the continuum if $|X| = |\mathbb{R}|$. We denote $|\mathbb{R}| = \mathfrak{c} $.

A nice proposition shows that power set of natural numbers has cardinality of continuum.

$|\mathcal{P}(\mathbb{N})| = \mathfrak{c}$.

Define a function $$ f: \mathcal{P}(\mathbb{N}) \rightarrow \mathbb{R},\ f(A) = \begin{cases} 2 & (\text{if } A = \emptyset) \\ 1 + \sum_{n \in A} 2^{-n} & (\text{if }A\text{ is finite})\\ \sum_{n = 1}^{\infty} \chi_{A}(n) 2^{-n} & (\text{if }A\text{ is infinite}) \end{cases}$$ where $\chi_{A}(x) = 1$ if $x \in A$ and $0$ otherwise. Now suppose $f(A) = f(B)$. Since finite sets have function value strictly larger than infinite sets, both are finite or both are infinite. Define $\alpha$ and $\beta$ be least elements on infinite sets $A$ and $B$ respectively. Then, $$ f(A) = 2^{-\alpha} + \Sigma^{A} = 2^{-\beta} + \Sigma^{B} = f(B) $$ for some $\Sigma^{A}$, $\Sigma^{B} > 0$. Then $$ 2^{-\alpha} < f(A) = 2^{-\beta} + \Sigma^{B} \leq 2^{-\beta} + 2^{-\beta} = 2^{-\beta + 1} $$ and $$ 2^{-\beta} < f(B) = 2^{-\alpha} + \Sigma^{A} \leq 2^{-\alpha + 1}$$ Combining both equations give $\alpha > \beta - 1$ and $\beta > \alpha - 1$, which in turn $ \beta - 1 < \alpha < \beta + 1 \implies \alpha = \beta$. Now using transfinite induction, $A = B$. For finite sets, exactly same reasoning (as in the case of infinite sets) can be applied. So $f$ is injection.

Every real number $x \in (0, 1)$ has a unique base-2 decimal expansion $x = \sum_{n = 1}^{\infty} x_{n}2^{-n}$ (not including the repeated 1's on the end). Define a function $$ g: \mathcal{P}(\mathbb{N}) \rightarrow \mathbb{R}^{\leq 0},\ g(A)= \begin{cases} \ln \left( \sum_{n=1}^{\infty} \chi_{A}(n) 2^{-n} \right) & (A \neq \emptyset) \\ -1 & (A = \emptyset) \end{cases} $$ This is clearly surjection. Composition with surjective function $$h:\mathbb{R}^{\leq 0} \rightarrow \mathbb{R},\ h(x) = \begin{cases} \ln(-x) &( x \neq 0) \\ 1 & (x = 0) \end{cases}$$ $h \circ g$ is surjection. By the Schröder-Bernstein theorem, $|\mathcal{P}(\mathbb{N})| = \mathfrak{c}$.

There is a proposition for $\mathfrak{c}$ analogous to countable sets.

1. If $|X| \leq \mathfrak{c}$ and $|Y| \leq \mathfrak{c}$, then $|X \times Y| \leq \mathfrak{c}$.
2. If $|A| \leq \mathfrak{c}$ and $|X_{a}| \leq \mathfrak{c}$ for all $a \in A$, then $|\cup_{a \in A} X_{a}| \leq \mathfrak{c}$.

1. It is sufficient to check for $X = Y = \mathcal{P}(\mathbb{N})$. First define $\phi, \psi: \mathbb{N} \rightarrow \mathbb{N}$ by $\phi(n) = 2n$ and $\psi(n) =2n-1$ (both are bijections). Now define a map $$ f: \mathcal{P}(\mathbb{N}) \times \mathcal{P}(\mathbb{N}) \rightarrow \mathcal{P}(\mathbb{N}),\ f(A, B) = \phi(A) \cup \psi(B) $$ This is clearly bijection because every nonempty subset of natural numbers can be partitioned into set of even numbers and set of odd numbers. So $|\mathcal{P}(\mathbb{N}) \times \mathcal{P}(\mathbb{N})| \leq \mathfrak{c}$.
2. Let $f: A \rightarrow \mathbb{R}$, $g_{\alpha}: X_{\alpha} \rightarrow \mathbb{R}$ ($\alpha \in A$) injections. Then $$ h: \mathbb{R} \times \mathbb{R} \rightarrow \bigcup_{\alpha \in A} X_{\alpha},\ h(x, y) = g_{f(x)}(y) $$ is surjection. Since $|\mathbb{R} \times \mathbb{R}| \leq \mathfrak{c}$, so does $\cup_{a \in A} X_{a}$.