Why There Are Infinitely Many Different Levels of Infinity

Because a recent post about the German mathematician Georg Cantor (1845-1918) generated a great deal of interest, I decided to do two more posts about Cantor’s contributions to mathematics. Of course, I find Cantor’s mathematics fascinating, and apparently many readers found the content of that post intellectually stimulating as well. You might think that Cantor’s work amounts to a bunch of clever and interesting mathematical mind games, but this is not the case. His work helped lay the foundation upon which much of modern mathematical analysis rests. If you have not read my first Cantor post, Infinity Does Not Necessarily Equal Infinity, I strongly suggest that you read it before continuing. The concepts presented in this post heavily depend on an understanding of the concepts presented in that post.

The purpose of this post is to show how Cantor proved that there are infinitely many levels of infinity or there are infinitely many different infinite cardinal numbers! The purpose of the next Cantor post will be to give readers a general description of the Cantor ternary set which is counter-intuitive, preposterous, absurd, and astonishing. I will not delve deeply into formal abstract mathematics, because my understanding of Cantor’s work only scratches the surface of his deep mathematics.

To get started, I will do a quick review of some basic definitions and concepts in set theory.

• A set can be any collection of objects such as numbers, character symbols, cars, people, cats, etc.
• Set A is a subset of set B if and only if every element of set A is an element of set B.
• Let A equal any subset of B. A is a proper subset of B if and only if there is an element in B that is not in A.
• The null or empty set is a set that contains no elements. The symbols { } or Ø denote the empty set.
• Sets {0}, {Ø}, and {{ }} are not the empty set because each of the three sets contains an element.
• The null set is both a subset and proper subset of every set.
• Set A equals set B if and only if the sets are subsets of each other.
• In set theory and Boolean algebra, the word “or” means “one or the other and possibly both.” In contrast, when a parent uses the word “or” with a child, the parent means “one or the other, but not both.”
• In set theory and Boolean algebra, the word “and” means “both are in the set” or “both are true.”
• The union of sets A and B, denoted by AB, is the set of elements that are in A or B.
• The intersection of sets A and B, denoted by A ∩ B, is the set of elements that are in A and B.
The text box below uses sets of numbers to illustrate the set definitions above.

The power set of set A, denoted by P(A), equals the set of all possible distinct subsets of A. In other words, P(A) is just another set that contains all of the distinct subsets of set A. To get a better idea of what P(A) means, the text box below gives P(A) for different finite sets of counting numbers. Note that if set A has n elements, then P(A) has 2n elements.

To see why increasing the number of elements in a set by one causes the number of elements in the power set to double, consider how you could go about creating a list of all 32 subsets of the set {1, 2, 3, 4, 5}. The first 16 subsets of {1, 2, 3, 4, 5} are given by the power set of {1, 2, 3, 4}. The other 16 subsets of {1, 2, 3, 4, 5} can be obtained by forming the union of {5} with each of the 16 subsets of {1, 2, 3, 4}. You should later go ahead and list all 32 subsets of {1, 2, 3, 4, 5} and then all 64 subsets of {1, 2, 3, 4, 5, 6}. I’m very serious about this suggestion because it will help you learn to think in a different way and help you better understand the fundamental counting principle, permutations, and combinations. You may find this task tedious and boring, but you will be rewarded with a better understanding of fundamental counting concepts.

I can now explain the proof Cantor’s theorem which states that the cardinal number of P(A) is strictly greater than the cardinal number of A where A is any finite or infinite set. Cantor’s theorem can be used to show that there are infinitely many different infinite cardinal numbers. Recall from my first Cantor post that the cardinal number of a set equals the number of elements the set contains. Therefore the cardinal number of a google of water molecules equals 10100, and the cardinal number of a MLB active roster equals 25.  Also recall from my first Cantor post that the symbol for the cardinal number of the counting numbers is ℵ0, the symbol for the cardinal number of the real numbers is ℵ1, and ℵ0 < ℵ1.

For finite sets, Cantor’s theorem is obvious. If the cardinal number of finite set A equals n, then the cardinal number of P(A) equals 2n. For infinite sets Cantor’s theorem might seem obvious, but it’s much more difficult to prove. To make Cantor’s proof more comprehensible for infinite sets, I will first give a proof that shows that the cardinal number of P(C) is strictly greater than the cardinal number of C where C equals the set of counting numbers. Like many deep abstract mathematical proofs, Cantor’s proof uses the sophisticated technique of proof by contradiction. For set C, his proof goes something like this:

• Assume that there is a one-to-one function f with domain C and range P(C) that matches the counting numbers in C with all of the elements of P(C). The text box below shows one of the infinitely many possible ways that we could create a matching rule for f. The order in which domain and range elements are listed makes no difference. The important point is that there exists a one-to-one function f such that the domain of f equals set C and the range of the function, all function values, equals the set P(C).
• Construct a special subset M of the counting numbers as follows: (See the text box above.) Let set M equal all counting numbers n such that n is not contained in f(n). M is not the empty set because counting number j, such that f(j) = {   }, must be an element of M by definition.
• Set M raises a contradiction as follows: There must be a unique counting number k such that f(k) = M. Either k is contained in M or k is not contained in M. If k is contained in M, then by the definition of set M, k is not an element of M. If k is not contained in M, they by the definition of set M, k is an element of M. Therefore the function f can’t exist. Hence there is no counting number k that matches with M, and the cardinal number of set P(C) is greater than the cardinal number of set C. (The contradiction is somewhat like damned if you do and damned if you don’t.)

Now let’s see how we can prove that the cardinal number of the set of real numbers is strictly less than the cardinal number of the power set of real numbers. We need only to modify the last proof a little bit to give us our proof. The following algorithm describes how to create the modified proof:

• Let R equal the set of real numbers and the variable x equal any real number or element of R.
• Assume that there is a one-to-one function f with domain R and range P(R) that matches the real numbers in R with all of the elements of P(R).
• Construct a special subset M of the real numbers as follows:
1. Let set M equal all real numbers x such that x is not contained in f(x).
2. M is not the empty set because real number y, such that f(y) = {   }, must be an element of M by definition.
• Set M raises a contradiction as follows:
1. There must be a unique real number k such that f(k) = M. Either k is an element of M or k is not an element of M.
2. If k is an element of M, then by definition of set M, k is not an element of M.
3. If k is not an element of M, they by definition of set M, k is an element of M.
4. Therefore function f can’t exist. Hence there is no real number k that matches with M, and the cardinal number of set P(R) is greater than the cardinal number of set R.
Using the proofs described above as a model, it’s relatively easy to prove that the cardinal number of P(A) is strictly greater than the cardinal number of set A where A is any infinite set. By letting our imaginations run wild and considering set expressions such as P(P(A)) and P(P(P(P(A)))), we can create as many different infinite cardinal numbers we wish.