La respuesta básica es algo así como Hagen ha dicho. La idea es la siguiente: La exponenciación se entiende como una función definida recursivamente: $y=2^x$ si existe una secuencia $t_0,t_1,\dots,t_x$ tal que
- $t_0=1$ ,
- $t_x=y$ y
- Para todos $n<x$ , $t_{n+1}=2\times t_n$ .
En este sentido, la exponenciación no es única: $y=x!$ se define de forma similar, por ejemplo Ahora se diría que hay una secuencia $z_0,z_1,\dots,z_x$ , de tal manera que
- $z_0=1$ ,
- $z_x=y$ y
- Para todos $n<x$ , $z_{n+1}=(n+1)\times z_n$ .
(Que $t_0=z_0=1$ es una coincidencia. En un caso es porque $2^0=1$ en el otro, porque $0!=1$ .)
Así, para definir una fórmula que diga que $y=2^x$ , te gustaría decir que hay una secuencia $t_0,\dots,t_x$ como en el caso anterior.
El problema, por supuesto, es que en la Aritmética de Peano se habla de números y no de secuencias. Gödel resolvió este problema cuando trabajaba en su demostración del teorema de incompletitud: Explicó cómo codificar secuencias finitas mediante números, utilizando la Teorema del resto chino . Recordemos que este resultado establece que, dados cualesquiera números $n_1,\dots,n_k$ , relativamente primos por parejas, y cualquier número $m_1,\dots,m_k$ Hay un número $x$ que satisface simultáneamente todas las congruencias $$ x\equiv m_i\pmod {n_i} $$ para $1\le i\le k$ .
En particular, teniendo en cuenta $m_1,\dots,m_k$ , dejemos que $n=t!$ donde $t=\max(m_1,\dots,m_k,k)$ . Dejar $n_1=n+1$ , $n_2=2n+1,\dots$ , $n_k=kn+1$ vemos que el $n_i$ son relativamente primos, y podemos encontrar un $x$ que satisface $x\equiv m_i\pmod{n_i}$ para todos $i$ . Podemos decir entonces que el par $\langle x,n\rangle$ códigos la secuencia $(m_1,\dots,m_k)$ . De hecho, teniendo en cuenta $x,n$ es bastante fácil "decodificar" el $m_i$ : Sólo hay que tener en cuenta que $m_i$ es el resto de dividir $x$ por $in+1$ .
En consecuencia, podemos definir $y=2^x$ diciendo que hay un par $\langle a,b\rangle$ que, en el sentido que acabamos de describir, codifica una secuencia $(t_0,t_1,\dots,t_x)$ tal que $t_0=1$ , $t_x=y$ y $t_{n+1}=2t_n$ para todos $n<x$ . (Una vez más, "en el sentido que se acaba de describir" termina significando simplemente que "el resto de dividir $a$ por $ib+1$ es $t_i$ para todos $i\le x$ ". Tenga en cuenta que no estamos requiriendo $b$ para ser el número particular que expusimos arriba usando factoriales).
Por supuesto, hay que demostrar que dos pares cualesquiera que codifiquen dicha secuencia coinciden en el valor de $t_x$ pero esto es fácil de establecer. Y podemos codificar un par por un número usando, por ejemplo, la enumeración de Cantor de $\mathbb N\times\mathbb N$ para que $\langle a,b\rangle$ se codifica como el número $$ c=\frac{(a+b)(a+b+1)}2+b. $$ Se trata de una biyección, y tiene las ventajas adicionales de que es definible y satisface $a,b\le c$ (por lo que viene dado por un limitado fórmula).
Una cuestión que aparece ahora es que necesitamos formalizar la discusión del teorema del resto chino y la subsiguiente codificación en Aritmética de Peano. Esto presenta nuevas dificultades, ya que de nuevo, no podemos (en el lenguaje de la aritmética) hablar de secuencias, y no podemos hablar de factoriales, hasta que no hagamos todo lo anterior, por lo que no está claro cómo demostrar o incluso cómo formular estos resultados.
Este problema puede resolverse observando que podemos utilizar la inducción dentro de la aritmética de Peano. Se procede entonces a demostrar, esencialmente, que dada cualquier secuencia finita, existe un par que la codifica, y que si un par codifica una secuencia $\vec s$ y un número $t$ está dado, entonces hay un par que codifica la secuencia $\vec s{}^\frown(t)$ . Es decir, se puede escribir una fórmula $\phi(x,y,z)$ , " $y$ codifica una secuencia, el $z$ -cuyo miembro número uno es $x$ ", de manera que PA demuestre:
- Para todos $z$ y $y$ hay un único $x$ tal que $\phi(x,y,z)$ .
- Para todos $x$ hay un $y$ tal que $\phi(x,y,0)$ .
- Para todos $x,y,z$ hay un $w$ de manera que el primer $z$ términos de las secuencias codificadas por $y$ y $w$ coinciden, y el siguiente término codificado por $w$ es $x$ .
De hecho, podemos dejar que $\phi$ sea una fórmula acotada: Tomemos $\phi(x,y,z)$ para ser
Hay $a,b\le y$ tal que $y=\langle a,b\rangle$ (el emparejamiento de Cantor) y $x<zb+1$ y hay un $d\le a$ tal que $a=d(zb+1)+x$ .
Una vez que tenemos en AP la existencia de secuencias codificadas como ésta, implementar definiciones recursivas como las funciones exponenciales es sencillo.
Hay dos referencias excelentes para estas cuestiones de codificación y las sutilezas que las rodean:
- Richard Kaye. Modelos de aritmética de Peano . Guías lógicas de Oxford, 15. Publicaciones científicas de Oxford. The Clarendon Press, Oxford University Press, Nueva York, 1991. MR1098499 (92k:03034) . (Véase el capítulo 5.)
- Petr Hájek y Pavel Pudlák. Metamatemática de la aritmética de primer orden . Perspectivas en Lógica Matemática. Springer-Verlag, Berlín, 1993. MR1219738 (94d:03001) . (Véase el capítulo 1.)
