Results 1 to 8 of 8

Math Help - How can we prove these sets are countable?

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    53

    How can we prove these sets are countable?

    a) The set of all numbers with two distinct decimal expansions(like 0.5000..., and 0.4999...)

    b) The set of all rational points in the plane

    c) The set of all rational intervals

    d) The set of all polynomials with rational coefficients

    I've seen the proof of "the set Q of all rational numbers is countable"
    but can't figure out the above.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by ninano1205 View Post
    a) The set of all numbers with two distinct decimal expansions(like 0.5000..., and 0.4999...)
    b) The set of all rational points in the plane
    c) The set of all rational intervals
    d) The set of all polynomials with rational coefficients
    Let \mathbb{N} = \left\{ {0,1,2, \cdots } \right\}, the non-negative integers.
    Define f:\mathbb{N} \times \mathbb{N} \mapsto \mathbb{N} as f(m,n) = 2^m  \cdot 3^n .
    It is easy to show that f is an injection which implies that \mathbb{N} \times \mathbb{N} is a countable set.
    That idea can be extended to \underbrace {\mathbb{N} \times \mathbb{N} \times \mathbb{N} \cdots  \times \mathbb{N} \times \mathbb{N}}_k by using a ordered listing of the primes as we used 2\;\&\;3 above. Hence that set is countable.
    Of course this can be extended set of all integers and to the set of all rational numbers.

    Now all your questions are proven by a simple application of this basic idea.
    Last edited by Plato; February 3rd 2009 at 11:07 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    53

    Could you give me little more detail?

    Not easy to comprehend...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by ninano1205 View Post
    Not easy to comprehend.
    Please post a reply to this.
    Show that f:\mathbb{N} \times \mathbb{N} \mapsto \mathbb{N} as f(m,n) = 2^m  \cdot 3^n is an injection.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2008
    Posts
    53

    ??

    Where did you get 2^m*3^n??
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by ninano1205 View Post
    Where did you get 2^m*3^n??
    You are just stalling! Do you know how to show that function is one-to-one?
    It matters not where the numbers came from. We need to know where you are.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2008
    Posts
    53

    one to one

    If we can invert a function, it is one to one. After inverting it and if it possess a non-empty domain in the real numbers , then it is one to one, or injective. ??
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by ninano1205 View Post
    If we can invert a function, it is one to one. After inverting it and if it possess a non-empty domain in the real numbers , then it is one to one, or injective. ??
    Thank you for your reply. I now see the problems you are having.
    My advice to you is simple: “Drop this current sequence of questions”.
    Go back to the basics. Learn how one proves a function is an injection, a surjection, and/or a bijection.
    Learn how compositions of such function work.
    Unless one has a through and complete understanding of that material, the idea of doing a proof involving cardinalities of set is out of the question.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 9th 2013, 06:14 AM
  2. [SOLVED] Countable union of closed sets/countable interesection of open sets
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 8th 2010, 01:59 PM
  3. Replies: 1
    Last Post: February 9th 2010, 01:51 PM
  4. Countable Sets
    Posted in the Calculus Forum
    Replies: 0
    Last Post: December 8th 2008, 05:17 PM
  5. Replies: 11
    Last Post: October 11th 2008, 06:49 PM

Search Tags


/mathhelpforum @mathhelpforum