Results 1 to 3 of 3

Thread: 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 $\displaystyle A$ is denumerable you should find a bijection $\displaystyle f : \mathbb{N} \to \mathbb{A} $.

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

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

    What could $\displaystyle 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 $\displaystyle A$ is denumerable you should find a bijection $\displaystyle f : \mathbb{N} \to \mathbb{A} $.

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

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

    What could $\displaystyle f$ look like?
    no it would not be equivalent to find a bijection $\displaystyle f: \mathbb{Q} \to \mathbb{N} $ becuase Q contains N so a trivial function would be $\displaystyle f: \mathbb{N} \to \mathbb{N}$. You need to find a function $\displaystyle 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 $\displaystyle \mathbb{Q^{+}} $ is denumerable. notice you can break $\displaystyle \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; Jun 29th 2010 at 10:51 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,796
    Thanks
    2827
    Awards
    1
    Consider the cross product of positive integers, $\displaystyle \mathbb{Z}^+\times \mathbb{Z}^+$.
    Map that set to $\displaystyle \mathbb{Z}^+$ by $\displaystyle \phi(m,n)=2^{m-1}(2m-1)$
    It can be shown that $\displaystyle \phi$ is a bijection.
    The positive rational can be seen as a subset of $\displaystyle \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: Oct 2nd 2010, 11:26 AM
  2. Replies: 1
    Last Post: Oct 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