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.

Understanding Cantor’s theorem in its most general form#

Cantor’s theorem isn’t just about the natural numbers — it’s a universal truth for any set A. It states that for every set A, the power set 𝒫(A) — the set of all subsets of A — has a strictly larger cardinality than A itself.

Formally:
|A| < |𝒫(A)|

This means there is no surjective function f : A → 𝒫(A), because we can always construct a subset of A not included in the range of f. This result is deeply foundational — it shows that infinity itself comes in larger and larger sizes.

One of the most illuminating ways to understand why the power set is larger is by thinking of subsets as functions.

Every subset of A corresponds to a characteristic function:

χₛ : A → {0, 1}, where
χₛ(a) = 1 if a ∈ S, and χₛ(a) = 0 otherwise.

This shows that:
|𝒫(A)| = |{0, 1}ᴬ|

This connection helps explain why the cardinality of the power set is exponential in the size of the original set — and why |𝒫(ℕ)| = 𝔠 (the cardinality of the continuum).

The continuum hypothesis and its independence#

The continuum hypothesis (CH) asks whether there exists a set whose size is strictly between |ℕ| (the size of the natural numbers) and |𝒫(ℕ)| (the size of the continuum).

Formally:
CH: There is no set A such that |ℕ| < |A| < |𝒫(ℕ)|

Kurt Gödel (1940) showed that CH cannot be disproved from the standard axioms of set theory (ZFC).
Paul Cohen (1963) showed that CH cannot be proved from ZFC either.

This means CH is independent of ZFC: both CH and ¬CH are logically consistent if ZFC itself is. Including this point gives readers an honest picture of one of mathematics’ most fascinating open questions.

Diagonalization beyond sets: applications in computer science#

Cantor’s diagonal argument is more than a clever proof — it’s a fundamental technique across mathematics and computer science.

Here are some key places it appears:

• Halting problem: Alan Turing used a diagonal argument to prove that no algorithm can decide whether all programs halt.

• Uncomputable numbers: Since there are only countably many algorithms but uncountably many real numbers, most real numbers are uncomputable.

• Gödel’s incompleteness theorem: Diagonal self-reference underpins Gödel’s proof that any sufficiently powerful formal system contains true but unprovable statements.

This broader view helps readers see Cantor’s argument not as a curiosity, but as a powerful tool with real-world consequences.

Avoiding pitfalls: binary expansion caveats#

When using diagonalization to prove that real numbers are uncountable, one subtle detail often gets overlooked: some real numbers have two binary representations.

For example:
0.1000… = 0.0111…

To avoid this ambiguity, mathematicians either restrict themselves to decimal expansions that don’t end in repeating 9s (or 1s in binary), or they work directly with infinite binary sequences {0,1}^ℕ, which sidestep the issue entirely.

The Cantor–Bernstein–Schröder theorem and paradoxes#

Cantor’s theorem fits into a larger landscape of set theory results. One key theorem to know is the Cantor–Bernstein–Schröder theorem, which says:

If there’s an injection from A to B and from B to A, then there’s a bijection between them.

This result complements Cantor’s theorem by providing a powerful tool for comparing infinities.

It’s also worth mentioning Cantor’s paradox — the observation that there can’t be a “set of all sets,” since its power set would necessarily be larger. This paradox was a major driver behind the development of modern axiomatic set theory.

Beth numbers and the hierarchy of infinities#

To deepen understanding, it’s helpful to introduce the concept of beth numbers — an alternative notation for infinite cardinalities defined by successive power sets:

ℶ₀ = |ℕ|
ℶ₁ = |𝒫(ℕ)| = 𝔠
ℶ₂ = |𝒫(𝒫(ℕ))|, and so on.

This notation emphasizes how applying the power-set operation again and again produces an infinite tower of ever-larger infinities — a direct consequence of Cantor’s theorem.

Conclusion#