Results 1 to 5 of 5

Thread: Cantor's Discovery

  1. Top | #1
    Veteran Member
    Join Date
    Feb 2001
    Location
    Birmingham, Alabama
    Posts
    2,287
    Archived
    4,109
    Total Posts
    6,396
    Rep Power
    75

    Cantor's Discovery

    The set of real numbers cannot be put into one-to-one correspondence with the integers, yet there is a one-to-one correspondence between the points of a line and the points of R^n. Cantor proved it but stated, “I see it but I do not believe it.”

    In a nutshell, what’s the proof?

  2. Top | #2
    Veteran Member
    Join Date
    Sep 2004
    Location
    California
    Posts
    4,116
    Archived
    4,797
    Total Posts
    8,913
    Rep Power
    64
    Quote Originally Posted by SLD View Post
    The set of real numbers cannot be put into one-to-one correspondence with the integers, yet there is a one-to-one correspondence between the points of a line and the points of R^n. Cantor proved it but stated, “I see it but I do not believe it.”

    In a nutshell, what’s the proof?
    Of which part? That there's a one-to-one correspondence between the points of a line and the points of R^n is pretty easy to see. A = 0.1234567891011... <=> X,Y,Z = (0.14711..., 0.2580..., 0.3691...). That's more or less how the proof goes for n=3; it works the same way for other n except you take every nth digit instead of every 3rd digit. There are some gotchas you have to work around. You have to turn all the terminating reals like 0.25 into the equivalent nonterminating 0.249999...; and the way I showed it only works for positive numbers, so you have to finesse it a little to get from one sign-bit to n sign-bits, but that's not hard.

    That the set of real numbers cannot be put into one-to-one correspondence with the integers is trickier; that's where Cantor proved he was a genius. I'll leave that half as an exercise for the reader.

  3. Top | #3
    Veteran Member
    Join Date
    Feb 2001
    Location
    Birmingham, Alabama
    Posts
    2,287
    Archived
    4,109
    Total Posts
    6,396
    Rep Power
    75
    Quote Originally Posted by Bomb#20 View Post
    Quote Originally Posted by SLD View Post
    The set of real numbers cannot be put into one-to-one correspondence with the integers, yet there is a one-to-one correspondence between the points of a line and the points of R^n. Cantor proved it but stated, “I see it but I do not believe it.”

    In a nutshell, what’s the proof?
    Of which part? That there's a one-to-one correspondence between the points of a line and the points of R^n is pretty easy to see. A = 0.1234567891011... <=> X,Y,Z = (0.14711..., 0.2580..., 0.3691...). That's more or less how the proof goes for n=3; it works the same way for other n except you take every nth digit instead of every 3rd digit. There are some gotchas you have to work around. You have to turn all the terminating reals like 0.25 into the equivalent nonterminating 0.249999...; and the way I showed it only works for positive numbers, so you have to finesse it a little to get from one sign-bit to n sign-bits, but that's not hard.

    That the set of real numbers cannot be put into one-to-one correspondence with the integers is trickier; that's where Cantor proved he was a genius. I'll leave that half as an exercise for the reader.
    That does seem rather simple. But it took Cantor three years to figure it out. Perhaps the details are more involved, but I see what you did.

    The first theorem seems more intuitive at first glance, but maybe not.

  4. Top | #4
    Mazzie Daius fromderinside's Avatar
    Join Date
    Oct 2008
    Location
    Oregon's westernmost
    Posts
    13,198
    Archived
    18,213
    Total Posts
    31,411
    Rep Power
    59
    Gnurs.

  5. Top | #5
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    11,323
    Archived
    16,829
    Total Posts
    28,152
    Rep Power
    87
    Cantor's diagonal argument presents the proof.

    It shows that R[0,1] is uncountable, and from there, that R is uncountable. It proceeds by contradiction. Suppose that R[0,1] is countable. Then one can take every member of that set with 1, 2, 3, ..., One can line them up in sequence. Now take the first trailing digit of the first number, the second trailing digit of the second number, and so forth. Change each digit, and assemble a member of R[0,1] from them. It is not in that list, thus making such a list is not possible.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •