Results 1 to 3 of 3

Math Help - Proving a set denumerable

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    32

    Proving a set denumerable

    Hi

    I my book, it says: To prove that a set A is denumerable you should find a bijection f : \mathbb{N} \to \mathbb{A} .

    Now, I need to prove that  \mathbb{Q} is denumerable.
    So I replace my A with  \mathbb{Q} in the previous paragraph. Now I need to find a bijection f.

    Would it be equivalent to find a bijection f: \mathbb{Q} \to \mathbb{N} ?
    If so, I need to find a function that takes the rational numbers to \mathbb{N}. Also, it need to be injective.
    It should be suffiecient to find a bijection f: \mathbb{Q} \to G \subseteq \mathbb{N} ?

    What could f look like?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member jakncoke's Avatar
    Joined
    May 2010
    Posts
    387
    Thanks
    80
    Quote Originally Posted by ecnanif View Post

    I my book, it says: To prove that a set A is denumerable you should find a bijection f : \mathbb{N} \to \mathbb{A} .

    Now, I need to prove that  \mathbb{Q} is denumerable.
    So I replace my A with  \mathbb{Q} in the previous paragraph. Now I need to find a bijection f.

    Would it be equivalent to find a bijection f: \mathbb{Q} \to \mathbb{N} ?
    If so, I need to find a function that takes the rational numbers to \mathbb{N}. Also, it need to be injective.
    It should be suffiecient to find a bijection f: \mathbb{Q} \to G \subseteq \mathbb{N} ?

    What could f look like?
    no it would not be equivalent to find a bijection f: \mathbb{Q} \to \mathbb{N} becuase Q contains N so a trivial function would be  f: \mathbb{N} \to \mathbb{N}. You need to find a function  f : \mathbb{N} \to \mathbb{Q} . Also bijection means both injection and surjection. so u don't need to single out injective.

    for example, to prove that  \mathbb{Q^{+}} is denumerable. notice you can break  \mathbb{Q^{+}} into classes depending on what the numerator and denominator adds up to like class{2} = 1/1, class{3} = 1/2, 2/1 class{4} = 3/1, 1/3 etc.... and each of these classes is finite...
    Last edited by jakncoke; June 29th 2010 at 10:51 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,649
    Thanks
    1597
    Awards
    1
    Consider the cross product of positive integers, \mathbb{Z}^+\times \mathbb{Z}^+.
    Map that set to  \mathbb{Z}^+ by \phi(m,n)=2^{m-1}(2m-1)
    It can be shown that \phi is a bijection.
    The positive rational can be seen as a subset of \mathbb{Z}^+\times \mathbb{Z}^+.
    So they are denumerable. Clearly we can extend this to the entire set of rationals.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove that a set is denumerable iff...
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 2nd 2010, 11:26 AM
  2. Replies: 1
    Last Post: October 2nd 2010, 11:21 AM
  3. Denumerable Set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2010, 11:54 AM
  4. Denumerable Partition
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 19th 2009, 08:37 AM
  5. Denumerable Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 18th 2009, 12:56 PM

Search Tags


/mathhelpforum @mathhelpforum