Gödel de la función beta, sin el teorema del resto Chino

Question

Como todos sabemos, Gödel de la función beta explota el teorema del resto Chino para codificar una secuencia finita de productos naturales en una sola naturales. Esto no requiere de una fuerte teoría; puede ser llevado a cabo en, por ejemplo, la teoría de los discretamente ordenó semiring más el $\Sigma_1$ inducción.

Mientras que el CTR es nada difícil, lo que sería útil para la base de la codificación de las cadenas en una aún más trivial de la serie de la teoría de los hechos, ya que habría menos posibilidades de equivocarse al tomar un examen oral o enseñar una clase.

Pregunta: se Puede utilizar aún más fácil de número de la teoría de los hechos para codificar la secuencia finita de productos naturales en una sola naturales? La codificación y decodificación tiene que ser capaz de hacer en la teoría de los discretamente ordenó semiring más el $\Sigma_1$ inducción.

Answer 1

Ver :

• Raymond Smullyan, la Teoría de los sistemas formales (1961), página 78:

nuestra prueba de la siguiente manera novela líneas en que toda apelación a la tradicional teoría de los números dispositivos otorgado en el pasado - por ejemplo, la descomposición en factores primos, congruencias y el teorema del resto Chino - se evitan. Por lo tanto Gödel del programa de establecimiento de la incompletitud, incluso de primer orden teorías que involucran más y a veces como su único aritmética primitivas, puede, por los métodos de esta sección, se llevó a cabo sin apelar a la teoría de números.

Answer 2

¿Qué acerca de la sustitución de la cadena de $a_n \dots a_0$ con el número de $f(a_n \dots a_0)$ cuya representación binaria se obtiene mediante la sustitución de cada una de las $a_i$$a_n \dots a_0$$1$, seguido por $a_i$ ceros? Esto le da bijection creo, con la cadena vacía ser enviado a $0$. La definición de $b_0$ $0$ $b_i$ $\sum_{j = 0}^{i - 1} (a_j + 1)$ otra cosa, creo que le da ese $f(a_n \dots a_0) = \sum_{i = 0}^n 2^{a_i + b_i}$. No sabemos si la codificación y decodificación es lo suficientemente simple para sus necesidades.