My theory stands as firm as a rock; every arrow directed against it will return quickly to its archer. — Georg Cantor

As quoted in Journey Through Genius (1990) by William Dunham

Indeed. Cantor’s theory of the infinite has stood the test of time and its fair share of critics. Over the years, it has progressed from Kronecker’s public denouncement of the theory as “corrupter of youth” to firmly establishing itself as the precursor to the now universally accepted ZFC set theory.

This article tries to give a sneak peek into the most famous implication of Cantor’s theory, the existence of an infinity of infinities. For better understandability, the article has been divided into two parts. The first one introduces the notion of one to one correspondence, which is the essence of Cantor’s famous theorem. The second part deals with the theorem, its proof and implications.

Part I : One to One Correspondence

Think you know counting? Yes, plain old counting. 1, 2, 3, 4, …. Think again! Maybe the below scenario will help invigorate your mind.

Do 1, 2, 3, … really mean anything?

Imagine you are in a tribal jungle as part of an expedition, and are trying to converse with the locals. Of course, they don’t know English (or any other language you know for that matter). And you need to convey the number “4” to them. How do you do that? Surely, you can’t use 4 as such, since it would be unintelligible to them. Instead, you would most likely display four fingers from your hand, or maybe pick up four sticks from the ground and point towards them.

The locals would then be able to comprehend what you are trying to say. They will translate your symbol into the representation for number 4 in their language, say ∇.

How was that possible? If you look closely, you would realize that our brain associates a mental picture with the number 4. That picture can be anything which contains a set of 4 objects. For example, the four lines on your little finger, four houses, or four playing cards. The important thing is not what those objects are, rather how many objects are there.

Returning to the above example, knowing that you can’t use the number 4 as such for communication, your brain directs you to use any set containing 4 elements to represent your thought. Next, the tribes’ brains are able to conceive the pictorial information you convey, and convert it into the number 4 in their language, ∇.

The Inspiration

That is the fundamental idea behind Cantor’s pioneering work on counting! Numbers by themselves are just symbols, sans meaning. What breathes life into them is the mental construction on which they are based. “4” is just a symbol. What really matters is the mental image you conceive when using that symbol. Over time, our brain becomes so adept at using that information that we no longer bother about it.

The Basics

Forget all that you know about counting. So now, you don’t know a thing about 0, 1, 2, 3, … Is there still a way which would allow you to determine if two sets contain the same number of elements? Some ideal that is more primitive than the counting symbols? It turns out there is one.

One to One Correspondence

We say that two sets, A and B, have the same number of elements (or are equi-cardinal or equipollent) if there exists a one to one correspondence between the two. A one-to-one correspondence is nothing more than a mapping that maps elements from set A to elements of set B, subject to fulfilment of the below conditions –

• Every element in set A is mapped to a unique element in set B.

• No two elements of A are mapped to the same element in B.

• For every element b ∈ B, there exists at least one element a ∈ A, such that a maps to b.

Taken together, the above three conditions imply that every element of A is mapped to exactly one element of B, and vice-versa.

Now, some examples …

Finite Sets

Here, we have used the word “finite” rather loosely. The concept of finiteness is one of the most exhaustively worked upon topics in set theory. However, for our purpose, the layman notion of finiteness will suffice. This will be evident from the below examples.

• A = {1, 2, Goat, Cat}, B = {Hello, 5, Q}
  Here, you won’t be able to find a one to one correspondence between the elements of sets A and B. That is because, no matter what you try, one element of A will be left without a partner in B. In some sense, A is too large to be mapped to B.

• A = {Hello, 5, Q}, B = {1, 2, Goat, Cat}
  Reverse of the above case turns out to be problematic as well. Now, though you would be able to map each element of A uniquely to an element of B, there would be an element of B left unassigned. In this case, B is too large to be mapped to A.

• A = {1, 2, Goat}, B = {Hello, 5, Q}
  This is what we wanted! Here, you can easily carry out a one to one mapping from A to B. And it turns out you can do so in more than one way. However, at least one is all that matters. That suffices for us to conclude that A and B contain the same number of elements (or are equipollent). Keep in mind that nowhere have we mentioned that A and B contain 3 elements each. In fact, we do not know how many elements each contains. Rather, what we do know (from one to one correspondence) is that they contain the same number of elements.

Now, things get interesting …

What about non-finite, or infinite, sets ?

Again assuming the layman notion, we now talk about infinite sets such as —

• ℕ = {1, 2, 3, …} (the set of all natural numbers)
• E = {2, 4, 6, 8, …} (the set of all even numbers)
• S = {1, 4, 9, 16, …} (the set of all perfect squares)

As it turns out, infinite sets can have one-to-one correspondence with their proper subsets as well, a rather unintuitive result. How? Consider this for an example —

ℕ has the same number of elements as E !

This can be easily proved by forming the below mapping :

For any element n ∈ ℕ, map it to 2n ∈ E. In this way, each element of ℕ gets assigned to a unique element of E, and vice-versa. Pictorially, it can be depicted as follows –

So, believe it or not, there are as many even numbers as there are natural numbers! It’s not the case that there are more natural numbers than even numbers, even though the set of even numbers is a proper subset of the set of natural numbers.

Let’s blend in some geometry …

What about sets containing the points on two lines of varying lengths? Intuitively, the larger line should have more number of points, right? Well … not really. In fact, it turns out that two line segments, irrespective of their lengths, contain exactly same number of points!

Proving this requires that given any two lines, we should be able to establish a one-to-one correspondence between their points. That can be done as shown below.

What about sets containing points on the boundary of two circles of different sizes? Most probably you guessed it yourself. Circles of different sizes contain the same number of points as well on their boundaries! And in this case, it’s much easier to visualize the one-to-one correspondence.

So, there you have it. A set containing the same number of elements as one of its proper subsets, lines of varying sizes containing the same number of points, and circles with different radii having exactly same number of points. Counting, it seems, is far from trivial and uninteresting!

Okay… so can we totally do away with numbers?

Obviously, counting is just the most primitive functionality associated with numbers. Then there are the basic arithmetical operations — addition, multiplication and exponentiation. What about these? Can these also be provided for by set theory? Indeed. As it turns out, set theory provides an elegant framework for these basic operations, without using the notion of numbers as such.

However, all this is not to argue that numbers should be done away with altogether. Rather, they are indispensable for everyday life. In some way, the numbers we use for daily transactions are abstractions for the underlying set theoretic principles. While we can completely forego the numbers and use set theoretic principles for our transactions as well, but it would be a cumbersome overkill for the layman. The concept of numbers allows the general public to carry out daily chores without having to be adept at set theory.

All in all, this was just a closer look into what these numbers really mean, what do they actually represent, and what does “equal” mean in context of counting.

Also, understanding the above is a pre-requisite for comprehending the following section, which explores Cantor’s infinity of infinities!

Part II : Cantor’s theorem

Before delving into Cantor’s theorem and its proof, we must be aware of the concept of the power set of a set.

Power set of A

The power set of A, 𝒫(A), is the set of all the subsets of A. For example, if

Then

Now, without further ado, let’s dive straight into Cantor’s theorem!

Cantor’s theorem states that there does not exist a set A such that A and 𝒫(A) have the same cardinality, i.e., a set A and its power set can never have the same number of elements.

Just in case the above seems obvious to you, note that

• Nowhere has it been mentioned how many elements do A and 𝒫(A) contain. Rather, it just asserts that regardless of the exact number, A and 𝒫(A) cannot contain the same number of elements.
• Also, you might argue that the theorem is plain obvious, because if A contains n elements, then 𝒫(A) contains 2ⁿ elements. But remember that first of all, we are not dealing in numbers here. Secondly, the theorem holds true for infinite sets as well, not just finite ones. Clearly, your n and 2ⁿ argument won’t hold up there.

The Proof

Remember that two sets having the same cardinality implies that there exists a one to one correspondence between the two.Now, we deploy a proof by contradiction. Let there exist a set A such that A and 𝒫(A) contain the same number of elements. Then, there must exist a one to one correspondence between them. Let it be represented by the symbol f.In mathematics, this f is called a function. It serves a simple purpose. It takes an input and gives an output. The input is an element from set A. The output is an element from 𝒫(A). Simple as that. To illustrate this point using the aforementioned example, one of the possibilities for f isf(1) = {1, 45}
f(ABC) = {45}
f(45) = Ø

However, to qualify as a one to one correspondence the function f must also satisfy the following condition

Now, consider the set

That is, C is the collection of all elements a belonging to A on the condition that these elements do not belong to their corresponding element in 𝒫(A). Here, by corresponding we mean the element to which a is mapped under the function f. Remember that f(a) is an element of 𝒫(A), and hence a set itself. That is why the notion of “belonging to” f(a) makes sense.Now, since every element of C is taken from A, therefore C is a subset of A. Therefore, C ∈ 𝒫(A).So, from (1), there must exist an element c ∈ A such that f(c) = C.Now, consider the question -- Does c ∈ C?Of course, there are only two possibilities here (i) c ∈ C
In this case, c belongs to f(c). That is, c is an element of A that belongs to its image in 𝒫(A). But then from (2), c should not belong to C.
Hence, this case cannot be possible.(ii) c ∉ C
In this case, c is an element of A that does not belong to its image in 𝒫(A). Then from (2), c should belong to C.
Hence, this case is also not possible.We have arrived at a contradiction! Neither case can hold true, while one must. Therefore, our initial assumption is wrong. That is, there does not exist a set A such that A and its power set have the same number of elements.

Implications on our understanding of infinity

One of the key criteria for judging a pure mathematics result is the depth of its implications. And as far as that is concerned, not many theorems can challenge Cantor’s. It literally blew off the roof mathematicians had been operating under for centuries.

Mathematicians got their first tangible glimpse into the nature of infinity. What unfolded was unimaginable. For, after the roof was out of the way, there wasn’t just one sky visible. Rather an infinite sequence of skies. One above the other, another one over that and so on …

The realization creeped in … Infinity comes in different sizes! With an endless list to choose from.

Wait, what … an infinity of infinities?

Yes! Let’s explore how Cantor’s theorem necessitates that there must exist infinities of different magnitudes. Consider the set of natural numbers

ℕ = {1, 2, 3, …}

Vaguely speaking, it contains an infinite number of elements. Okay, but then what about 𝒫(ℕ)? It also contains an infinite number of elements. But are the two infinities same in magnitude? No! That’s what Cantor’s theorem ascertains, that no set and its power set can have the same number of elements. In some sense, the number of elements in 𝒫(ℕ) is strictly greater than the number of elements in ℕ.

Cantor used the symbol ℵ₀ to represent the number of elements in ℕ, and ℵ₁ to represent the number of elements in 𝒫(ℕ). Though both are infinite, it turns out that ℵ₀< ℵ₁. Thus we have a relative ordering among the infinities! Carrying on along among similar lines, the number of elements in 𝒫(𝒫(ℕ)), ℵ₂, is an infinity of greater magnitude than ℵ₁.

Thus

ℵ₀ < ℵ₁ < ℵ₂ .…

This is the gist of Cantor’s infinity of infinities. Two sets containing an infinite number of elements may or may not have the same number of elements. One may have more elements with respect to the other.

Cardinalities of ℚ, ℝ and the Continuum Hypothesis

Cantor went on to prove that the set of real numbers, ℝ, also has ℵ₁ elements. That is, there is a one to one correspondence between R and 𝒫(ℕ). This implies that the number of real numbers (ℵ₁) is greater than the number of natural numbers (ℵ₀). That is, there are more reals than naturals (this may seem obvious, but contrast it against the fact that the number of rational numbers, ℚ, is equal to the number of natural numbers, ℕ!)

Further, Cantor conjectured that there is no set whose cardinality is strictly in between ℵ₀ and ℵ₁, though he was unable to either prove or disprove the hypothesis. Now famously known as the Continuum Hypothesis, the pursuit of providing a resolution to it motivated ground breaking research in set theory and logic in the years to follow.

References / Further Reads

• Analysis : Volume I, By Terence Tao (Chapter 3: Set Theory).
• https://medium.com/cantors-paradise/the-nature-of-infinity-and-beyond-a05c146df02c

Credits

• The diagrams were made possible by https://app.diagrams.net/