This is my version of Cantor's proof, its form is that of an indirect

proof, or a reductio of the claim that the set of real numbers is the

same size as the set of natural numbers. I posted this awhile back, but it has come up again in this forum, so what the hell?

1. For any set X and any set Y, X and Y are of the same size if and

only if the elements of X bear a one-to-one correspondance with the

elements of Y. (This is assumed by Cantor, but seems pretty

intuitive. If I want to know whether the number of students in my

room equals the number of chairs, I tell everyone to sit down and see

what's left over. That is, I try to establish a one-to-one

correspondance between students and chairs.)

2. For any set X and any set Y, the elements of X and the elements

of Y bear a one-to-one correspondance with each other if and only if

both X and Y are denumerable.

3. For any set X, X is denumerable if and only if (1) the elements of

N can be arranged into a list with a first member, second

member,...,nth member and (2) each element of X is quaranteed a

definite unique position on the list.

4. The set of natural numbers N is denumerable (The natural

numbers are 0, 1, 2, etc. no negative numbers, no fractions with

denominators other than 1.)

5. Suppose the set R of real numbers in the interval from 0 to 1 is

denumerable. [Real numbers are those that start with a decimal and

go on forever to the right of the decimal. Among the real numbers

are (1) the rational numbers (that repeat some digit or string of digits

infinitely) and (2) the irrational numbers (that have no infinitely

repeating pattern). .499999....is rational, in fact, it's equal to .5. The

decimal expansion of pi is irrational.]

6. If so, then the elements of R can be arranged in a list with a first

member, second member,..., nth member, and each element of R will

be guaranteed a definite unique position on the list. (This follows

from our 3 and 5).

7. Let L be the list of the elements of R. Let each element of R be a

decimal point followed by an infinite string of digits. We can represent

each element of R in the following fashion: Where B is some digit in

some element E of R, let x be the ordinal position of B in the string of

digits that constitute E; let y be the oridinal postiion of E in L. Then,

the ordered pair (x,y) specifies a definite unique location within L for

any particular B. Thus, B(x,y) picks out a definite unigue digit within L.

8. Suppose we apply the following procedure: Beginning at B(1,1),

followed by B(2,2)....B(n,n), for any B(x,y) if B(x,y) is the digit '1',

change it to '2'. If B(x,y) is any digit other than '1', change it to '1'.

The resultant string of digits, B(1,), B(2,2)....B(n,n), subsequent to

our procedure, is the Diagonal of L.

9. The Diagonal of L will itself be a real number within the interval

from 0 to 1, and thus will be an element of R. But the procedure

above guarantees that the Diagonal of L will not itself appear as an

entry of L, because for any entry (e.g., the nth entry) in L the

Diagonal of L will have some digit (the nthe digit) that differs from the

digit found in the entry in L.

10. Thus, if R is denumerable, then any list of the elements of R will

necessarily by incomplete (it will not contain its diagonal). But this

contradicts 6, so R must not be denumerable. (Any assumption that

leads to a contradiction is rejected and the assumption's negation is

adopted)

11. But if R is not denumerable, then the elements of R cannot be

put in a one-to-one correspondence with the the elements of N.

12. Thus the sets R and N are not of the same size.

So Cantor shows us that not all infinite sets are the same size, but he

assumes that all denumeralbe sets are of the same size. This

assumption already may do violence to your metaphysical intuitions,

because you may think that the set of even numbers is roughly half

as big as the set of natural numbers. I admit to finding this view

persuasive, but imagine you have two perfect random number

generators. The first generator is set up so that it only produces an

even number when operated. The second can produce any of the

natural numbers when operated. Each operation yields just one

number from each machine. If the set of evens is half as big as the

set of naturals, then it ought to be twice as likely getting a '2' from

the first machine than from the second. But each machine picks their

numbers completely at random and both have an infinite number of

choices. So the probability of getting a '2' on either should be

1/infinity. At this point my intuitions become silent and I begin to

drink beer.