Department of Philosophy, Psychology, and Cognitive Science

Rensselaer Polytechnic Institute

Troy, NY

andy@andyland.com

The history of mathematics has shown a general controversy regarding set theory and the infinite, especially during the late 19^th and early 20^th centuries. However, around that time Georg Cantor presented a proof that is generally accepted today - a proof that there are more real numbers between 0 and 1 than there are natural numbers, in the "correlation" sense.

It is important that the distinction between the "correlation" and the "subset" sense of set size comparison be made clear. For two sets to be of the same size in the subset sense, they must contain all of the same members. For two sets to be of the same size in the correlation sense, there must be a way to bind each member of one set to each member in the second set in a one-to-one correlation.

For all pairs of finite sets, the correlation and subset senses of set size comparison happen to be identical, but when applied to infinite sets they are distinct. For example, the set of even natural numbers is the same size as the set of all natural numbers in the correlation sense, but is smaller in the subset

sense. This is because the second set clearly includes all members of the first set, plus all of the odd natural numbers. This paradox seems to bring into question our notions of the

existence and nature of sets of infinite size, but it is now commonly agreed upon by mathematicians that this is only an apparent glitch and can be overlooked if we are explicit about which sense of infinite set size comparison we wish to discuss. For the purposes of analyzing Cantor's work, we use the correlation sense of set size since this is the one that his proofs deal with.

Briefly, the prerequisites for Cantor's proofs go roughly as follows: First, the set of natural numbers is often presented as proof that sets of infinite size exist, and then it is shown that the set of natural numbers is also countable. In other words, the set of natural numbers is countable since you can enumerate all of them simply by starting with 0 and repeatedly adding one. Furthermore, the set is infinite because such an act would take an infinite amount of time, i.e., at any point in the counting when you are at natural number n, there is always the natural number n+1 that you need to count next. Then, given the correlation sense of set size it is said that any set whose members can be paired off with the natural numbers is countable, or enumerable, and any set whose members cannot be paired off in such a way is uncountable, or innumerable.

Cantor claims to have shown that the set of real numbers between 0 and 1 is uncountably infinite. I disagree. I'll hold his diagonalization proof for my objections section. Let us first analyze the importance of the order by which we attempt to pair off the real numbers between 0 and 1 with the natural numbers.

First of all, let me point out that you cannot prove the real numbers between 0 and 1 to be innumerable by presenting methods that fail to enumerate them. Doing so simply shows that the methods in question won't work. If this were not the case, I could show that the natural numbers themselves are innumerable. For example, if I try to enumerate the natural numbers by first enumerating the even ones and then enumerating the odd ones, I will never reach all of the natural numbers. In particular, given infinite time I will only enumerate the even ones by this method.

Therefore I will not mention any of the historical examples that fail to enumerate the reals between 0 and 1, but rather I will move right on to the algorithm that I believe will work, and then address the objections. Here I simply wish to emphasize the importance of the method by which we pair off the reals between 0 and 1 with the natural numbers. Much like the fact that in order to be successful we need to enumerate the natural numbers in the order: even, odd, even, odd…, we need to enumerate the real numbers between 0 and 1 in a certain order if we are to be successful.

Here is the algorithm I propose will bind each real number between 0 and 1 to a natural number. If C++ is unfamiliar to you, please take note of the comments (those statements after "//" at the end of many of the lines). Additionally, the subsequent analysis of the algorithm will provide further clarification. Also, please treat this as only pseudocode, as an actual successful running of this program for infinite time require a decimal (as opposed to binary) storage of reals and integers, and one which allowed integers and reals of any size or length. However, this is runnable C++ code, so feel free to run it to get a sense of what the output would look like.

//C++ algorithm for the enumeration of all reals between 0 and 1.

#include <iostream.h>

#include <math.h>

int count = 0; //global variable that will be the natural number we bind to each

//real from 0 to 1.

enumerateReals (float, int, int);

main() { //the main program calls enumerateReals with each natural number.

//notice that this is doable in infinite time if enumerateReals is

//always doable in a finite amount of time, given any natural number i.

int i = 1;

while ((2 + 2) == 4) { //infinite loop.

enumerateReals(0.0, 1, i);

i++;

}

}

enumerateReals (float numSoFar, int decimalPlace, int decimalLength) {

//this is a recursive function to enumerate all of the reals of some

//length, decimalLength. this is doable in a finite amount of time

//given any natural number, decimalLength.

int j;

if (decimalPlace == decimalLength) {

for (j = 1; j <= 9; j++) {

cout<<count<<" is bound to ";

cout<<(numSoFar + ((float)(j))/(pow(10, decimalPlace)))<<"\n";

count++;

}

} else {

for (j = 0; j <= 9; j++)

enumerateReals(numSoFar + ((float)(j))/(pow (10, decimalPlace)),

decimalPlace + 1, decimalLength);

}

}

So essentially what the algorithm does is enumerate the real numbers between 0 and 1 in order of their decimal length, from one on towards infinity. A quick analysis of the subroutine enumerateReals will show that it indeed will enumerate, in finite time, all of the reals between 0 and 1 that have length of n, where n is any natural number. Therefore, if we call the function with 1, 2, 3, etc., etc., for an infinite amount of time we will get all of the real numbers between 0 and 1 of all lengths. A formalization of this proof follows:

1. For any n, an execution of my enumerateReals on n will enumerate all of the real numbers between 0 and 1 of length n.
2. For any n, an execution of my enumerateReals on (n +1) will enumerate all of the real numbers between 0 and 1 of length (n+1).
3. An execution of my enumerateReals on 1 will enumerate all of the real numbers between 0 and 1 of length 1.
4. Therefore, by mathematical induction, if we call my enumerateReals with 1, 1+1, 1+1+1, etc., etc., forever, (i.e., with each of the natural numbers), it will enumerate all of the real numbers between 0 and 1 of all lengths.

Actual output of the algorithm follows: (ellipses substituted for readability)

1 is bound to 0.2

2 is bound to 0.3

3 is bound to 0.4

4 is bound to 0.5

…

16 is bound to 0.08

17 is bound to 0.09

18 is bound to 0.11

19 is bound to 0.12

…

48 is bound to 0.44

49 is bound to 0.45

50 is bound to 0.46

…

98 is bound to 0.99

99 is bound to 0.001

100 is bound to 0.002

101 is bound to 0.003

102 is bound to 0.004

…

752 is bound to 0.726

753 is bound to 0.727

754 is bound to 0.728

755 is bound to 0.729

…

997 is bound to 0.998

998 is bound to 0.999

999 is bound to 0.0001

1000 is bound to 0.0002

…

We now present a formalization of the proof that my algorithm is computable in infinite time.

1. For all computational procedures P, and for all computational procedures C, if P is an infinite loop whose contents are exactly C, and C is computable in finite time, then P is computable in infinite time.
2. My procedure "main" is an infinite loop whose contents are exactly my procedure "enumerateReals."
3. My procedure enumerateReals is computable in finite time.
4. Therefore, by (1), (2), and (3), my procedure "main" is computable in infinite time.

Or, in strict logical terms:

1. " P" C(InfiniteLoop(P)Ù Contents(P, C)Ù CompFinite(C))® CompInfinite(P)

1b. InfiniteLoop(main)Ù Contents(main, enumerateReals)Ù CompFinite(enumerateReals))

® CompInfinite(main) [univ. elim., cite 1]

2. InfiniteLoop(main) Ù Contents(main, enumerateReals)
3. CompFinite(enumerateReals)
4. CompInfinite(main) [taut. con., cite 1b, 2, 3]

So, we have shown that my algorithm will (1) systematically enumerate all of the real numbers between 0 and 1, of all lengths, and (2) that it will do so in infinite time.

Cantor's Diagonalization - Georg Cantor's original proof that the real numbers between 0 and 1 are not countable was his diagonalization proof, which goes like this:

The diagonalization proof presupposes that, at least in theory, there is a point in time when we can stop and have all of the real numbers from 0 to 1 listed. (namely the point in time after infinite time has passed) But this presupposition is contrary to the very definition of infinity and infinite time. It is a misconstrued use of the terms and is not admissible in a proof. The definition of infinity is roughly "that which has no bounds" and the definition of infinite time is roughly "time which has no bounds," or "given any point in time n, you always have point n+1 left." Therefore, the notion that you can assemble a real number via diagonalization that my algorithm hasn't yet enumerated is useless since by definition, how long will it take to assemble such a number? An infinite amount of time. In other words, when will it be done? Never.

One might point out that my algorithm takes an infinite amount of time, so it too will never be done. But the point that my algorithm proves does not rely on the algorithm actually operating to completion, not in the same sense that Cantor's proof uses infinity. I only needs to show that it is going in the right direction and continues forever. The claim is only that my algorithm can pair off the reals with the natural numbers by some method, at each step of the way, and will do so forever. However, in a proof that is supposed to show that something is possible, the presence of something that says it is possible and it takes an infinite amount of time to do so is contradictory. Saying something takes an infinite amount of time is saying that it is impossible, even in theory.

If you still believe in the diagonalization proof, consider the following application of the diagonalization proof to the natural numbers. If I can prove by a method analogous to the diagonalization method that the natural numbers themselves are uncountable, even in infinite time, then surely the diagonalization method is not an acceptable proof.

Given that absurd result and analysis of the bases on which it rests, it becomes clear that those are the same bases on which Cantor's diagonalization proof rests - namely a general misuse of the concept of infinity as some sort of number.

So my final answer to the diagonalization proof is that at any point in time if you construct a number (via the diagonalization method) that my algorithm has not yet enumerated, it is because the algorithm is not done yet. How much more time does it need to complete? An infinite amount of time. And as you can see from close inspection of my algorithm, it is indeed headed in the right direction to enumerate, among all of the others, the exact number you mentioned, eventually, just as when you count the natural numbers. The important point is that my algorithm is systematically binding each real from 0 to 1 to a natural number, it is hitting all numbers in the process, and clearly when time reaches infinity (theoretically), my algorithm will have enumerated all of the reals from 0 to 1.

Bringsjord's Objection - Selmer Bringsjord raised roughly the following objection.

This objection is again rooted in the confusion that results when we use the infinite as a measurement of length, for example. First of all, let's examine the grounds on which we claim that infinitely long real numbers exist, or rather in what sense do we claim they exist?

The argument often goes that regardless of their existence in the real world, we can logically conceive of a real number of infinite length. Perhaps the most straightforward example is 1/3, or 0.333333… Clearly this number is infinite in length. Why do we believe it exists? Because conceptually we can imagine taking a zero and a decimal point and then adding a three, and another three, and another three, forever and ever. Such a task could be complete in infinite time and therefore it is conceptually coherent - because we can show a coherent systematic way of defining or constructing it. Notice that at any point in time the number we will have constructed is not infinite in length, but in an abstract sense when infinite time has passed we will have an infinitely long number.

So why doesn't my algorithm hit the infinitely long numbers in infinite time? I think intuitively the argument would go something like this: We can construct one infinitely long number in infinite time, but just one. For example, we can construct 1/3 as we explained above, but when infinite time is up, we have only constructed one of them, not all (infinitely many) of them. Therefore, you can only construct a maximum of one infinitely long real number in infinite time. But this argument is incorrect. The method of enumerating 1/3 first, and then pi - 3, for example, and then 2/3, will clearly not work, but that is just one proposed method. My method, on the other hand, will work. Why? Essentially, because my algorithm enumerates and builds the numbers in the right order, the importance of which is discussed in section 2. This is similar to the issue of counting the natural numbers in the right order: even, odd, even, odd…

My algorithm will hit the real numbers of infinite length in the same abstract sense that such numbers exist. And not only will it hit one of them, but it will hit absolutely all of them. Let us now address some of Bringsjord's points.

This is not a problem for my algorithm any more than it is a problem for the existence of infinitely long real numbers themselves. When you define a number of infinite length, (which you must do to show that it is conceptually coherent and therefore exists) like we did with 1/3, at absolutely every "step" of the way, the length of your number is finite. In particular, the set of lengths at each point in time is the set of natural numbers. Although infinity is the size of the set of natural numbers, infinity itself is not a natural number. The idea that infinitely long real numbers exist is only in the sense of ongoing-ness, the sense that you can always add another digit to the decimal expansion. And the sense that in infinite time, an infinitely long number would theoretically be created. But notice that my algorithm exactly capitalizes on this reality - that (1) at every real step of the way, the length of a real number is one of the natural numbers, and (2) given an infinite amount of time we can coherently conceive of real numbers of infinite length being constructed or defined. So, it is in exactly the same sense that infinitely long real numbers exist that they will be enumerated by my algorithm. And more importantly, my algorithm by its definition is targeted towards hitting absolutely all of the real numbers between 0 and 1 of infinite length.

Then there is the objection that my algorithm may hit 1/3, as shown, but it will never hit any infinitely long irrational numbers. The answer to this is simply that my algorithm clearly does not discriminate against any type of number, it hits them all. At each step of the way it hits all of the numbers of that length, and in infinite time (in an abstract sense) it will hit all of the numbers of infinite length. So in other words, if I can show that my algorithm hits all of the infinitely long real numbers between 0 and 1, (as I have done in the previous paragraph) then among those are clearly all of the irrational numbers between 0 and 1. So this objection is reducible to the one addressed in the previous paragraph. Notice that in proving that pi - 3, for example, exists, one might show something like 0.1415… and show that they can keep adding more and more numbers, in particular the actual digits of pi - 3. But also notice that not only does my algorithm do this for pi -3, but it does it for all other real numbers, rational and irrational, between 0 and 1 as well. Therefore, in the sense that irrational numbers exist, my algorithm will indeed enumerate them if it keeps going forever.

The Objection from Intuition - The final objection I feel I should address is the objection from intuition. Silencing the objections that I've gotten so far doesn't necessarily mean that I will not get a valid objection somewhere down the road. But if I could dispel the intuition that underlies many of the potential objections I think I will have done a great deal for my case.

The objection from intuition is simply that when you think about it, it really does seem like there are more real numbers from 0 to 1 than there are natural numbers. In particular, it seems this way because given any two real numbers, there are an infinite number of real numbers between them, whereas given any two natural numbers, there are only a finite number of natural numbers between them.

The problem again is simply due to the fact that the natural numbers are naturally ordered so well. Take the set of even natural numbers and the set of all natural numbers, for example. It is clear that between any two numbers, there are more numbers between them in the set of natural numbers than there are between them in the set of even natural numbers. Yet it is agreed that both sets are of the same size. And this is the same argument that was just used in the previous paragraph to claim that the set of reals between 0 and 1 is bigger than the set of natural numbers! So that objection is silenced.

Finally, it is pointed out that although I can show two subsets of the natural numbers (i.e., the evens and the odds) that are each of infinite size, the set of real numbers between 0 and 1 consists of an infinite number of subsets each of infinite size. It is said that it is exactly in this notion that the difference in cardinality of the reals between 0 and 1 and the natural numbers lies. I will use the final section of my paper to conclude with an all out silencing of this notion. I will show that the set of natural numbers can be broken down into an infinite number of subsets each of infinite length, just as the reals between 0 and 1 can.

The intuition underlying many claims that there are more real numbers than natural numbers lies on the fact that it seems that the set of real numbers can be broken down into an infinite number of subsets each of infinite size. However, I will show here that the same thing can be done with the natural numbers.

1. http://forum.swarthmore.edu/dr.math/problems/cansever10.20.97.html
2. http://forum.swarthmore.edu/dr.math/problems/stephanie9.9.98.html
3. http://forum.swarthmore.edu/dr.math/problems/ramos10.31.97.html
4. http://forum.swarthmore.edu/dr.math/problems/continuum.html
5. http://forum.swarthmore.edu/dr.math/problems/klimkow.4.8.97.html