Results 1 to 10 of 10

Thread: 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 $\displaystyle \mathbb{N} \times \mathbb{N} = \left\{ (i,j): i,j \in \mathbb{N} \right\} $ and $\displaystyle \mathbb{Q} $ are denumerable.

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

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

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

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

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,796
    Thanks
    2827
    Awards
    1
    Assuming that $\displaystyle \mathbb{N}=\{0,1,2,\cdots\}$ then a set is denumerable if it bijects with $\displaystyle \mathbb{N}$.
    $\displaystyle f:\mathbb{N}\times \mathbb{N}\to \mathbb{N} $ by $\displaystyle 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
    21,796
    Thanks
    2827
    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 $\displaystyle 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 $\displaystyle \mathbb{N}$. It is a bijection with the set $\displaystyle \{2^i3^j\ |\ i,j\in \mathbb{N}\}$.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,796
    Thanks
    2827
    Awards
    1
    Quote Originally Posted by ecnanif View Post
    But how can this be a bijection? Doesn´t bijective also mean surjective? Can $\displaystyle 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:
    $\displaystyle (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 $\displaystyle (i,j) \neq (x,y) $ and
    $\displaystyle
    \begin{array}{ccc}
    2^{j}3^{k}=A \\
    2^{x}3^{y}=A
    \end{array}
    $
    We get that $\displaystyle 2^{j}3^{k}=2^{x}3^{y} \Leftrightarrow 2^{j-x}3^{k-y}=1 $
    And this implies $\displaystyle j=x \mbox{ and } k=y $

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

    Thanks again
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,795
    Thanks
    3035
    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, $\displaystyle Q^+$, can be written in the form $\displaystyle \frac{m}{n}$ where m and n are relatively prime integers in N. The mapping $\displaystyle \frac{m}{n}\to (m, n)$ is an injection from $\displaystyle Q^+$ to NxN showing the $\displaystyle 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: Oct 2nd 2010, 11:21 AM
  2. finite and infinite sets...denumerable
    Posted in the Differential Geometry Forum
    Replies: 15
    Last Post: Nov 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: Dec 14th 2008, 10:39 PM
  5. denumerable sets
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: Feb 20th 2008, 10:08 AM

Search Tags


/mathhelpforum @mathhelpforum