On counting and Cantor’s Theorem
Recently I’ve been studying discrete mathematics and one of the things that amazed me was how difficult is for humans (at least this one) to get a grasp of the concept of infinity. The discovery made by Cantor was really groundbreaking at the time and it’s amazing to think about how he was able to come up with it, seeing beyond a concept so complex as infinity.
I decided to give a try explaining this in order to consolidate my understanding and hoping that somebody finds my explanation useful.
Before jumping right into the theorem itself, let me give you a little bit of background on set theory.
Cardinality
The cardinality of a set is a measure of the set’s size, meaning, the number of elements that belong to it. We can obtain the cardinality of a set A by counting each of the elements. Let’s say that set A = {9, 2, 5}, we would then proceed to count the number of elements in A.
When comparing the cardinality of two sets, say set A and set B, we can obtain each of them individually and then compare them.
Alternatively, we can pair each element in the sets in a 1 to 1 relationship, where each element in set A is paired with one and only one element in set B and vice versa, if we are able to come up with such a relationship we know both sets have the same cardinality.
We can think of this pairing process as a generalization of counting, if you think about it when counting elements in a set A with |A| = n we are trying to match each of the elements of A with the elements of a subset of the set of natural numbers N, namely the set of numbers from 1 to n.
This technique to compare sets is powerful because it allows us to compare the size of sets which sizes are unknown; imagine you are at the theater and you notice all the seats are taken and there is no person standing up you know the cardinality of the set of seats is the same as the cardinality of the set of people in the theater.
Infinite Sets
Think about the process of counting I mentioned above, there are some sets for which we simply cannot choose a natural number n to pair its elements to the set of numbers from 1 to n. Think about the set of ALL natural numbers N; it doesn’t matter which n you choose, the set N will always contain an element to pair with n + 1, so we say that a given set A is infinite if there is no number n for which we can establish a 1 to 1 relationship between the elements in A and the elements in the set of numbers between 1 and n. Of course, there are many of these infinite sets out there: the set Z of integers, the set Q of rational numbers, to name a few.
It’s interesting to observe that even subsets of one of these infinite sets are infinite themselves, let’s take for example the set of even natural numbers, we know that this set must be a proper subset of N, but actually, we can easily pair the set N with the set of even natural numbers in such a way that proves they actually have the same cardinality!
We just need to pair each element n in N with an element that is equal to 2n:
Sets that can be paired in this way with the set N of natural numbers are called appropriately countable sets, some authors may use countable set to mean infinite countable alone. To avoid this ambiguity, the term at most countable may be used when finite sets are included and countably infinite, enumerable, denumerable otherwise.
The Powerset
The last concept I want to talk you about before jumping in Cantor’s Theorem is the powerset, the powerset of a set A, denoted by P(A), is the set of all the subsets of A. Let’s say we got a set A = { 1, 2, 3 }, then P(A) = { ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }.
Cantor’s Theorem
Let’s imagine Bob & Alice are immortal, Bob offers Alice a great prize if she can guess the integer he is thinking about (either negative or positive), but she has only one single guess per day. Take a moment to think about a strategy that guarantees Alice to eventually get the prize.
Given that we know that the set Z of integers is denumerable, we definitely can come up with such a strategy: On day one Alice will try with 1, on day two with -1, on day three with 2, on day four she tries with -2 and so on, alternating the numbers in this way guarantees that Alice eventually will guess Bob’s number.
Notice that it is important to alternate between positive and negative numbers, if we try with positive (or negative) numbers first Alice will never guess the number in case it’s negative (or positive) because both sets are infinite.
What Cantor discovered is that for any set A the cardinality of its powerset P(A) is strictly greater than the set A itself. On finite sets this is easily proven by enumerating the elements of P(A), if n is the size of A then |P(A)| = 2ⁿ.
Cantor’s theorem is of fundamental importance because it holds for any set A whether finite or infinite. This has the implication that the powerset of the set of natural numbers P(N) is uncountable; there is no way we can pair P(N) with N in such a way that all elements of P(N) are paired with an element of N simply because |P(N)| > |N|. We can easily prove this with another imaginary experiment:
Think about a book with infinite enumerated pages and on each of these pages we write down one of the subsets of N, without even looking at any attempt of this we know there is a subset of N which cannot possibly be listed in ANY page of the book; let’s say that for each page number b of the book we call it extraordinary if b is contained in the subset of N listed on page b and ordinary if it’s not. Now we can construct a set B of all ordinary numbers since all the subsets of N must be in the book this subset clearly must exist somewhere in the book. If b ∉ B then b is ordinary and should be contained in B, but on the other hand if b ∈ B it means that b is extraordinary and should not be present in B.
With this paradox we prove that is not possible to count P(N) because it’s cardinality is strictly larger than N’s, P(P(N)) being greater than P(N) and P(P(P(N))) greater than P(P(N)) and so on to the infinite.
For me, it’s really amazing to discover this kind of stuff because it makes me just wonder how little we actually know about math and in a sense about our reality and just motivates me to learn a little bit more. Hopefully, this helps you understand Cantor’s theorem better.
