Cómo construir un bijection $\mathbb{N} \to \mathbb{N} \times \{0, 1\}.$

Question

Cómo construir un bijection de $\mathbb{N}$ $\mathbb{N} \times \{0, 1\}?$ Mi primera idea fue la de $n \mapsto (n, n \mod 2)$, pero está mal. Cualquier sugerencia?

Answer 1

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

Answer 2

SUGERENCIA: Recordar que $\Bbb N\times\{0,1\}=(\Bbb N\times\{0\})\cup(\Bbb N\times\{1\})$. ¿Qué otras contables pueden ser, naturalmente, el pensamiento como la inconexión de la unión de dos copias de $\Bbb N$, y ¿cómo se puede definir un bijection en ese caso? (También está escrito con una Pizarra en Negrita en muchos lugares)

Answer 3

Sugerencia:

• Tomar el binario de expansión $b_nb_{n-1}\ldots{}b_2b_1b_0$, y reinterpretar el último bit, es decir, interpretar el número entero como par $\langle b_nb_{n-1}\ldots{}b_2b_1, b_0\rangle$.

Espero que te ayude a $\ddot\smile$

Answer 4

Este problema es más fácil si primero hacer un bijection $g:\Bbb{Z} \to \Bbb{N} \times \{0,1 \}$ donde $$g(n) = \begin{cases} (n+1,0) &\text{if} \space n \geq 0 \\ (-n,1)&\text{if} \space n<0\end{casos}$$ $g$ is defined to work around the fact that $0 \noen \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} \\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 \}$$ es un bijection.

Answer 5

Cómo acerca de $n \mapsto (\lceil{n \over 2}\rceil, n \mod 2)$