Results 1 to 10 of 10

Math Help - Prove that sets are denumerable

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    32

    Prove that sets are denumerable

    Hi!

    Problem:

    Prove that the sets  \mathbb{N} \times \mathbb{N} = \left\{ (i,j): i,j \in \mathbb{N} \right\} and  \mathbb{Q} are denumerable.

    (If someone wants to give a precise definition of denumerable please do).

    For a fixed  j \in \mathbb{N} the set  \left\{ (i,j): i,j \in \mathbb{N} \right\} is denumerable since  \mathbb{N} is denumerable.
    If we change  j to  j' , the set  \left\{ (i,j'): i,j' \in \mathbb{N} \right\} is also denumerable.
    So we have a denumerable amount of denumerable sets, which gives that  \mathbb{N} \times \mathbb{N} is denumerable?

    I tried proving  \mathbb{Q} in a similar way.

    Help appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1
    Assuming that \mathbb{N}=\{0,1,2,\cdots\} then a set is denumerable if it bijects with \mathbb{N}.
    f:\mathbb{N}\times \mathbb{N}\to \mathbb{N} by j,k)\mapsto 2^j3^k" alt="fj,k)\mapsto 2^j3^k" /> is an injection.
    Because any infinite subset of a denumerable set is denumerable, we are done.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2010
    Posts
    32
    Thanks for the definition.

    Why did you choose just 2 and 3?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1
    They work.
    Prove that function is an injection.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jun 2010
    Posts
    32
    But how can this be a bijection? Doesn´t bijective also mean surjective? Can 2^{j}3^{k} = 5 ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    It's not a bijection with \mathbb{N}. It is a bijection with the set \{2^i3^j\ |\ i,j\in \mathbb{N}\}.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1
    Quote Originally Posted by ecnanif View Post
    But how can this be a bijection? Doesn´t bijective also mean surjective? Can 2^{j}3^{k} = 5 ?
    Well of course it is not a bijection! All it has to is an injection.
    Because an infinite subset of a denumerable set is denumerable

    But if you are required to have a bijection, here is one:
    (0,0)\mapsto 0~\&~(j,k)\mapsto 2^j(2k-1).
    But that is harder to prove.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jun 2010
    Posts
    32
    So if  (i,j) \neq (x,y) and
    <br />
\begin{array}{ccc}<br />
2^{j}3^{k}=A \\<br />
2^{x}3^{y}=A<br />
\end{array}<br />
    We get that 2^{j}3^{k}=2^{x}3^{y} \Leftrightarrow 2^{j-x}3^{k-y}=1
    And this implies  j=x \mbox{ and } k=y

    So f is an injection.
    What have we shown? The codomain of f is a subset of  \mathbb{N} ?

    Thanks again
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121
    The codomain is an infinite subset of N- and so denumerable.

    As Plato said before, "an infinite subset of a denumerable set is denumerable".

    As for showing that Q is denumerable, now you can use: every positive number in Q, Q^+, can be written in the form \frac{m}{n} where m and n are relatively prime integers in N. The mapping \frac{m}{n}\to (m, n) is an injection from Q^+ to NxN showing the Q^+ is denumerable. The set of negative rationals can be handled in the same way and the union of two denumerable sets is denumerable.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Jun 2010
    Posts
    32
    Quote Originally Posted by HallsofIvy View Post
    As Plato said before, "an infinite subset of a denumerable set is denumerable".
    Thanks all! This was a very important point.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 2nd 2010, 11:21 AM
  2. finite and infinite sets...denumerable
    Posted in the Differential Geometry Forum
    Replies: 15
    Last Post: November 22nd 2009, 05:38 PM
  3. Denumerable sets...
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 5th 2009, 10:26 PM
  4. denumerable sets
    Posted in the Advanced Math Topics Forum
    Replies: 15
    Last Post: December 14th 2008, 10:39 PM
  5. denumerable sets
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: February 20th 2008, 10:08 AM

Search Tags


/mathhelpforum @mathhelpforum