5
$\begingroup$

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?

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

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

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

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)

$\endgroup$
5
$\begingroup$

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$

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

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.

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

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

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

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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)$$

$\endgroup$
  • $\begingroup$ what be $f^{-1}(n,0)$ and $f^{-1}(n,1)$? $\endgroup$ – Leox Dec 6 '14 at 20:09
  • 1
    $\begingroup$ @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})$$ $\endgroup$ – Tacet Dec 6 '14 at 20:16
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.