Results 1 to 14 of 14

Math Help - prove set of irrational number is uncountable

  1. #1
    Member
    Joined
    Jul 2010
    Posts
    99

    prove set of irrational number is uncountable

    Hi, can friends here please help me with this question? I'm really struggling with it.

    Prove the set of irrational number R\Q is uncountable.

    I know the idea is try to find the bijection function, right? But I just cannot do it. Please help me with it. Thanks a lot.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16
    What things are you given? Are you given that R is uncountable?

    You use bijections to prove sets are COUNTABLE, not uncountable. In this case you won't be able to find a bijection, i think.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2010
    Posts
    99
    Quote Originally Posted by Vlasev View Post
    What things are you given? Are you given that R is uncountable?

    You use bijections to prove sets are COUNTABLE, not uncountable. In this case you won't be able to find a bijection, i think.
    Yes, sorry that I was a bit drunk, haha, of course, bijection is for COUNTABLE, I knew that, thanks.
    And yes, I was given R is uncountable. I guess I have the idea is that prove union or intersection of uncountable is uncountable as well. But I just really don't know how to do in details. Please help me. Thanks a lot.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16
    You only need to show that the irrationals are the complement of the rationals.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2010
    Posts
    99

    prove set of irrational number is uncountable

    I was given R is uncountable. I guess I have the idea is that prove union or intersection of uncountable is uncountable as well. But I just really don't know how to do in details. Please help me. Thanks a lot.
    Last edited by mr fantastic; August 8th 2010 at 04:51 AM. Reason: Moved from thread created by duplicate post.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,677
    Thanks
    1618
    Awards
    1
    You know that \mathbb{R} is uncountable and \mathbb{Q} is countable.
    The union of two countable set is countable.
    So what does that mean about \mathbb{Q}\cup (\mathbb{R}\setminus \mathbb{Q})?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jul 2010
    Posts
    99
    Quote Originally Posted by Plato View Post
    You know that \mathbb{R} is uncountable and \mathbb{Q} is countable.
    The union of two countable set is countable.
    So what does that mean about \mathbb{Q}\cup (\mathbb{R}\setminus \mathbb{Q})?

    Sorry, I still cannot get it. I just started Real Analysis course two weeks ago, so I haven't built enough foundation. Please help me with more details, I cannot thank you more.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,714
    Thanks
    1472
    Not necessarily so. A bijection from a set A to the set of real numbers between 0 and 1 would prove that A is uncountable. A bijection always shows that two sets have the same cardinality.

    Sorry: this was in response to Vsalev's post: "You use bijections to prove sets are COUNTABLE, not uncountable. In this case you won't be able to find a bijection, i think."
    Last edited by HallsofIvy; August 11th 2010 at 04:13 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Apr 2009
    Posts
    48
    Quote Originally Posted by Plato View Post
    You know that \mathbb{R} is uncountable and \mathbb{Q} is countable.
    The union of two countable set is countable.
    So what does that mean about \mathbb{Q}\cup (\mathbb{R}\setminus \mathbb{Q})?
    I see what you're doing here. The set \mathbb{Q}\cup (\mathbb{R}\setminus \mathbb{Q}) = \mathbb{R}, which we know is uncountable. We also know that \mathbb{Q} is countable. But a number must either be rational or irrational, so it follows logically that \mathbb{R}\setminus \mathbb{Q} must be uncountable.

    Now, proving this formally... Could one more or less just follow the logic here, or is there a more rigorous approach? For instance, is it acceptable just to state \mathbb{Q}\cup (\mathbb{R}\setminus \mathbb{Q}) = \mathbb{R} (which is obvious), or should we go about proving this first?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,714
    Thanks
    1472
    that's a perfectly valid proof as it stands. The union of two countable sets is countable. (Have you proved that yet?)

    If the set of all irrational numbers were countable then the set of all real numbers, the union of the set of irrational numbers and the set of rational numbers, would be the union of two countable set and so countable. That contradicts the fact that the set or all real numbers is uncountable.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Apr 2009
    Posts
    48
    Quote Originally Posted by HallsofIvy View Post
    that's a perfectly valid proof as it stands. The union of two countable sets is countable. (Have you proved that yet?)

    If the set of all irrational numbers were countable then the set of all real numbers, the union of the set of irrational numbers and the set of rational numbers, would be the union of two countable set and so countable. That contradicts the fact that the set or all real numbers is uncountable.
    Yep, got it.

    I don't believe we've proved the union of two countable sets yet, so I'll avoid quoting the result directly in my final proof. Although, it really seems intuitive enough that I could and still get away with it.
    Last edited by Ares_D1; August 8th 2010 at 09:10 AM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    You can do this with a variant of Cantor's diagonal slash (I will be leaving out most of the hard work to leave something for the reader to do, that and I'm too lazy to do it myself)

    We will be working with reals in the interval $$[0,1) and with decimal expansions, so the decimal expansion of a real $$a in $$[0,1) is 0.a_1a_2,...\ : a_i \in \{0,1,2,3,4,5,6,7,8,9\}.

    I will use the expressions "the decimal expansion of $$ a is periodic" or " $$ a is periodic" to mean the eventually the decimal expansion of $$ a becomes periodic.

    ----------------------------------------------------------------------

    Lemma

    A real in $$ [0,1) is rational if and only if it is periodic

    Proof

    Excersise for the reader (it can be looked up)

    -----------------------------------------------------------------------

    Suppose the set or irrational numbers is enumerable and that x(i), i=1,2.. is an enumeration. Let x_{i,j} denote the $$ j th term in the decimal expansion of x(i)

    Now we combine Cantor's slash argument with an idea of Liouville's, define the real $$ z with decimal expansion:

    z_k=\begin{cases}<br />
1 &,{\text{if }} (\not\exists r: k=r!) \land (x_{k,k}= 0)\\<br />
0 &,{\text{if }} (\not\exists r: k=r!) \land (x_{k,k}\ne0)\\<br />
2 &,{\text{if }} (\exists r: k=r!) \land (x_{k,k}\ne 2)\\<br />
3 &,{\text{if }} (\exists r: k=r!) \land (x_{k,k}= 2)\\<br />
\end{cases}

    Then z \in [0,1) and $$z is not periodic, so as $$z differes from each irrational in our enumeration at at least one place in its' decimal expansion it is not in our enumeration and $$z is irrational. hence we have the required contradiction ...

    CB
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by CaptainBlack View Post
    You can do this with a variant of Cantor's diagonal slash (I will be leaving out most of the hard work to leave something for the reader to do, that and I'm too lazy to do it myself)

    \vdots

    CB
    We can also use cos(x): \mathbb{R} \rightarrow [-1, 1]. Note that this is a surjection.

    Noting that cos(x) = cos(x+2\pi), if x \in \mathbb{Q} then x+2\pi \not\in \mathbb{Q}. Thus, letting f be the restriction of cos(x) to \mathbb{R}\setminus \mathbb{Q} we see that f: \mathbb{R}\setminus \mathbb{Q} \rightarrow [-1, 1] is a surjection onto something with cardinality that of \mathbb{R}. This is sufficient.

    (This is sufficient because if there exists a surjection from A to B then |A| \geq |B|. Similarly, if there exists an injection from A to B then |A| \leq |B|. Clearly the latter holds, and the former holds by what I just wrote about. Thus, |\mathbb{R} \setminus \mathbb{Q}| = |\mathbb{R}|, as required.)
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Swlabr View Post
    We can also use cos(x): \mathbb{R} \rightarrow [-1, 1]. Note that this is a surjection.

    Noting that cos(x) = cos(x+2\pi), if x \in \mathbb{Q} then x+2\pi \not\in \mathbb{Q}. Thus, letting f be the restriction of cos(x) to \mathbb{R}\setminus \mathbb{Q} we see that f: \mathbb{R}\setminus \mathbb{Q} \rightarrow [-1, 1] is a surjection onto something with cardinality that of \mathbb{R}. This is sufficient.

    (This is sufficient because if there exists a surjection from A to B then |A| \geq |B|. Similarly, if there exists an injection from A to B then |A| \leq |B|. Clearly the latter holds, and the former holds by what I just wrote about. Thus, |\mathbb{R} \setminus \mathbb{Q}| = |\mathbb{R}|, as required.)
    This is quite nice, but it is a case of the formalism of the language used obscuring the idea, or at least increasing the work load required to see how nice a method it is. I blame Rudin myself, and Bourbaki for that matter.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove that z=log base p (qr) is an irrational number
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 4th 2010, 11:30 AM
  2. Replies: 0
    Last Post: February 16th 2010, 05:04 AM
  3. Replies: 11
    Last Post: October 25th 2009, 06:45 PM
  4. Replies: 7
    Last Post: January 29th 2009, 03:26 AM
  5. Replies: 4
    Last Post: October 11th 2008, 01:42 PM

Search Tags


/mathhelpforum @mathhelpforum