inyección $(\mathbb{N}\to\{0,1,2\})\to\ (\mathbb{N}\to\{0,1\})$

Question

También es posible encontrar una suryección en la otra dirección - estoy intentando demostrar la cardinalidad de $$\mathbb{N}\to\{0,1,2\}$$ es menor o igual que $$\mathbb{N}\to\{0,1\}$$

Answer 1

Pista: Escriba una función $\mathbb{N}\to\{0,1,2\}$ como una cadena de dígitos $0,1,2$ . Ahora codifica esta cadena en binario, mapeando $0 \mapsto 00$ , $1 \mapsto 01$ , $2 \mapsto 10$ . Esto da una función $\mathbb{N}\to\{0,1\}$ a partir de la cual se puede recuperar la función original.

Answer 2

Para una secuencia $f : \mathbb{N} \to \{0, 1, 2\}$ definen una secuencia que asigna los dígitos como $0 \mapsto 1$ , $1 \mapsto 10$ , $2 \mapsto 100$ .

Por ejemplo:

$$(1,2,1,0,2, \ldots ) \mapsto (1,0,1,0,0,1,0,1,1,0,0, \ldots)$$

Este mapa es claramente inyectivo ya que el número de ceros después de cada $1$ determina cuál era el dígito de la secuencia original.

Answer 3

Para $f \colon \mathbb N \to \{0,1,2\}$ y $n \in \mathbb N$ deje $$ f^*(3n) = \begin{cases} 1 & \text{, if } f(n) = 0 \\ 0 & \text{, otherwise} \end{cases} $$ $$ f^*(3n+1) = \begin{cases} 1 & \text{, if } f(n) = 1 \\ 0 & \text{, otherwise} \end{cases} $$ $$ f^*(3n+2) = \begin{cases} 1 & \text{, if } f(n) = 2 \\ 0 & \text{, otherwise} \end{cases} $$ Entonces $$ \pi \colon (\mathbb N \to \{0,1,2\}) \to (\mathbb N \to \{0,1\}), \ f \mapsto f^* $$ es una inyección.

Answer 4

Puede codificar las funciones de $\mathbb N \to \{0, 1, 2\}$ en $\mathbb N \to \{0, 1\}$ como sigue:

dada una función $f : \mathbb N \to \{0, 1, 2\}$ ,

• deje $g(2n) = f(n)$ si $f(n) \in \{0, 1\}$ y $g(2n) = 0$ de lo contrario,
• y que $g(2n+1) = 1$ si $f(n) = 2$ y $g(2n+1) = 0$ de lo contrario.