¿Existe alguna forma de dar una función inyectiva desde el conjunto de todas las secuencias naturales finitas a $\mathbb{N}$ sin depender de los números primos?

Question

Estoy tratando de demostrar que $|\bigcup_{k\in\mathbb{N}}\mathbb{N}^k|=|\mathbb{N}|$ . Tengo una idea, pero para que funcione, debo definir, de forma bastante convincente, una función $$G\colon\bigcup_{k\in\mathbb{N}}\mathbb{N}^k\to\mathbb{N}$$ que, según lo que he encontrado que se necesita, debe ser inyectiva entre (probablemente) otras cosas. El problema aquí es que por más que lo intento, no se me ocurre nada de cómo hacerlo sin depender de números primos.

Dicho esto, me gustaría saber si es posible definir una función inyectiva (por no hablar de todas las demás propiedades que seguramente necesito) sin utilizar números primos.

Tenga en cuenta que no estoy buscando una respuesta completa, tal vez sólo una pista si es realmente el caso.

Gracias de antemano.

Answer 1

Contrariamente a mi práctica habitual, interpretaré $\Bbb N$ como $\Bbb Z^+$ como el conjunto de enteros positivos, en lugar de como el conjunto de enteros no negativos, ya que facilita un poco las cosas. Sólo por diversión, aquí está una biyección real de $\bigcup_{k\ge 1}\Bbb N^k$ a $\Bbb N$ que sólo utiliza un resultado combinatorio elemental.

Es un hecho estándar y es fácil demostrar que hay exactamente $\binom{n-1}{k-1}$ pedido $k$ -tuplas de números enteros positivos cuya suma es $n$ . De ello se deduce que existen $\sum_{k=1}^n\binom{n-1}{k-1}=\sum_{k=0}^{n-1}\binom{n-1}k=2^{n-1}$ secuencias finitas de números enteros positivos que suman $n$ ya que cualquier secuencia de este tipo es una $k$ -para algunos $k\le n$ . Para $n\in\Bbb N$ deje $S_n$ el conjunto de secuencias finitas de números enteros positivos cuya suma es $n$ Entonces $\left|\bigcup_{k=1}^{n-1}S_k\right|=\sum_{k=0}^{n-2}2^k=2^{n-1}-1$ intentemos definir una biyección entre $S_n$ y $[2^{n-1},2^n-1]$ . (Todos los intervalos están tomados en $\Bbb Z$ .)

Una posibilidad natural es pedir $S_n$ lexicográficamente y que $\varphi_n:S_n\to[2^{n-1},2^n-1]$ sea el único isomorfismo de orden; $\varphi=\bigcup_{n\in\Bbb Z^+}\varphi_n$ es entonces una biyección desde $\bigcup_{k\ge 1}\Bbb N^k$ a $\Bbb N$ . Esto está claramente bien definido, pero en realidad cuesta un poco de trabajo exponer las funciones $\varphi_n$ . En lugar de limitarme a presentar el resultado y luego justificarlo, creo que será más claro si lo planteo de forma más parecida a como lo hice al pensar en el problema.

En $S_n$ hay $2^{n-2}$ secuencias que empiezan por $1$ , $2^{n-3}$ que empiezan por $2$ y así sucesivamente hasta $2^0$ que empiezan por $n-1$ y luego está el $1$ -secuencia de términos $\langle n\rangle$ . Esto se debe a que cuando el primer término de una secuencia en $S_n$ es $d$ o bien $d=n$ y no hay más términos, o el resto de la secuencia es cualquiera de los $2^{n-d-1}$ miembros de $S_{n-d}$ . Una secuencia en $S_n$ que comienza con $d>1$ por lo tanto tiene al menos $\sum_{k=1}^{d-1}2^{n-1-k}=\sum_{k=n-d}^{n-2}2^k=2^{n-1}-2^{n-d}$ predecesores en $S_n$ y la expresión final es evidentemente válida también para $d=1$ .

El mismo razonamiento muestra que una secuencia en $S_n$ que comienza $\langle d_1,d_2\rangle$ tiene al menos

$$(2^{n-1}-2^{n-d_1})+(2^{n-d_1-1}-2^{n-d_1-d_2})=2^{n-1}-2^{n-d_1-1}-2^{n-d_1-d_2}$$

predecesores en $S_n$ . Uno que comienza $\langle d_1,d_2,d_3\rangle$ tiene al menos

$$\begin{align*} &\;\;\;\;\;2^{n-1}-2^{n-d_1-1}-2^{n-d_1-d_2}+2^{n-d_1-d_2-1}-2^{n-d_1-d_2-d_3}\\ &=2^{n-1}-2^{n-d_1-1}-2^{n-d_1-d_2-1}-2^{n-d_1-d_2-d_3} \end{align*}$$

predecesores en $S_n$ . Y en general $\langle d_1,d_2,\ldots,d_k\rangle\in S_n$ tiene exactamente

$$\begin{align*} &\;\;\;\;\;2^{n-1}-2^{n-1-d_1}-2^{n-d_1-d_2-1}-\ldots-2^{n-d_1-d_2-\ldots-d_{k-1}-1}-2^{n-d_1-d_2-\ldots-d_k}\\ &=2^{n-1}-2^{n-1-d_1}-2^{n-d_1-d_2-1}-\ldots-2^{n-d_1-d_2-\ldots-d_{k-1}-1}-1\\ &=2^{n-1}-1-\frac12\sum_{i=1}^{k-1}2^{n-\sum_{j=1}^id_j}\\ &=2^{n-1}-1-\frac12\sum_{i=2}^k2^{\sum_{j=i}^kd_j}\tag{1} \end{align*}$$

predecesores en $S_n$ . Como una comprobación rápida y sucia, $(1)$ dice que la secuencia $\langle n\rangle$ debería haber $2^{n-1}-1$ predecesores en $S_n$ mientras que la secuencia de $n$ no deberían tener ninguna, como de hecho es el caso.

Ahora podemos escribir $\varphi$ : si $\sigma=\langle d_1,d_2,\ldots,d_k\rangle$ es una sucesión finita de números enteros positivos cuya suma es $n$ entonces

$$\begin{align*} \varphi(\sigma)&=2^{n-1}-1-\frac12\sum_{i=2}^k2^{\sum_{j=i}^kd_j}\\ &=2^{n-1}-1-\frac12\sum_{i=2}^k2^{\sum_{j=i}^kd_j}\;. \end{align*}$$

Por supuesto, se entiende que el sumatorio final es $0$ cuando $k=1$ .

Answer 2

Me gusta $$(n_1,\ldots,n_k)\mapsto 2^{n_1}+2^{n_1+n_2}+\cdots+2^{n_1+n_2+\cdots+n_k}.$$ Pero esto utiliza el número primo $2$ .