How to show the integers have same cardinality as the natural numbers?

How would I show the following have a bijection. Which is one to one and onto ofcourse.

$\mathbb{Z}\rightarrow \mathbb{N}$

I know I need to find a function. But I do not see the pattern that makes integer go to natural. I already did this problem from natural to integer but now I want to see it done this way.

I have listed some numbers

$,..,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,..$

$1,2,3,4,5,6,7,8,9,10,11,12,13,14,.$

• No dont close por favor..... – Fernando Martinez Jul 21 '14 at 17:57

I like the one that snake around, $0, -1, 1, -2, 2, -3, 3,\ldots$

So it goes

$$\begin{cases}f: \Bbb N\to \Bbb Z \\ f(2n)=n-1 \\ f(2n-1)=-n\end{cases}$$

If you want it to go the other way, you just reverse the idea and compute the inverse of $f$.

• Yes from N to Z the pattern is $n/2$ n is even, $(1-n)/2$ n is odd but I want to see from Integer to Natural. Altrough I do appreciate the insight of your pattern. – Fernando Martinez Jul 21 '14 at 18:03
• @Adam: How about letting the OP work out the inverse for themselves? It's not very difficult, and it is a good exercise. – Asaf Karagila Jul 21 '14 at 18:05
• @AsafKaragila a solid idea. I'll take that to heart. – Adam Hughes Jul 21 '14 at 18:08
• Well you can still write it so I can compare it to mine and see if I did it correctly. If you want to ofcourse. – Fernando Martinez Jul 21 '14 at 18:10
• I think so is it $-2(n)-1$ when $n<0$ – Fernando Martinez Jul 21 '14 at 18:25

Your list has absolutely no pattern, because you're doing it "wrong", in the sense that you are not writing it in a way that a pattern emerges.

Of course there is no order preserving function, so writing both sets with their natural order will promise you that there is no reasonable pattern. Instead write the natural numbers, and then try to write the integers:

$$\begin{array} & 1 & 2& 3& 4& 5& 6& 7& 8&\ldots\\ 0 & 1& -1& 2& -2& 3& -3& 4&\ldots \end{array}$$

This gives rise to a bijection from $\Bbb N$ onto $\Bbb Z$. Now just find its inverse.

(Note that it is in general easier to find "pattern" when $\Bbb N$ is the domain, because the list does not require you to go into two directions.)

• I see it has something to do with odds and evens... – Fernando Martinez Jul 21 '14 at 18:11
• Yes, very good. What else do you see? – Asaf Karagila Jul 21 '14 at 18:13

For example $$f:\mathbb Z\rightarrow\mathbb N$$ $$f(n)=\begin{cases} 2n+1 \text{ if } n\geq0 \\ -2n \text{ if } n<0\end{cases}$$

By some different definitions, $\mathbb{N}$ may contain the element $0$. So the map should look like this:

\begin{array} &0 & 1 & \phantom{-}2& 3& \phantom{-}4& 5& \phantom{-}6& 7& \phantom{-}8&\ldots\\ 0 & 1& -1& 2& -2& 3& -3& 4& -4&\ldots \end{array}

So the function $f: \mathbb{Z} \to \mathbb{N}$ is:

$$f(n)=\begin{cases} 2n-1 \, \text{ if } n\gt 0 \\ -2n \quad \text{ if } n \leq0\end{cases}$$