Uncountable Set

set-theory

Definition

Uncountable Set

An uncountable set $S$ is an infinite set that is too large to enumerate with the natural numbers, i.e. there is no bijection between $S$ and $\mathbb{N}$.

Equivalently, its elements cannot be enumerated as a single infinite sequence.

Examples: $\mathbb{R},\mathcal{P}(\mathbb{N}),\{0,1{\}}^{\mathbb{N}}$

Examples

$\{0,1{\}}^{\mathbb{N}}$

Diagonalisation: Assume that $\{0,1{\}}^{\mathbb{N}}$ is countable. Then, there exists a bijection $f:\mathbb{N}\to \{0,1{\}}^{\mathbb{N}}$, i.e. every natural number can be represented as a sequence of zeros and ones.

Define a new sequence $d:\mathbb{N}\to \{0,1\}$ that flips the $k$-th bit of the $k$-th listed sequence.

$$d(k)=1-f(k{)}_k$$

Trivially, $\forall n\in \mathbb{N}:d(n)\ne f(n{)}_n$. Thus $d\in \{0,1{\}}^{\mathbb{N}}$ but $d$ is not equal to any $f(n)$, contradicting that $f$ that $f$ is surjective. Therefore, the assumption that $\{0,1{\}}^{\mathbb{N}}$ is countable is wrong and $\{0,1{\}}^{\mathbb{N}}$ is uncountable.

Visually:

$$\begin{array}{rclllllll}f(0)& =& (& 0,& 1,& 1,& 0,& 1,& \dots )\\ f(1)& =& (& 0,& 1,& 0,& 1,& 0,& \dots )\\ f(2)& =& (& 1,& 1,& 0,& 1,& 1,& \dots )\\ f(3)& =& (& 0,& 1,& 1,& 0,& 1,& \dots )\\ f(4)& =& (& 1,& 0,& 1,& 1,& 1,& \dots )\\ ⋮& & & & & & & & \\ & & & & & & & & \\ \text{Diagonal:}& & & 0,& 1,& 0,& 0,& 1,& \dots \\ & & & & & & & & \\ d& =& (& 1,& 0,& 1,& 1,& 0,& \dots )=(1-f(n{)}_n{)}_{n\in \mathbb{N}}\end{array}$$

$[0.5,0.51)$

Diagonalisation: Assume that $I=[0.5,0.51)$ is countable. Then, there exists a bijection $f:\mathbb{N}\to I$.

All real numbers $x\in I$ is uniquely identified by its decimal digits and can be represented by:

$$\forall x\in I:\exists a_1,a_2,\cdots \in \{0,1,\dots ,9\}:x=0.50a_1{a}_2{a}_3\dots$$

Since $f$ is injective, $n_1\ne n_2⟹f(n_1)\ne f(n_2)$. Therefore, every $n\in \mathbb{N}$ has its own selection of $(a_i)$:

$$f(n):=0.50a_{n,1}{a}_{n,2}{a}_{n,3}\dots$$

Visually, a 2D matrix appears which can be used to create a diagonal.

$$\begin{array}{rl}f(0)& =(a_{0,1},a_{0,2},a_{0,3},\dots )\\ f(1)& =(a_{1,1},a_{1,2},a_{1,3},\dots )\\ f(2)& =(a_{2,1},a_{2,2},a_{2,3},\dots )\\ ⋮& =⋮\end{array}$$

To show is that there is no $r\in I⟹r\notin f[\mathbb{N}]$. As said above, real numbers are uniquely identified by their digits, i.e. if one digit differs, they are considered distinct. Let $(b_n{)}_{n\in \mathbb{N}}$ be a helper sequence that ensures that the $n$-th digit is always different from each sequence:

$$b_n:=\{\begin{array}{ll}1& \text{if}{a}_{n,n}=0\\ 0& \text{else}\end{array}$$

Further, let’s define $r$ as:

$$r=0.50b_0{b}_1{b}_2{b}_3\dots$$

$r\ne f(0)$ because $b_0\ne a_{0,0}$. $r\ne f(1)$ because $b_1\ne a_{1,1}$, etc. Therefore:

$$\forall n\in \mathbb{N}:r\ne f(n)$$

which means a number $r\in I$ is found that does not occur in $f[\mathbb{N}]$, which is contradictory since $f$ is surjective. Hence, the initial assumption is wrong and $I=[0.5,0.51)$ is uncountable.