Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cantor's Diagonal Argument

  1. Feb 19, 2014 #1
    I had an undergraduate pose an interesting question to me. "Why doesn't Cantor's Diagonal Argument apply to the rationals?"

    http://www.proofwiki.org/wiki/Real_Numbers_are_Uncountable/Cantor%27s_Diagonal_Argument

    Now obviously it doesn't since the rationals are countable. But what breaks the argument? It seems obvious that the resulting "diagonal number" won't be rational since the decimal expansion of rationals either terminate or repeat.

    But actually proving that this "diagonal number" can't be rational seems like it would be difficult.

    What do you guys think?
     
  2. jcsd
  3. Feb 19, 2014 #2
    The "diagonal number" in the standard argument is constructed based on a mythical list, namely a given denumeration of the real numbers. So that number is mythical. If we're willing to consider proving properties about the mythical number, it can be proved to have any property we want; in particular, it's both provably rational and provably irrational.

    A different, well-posed question. If we let [itex](x_i)_{i=1}^\infty[/itex] be an enumeration of [itex][0,1]\cap\mathbb Q[/itex] and let [itex]x_i=0.d_{i1}d_{i2}d_{i3}...[/itex] be a decimal expansion, then is the associated diagonal number rational? Equivalently, do its digits eventually cycle?

    The answer to this is no, and there's an easy proof. By construction, it's not in the list. By fiat, the list exhausted the rationals. Hence it isn't rational.
     
  4. Feb 19, 2014 #3
    Given a (necessarily incomplete) list of rationals with a rational diagonal, I want to think that it should be fairly straightforward, if not a bit tedious, to construct a rational that is not on the list, just by looking at the repeating digits of the diagonal and noticing that "too many" rationals would need to appear on the list very early on.

    At the very least, it should be easy to construct a finite set of rationals that couldn't all be on the list.
     
  5. Feb 19, 2014 #4

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You don't have to prove that the diagonal number is not rational. It's the fact that you cannot prove it is rational that means the proof doesn't work.

    If you're left not knowing whether the number is rational or not, then you haven't proved anything. In particular, you haven't found a rational not in the original list.
     
  6. Feb 20, 2014 #5

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    And no wonder it is hard to prove the diagonal number is rational. If the original list is the counting list of rationals (easy to prove the rationals are countable), the diagonal is not on the list and can not be rational.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Cantor's Diagonal Argument
Loading...