# How to construct a bijection $\mathbb{N} \to \mathbb{N} \times \{0, 1\}.$

How to construct a bijection from $\mathbb{N}$ to $\mathbb{N} \times \{0, 1\}?$ My first idea was $n \mapsto (n, n \mod 2)$ but it is wrong. Any hint?

• Decompose $\mathbb{N}$ into two classes namely even and odd. – Rubertos Dec 6 '14 at 19:18
• $2n\mapsto (n,0)$ and $2n+1\mapsto (n,1)$ for each $n$. – ujsgeyrr1f0d0d0r0h1h0j0j_juj Dec 6 '14 at 19:23

Consider $$f(n) = \begin{cases} (\frac n2, 0) &\text{if } 2|n \\ (\frac{n-1}2, 1)&\text{otherwise}\end{cases}$$

• what be $f^{-1}(n,0)$ and $f^{-1}(n,1)$? – Leox Dec 6 '14 at 20:00
• @Leox $$f^{-1}: (x,y) \mapsto 2x + y$$ – Tacet Dec 6 '14 at 20:09
• @Leox $f^{-1}(n,0) = 2n$ and $f^{-1}(n,1) = 2n + 1$ – mookid Dec 6 '14 at 20:42

HINT: Recall that $\Bbb N\times\{0,1\}=(\Bbb N\times\{0\})\cup(\Bbb N\times\{1\})$. What other countable set can be naturally thought as the disjoint union of two copies of $\Bbb N$, and how do you define a bijection in that case? (It is also written with a Blackboard Bold font in many places)

Hint:

• Take the binary expansion $b_nb_{n-1}\ldots{}b_2b_1b_0$, and reinterpret the last bit, i.e. interpret the whole number as pair $\langle b_nb_{n-1}\ldots{}b_2b_1, b_0\rangle$.

I hope it helps $\ddot\smile$

• quite nice to be put in a computer :) – mookid Dec 6 '14 at 19:35

This problem is easier if you first make a bijection $g:\Bbb{Z} \to \Bbb{N} \times \{0,1 \}$ where $$g(n) = \begin{cases} (n+1,0) &\text{if} \space n \geq 0 \\ (-n,1)&\text{if} \space n<0\end{cases}$$ $g$ is defined to work around the fact that $0 \notin \Bbb{N}$ for me; your answer could be adjusted easily if this is not the case for you. It remains to be shown that $g$ is a bijection. It is also well known that there exists a bijection (we'll call it $f: \Bbb{N} \to \Bbb{Z}$) between the naturals and the integers. Once you know $g$ is a bijection it follows that $$f \circ g: \Bbb{N} \to \Bbb{N} \times \{0,1 \}$$ is a bijection.

• what be $f^{-1}(n,0)$ and $f^{-1}(n,1)$? – Leox Dec 6 '14 at 20:03
• The range of $f$ is $\Bbb{Z}$, so you can't evaluate the inverse of $f$ at the points you are asking about – graydad Dec 6 '14 at 20:39

How about $n \mapsto (\lceil{n \over 2}\rceil, n \mod 2)$

• what be $f^{-1}(n,0)$ and $f^{-1}(n,1)$? – Leox Dec 6 '14 at 20:04
• I'm not sure if it satisfy all requirements, if $0 \in \mathbb{N}$. – Tacet Dec 6 '14 at 20:24
• @Tacet I was supposing that $\mathbb{N} = \{1,2,3,\dots\}$ – Zereges Dec 7 '14 at 0:16
• @Leox $f^{-1}(n,0) = 2n$ and $f^{-1}(n,1) = 2n -1$ – Zereges Dec 7 '14 at 0:19

Here's a general "solution". Let $S,T \subset N$ be any two infinite, disjoint subsets of the natural numbers. Then there are bijections $f: S \to N$ and $g:S \to N$.

Define $h:N \to N \times \{0,1\}$ as $$h(n) = \begin{cases} (f(n), 0) &\text{if } n \in S \\ (g(n), 1)&\text{otherwise}\end{cases}.$$

It is clear the map is onto. And if $(f(n),0) = (f(m), 0)$ then $n=m$ and likewise for $(g(n),0) = (g(m), 0)$. So it is one-to-one as well. In most of the answer already given, $T$ was taken to be the even integers, $S$ the odd integers, and the bijections $f(n)=n/2$ and $g(n) = (n-1)/2$ where chosen.

Define $f:\mathbb{N} \times \{0, 1\}\to\mathbb{N}$ as $f(x,y)=2x+y$ and use $f^{-1}$.

You have to split natural numbers into two groups. You can use to it for example fact, that function sinus is periodic.

$$\left(\forall k \in \mathbb{Z}\right) \left(\sin(k\Pi) = 0 \wedge \left|\sin\left(k\cdot\frac{\Pi}{2}\right)\right| = 1\right)$$

You should also care about all firs element of pair. Look, from the foregoing $n-\sin(n\cdot\frac{\Pi}{2})$ is the biggest even number, not-greater than $n$. So your function for example could looks like below.

$$f(n) = \left(\frac{n-\sin(n\cdot \frac{\Pi}{2})}{2};\sin^2(n\cdot\frac{\Pi}{2})\right)$$

• what be $f^{-1}(n,0)$ and $f^{-1}(n,1)$? – Leox Dec 6 '14 at 20:09
• @Leox Here exists a lot of functions. Same as for function from mookid answer will work too. But using similar notation for example: $$f^{-1}(x,y) = 2x + \sin(y\cdot\frac{\Pi}{2})$$ – Tacet Dec 6 '14 at 20:16

You can use this kind of Cantor diagonalization counting scheme:

(k,0):  0   1   2   3   4 ..
|  /|  /|  /|  /|  ^
v / v / v / v / v /
(k,1):  0   1   2   3   4 ..


$$\mathbb{N}\times\{0,1\}\to \mathbb{N}: (k, b) \mapsto 2 k + b \\ \mathbb{N}\to\mathbb{N}\times\{0,1\}: n \mapsto \left(\lfloor n / 2 \rfloor, n - 2 \lfloor n / 2 \rfloor \right)$$

Or this one

(k,0):  0   1   2   3   4 ..
^ \ ^ \ ^ \ ^ \ ^ \
|  \|  \|  \|  \|  v
(k,1):  0   1   2   3   4 ..


$$\mathbb{N}\times\{0,1\}\to \mathbb{N}: (k, b) \mapsto 2 k + 1 - b \\ \mathbb{N}\to\mathbb{N}\times\{0,1\}: n \mapsto \left(\lfloor n / 2 \rfloor, 1 - n + 2 \lfloor n / 2 \rfloor \right)$$

Note: $0 \in \mathbb{N}$ assumed