Uncountable Sets

What is an uncountable set?

A set that is not countable is called an uncountable set. To establish that a set $A$ is uncountable, we must show that a bijection between the set of positive integers $\mathbb{Z}^+$ and the set $A$ does not exist. However, it is not obvious to prove that a bijection between two sets does not exist.

As our first example, we will show that a set of real numbers is uncountable. For that, Cantor’s diagonalization method is a powerful argument—developed by Georg Cantor—to show the nonexistence of a bijection between a set of positive integers and a set of real numbers. This technique has applications in many areas of science and philosophy.

A set of real numbers

In this section, we will prove that a set of real numbers $\mathbb{R}$ is uncountable by showing that no bijection exists between a set of positive integers and the set of real numbers using the technique of proof by contradiction. A real number $r_n$—in its general form with the position of a decimal point after the digit $d_n^p$—can be viewed as follows:

Let’s assume that this set of real numbers is countable. If that is the case, then there exists a bijection $f: \mathbb{Z}^+ \mapsto \mathbb{R}$. We can abstractly represent $f$ as shown in the table below, where the first column shows the elements of the domain, and the second column shows the images assigned to them under $f$.