Cantor’s theorem demystified: understanding uncountable sets

In this blog, we are going to learn why there is not a unique infinity and how it is possible that there are infinitely many infinities. But first, we need to understand what bijective functions, Cantor’s theorem, and countable and uncountable sets are. Let’s explore them one by one.

What is a bijective function?#

A function from the domain set to the codomain set assigns each element of the domain set to some element of the codomain set. Say the domain set is $A = \{1,2,3,4,5\}$, and the codomain set is $B=\{u,v,w,x,y,z\}$. An example of the function $f:A\to B$ is shown below:

As we can see, when the function $f$ maps the elements $2,3,$ and $5$ from $A$ to the same element $z$ in $B$, we say that $2,3,$ and $5$ has the same image ($z$). If a function maps every element of the domain to a unique element of the codomain, we call it an injective function. Therefore, under an injective function, no two elements of the domain set have the same image in the codomain set. If a function is such that every element of the codomain is an image of some element of the domain set, we call it a surjective function. If a function is both injective and surjective, we call it a bijective function.

The function $f$ shown in the figure above is neither injective nor surjective. Hence, it is not a bijective function.

Other than the sets $A$ and $B$, also consider the following two sets:

In the following illustration, the function $f_1$ (shown left) is injective but not surjective. The function $f_2$ (shown middle) is surjective but not injective. The function $f_3$ (shown right) is both injective and surjective—therefore, it is bijective.

A bijective function is also called a one-to-one correspondence or simply a correspondence. A correspondence pairs up the elements of domain and codomain.

• If a correspondence between two sets (say $X$ and $Y$) exists, then the cardinality of both sets is the same. Therefore:

• If no correspondence exists from $X$ to $Y$, then that means either no surjective function or no injective function exists from $X$ to $Y$. Let’s look at both scenarios.

• If no surjective function exists from $X$ to $Y$, then we can conclude that the number of elements in the set $X$is not sufficient to map every element of the set $Y$. Therefore:

• If no injective function exists from $X$ to $Y$, then we can conclude that there are not sufficient elements in $Y$ to assign a unique image to every element of $X$. Therefore:

Which set is a countable set?#

The set of natural numbers is a fundamental concept in mathematics and is denoted by the symbol $\mathbb{N}$. The set $\mathbb{N}$ consists of all positive integers, starting from $1$ and extending infinitely:

In some contexts, the set of natural numbers may include zero. Natural numbers are used for counting and ordering. The cardinality of the set of natural numbers is denoted by the Hebrew letter aleph ($\aleph$) with a subscript zero, as follows:

A set is countable if it is either finite or possesses the same cardinality as the set of natural numbers. Therefore, any set with a finite number of elements is, by definition, countable.

• Challenge with Infinite Sets: Assessing the countability of infinite sets depends on their cardinality matching that of the set of natural numbers.

• Determining Countability: To determine an infinite set's countability, verify if it has a bijection with the set of natural numbers.

• Role of Bijections: Bijections are used to establish whether two sets have equal or unequal cardinalities.

• Example Sets: Specific sets are examined to apply these concepts of countability and bijections. Consider the following sets:

Does $N_3, N_5,$ or $N_7$ have the same number of elements as $\mathbb{N}$? The answer is yes because we can show the following bijections:

These bijections are defined as follows:

To see why these functions are bijections, note that if $i\ne j$, then $3i\ne 3j, 5i\ne 5j,$ and $7i\ne 7j$. Therefore, $f_3,f_5,$ and $f_7$ are injective functions. Every element, $3x\in N_3,5x\in N_5,$ and $7x\in N_7$, is an image of $x\in \mathbb{N}$. Therefore, $f_3,f_5,$ and $f_7$ are surjective functions. This means that, $N_3, N_5$ and $N_7$ are countable sets, and we can conclude that their cardinality is the same as the set of natural numbers:

Other examples of countable sets include the set of integers, the set of even positive integers, the set of odd positive integers, the set of ordered pairs $(i,j)$ where $i$ and $j$ are integers, and the set of rational numbers.

Which set is an uncountable set?#

A set is uncountable when it is not finite and when no bijection exists from the set of natural numbers to the set. If we want to show that a given infinite set, $S$, is uncountable, we need to show that no bijection exists from the set of natural numbers to the set $S$. It is much more difficult to show that no bijection exists than to show that one does exist. The famous mathematician Georg Cantor, through his famous diagonalization method, showed that there is no surjective function from a set $A$ to its powerset, $\mathcal{P}(A)$. Therefore:

As a consequence of this result, we can use the diagonalization method to show that the set of real numbers is uncountable. This result has deep consequences in mathematics and philosophy.

Powerset of the set of natural numbers#

As a first example of an uncountable set, consider the powerset of the set of natural numbers $\mathcal{P}(\mathbb{N})$. No surjective function exists from the set of natural numbers to the powerset of the set of natural numbers. The reason is that no function $f$ maps a natural number to the following subset $S_f$ of natural numbers:

If we select a function $f$ that maps each natural number $i$ to a subset of natural numbers $f(i)$, it may or may not be the case that $f(i)$ contains the natural number $i$. We can simply state it as “under function $f$, a natural number may or may not be in its own image.” The set $S_f$ contains all those natural numbers, $x$, which are not present in their own image under the function $f$.

For every function $f: \mathbb{N}\to \mathcal{P}(\mathbb{N})$, there is a set $S_f$, which is not an image of any natural number under the function $f$.

Cantor’s argument here shows us that no surjective function from the set of natural numbers to the powerset of the set of natural numbers exists. Therefore, we can conclude that $\mathcal{P}(\mathbb{N})$ is an uncountable set and

To see why $S_f$ is always left unmapped under the mapping of $f$, we assume the opposite to get a contradiction. Assume that $n \mapsto S_f$ under the function $f$. We ask the question, “Is $n$ present in the set $S_f$?” There are two possible cases, and both lead to a contradiction.

If $n\in S_f$, then $n$ is in its own image, and this should not be the case because $S_f$ only contains those numbers that are not in their own image. Hence, this case leads to a contradiction.

If $n\not\in S_f$, then $n$ is not in its own image. Therefore, $S_f$ must contain $n$ because it contains all such numbers that are not in their own image. This is a contradiction.

Hence, we conclude that for every function $f$, a subset $S_f$ of the set of natural numbers is left unmapped. Therefore, $f$ is not surjective.

Infinitely many infinities#

Once it was established that $\left| A \right| < \left| \mathcal{P}(A) \right|$ for any set $A$, we used this fact to show that $\aleph_0 < \mathfrak c$ by taking $A = \mathbb{N}$. Here, $\mathfrak c$ is also an infinity, called the cardinality of the continuum, but it is greater than $\aleph_0$ and sometimes written as $2^{\aleph_0}$. We can keep taking powersets to make even bigger infinities. We can make infinitely many infinities, as shown below, in terms of the sizes of the sets:

The cardinality of the real numbers is $\mathfrak c$, and we can show this by presenting a bijection between the set of real numbers and the powerset of the set of natural numbers.

The continuum hypothesis#

We have defined the first infinity as $\left| \mathbb{N} \right| = \aleph_0$. The next infinity should be called $\aleph_1$, which is the smallest infinity that is larger than $\aleph_0$. The next infinity greater than the one we defined above is $\mathfrak c$. There are two possibilities: either $\mathfrak c = \aleph_1$ or $\mathfrak c > \aleph_1$. Cantor hypothesized that $\aleph_1 =\mathfrak c$—this is called the continuum hypothesis.

Conclusion#