Results 1 to 2 of 2

Thread: Denumerable Set

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

    Denumerable Set

    My book shows that the set of integers, $\displaystyle \mathbb{Z}, $ is denumerable by expressing the elements of the set as infinite sequence

    $\displaystyle \mathbb{Z}=\{0, 1,-1,2,-2,...\}$, and then shows that the function

    $\displaystyle f: \mathbb{N}\rightarrow \mathbb{Z}$ is bijective, where

    $\displaystyle f$ is defined as

    $\displaystyle f(n)=\frac{1+(-1)^n(2n-1)}{4}$

    The picture shows that there is one-one correspondence, such as this:

    $\displaystyle 1 \rightarrow 0$

    $\displaystyle 1 \rightarrow 1$

    $\displaystyle 2 \rightarrow -1$

    $\displaystyle 3 \rightarrow 2$

    $\displaystyle 4 \rightarrow -2$

    .
    .
    .

    Now I want to prove that $\displaystyle f(n)=\frac{1+(-1)^n(2n-1)}{4}$ bijective, but $\displaystyle (-1)^n$ in the expression is making it very clumsy.

    To prove the one-to-one isn't too bad, since $\displaystyle f(a_1)=f(a_2)$ seems to look clean, but now when I get to the part where I need to prove it an onto function, I got a huge mess, so I am wondering whether it be alright to split the proof in two parts such that

    $\displaystyle f(n) = g(s) \cup h(t)$ and define $\displaystyle g(s) \subset \mathbb{Z}^-$ and $\displaystyle h(t) \subset \mathbb{Z}^+$ and by so doing, I plan to prove that

    there exists an odd positive integer $\displaystyle p\in \mathbb{N}$ such that $\displaystyle g(s)=\frac{1+(-1)^s(2s-1)}{4}$ where $\displaystyle s=2n-1, n \in \mathbb{N}$

    and there also exists an even positive integer $\displaystyle q\in \mathbb{N}$ such that $\displaystyle h(t)=\frac{1+(-1)^t(2t-1)}{4}$ where $\displaystyle t=2n, n \in \mathbb{N}$

    Questions:

    1. Is there a simpler way than to prove the onto-function in two parts?

    2. Is there a better way with handling $\displaystyle (-1)^n$ expression ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,743
    Thanks
    2814
    Awards
    1
    If $\displaystyle x=0$ then $\displaystyle f(1)=0$.
    If $\displaystyle x>0$ then $\displaystyle f(2x)=x$.
    If $\displaystyle x<0$ then $\displaystyle f(2|x|+1)=x$.
    So it is onto.
    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. Proving a set denumerable
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Jun 29th 2010, 01:22 PM
  4. Denumerable Partition
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 19th 2009, 08:37 AM
  5. denumerable sets
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: Feb 20th 2008, 10:08 AM

Search Tags


/mathhelpforum @mathhelpforum