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?
 A: Consider $$
f(n) = \begin{cases}
(\frac n2, 0) &\text{if } 2|n
\\
(\frac{n-1}2, 1)&\text{otherwise}\end{cases}
$$
A: 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)
A: 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$
A: 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.
A: How about $n \mapsto (\lceil{n \over 2}\rceil, n \mod 2)$
A: 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.
A: 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)$$
A: 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
A: Define $f:\mathbb{N} \times \{0, 1\}\to\mathbb{N}$ as $f(x,y)=2x+y$ and use $f^{-1}$.
