Denumerable Set

Sep 2009
502
39
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 ?
 

Plato

MHF Helper
Aug 2006
22,456
8,631
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.
 
  • Like
Reactions: novice