How to prove that the positive irrationals are not denumerable?

1. Sep 15, 2007

Werg22

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. Sep 15, 2007

mathwonk

you can do this.

3. Sep 15, 2007

Werg22

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.

4. Sep 15, 2007

Hurkyl

Staff Emeritus
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 $0.\bar{9} = 1.\bar{0}$, and the like)

Last edited: Sep 15, 2007
5. Sep 15, 2007

HallsofIvy

Staff Emeritus
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.)

6. Sep 15, 2007

redrzewski

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.

7. Sep 15, 2007

HallsofIvy

Staff Emeritus
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".

8. Sep 15, 2007

CRGreathouse

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.

9. Sep 16, 2007

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.

10. Sep 16, 2007

mathwonk

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
11. Sep 16, 2007

Werg22

12. Sep 17, 2007

mathwonk

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
13. Sep 17, 2007

No, he wanted to show that the irrationals are uncountable WITHOUT being given that the reals are.

14. Sep 17, 2007

mathwonk

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.

15. Sep 18, 2007

16. Sep 18, 2007

mathwonk

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
17. Sep 18, 2007

mathwonk

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
18. Sep 18, 2007

mathwonk

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.

19. Sep 18, 2007

mathwonk

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
20. Sep 19, 2007

mathwonk

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]?