Una codificación efectiva de $\mathbb N^*$

Question

Problema: Suponga $\Pi:\mathbb N^2\to\mathbb N\setminus\{0\}$ es una primitiva recursiva de codificación de los pares de números, que es también un bijection y $(\forall (x,y)\in\mathbb N^2)(\Pi(x,y)>max(x,y))$.

Deje $\mathbb N^*$ son las palabras sobre el alfabeto de los números naturales y $\epsilon$ ser la palabra vacía. Vamos

$$k:\mathbb N^*\to\mathbb N:$$ $$k(\epsilon)=0$$ $$k(\langle x_1\dots x_n\rangle)=\Pi(x_1,k(\langle x_2\dots x_n\rangle)$$

Mostrar que $k$ es un eficaz codificación de $\mathbb N^*$

Algunos pensamientos: necesito mostrar que $k$ es un bijection y que su longitud de miembros y funciones son primitivas recursivas. Puedo mostrar que $k$ es inyectiva en el mío propio. ¿Cómo puedo demostrar que $k$ es surjective? He intentado utilizar de curso por los valores de inducción sobre la longitud de la palabra, pero fracasó. Además, ¿cómo puedo demostrar que la longitud de la función es primitiva recursiva? Teniendo lo anterior, puedo demostrar que las funciones miembro son primitivas recursivas.

p.s. Esto es parte del problema. Estoy trabajando con un determinado $\Pi$, que me han demostrado ser una primitiva recursiva de codificación. Por otra parte, el uso de ese $k$ es un eficaz codificación he demostrado que un montón de otras funciones son primitivas recursivas. Para evitar un largo post, sin embargo, he dejado fuera de esos detalles.

Answer 1

Los supuestos en que la pregunta no es suficiente para que su $k$ a de trabajo.

Por ejemplo, si $\Pi(x,y)=\frac{(x+y)(x+y+1)}2+x$ (el Cantor de zigzag, bastante estándar de elección de la vinculación de la función), a continuación, $\Pi(0,0)=0$ y por lo tanto $$ k(\langle \rangle) = 0 = k(\langle 0 \rangle) = k(\langle0,0\rangle) = \cdots$$

Usted necesita la suposición adicional de que el rango de $\Pi$ es exactamente $\mathbb N\setminus\{0\}$ (como es el caso de la $\Pi$ se dan en los comentarios), $k$ va a un bijection.