Georg Cantor and Transinfinity

Ordinality and the Continuum Hypothesis 6

Cantor and Set Theory

Georg Cantor

1/11/99 Robleh Wais

Georg Cantor was a 19th-century, Jewish-German mathematician who almost single-handedly created set theory. Much of his work was based on the preceding work by Ernst Zermelo and Ferdinand Fraenkel. Together they form the basis for set theory, and their somewhat obvious proof schemes are now called Zermelo-Fraenkel Theory (ZF), being the starting point for all set theory study. I don't cover them in this essay, but I encourage interested readers to examine their works. There are some aspects of set theory that I don't cover in detail in this essay for clarity. They are the Axiom of Choice (AOC) and ZF, both are necessary for a satisfactory understanding of transfinite numbers. I leave these concepts to the reader to discover. The point of this essay is to interest the reader in this area of set theory, not give a lesson in it.

The Axiom of Choice is so important in this field I should give at least a simplified explanation of it. AOC simply states that there is a way to specify the members of a given set when the sets are related. But, how do we do this? Here is the actual postulate as it was developed by Ernst Zermelo and stated by Eves (Eves, 1990, p 297).

If a set S is divided into a collection of mutually disjoint nonempty subsets A, B, C, there exists at least one set R that has as its elements exactly one element from each of the subsets A, B, C

This refers to set mappings that are surjective when taken from left to right and can be made injective when taken from right to left. Or in other words, a relation that maps one set onto another and the reverse maps one set into another. In the case where one set is mapped onto another, not every member has to pair with one in the other set. But in the case of mapping into another set, every member must pair with the other, and this is called a one-to-one mapping. If a set is inversely mapped to a set that has been previously surjectively mapped, the members that may have no elements mapped to them will end up being mapped to some of the same members in the original set. This would violate the one-to-one property of injective maps. So, again, the Axiom of Choice allows for the orphan member to be paired with an arbitrary set R to prevent a double map of one member in one set to the same member in the other set.

What this postulate is saying in simpler terms is that we can choose a member from each of the aforementioned sets. This set, called R, allows you to specify members from each of the given sets and thus is created by choice, hence the name the Axiom of Choice. Now, let's move on to our story.

Georg Cantor's set theory proof of the existence of numbers larger than infinity still fascinates me to this day. As a mathematics student in the 1970s, I stumbled upon a book by Georg Cantor entitled Transfinite Numbers. This work is the foundation for all studies of infinite sets today. I used it as a reference for writing this article. Interested parties should consult it as needed.

The question Cantor started with is at first glance, quite simple. Of the two sets: natural numbers and real numbers, which has greater size, if we relate them as infinite sets? The answer to this question is more involved than one might expect. Let's examine the underpinnings of set theory that lead to the answer.

Cardinality, Ordinality and Sets

Set theory differentiates between the number of elements in a set and the value of the number of elements in a set. The former quality is said to be denumerable (countable) if the set can be put in a one-to-one correspondence with some other set. The latter is called cardinality and is the numerical value of the set. There is a third property of sets I won't examine in any detail in this essay but is extremely important to the study of infinite sets, ordinality. This property refers to the order in which elements of sets are structured. I will briefly touch on this property's importance to the ongoing study of infinite sets, in my concluding remarks.

Now, it is obvious that both sets are infinite. It is also obvious that any finite subset of these sets will not be equal in cardinality. This is true because the reals are infinitely dense and the naturals are not. For instance, for any real numbers a and b, there is always another real number c that lies between a and b. C could be an irrational or rational number between two given reals. The naturals, however, are just positive integers and have less density. It is clear that if we made a one-to-one correspondence (hereafter called an isomorphism) between a finite set of naturals and reals, the reals would have infinitely many more members of their set than the naturals.

What if we let the naturals extend to infinity? Would they then be equal to the reals? This is the question Cantor asked himself and found the answer is NO. That is to say, the number of members of the infinite natural set would not be equal to that in the real set. This seems impossible, doesn't it? If both sets are infinite, then you should always be able to find an element in one to pair with the other. Nevertheless, Cantor proved this common-sense notion to be false. To understand his strange proof, first, let's get an idea of how we could ever have a notion of the cardinality of an infinite set.

Of course, we can't count every member of an infinite set and give the result a name. But you can specify a procedure that, if applied consistently, will ensure that the infinite set has some definable size. This size or cardinality is just given a name. Cantor used the first letter of the Hebrew alphabet to denote this infinite cardinality: א. So, to prove that the naturals are not isomorphic to the reals in infinity, we have to do something that set theory mathematics has come to rely upon frequently. The logical method modus tollens, or proof by negativity. We assume the thing we want to confute is true, then show it's contradictory, and thus prove our conclusion. Later, I will explain why this method is not always a good one, and how newer concepts in mathematics may call some of these methodologies into question. Now, back to the story of the naturals vs reals.

So, we assume that the set of natural numbers Q is equal to the real numbers Z.

Next, we specify that Q =Z, iff (if and only if) Q and Z both = א

They both must be the same size. How can we check? Let's see if they do. You see, Cantor devised a well-defined method to do this. We will make them an isomorphic mapping in the table below

Natural number	Real number
1	1.1
2	1.2
3	1.3
4	1.4
5	1.5
6	1.6
7	1.7
8	1.8
9	1.9
10	1.10

It is clear from the table that this procedure could go on endlessly. Assuming it did, we would have all the reals paired with the naturals. Or would we? Since the reals are everywhere dense, we can exploit this property to show that even if we can pair a natural for every real, there will still be reals left over.

In the table above, suppose we wanted to create a new real number that was not in the table. How could we do this? We could specify a rule that said for every natural number already paired to a real number, we'll change the digit of the real number behind the decimal by one integer value. So, for the natural 1.0 it would be 1.1, then with 1.1, the new number would be 1.2, for 1.2, the new number would be 1.3, for 1.3 it would be 1.4, and so on. If we followed this procedure rigorously, we would end up with new real numbers that were not paired to some natural number. It might be hard to see that is true at first glance. I've only given a few iterations of this rule. For instance, if we were at random to take the isomorphism of say 1,000,000,000,000 to 1,000,000,000,0001.2, then a new real number could be created by simply changing the last digit of the real to the next number in succession, e.g., 1,000,000,000,0000--> 1,000,000,000,0001.3. It is important to note that this real number would be greater than the number to which it is paired. It would be different and endlessly different. While an isomorphism of 1,000,000,000,0000->1,000,000,000,0001 would not be. This isomorphism would only lead us to equality in infinity. Since every integer could always be paired with another integer. But not so, with the reals. No integer could ever be paired with a real. This is because the integers are not dense. This process works just as well if we drill down to the integers isomorphic with the reals in the interval between 0 and 1. This means in infinity, one set is beyond the other set in density. This procedure itself would ensure that a new real number could be created for every pairing between the reals and naturals. The procedure defines a process that necessarily yields the result. It means that potentially there is a set that is beyond infinity. This is extremely important. Cantor never proved that infinite sets were unequal as absolute collections of their elements. This is impossible to do, set theoretically. He proved in potential infinity, they are not equal. If this is true, then our assumption that Q =Z, iff (if and only if) Q and Z both =א, can't be true. Furthermore, the following must be true Q=א, but Z>א. That is the naturals equal infinite cardinality א, but the reals have an infinite cardinality greater than א. Or, in more plain terms, the reals are bigger than infinity.

Power Sets, Transinfinity, and Beyond

Cantor called this first transfinite cardinality א₀. It is now known as the continuum, and is denoted by the letter c. The real numbers constitute the first set of numbers that exceed infinity. Of course, it's not hard to see if there is one set of numbers that is transfinite; then there can be many, in fact, infinitely many more. For example, take what is called the power set. The power set is the set of all subsets of a set. Here, I should explain another distinction that set theory makes regarding sets. A set is said to be a proper subset of a given set if for any set M { a,b,c} there exists a subset { m} member of M, such that M>m. All this simply means is that a proper subset of M has fewer of the same members than it. This is an important distinction. For instance M=(1,2,3) and m=(1,2) is proper. But, M = (1,2,3) and m = (4,5) is not, because these are different members and m is not a subset of M. Now, to get back to the power set, a power set is simply the set of all subsets of a set, including proper subsets. By convention, every set is a subset of itself, and every set contains the null set: { /0 }. The cardinality of the power set is given by the formula 2^N, where N is the number of elements in the set. So, for our example above M = (a,b,c), its cardinality would be 2³=8. That is (a), (b), (c), (a,b), (a,c) (b,c) (a,b,c), (/0) . It is interesting to note here that if we considered the ordinality of this finite set, there would be many more possibilities like (b,a), and (c,a,b), etc. So, let's look at our transfinite real number set and find its power set cardinality. The power set cardinality would be 2^א0. Cantor introduced a definition of the cardinality of power sets that leads to a strange conclusion for transfinite numbers. The cardinality of a set's power set is always greater than the given set's cardinality. The definition is so trivial as not to be worth specifying at first sight. Armed with this definition, we can say the cardinal number for the power set of the reals is greater than the reals cardinal number. This means that a number bigger than infinity has another number even bigger than bigger than infinity, e.g 2^א0. Of course, we can go on to take the power set of that set and the next after it, and so on infinitely. Here is where the question that Cantor couldn't answer crops up. This is a strange conclusion to which I referred.

Ordinality and the Continuum Hypothesis

Here also is where ordinality becomes important. And here is where I'll end since I promised not to talk about ordinality. But, just a parting comment. From what I've said, we know that the infinite set of real numbers is greater than the infinite set of naturals. They are transfinite if you will. We also know, there are infinitely many transfinite sets. What we don't know is the order of these sets! Is the transfinite set with cardinality א₀ the first one? Or, is there another between the naturals and reals, or integers and reals for that matter? Even if this is true, what is the second transfinite set? What is the third? This leads to a hypothesis known as the Continuum Hypothesis (CH). It simply states that א₀=c. If this is true, there can't be any set between א₀(the first infinite set bigger than infinity) and the c (the real numbers, which is the continuum. They are the Continuum because there are no gaps of numbers like in the integers). If there is a set >א₀and < c then CH is false. But, so far, no one has found such a set.

See, this involves the order of these strange, larger than infinite, sets, and nobody in set theory has been able to prove the ordering of these sets, at least not yet. And, there are those in the field who believe such proof can never be obtained.

Lastly, what about proof methodology that doesn't use the schemes I described above? And yes, there are such methods. There is an area of mathematical logic known as modal logic that doesn't rely on proof by negation. It tries to capture things like: I might do this, or if there were a time, or it might be wrong to do this--in other words, the subjunctive mood. Many logics have formed around the subjunctive mood, and most consider questions of time, morals, and knowledge. Even more interesting is the proposal by the Intuitionist school of mathematicians that we dispense with the rule that a negative times a negative makes a positive.

Luitzen Brouwer, a Dutch mathematician, led the way to this idea. What he challenged was such an accepted principle of Logic proper and Mathematical Logic it seems odd today. Take the arithmetical construction, -3*-3. It doesn't make +9 if we reject the rule that -*- = +. As insignificant as this sounds, it directly affects proving by negativity. If you look at when we assume that what we want to prove is true and find it's not, we are using the process I just stated, e.g. if we assume something not true is true, then find it's not true, thus it's true is the same as positing not-true times not-true is true. What is striking about this is it's only a convention. Brouwer realized this. There is no logical reason for this to be the case. Brouwer thought (and I agree) that proofs are all about how our minds work. He is closest to Immanuel Kant in this idea. I won't go into details in this essay.

Philosophic Implications

Does this mean there are things we can't know through set theory reasoning? Is there a state that exceeds infinity, is that the province of God? Is reality divided by the infinite and supra-infinite? I won't delve into these questions, though I agree that Cantor's discovery does raise them. What Cantor's proof does show is our knowledge is not complete.

References
1. Cantor, G. (1915). Transfinite Numbers. New York: Dover Publications
2. Eves, Howard (1990). Fundamental Concepts of Mathematics. Mineola: Dover Publications

The Portal to Related Articles

Philosophies Science Math and Music

Cantor and Set Theory

Cardinality, Ordinality and Sets

Power Sets, Transinfinity, and Beyond

Ordinality and the Continuum Hypothesis

Philosophic Implications

Other Articles of Interest