countable

Countable

A set $S$ is called countable if its elements can be put into a one-to-one correspondence with the natural numbers $\mathbb{N}=\{0,1,2,3,\dots \}$, i.e. if there exists a bijection $f:\mathbb{N}\to S$.

This means you can list the elements of $S$ in a sequence (possibly infinite), such that every element appears exactly once in the list. It’s like enumerate in Python.

Note

Countable doesn’t mean we can actually count every natural number, but that we can map any element of a set to a unique natural number.
E.g. we can count all integers, even though there seem to be “more” integers than natural numbers, because we can map them to natural numbers like this:

$$f(n)=\{\begin{array}{ll}2n& \text{if }n\ge 0\\ -2n-1& \text{if }n<0\end{array}$$

→ $f(0)=0,f(1)=2,f(-1)=1,f(2)=4,f(-2)=3,\dots$
And we can map that back to the natural numbers:

$$f^{-1}(m)=\{\begin{array}{ll}\frac{m}{2}& \text{if }m\text{ is even}\\ -\frac{m+1}{2}& \text{if }m\text{ is odd}\end{array}$$

→ $f^{-1}(0)=0,f^{-1}(1)=-1,f^{-1}(2)=1,f^{-1}(3)=-2,f^{-1}(4)=2,\dots$
→ $\mathbb{N}$ and $\mathbb{Z}$ have the same cardinality.

Uncountable

TODO https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

Uncountable sets

The real number interval $[0,1]$
The power set of $\mathbb{N}$.
The set of all infinite binary sequences $\{0,1{\}}^{\mathbb{N}}$