Functions - 8
Uncountable Sets
A set that is not countable is called uncountable. The following set is uncountable:
\[S = \{ x \in \mathbb{R} \vert 0 < x < 1 \}\]There is no bijective function from this set to the set of all natural numbers.
Cantor’s Diagonal Argument
Suppose for a proof by contradiction that there exists a bijection $f:\mathbb{N^+}\rightarrow S$. Consider decimal representation of $f(n)$, for $n\in\mathbb{N^+}$:
In this example we are proving for all decimals between 0 and 1. We are considering that there is a mapping that makes them countable.
- $f(1)=0.a_{11}a_{12}a_{13}\ldots a_{1n}\ldots$
- $f(2)=0.a_{21}a_{22}a_{23}\ldots a_{2n}\ldots$
- $f(3)=0.a_{31}a_{32}a_{33}\ldots a_{3n}\ldots$
- $\vdots$
- $f(n)=0.a_{n1}a_{n2}a_{n3}\ldots a_{nn}\ldots$
- $\vdots$
In this proof we treat this as a table without the leading zero and consider the main diagonal where the digit $a_{ij}$ has equal $i$ and $j$.
We show that there exists $d\in S$ such that for no $i\in\mathbb{N^+}$ we have $f(i)=d$.
Let $d=0.d_{1}d_{2}d_{3}\ldots d_{n}\ldots$ where $d_i=\begin{cases}2, & \text{if } a_{ii}=1\ 1, & \text{if } a_{ii}\neq 1\end{cases}$
Then for every $i\in\mathbb{N^+}$ $d$ is different at position $i$ from $f(i)$. So, for no $i\in\mathbb{N^+}$ we have $f(i)=d$, fo $f$ is not surjective. A contradiction.