Cantor and Set Theory1

Cardinality, Ordinality and Sets 2

Power sets, Transinfinity and Beyond 5

Ordinality and the Continuum Hypothesis 6

Other Articles of Interest7

Cantor and Set Theory

Georg Cantor

Cantor's Proof Method

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 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 that 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 inverse mapped a set that has been previously surjective 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 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 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 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, 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 to randomly 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 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. Every integer could always be paired with another integer. But not so, with the reals. Every integer could never 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 that 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 that 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 א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} there exists a subset { m} member of M, such that M>m. All this simply means is that a proper subset of M is one that has fewer 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 2N, where N is the number of elements in the set. So, for our example above M= (a,b,c) its cardinality would 23=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 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 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 א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. They are called the Continuum because there are no gaps of numbers like in the integers). 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 proof can never be obtained.

Lastly, what about proof schema that don't use the method 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 negativity. 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. There are many logics that have formed around the subjunctive mood, and most consider questions of time, morals, and knowledge. Even more interesting is the proposal by the Intuitionists 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 prove 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 most close 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 that 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

List of Articles

Maybe there is a way around Goedel's famous Incompleteness ProofIntuitionistic Logic

A review of Master and Man, short story by Leo Tolstoy.Master and Man

Is language infinite? Can we make an infinite sentence in any language? This is what this article considers. My answer is a qualified no. Linguistic Combinatorics

Is there alien life in our galaxy? This question was examined by two famous physicists, Barrow and Tipler. Their conclusion is one I can't accept. Alien Life the galaxy

Tzameti 13 is a film by Georgian Director Gela Babluani with deep Probability and Game Theory implications. I review this riveting film and those implications below. Tzameti means Number in Georgian for those interested. A NOT very unlucky number for the protagonist of this film as you will see.

13 Tzameti