Cantor and Set Theory
Georg Cantor was a 19^{th} century, Jewish-German mathematician that almost single-handedly created set theory. Much of his work was based on the preceding work by Zermelo and Fraenkel. Together they set the basis for set theory, and their somewhat obvious proof schemes are now called Zermelo-Fraenkel Theory (ZF) and are the starting point for all set theory study. I don’t cover them in this essay, but encourage interested readers to examine their works. There are some aspect of set theory that I omit from this essay in the interest of space and clarity. They are The Axiom of Choice and ZF, both are really necessary for a satisfactory understanding of transfinite numbers. But, 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 mathematics, not give him or her a lesson in it.
Georg Cantor's set theory proof of the existence of numbers larger than infinity still fascinates me to this day. He named them transfinite numbers. Here is a non-technical description of it.
The 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. Lets 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 set, 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 their 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 c that lies between a and b. C could be an irrational or rational number between two given reals. The naturals however, are just the positive integers and have less density. It is clear that if we made a one-to-one correspondence (hereafter called isomorphism) between a finite set of naturals and reals, the reals would have infinitely many more members of its 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 those 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 lets get an idea 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. In fact, set theory explicitly defines this. A definition states: No infinite set is denumerable. A nice way of saying you can't count all the members of an infinite set. 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 say ®. Actually, 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 actually 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 are equal to the real numbers Z.
Next we specify that Q =Z, iff (if and only if) Q and Z both = א
So, they both must have the same size. Lets see if they do
How can we check? Here is where Cantor, showed his genius.
Well, we can make them isomorphic. As 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? Actually, 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 behind the decimal by one value. So, for natural 1® 1.1, the new number would be 1.2, for 2® 1.2, it would be 1.3., and so on. If we followed this procedure vigorously we would eventually 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,0000® 1.1234567892929292, then a new real could be created by simply changing the last digit of the real to the next number in succession, e.g. 3. This procedure itself would ensure that a new real number could be created for every pairing between the reals and naturals. If this is true, then our assumption that Q =Z, iff (if and only if) Q and Z both =א, can't be true and Q ¹ Z, 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 and Transfinite numbers
Cantor called this first transfinite cardinality א_{0, }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 in regard to sets. A set is said to be a proper subset of a given set, if for any set M { a,b,c} $ a set { m} Î M, such that M>m. All this simply means is that a proper subset of M is one that has less 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:{ f } . The cardinality of the power set is given by the formula 2^{N}, where N is the number elements in the set. So, for our example above M= (a,b,c) its cardinality would 2^{3}=8. That is (a), (b), (c), (a,b), (a,c) (b,c) (a,b,c), { f } .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, lets 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 are greater than the infinite set of naturals. They are transfinite, if you will. We know also, there are infinitely many transfinite sets. What we don't know is the order of these sets! Is the transfinite set with cardinality א_{0} the first one? Or, is there another between the naturals and reals, or integers and reals for that matter? Even if this true, what is the second transfinite set? What is the third? This leads to a hypothesis known a the Continuum Hypothesis (CH). It simply states that א_{0 }=c. If this is true there can’t be any set between א_{0 }(the first infinite set bigger than infinity) and the c (the reals numbers which is the continuum). If there is a set >א_{0 }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, that believe such a proof can never be obtained. But, you know that's a story for another essay.
Some modern outcomes
Interestingly, physics has been affected by this notion of a continuum in set theory. General Relativity uses the idea of a continuous function between matter and space to establish the Equivalence Principle. This idea is applied in Group Theory to geometric constructions. Group Theory in mathematical physics is a direct analogue its set theory counterpart. If the space-time continuum is a non-discrete relationship of matter to space, then mathematically is nothing more than an Ideal of a Ring.