Descomposición en primos en la aritmética de Peano.

Question

El lenguaje de la aritmética de Peano de primer orden me parece bastante limitado. Hasta donde yo sé, sólo tiene los símbolos $S, 0, +, \times ,= $ . Ahora el teorema de la factorización única en primos, establece que para cada $n$ número natural, existe una única secuencia creciente finita de primos $(p_k)_{k \leq m}$ , de tal manera que $n=p_0 \times \cdots \times p_m$ pero como este lenguaje no tiene una noción inherente de secuencia, no sé cómo se puede escribir este teorema en este lenguaje.

¿Hay alguna forma sencilla de solucionar este problema? Me gustaría señalar que no estoy muy familiarizado con la lógica y que soy principalmente autodidacta.

Answer 1

Aunque PA no tiene una noción incorporada de secuencias finitas, podemos hablar de secuencias finitas en PA. (Y esto significa que hablar, por ejemplo, de la factorización de primos se puede hacer fácilmente en PA).

Esto es fácil de ver si consideramos la PA aumentada por la exponenciación: entonces podemos codificar cualquier secuencia $\langle a_1, ..., a_n\rangle$ por el número $2^{a_1+1}3^{a_2+1}...p_n^{a_n+1}$ (piense en por qué necesitamos el " $+1$ "). Los hechos básicos sobre las secuencias pueden entonces expresarse y manejarse adecuadamente.

En la propia PA, esto es un poco más complicado, pero todavía se puede hacer usando un aplicación inteligente del teorema del resto chino , descubierto por Godel.

Answer 2

Sí.

Se puede codificar fácilmente la noción de secuencia finita en los números naturales con el lenguaje de la aritmética. Hay muchas formas, por ejemplo la de Godel $\beta$ o utilizando potencias primarias.

Pero la idea es que se puede codificar de forma única cada secuencia finita de números naturales como otro número natural. Y puedes hacerlo de forma recursiva (incluso recursiva primitiva), de modo que el proceso de decodificación de la longitud y las coordenadas también son recursivos (e incluso recursivos primitivos).

Entonces, la descomposición de los primos resulta fácil de enunciar.