Uncountable

A set $S$ is said to be uncountable if there is no injection $f:S\to\mathbb{N}$ . A well-known example of an uncountable set is the set of real numbers $\mathbb{R}$ .

Proof that $\mathbb{R}$ is uncountable

We give an indirect proof here. This is one of the most famous indirect proofs and was first given by Georg Cantor.

Suppose that the set $A=\{x\in\mathbb{R}:0<x< 1\}$ is countable. Let $\{\omega_1, \omega_2, \omega_3, ...\}$ be any enumeration of the elements of $A$ . Consider the binary expansion of each $\omega_i$ . For dyadic rationals, take only the expansion terminating in an infinite chain of zeros, so that we have a unique binary expansion for each element of $A$ . Say $\omega_i=(.b_{i1}b_{i2}b_{i3}...)_2$ for all $i$ . Now construct $\omega=(.b_1b_2b_3...)_2$ such that $b_i=1-b_{ii}$ for all $i$ . So $\omega$ is different from $\omega_i$ for all $i$ . So $\omega\not\in A$ . But $\omega\in\mathbb{R},0<\omega<1$ , a contradiction. So $\mathbb{R}$ is uncountable.

Page

Toolbox

Search

Uncountable

Proof that $\mathbb{R}$ is uncountable

See Also

Page

Toolbox

Search

Uncountable

Proof that is uncountable

See Also

Proof that $\mathbb{R}$ is uncountable