14 - More on countability

Countable Sets of Unions and Products

Let $A,B$ be countable sets

1. If $A$ and $B$ are disjoint, then $A\cup B$ is countable

2. $A\times B$ is countable

Proof

1. Since $A,B$ are countable then there are injections

$$f:A\to \mathbb{N}\text{ and }g:B\to \mathbb{N}$$

Define $h:A\cup B\to \mathbb{N}$ by

$$h(x)=\{\begin{array}{ll}2f(x)-1& \text{ if }x\in A\\ 2g(x)& \text{ if }x\in B\end{array}$$

Naturally this is an injection as both $f$ and $g$ are
2) Define

$$h:A\times B\to \mathbb{N}\text{by}h((a,b))=2^{f(a)}{3}^{g(b)}$$

By the uniqueness of prime factorisation in $\mathbb{N}$, it is an injection

Link to original

Countability of Positive Rationals

$${\mathbb{Q}}^{>0}\text{ is countable}$$

Proof

Define $f:{\mathbb{Q}}^{>0}\to \mathbb{N}$ by

$$f\left(\frac{p}{q}\right)=2^p{3}^q$$

where $p,q\in {\mathbb{Z}}^{>0}$ and $\mathrm{hcf}(p,q)=1$
And this is also an injection

Link to original

Countability of $\mathbb{Q}$

$$\mathbb{Q}\text{ is countable}$$

Proof

We can write $\mathbb{Q}={\mathbb{Q}}^{>0}\cup \{0\}\cup {\mathbb{Q}}^{<0}$
This is a disjoint union so as ${\mathbb{Q}}^{>0}$ is countable and then so is ${\mathbb{Q}}^{<0}$
with $\{0\}$ being finite hence it is countable
Therefore by countability of disjoint sets, $\mathbb{Q}$ is coutable

Link to original

Uncountability of ℝ

$$\mathbb{R}\text{ is uncountable}$$

Proof

It is sufficient to show that $(0,1]$ is uncountable
We know that $(0,1]$ is uncountable by the archimedean property

Suppose, for a contradiction, that $(0,1]$ is countably infinite so
Let the elements be $x_1,x_2,\cdots$
Each has a non-terminating decimal expression

$$\begin{array}{rl}{x}_1& =0.a_{11}{a}_{12}{a}_{13}{a}_{14}\cdots \\ x_2& =0.a_{21}{a}_{22}{a}_{23}{a}_{24}\cdots \\ x_3& =0.a_{31}{a}_{32}{a}_{33}{a}_{34}\cdots \\ ⋮& \\ x_k& =0.a_{k1}{a}_{k2}{a}_{k3}{a}_{k4}\cdots \\ ⋮& \end{array}$$

Construct a real number $x\in (0,1]$ with decimal expansion $0.b_1{b}_2{b}_3\cdots$
where

$$b_k=\{\begin{array}{ll}5& \text{if }{a}_{kk}=6\\ 6& \text{if }{a}_{kk}\ne 6\end{array}$$

Then $x_k\ne x$ for all $k$ as it differs at the $k^{\text{th}}$ decimal place
Hence $x$ is not in the list so it’s a contradiction
We pick $5$ and $6$ just to avoid $0$ or $9$

Link to original