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

How to prove that the positive irrationals are not denumerable?

  1. Sep 15, 2007 #1
    Since the positive reals aren't denumerable (or so do I read) and the positive rationals are, then that must mean the positive irrationals aren't. How do we go on about proving this?
     
  2. jcsd
  3. Sep 15, 2007 #2

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    you can do this.
     
  4. Sep 15, 2007 #3
    Huh... The whole point is show that P is not denumerable in order to prove that R isn't either... The starting point is P not R.
     
  5. Sep 15, 2007 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I think it's easier to start with R. At least, I don't see how one would prove it for P without first proving it for R.

    Maybe the special case in the standard proof for R can be appropriately tweaked to turn it into a proof for P? I'll have to think on that...

    (The standard proof works on decimal representations, so you have to do something special to handle the fact that [itex]0.\bar{9} = 1.\bar{0}[/itex], and the like)
     
    Last edited: Sep 15, 2007
  6. Sep 15, 2007 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    That strikes me as an awfully clumsy way to prove that R is not denumerable! It's easy to use Cantor's diagonal method to prove that R is not denumerable. That same method wouldn't work with P. (The number you produce by changing the "diagonal" digit might be rational.)
     
  7. Sep 15, 2007 #6
    R uncountable. Q countable. P = R - Q is uncountable.

    Proof:
    Assume P countable. The P U Q is finite union of countable sets, and hence countable. Which is a contradiction.
     
  8. Sep 15, 2007 #7

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Yes, that point was made before. The problem is that Werg22 want to FIRST prove that P is uncountable, then use that to prove that R in uncountable. He can't use the fact that R is uncountable because it "hasn't been proved yet".
     
  9. Sep 15, 2007 #8

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I concur that the method would be clumsy, but I can see a way of avoiding rationals for the diagonal number:

    Replacement scheme A: 1 |--> 2, all else |--> 3.
    Replacement scheme B: 1|--> 4, all else |--> 5.

    Use replacement scheme A for the first 2 digits, B for the next 4, A for the next 8, and so on. No series of digits can repeat because the ever-increasing blocks get in their way.
     
  10. Sep 16, 2007 #9
    In any case the original poster should realize that the only basic theorem here is that the power set of any set has strictly greater cardinality, and so the most simple proof is not the proof that deals with the "smallest' set (in terms of containment), but rather the set which has the simplist relationship with the power set.
     
  11. Sep 16, 2007 #10

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    come on guys. this trivial. he only has to prove that the union of two denumerable sets is denumerable. this is almost nothing.

    hint: enumerate one set by the odd numnbers and the other by the even numbers.
     
    Last edited: Sep 16, 2007
  12. Sep 16, 2007 #11
    Please read more of the thread...
     
  13. Sep 17, 2007 #12

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    you think i am missing something here in this thread? how interesting,

    i have read it twice. but i may indeed have been careless or stupid.

    i believe you asked in #1 why the positive irrationals could be proved non denumerable, given that the positive rationals are denumerable, yet the positive reals are not.

    proof by contradiction: if the positive irrationals were also denumerable, then since the union of two denumerable sets is also denumerable, so would be the positive reals.

    done.

    what have i missed? maybe i have miosunderstood wha=t you meant by the word :"this"?

    be mindful, these are matters i read independently as a 16 year old in 1959. so maybe i have lost some of the fascination of them.
     
    Last edited: Sep 17, 2007
  14. Sep 17, 2007 #13
    No, he wanted to show that the irrationals are uncountable WITHOUT being given that the reals are.
     
  15. Sep 17, 2007 #14

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    so you agree with me that the question, as asked, is trivial? but they are saying they really want to know why the reals are non denumerable?

    if so, i have still less interest in this, having as i said, learnt it as a junior in high school..

    thanks dead wolfe, but thats not what he said.
     
  16. Sep 18, 2007 #15
    Read post 3.
     
  17. Sep 18, 2007 #16

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    thank you. i did not knw what
    p stood for, and did not spend time wondering about it, so i missed it.
     
    Last edited: Sep 18, 2007
  18. Sep 18, 2007 #17

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    i am vainly searching for another alternative, to the obvious one of my being extremely stuopid in this matter, and have fiinalkly obtained a tenous one.

    namely it is very hard to shake loose an erroneous first impression. the original post semed very clear that one may assume uncountability of the reals, and having seized on this, some of us were unable to change it.

    I was once part of an experiment wherein people were given a wrong imopressiion at first, and then gradually given more correct information over time, until they first grasped the right notion. Other people were brought in somewhat later and given the information then being provided.

    these other people, usually got the right idea sooner than the original subjects. i.e. less information, but also less incorrect information, communicates better.


    In the actual experiment, a fuzzy picture was gradually clarified. subjects were urged to make guesses before the picture could really be well seen, and usually made erroneous ones that they kept trying to justify, long after the picture was so clear that a new subject broguht in would recognize the picture's content instantly.

    so, long after the picture became obviously a donkey, the original guesser was still trying to see it as an elephant. or long after the venture was obviously a disaster, the original miscreant was still trying to see it as a success.
     
    Last edited: Sep 18, 2007
  19. Sep 18, 2007 #18

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    i have finally become entranced by the posters question. is the desire to show the irrationals uncountable without first enlarging them by adding in any countable set?

    e.g. is it desired to show how to construct a new irrational out of any sequence of irrationals? i do admit failure at my first few tries at this.
     
  20. Sep 18, 2007 #19

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    but this seems a bit unnatural. i.e. consider infinite sets, but allow the equivalence relation wherein two sets are equivalent if their symmetric difference (A-B)union(B-A) is at most countable.

    then all equivalent sets have the same (infinite) cardinality. thus it is natural in deciding the cardinality of an infinite set to consider it only modulo this relation, sort of as one does in measure theiory, considering functions as equivalent which differ on a set of measure zero. so one naturally chooses a good representative for a given class on which to work.

    e.g. the characteristic function of the irrationals between 0 and 1, is equivalent to the constant function 1, hence ahs integral 1, not zero.

    so the irrationals are uncountable. this is the usual argument, but in a setting where one is commonly used to making these equivalences.
     
    Last edited: Sep 18, 2007
  21. Sep 19, 2007 #20

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    how do you like this measure theory version of the usual proof?

    another version usues compactness of [0,1], and makes a countable cover of the interval by intervals whose length is less than 1/2. then taking a finite subcover gives a rather puzzling situation. or in fact without doing so, by countable additivity of measure.

    or assume you have a small countable cover of the irrationals, isn't it natural to extend it to a countable cover of [0,1]?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: How to prove that the positive irrationals are not denumerable?
  1. Proving irrationality (Replies: 11)

Loading...