This is my version of Cantor's proof, it 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.
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.
Thanks for the great topic Mark.
Bennett
Yes Sir!!! Superb stuff. The words "nail on the head" spring to mind.
For anyone interested, the following link has the argument that
Bennett detailed, with helpful examples/a picture of what is going on.
It's just a slightly different (perhaps simpler) way of explaining
Bennett's superb post above.
http://www.wikipedia.org/wiki/Cantor%2527s_diagonal_argument
[Bennett is right when he says that Cantor's work and what followed
can play havoc with your beliefs and what you hold to be self-evident.
I don't know whether Cantor is directly or indirectly involved in this
but "sawtooth" functions have been known to give curves that have
infinite perimeters but actually contain a finite area. This shakes me
senseless. One of these days I'ma going to try and read into this.
Anyone with any knowledge of what a Koch snowflake is please post!]
Anyway, Cantor. Cantor was unable to prove, however, something
called the Continuum Hypothesis. What this says is that there is no
set whose "size" (or, to give it the correct lingo: "cardinality"😉 is strictly
between that of the integers and that of the real numbers. Cantor
really believed this to be true and spent many years trying to prove it
so.
A German(? I think he was German) mathematician called David
Hilbert published roughly 25 (off the top of my head, I may be wrong)
outstanding, unsolved problems in mathematics in 1900, problems he
believed that efforts should be directed towards in the new century.
The Continuum Hypothesis was number 1.
I always get the shivers when I hear the name "Godel". From the little
I know I'd say he must have been arguably the biggest spoilsport in
the history of intellectual thought. Broke a lot of people's hearts and
hopes for the completeness and fundamental truth of mathematics.
Godel showed that it is impossible to *disprove* the Continuum
Hypothesis. Having said that he did however deeply suspect it to be
false. It was problems with the axioms used that was getting in the
way, rather than the hypothesis itself necessarily.
Godel's incompleteness theorem was a killer. Been a while since I
read about it but from what I can remember he showed that if you
have axioms strong enough to allow arithmetic, from them it is
possible to create things whereby it is impossible to either prove or
disprove. I think he went on to show that not only this, but also it was
possible, in theory to prove and disprove a statement.
I said that it broke hearts. The reason why was that it became
apparant the people called "the formalists", ie those that wanted to
show mathematics to be this totally consistent edifice, would never be
able to attain their goal.
I'm on sketchy ground here (which is a pity because the
incompleteness theorem and it's implications fascinate me) so I'll let
someone else pick up the baton who knows more about it than me.
Maggoteer!!!!! Good to see you posting in the forums! As ever
contributing with quality. That book you mentioned, by Hofstadter
(spelling there wonky probably), Godel, Escher, Bach; an eternal
golden braid. Did you manage to get through it all? It's an astonishing
book isn't it?! I struggled big time. Was fascinated though. He seems
to wander from this to that back to this with a bit of that thrown in for
fun. Incredible really. Would you recommend giving it another crack?
Or should I cut my losses before my head explodes? (If you say that
it was easy to read and a doddle then I think I'll cry!!).
Anyway, people, tell me more about Godel!! (and, on a slightly
different tack, Koch snowflakes too!)
Mark
Extremely grateful to Bennett and others for getting on board this topic