9. Countable sets

Countable sets

For finite sets, we can simply count the number of elements in each. If finite sets have the same number of elements, then there is always a bijection between them.

Two infinite sets have the same size if there is a bijection between them.

Countable set

We can call a set $A$ countable if it is either finite or there is a [[Bijection (function)|bijection]] between $A$ and $\mathbb N$.

For example:

• ${\text{id}}_N:\mathbb{N}\to \mathbb{N}$ is a bijection hence $N$ is countable.
• Given Odd is the set of odd natural numbers, we find that even if $\text{Odd}\subset \mathbb{N}$, it still has the same size as $\mathbb{N}$. The function $f:\mathbb{N}\to \text{Odd}$ defined by $\boxed{f(x)=2x+1}$ is a bijection.

Link to original

$\mathbb{N}\times \mathbb{N}$ is countable

title: Not in exam.

We need to describe a bijection between $\mathbb{N}\times \mathbb{N}$ and $\mathbb{N}$. We arrange the ordered pairs in $\mathbb{N}\times \mathbb{N}$ in such a way that they can be easily counted:

$$\begin{array}{rl}(0,0)& ⟺0,\\ (0,1),(1,0)& ⟺1,2,\\ (0,2),(1,1),(2,0)& ⟺3,4,5,\\ (0,3),(1,2),(2,1),(3,0)& ⟺6,7,8,9,\\ & [...]\end{array}$$

We can describe this $\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ bijection by

$$(m,n)⟺(1+2+...+(m+n))+m$$