1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question about diagonal argument

  1. Dec 24, 2012 #1
    I thought I understood cantors diagonal argument but then I started to rethink it.
    Why couldn't i just line up all the decimal numbers with the the odd natural numbers.
    Then when we create a new decimal that is on my list I will line it up with an even number because I haven't used any of those yet.
     
  2. jcsd
  3. Dec 24, 2012 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Yes, you could do that but you haven't proved anything that way. Cantor's diagonal proof does not produce one number that cannot be matched up, it produces an infinite number of them. You have not yet shown that all of those numbers, that are not matched to the odd numbers, can be matched with the even numbers. In fact, we know, from Cantor's proof, that they can't.
     
  4. Dec 24, 2012 #3

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Why do you think you can even do that?? You can't. That's the whole point of the diagonal argument, you can't line up all the decimal numbers with the odd natural numbers.

    The diagonal argument is a proof by contradiction.
     
  5. Dec 24, 2012 #4
    im not saying you can line up all the decimals with the odd numbers , Im
    just saying we will start with that, then the new number that you create that is not on
    my list I will line that one up with an even number and the next decimal you line
    up with the next even number. I could do that with the rational numbers
    I could line up the naturals with the naturals and then create a rational that wasn't on my list but we know that the rationals are countable so it is not clear to me why the diagonal argument works now.
     
  6. Dec 24, 2012 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    The same does not work with the rationals because the diagonal number is not guaranteed to be rational.
     
  7. Dec 25, 2012 #6
    ok but it still isn't clear to me why the diagonal arguement works for the reals because I could just start to line them up with all the powers of 5 and then I would have all the
    powers of primes to line up with the new numbers that you create that aren't on my list .
    It just isn't clear to me.
     
  8. Dec 25, 2012 #7

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    So that way you won't find a contradiction.
    But the usual way, you do find a contradiction.

    It's not because you can't find a contradiction if you do something different, that the diagonal argument doesn't work.
     
  9. Dec 25, 2012 #8

    lurflurf

    User Avatar
    Homework Helper

    First of is the fluff of requiring each number to be uniquely represented. Next given a countably infinite list it is always possible to produce a number not among them by choosing a feature of each listed number and not matching it. Imagine you have an infinite number of binary options for a sandwich (such as has and does not have). Given an infinite number of sandwiched we can always make a new one by switching one option on each sandwich.

    like this
    1 has egg
    2 does not have mayo
    3 does not have onion
    4 has pickle
    5 has worms
    6 has orange peel
    7 has yak cheese
    8 does not have rhubarb
    ...


    To make a new sandwich switch the option given for each existing sandwich. Since the sandwich differs from each existing sandwich in at least one option, it must be new.
     
  10. Dec 25, 2012 #9

    lavinia

    User Avatar
    Science Advisor
    Gold Member

    You can't line up the reals with the powers of 5 or the odd numbers ot any subset of the integers. You are assuming what you want to disprove.
     
  11. Dec 25, 2012 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Once we've made infinitely many choices to fill up your list completely, I'm going to apply the diagonal argument again to produce yet another number not on your list.

    Since your list is full, there's no room for you to add this new number to the list.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook