7.14 Teorema de incompletitud

Sea \[Verd_{\mathbf{\omega}}=\{\varphi\in S^{\tau_{A}}:\mathbf{\omega}\models\varphi\}.\] Notese que por el teorema de correccion tenemos que todo teorema de \(Arit\) pertenece a \(Verd_{\mathbf{\omega}}\). Como puede notarse a medida que uno se va familiarizando con la teoria \(Arit\), todos los resultados clasicos de la aritmetica los cuales pueden ser enunciados por medio de una sentencia de \(Verd_{\mathbf{\omega}}\) son en realidad teoremas de \(Arit\). Sin envargo Godel probo en su famoso teorema de incompletitud (1931) que hay una sentencia de \(Verd_{\mathbf{\omega}}\) la cual no es un teorema de \(Arit\). Por años nadie fue capaz de dar una sentencia de \(Verd_{\mathbf{\omega}}\) la cual tenga un genuino interes aritmetico y la cual no sea un teorema de \(Arit\). Recien en 1977 Paris y Harrington dieron el primer ejemplo de una tal sentencia. Una ves sabido que los axiomas de \(Arit\) no son suficientemente poderosos como para probar toda sentencia verdadera en \(\mathbf{\omega}\), una pregunta interesante es

1. adhocprefix-adhocsufix Hay un conjunto "razonable" de axiomas \(\Gamma\subseteq Verd_{\mathbf{\omega}}\) tal que toda sentencia de \(Verd_{\mathbf{\omega}}\) es un teorema de \((\Gamma,\tau_{A})\)

Una respuesta negativa a este problema tambien es dada por el teorema de incompletitud de Godel. En esta seccion daremos una prueba basada en las ideas de la computabilidad.

7.14.1 Analisis de recursividad del lenguaje de primer orden

En esta seccion estudiaremos la recursividad de la sintaxis de \(\tau_{A}\). Los resultados obtenidos valen para un tipo cualquiera y hemos elejido a \(\tau_{A}\) solo para facilitar la exposicion.

Analizaremos la recursividad del concepto de prueba formal en una teoria de la forma \((\Sigma,\tau_{A})\), donde \(\Sigma\) es un conjunto recursivamente enumerable. Para hacer mas concreto el tratamiento supondremos que los nombres de constante auxiliares en las pruebas formales estaran siempre en el conjunto \[Aux=\{\triangle\Box\triangle,\triangle\Box\Box\triangle,\triangle\Box\Box\Box\triangle,...\}\] Esto no afectara nuestro analisis ya que es claro que toda prueba formal de una teoria de la forma \((\Sigma,\tau_{A})\) puede ser reemplazada por una que sus nombres de constante auxiliares esten en \(Aux\). Es decir que las sentencias involucradas en las pruebas formales que consideraremos seran sentencias de tipo \(\tau_{A}^{e}\) donde \[\tau_{A}^{e}=(\{0,1\}\cup Aux,\{+^{2},.^{2}\},\{\leq^{2}\},a)\] Sea \(\mathcal{A}\) el alfabeto formado por los siguientes simbolos \[\forall\ \ \exists\ \ \lnot\ \ \vee\ \ \wedge\ \ \rightarrow\ \ \leftrightarrow\ \ (\ \ )\ \ ,\ \ \equiv\ \ 0\ \ 1\ \ +\ \ .\ \ \leq\ \ \triangle\ \ \Box\ \ \mathsf{X}\ \ \mathit{0}\ \ \mathit{1}\ \ ...\ \ \mathit{9}\ \ \mathbf{0}\ \ \mathbf{1}\ \ ...\ \ \mathbf{9}\] Notese que los simbolos del alfabeto \(\mathcal{A}\) son justamente los simbolos que ocurren en las formulas y terminos de tipo \(\tau_{A}^{e}\), es decir que \(T^{\tau_{A}^{e}}\) y \(F^{\tau_{A}^{e}}\) son conjuntos \(\mathcal{A}\)-mixtos. Mas aun tenemos:

Proof. Notese que los conjuntos \(T^{\tau_{A}^{e}}\), \(F^{\tau_{A}^{e}}\), \(T^{\tau_{A}}\) y \(F^{\tau_{A}}\) son \(\mathcal{A}\)-efectivamente computables (justifique). Entonces la Tesis de Church nos garantiza que dichos conjuntos son \(\mathcal{A}\)-recursivos.

A continuacion daremos una prueba de que dichos conjuntos son en realidad \(\mathcal{A}\)-recursivos primitivos. Veamos por ejemplo que \(T^{\tau_{A}^{e}}\) es \(\mathcal{A}\)-recursivo primitivo. Fijemos un orden total \(\leq\) sobre \(\mathcal{A}\). Sea \(P=\lambda x[\ast^{\leq}(x)\in T^{\tau_{A}^{e}}]\). Notese que \(P(0)=0\) y \(P(x+1)=1\) si y solo si se da alguna de las siguientes

1. adhocprefix-adhocsufix \(\ast^{\leq}(x+1)\in\{0,1\}\cup Aux\)

2. adhocprefix-adhocsufix \((\exists u,v\in\omega)\ast^{\leq}(x+1)=+(\ast^{\leq}(u),\ast^{\leq}(v))\wedge(P^{\downarrow}(x))_{u+1}\wedge(P^{\downarrow}(x))_{v+1}\)

3. adhocprefix-adhocsufix \((\exists u,v\in\omega)\ast^{\leq}(x+1)=\mathrm{.}(\ast^{\leq}(u),\ast^{\leq}(v))\wedge(P^{\downarrow}(x))_{u+1}\wedge(P^{\downarrow}(x))_{v+1}\)

Por el Lema 4.36 tenemos que \(P\) es \(\mathcal{A}\)-p.r., por lo cual \(\chi_{T^{\tau_{A}^{e}}}^{\mathcal{A}^{\ast}}=P\circ\#^{\leq}\) lo es. Notese que \[t\in T^{\tau_{A}}\text{ sii }t\in T^{\tau_{A}^{e}}\wedge\triangle\text{ no ocurre en }t\wedge\Box\text{ no ocurre en }t\] por lo cual \(T^{\tau_{A}}\) es \(\mathcal{A}\)-p.r.  

Recordemos que en la Subseccion [VariablesLibres] definimos cuando \("v\mathit{\ ocurre\ libremente\ en\ }\varphi\mathit{\ a\ partir\ de\ }i"\), para el caso en que \(v\in Var\), \(\varphi\in F^{\tau}\) y \(i\in\{1,...,\left\vert \varphi\right\vert \}\). Extendamos esta definicion diciendo que cuando \(v\in Var\), \(\varphi\in F^{\tau}\) y \(i\in\omega-\{1,...,\left\vert \varphi\right\vert \}\), se da que \(v\mathit{\ no\ ocurre\ libremente\ en\ }\varphi\mathit{\ a\ partir\ de\ }i\).

Proof. Notese que los predicados dados en (1), (2) y (3) son \(\mathcal{A}\)-efectivamente computables (justifique). Entonces la Tesis de Church nos garantiza que dichos predicados son \(\mathcal{A}\)-recursivos.

En realidad dichos predicados son \(\mathcal{A}\)-p.r.. Veamos por ejemplo que \(P:\omega\times Var\times F^{\tau_{A}^{e}}\rightarrow\omega\), dado por \[P(i,v,\varphi)=\left\{ \begin{array}{ccl} 1 & & \text{si }v\mathit{\ }\text{ocurre libremente en}\mathit{\ }\varphi\text{ a partir de }i\\ 0 & & \text{caso contrario} \end{array}\right.\] es \(\mathcal{A}\)-p.r.. Sea \(R:\mathbf{N}\times Var\rightarrow\omega\) el predicado dado por \(R(x,v)=1\) si y solo si \(\ast^{\leq}((x)_{1})\in F^{\tau_{A}^{e}}\) y \(v\mathit{\ }\)ocurre libremente en\(\mathit{\ }\ast^{\leq}((x)_{1})\) a partir de \((x)_{2}\). Sea \(\bar{R}=R\cup C_{0}^{1,1}|_{\{0\}\times Var}\). \(\mathrm{Nex}=\{\wedge,\vee,\rightarrow,\leftrightarrow\}\). Notese que \(F_{0}^{\tau_{A}^{e}}\) es \(\mathcal{A}\)-p.r. ya que \[F_{0}^{\tau_{A}^{e}}=F^{\tau_{A}^{e}}\cap(\mathcal{A}-\{\forall,\exists,\lnot,\vee,\wedge,\rightarrow,\leftrightarrow\})^{\ast}\] Notese que \(\bar{R}(0,v)=0\), para cada \(v\in Var\) y que \(\bar{R}(x+1,v)=1\) si y solo si \((x+1)_{2}\geq1\) y se da alguna de las siguientes:

1. adhocprefix-adhocsufix \(\ast^{\leq}((x+1)_{1})\in F_{0}^{\tau_{A}^{e}}\wedge v\) ocurre en \(\ast^{\leq}((x+1)_{1})\) a partir de \((x+1)_{2}\)

2. adhocprefix-adhocsufix \((\exists\varphi_{1},\varphi_{2}\in F^{\tau_{A}^{e}})(\exists\eta\in\mathrm{Nex})\ast^{\leq}((x+1)_{1})=(\varphi_{1}\eta\varphi_{2})\wedge\)

   \(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \left((\bar{R}^{\downarrow}(x,v))_{\left\langle \#^{\leq}(\varphi_{1}),(x+1)_{2}-1\right\rangle +1}=1\vee(\bar{R}^{\downarrow}(x,v))_{\left\langle \#^{\leq}(\varphi_{2}),(x+1)_{2}-\left\vert (\varphi_{1}\eta\right\vert \right\rangle +1}=1\right)\)

3. adhocprefix-adhocsufix \((\exists\varphi_{1}\in F^{\tau_{A}^{e}})\ast^{\leq}((x+1)_{1})=\lnot\varphi_{1}\wedge(\bar{R}^{\downarrow}(x,v))_{\left\langle \#^{\leq}(\varphi_{1}),(x+1)_{2}-1\right\rangle +1}=1\)

4. adhocprefix-adhocsufix \((\exists\varphi_{1}\in F^{\tau_{A}^{e}})(\exists w\in Var)(Q\in\{\forall,\exists\})\;w\neq v\wedge\)

   \(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ast^{\leq}((x+1)_{1})=Qw\varphi_{1}\wedge(\bar{R}^{\downarrow}(x,v))_{\left\langle \#^{\leq}(\varphi_{1}),(x+1)_{2}-\left\vert (Qw\right\vert \right\rangle +1}=1\)

Es decir que por el Lema 4.36 tenemos que \(\bar{R}\) es \(\mathcal{A}\)-p.r.. Notese que para \((i,v,\varphi)\in\omega\times Var\times F^{\tau_{A}^{e}}\), tenemos \(P(i,v,\varphi)=\bar{R}(\left\langle \#^{\leq}(\varphi),i\right\rangle ,v)\). Ahora es facil obtener la funcion \(P\) haciendo composiciones adecuadas con \(\bar{R}\).  

Dados \(v\in Var\) y \(t,s\in T^{\tau_{A}^{e}}\), usaremos \(\downarrow_{v}^{t}(s)\) para denotar el resultado de reemplazar simultaneamente cada ocurrencia de \(v\) en \(s\) por \(t\). Similarmente, si \(\varphi\in F^{\tau_{A}^{e}}\), usaremos \(\downarrow_{v}^{t}(\varphi)\) para denotar el resultado de reemplazar simultaneamente cada ocurrencia libre de \(v\) en \(\varphi\) por \(t\).

Proof. Notese que las funciones \(\lambda svt[\downarrow_{v}^{t}(s)]\) y \(\lambda\varphi vt[\downarrow_{v}^{t}(\varphi)]\) son \(\mathcal{A}\)-efectivamente computables (justifique). Entonces la Tesis de Church nos garantiza que dichas funciones son \(\mathcal{A}\)-recursivas.

En realidad son \(\mathcal{A}\)-p.r.. Veamos por ejemplo que \(\lambda svt[\downarrow_{v}^{t}(s)]\) es \(\mathcal{A}\)-p.r.. Sea \(\leq\) un orden total sobre \(\mathcal{A}\). Sea \(h:\omega\times Var\times T^{\tau_{A}^{e}}\rightarrow\omega\) dada por \[h(x,v,t)=\left\{ \begin{array}{ccc} \#^{\leq}(\downarrow_{v}^{t}(\ast^{\leq}(x))) & & \text{si }\ast^{\leq}(x)\in T^{\tau_{A}^{e}}\\ 0 & & \text{caso contrario} \end{array}\right.\] Sea \(P:\mathbf{N}\times\omega\times Var\times T^{\tau_{A}^{e}}\times\mathcal{A}^{\ast}\rightarrow\omega\) tal que \(P(A,x,v,t,\alpha)=1\) si y solo si se da alguna de las siguientes

1. adhocprefix-adhocsufix \(\ast^{\leq}(x+1)\notin T^{\tau_{A}^{e}}\wedge\alpha=\varepsilon\)

2. adhocprefix-adhocsufix \(\ast^{\leq}(x+1)=v\wedge\alpha=t\)

3. adhocprefix-adhocsufix \(\ast^{\leq}(x+1)\in(\{0,1\}\cup Aux)-\{v\}\wedge\alpha=\ast^{\leq}(x+1)\)

4. adhocprefix-adhocsufix \((\exists r,s\in T^{\tau_{A}^{e}})\ast^{\leq}(x+1)=+(r,s)\wedge\alpha=+(\ast^{\leq}((A)_{\#^{\leq}(r)+1}),\ast^{\leq}((A)_{\#^{\leq}(s)+1}))\)

5. adhocprefix-adhocsufix \((\exists r,s\in T^{\tau_{A}^{e}})\ast^{\leq}(x+1)=\mathrm{.}(r,s)\wedge\alpha=\mathrm{.}(\ast^{\leq}((A)_{\#^{\leq}(r)+1}),\ast^{\leq}((A)_{\#^{\leq}(s)+1}))\)

Sea \(\bar{P}=P\cup C_{0}^{2,2}|_{\{0\}\times\omega\times Var\times T^{\tau_{A}^{e}}\times\mathcal{A}^{\ast}}\). Notese que \(\bar{P}(h^{\downarrow}(x,v,t),x,v,t,\alpha)=1\) si y solo si ya sea \(\ast^{\leq}(x+1)\notin T^{\tau_{A}^{e}}\) y \(\alpha=\varepsilon\) o \(\ast^{\leq}(x+1)\in T^{\tau_{A}^{e}}\) y \(\alpha=\mathrm{\downarrow}_{v}^{t}(\ast^{\leq}(x+1))\). Tenemos entonces \[\begin{aligned} h(0,v,t) & =0\\ h(x+1,v,t) & =\#^{\leq}(\min_{\alpha}^{\leq}\bar{P}(h^{\downarrow}(x,v,t),x,v,t,\alpha)), \end{aligned}\] por lo cual el Lema 4.36 nos dice que \(h\) es \(\mathcal{A}\)-p.r. Ahora es facil obtener la funcion \(\lambda svt[\downarrow_{v}^{t}(s)]:T^{\tau_{A}^{e}}\times Var\times T^{\tau_{A}^{e}}\rightarrow T^{\tau_{A}^{e}}\) haciendo composiciones adecuadas con \(h\).  

Proof. Notese que el predicado \(R\) es \(\mathcal{A}\)-efectivamente computable. Entonces la Tesis de Church nos garantiza que \(R\) es \(\mathcal{A}\)-recursivo.

En realidad \(R\) es \(\mathcal{A}\)-p.r. y esto puede verse facilmente ya que \(R(\alpha,\beta,\gamma,\zeta)=1\) sii existen \(\alpha_{1},\alpha_{2}\) tales que \(\alpha=\alpha_{1}\gamma\alpha_{2}\) y \(\beta=\alpha_{1}\zeta\alpha_{2}\).  

Proof. Dejamos al lector una prueba via la Tesis de Church. En realidad dichos conjuntos son \(\mathcal{A}\)-p.r.. Veremos, por ejemplo que \(Reem^{\tau_{A}^{e}}\) es \(\mathcal{A}\)-p.r.. Basta con ver que \(Reem1^{\tau_{A}^{e}}\) y \(Reem2^{\tau_{A}^{e}}\) lo son. Veremos que \(Reem2^{\tau_{A}^{e}}\) es \(\mathcal{A}\)-p.r.. Sea \(Q:F^{\tau_{A}^{e}}\times F^{\tau_{A}^{e}}\times F^{\tau_{A}^{e}}\rightarrow\omega\) el predicado tal que \(Q(\psi,\varphi,\sigma)=1\) si y solo si

1. adhocprefix adhocsufix \((\exists\alpha\in(\forall Var)^{\ast})(\exists\psi_{1},\psi_{2}\in F^{\tau_{A}^{e}})\ \psi=\alpha(\psi_{1}\leftrightarrow\psi_{2})\wedge\)

2. adhocprefix adhocsufix \(\ \ \ \ \ Li(\psi_{1})=Li(\psi_{2})\wedge\left((\forall v\in Var)\ v\notin Li(\psi_{1})\vee v\text{ ocurre en }\alpha\right)\)

3. adhocprefix adhocsufix           \(\left((\forall v\in Var)\ v\text{ no ocurre en }\alpha\vee v\in Li(\psi_{1})\right)\wedge R(\varphi,\sigma,\psi_{1},\psi_{2})\)

(\(R\) es el predicado dado por el Lema 7.58). Es facil ver que \(Q\) es \(\mathcal{A}\)-p.r. y que \(\chi_{Reem2^{\tau_{A}^{e}}}^{\mathcal{A}^{4}}=Q|_{S^{\tau_{A}^{e}}\times S^{\tau_{A}^{e}}\times S^{\tau_{A}^{e}}}\).  

Proof. Es claro que el predicado en cuestion es \(\mathcal{A}\)-efectivamente computable (justifique). Por la Tesis de Church tenemos entonces que dicho predicado es \(\mathcal{A}\)-r.

Para probar que en realidad dicho predicado es \(\mathcal{A}\)-p.r., notese que: \(\psi\) se deduce de \(\varphi\) por generalizacion con constante \(c\) si y solo si hay una formula \(\gamma\) y una variable \(v\) tales que

1. adhocprefix-adhocsufix \(Li(\gamma)=\{v\}\)

2. adhocprefix-adhocsufix \(c\) no ocurre en \(\gamma\)

3. adhocprefix-adhocsufix \(\varphi=\mathrm{\downarrow}_{v}^{c}(\gamma)\wedge\psi=\forall v\gamma\)

Proof. Es claro que el predicado en cuestion es \(\mathcal{A}\)-efectivamente computable (justifique). Por la Tesis de Church tenemos entonces que dicho predicado es \(\mathcal{A}\)-r.

Dejamos al lector probar que en realidad dicho predicado es \(\mathcal{A}\)-p.r.  

Recordemos que \[AxLog^{\tau_{A}^{e}}=\{\varphi\in S^{\tau_{A}^{e}}:\varphi\text{ es un axioma logico de tipo }\tau_{A}^{e}\}\]

Proof. Es claro que el conjunto en cuestion es \(\mathcal{A}\)-efectivamente computable (justifique). Por la Tesis de Church tenemos entonces que dicho conjunto es \(\mathcal{A}\)-r.

Dejamos al lector probar que en realidad dicho conjunto es \(\mathcal{A}\)-p.r. La prueba es completamente analoga a la prueba de que \(\mathrm{Ins}^{\Sigma}\) es un conjunto \((\Sigma\cup\Sigma_{p})\)-p.r. (Lema [Ins-es-pr])

Proof. Ya que \(S\) es \(\Sigma\)-r., tenemos que \(S\) es \(\Sigma\)-efectivamente computable. Es facil ver que entonces \(S^{+}\) es \(\Sigma\)-efectivamente computable. Por la Tesis de Church tenemos entonces que \(S\) es \(\Sigma\)-recursivo.

Ya que \(\alpha\in S^{+}\) si y solo si \[(\exists z\in\mathbf{N})(\forall i\in\mathbf{N})_{i\leq Lt(z)}\ast^{\leq}((z)_{i})\in S\wedge\alpha=\mathrm{\subset}_{i=1}^{Lt(z)}\ast^{\leq}((z)_{i})\] se puede probar tambien este lema sin usar la Tesis de Church. Dejamos al lector los detalles.  

Recordemos que dada \(\boldsymbol{\varphi}\in S^{\tau_{A}^{e}+}\), usamos \(n(\boldsymbol{\varphi})\) y \(\boldsymbol{\varphi}_{1},...,\boldsymbol{\varphi}_{n(\boldsymbol{\varphi})}\) para denotar los unicos \(n\) y \(\varphi_{1},...,\varphi_{n}\) tales que \(\boldsymbol{\varphi}=\varphi_{1}...\varphi_{n}\) (la unicidad es garantizada en Lema 7.33). Extendamos esta notacion definiendo \(\boldsymbol{\varphi}_{i}=\varepsilon\) para \(i=0\) o \(i>n(\boldsymbol{\varphi})\).

Proof. Es claro que la funciones en cuestion son \(\mathcal{A}\)-efectivamente computables (justifique). Por la Tesis de Church tenemos entonces que son \(\mathcal{A}\)-r.

Dejamos al lector probar que en realidad dicho conjunto es \(\mathcal{A}\)-p.r. La prueba es completamente analoga a la prueba de que \(\lambda\mathcal{P}\left[n(\mathcal{P})\right]\) y \(\lambda i\mathcal{P}\left[I_{i}^{\mathcal{P}}\right]\) son funciones \((\Sigma\cup\Sigma_{p})\)-p.r. (Lema 4.45)  

Recordemos que dada \(\mathbf{J}\in Just^{+}\), usamos \(n(\mathbf{J})\) y \(\mathbf{J}_{1},...,\mathbf{J}_{n(\mathbf{J})}\) para denotar los unicos \(n\) y \(J_{1},...,J_{n}\) tales que \(\mathbf{J}=J_{1}...J_{n}\) (la unicidad es garantizada en Lema 7.32). Extendamos esta notacion definiendo \(\mathbf{J}_{i}=\varepsilon\) para \(i=0\) o \(i>n(\mathbf{J})\).

Sea \(\mathcal{B}\) el alfabeto que consiste en todos los simbolos que ocurren en alguna palabra de \(Just\). Es decir \(\mathcal{B}\) consiste de los simbolos \[(\ )\ ,\ 0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ \text{A\ B\ C\ D\ E\ G\ H\ I\ J\ L\ M\ N\ O\ P\ Q\ R\ S\ T\ U\ V\ X Z}\]

Proof. Es claro que la funciones en cuestion son \(\mathcal{B}\)-efectivamente computables (justifique). Por la Tesis de Church tenemos entonces que son \(\mathcal{B}\)-r.  

Proof. Es claro que dicho predicado es \(\mathcal{B}\)-efectivamente computable (justifique). Por la Tesis de Church tenemos entonces que es \(\mathcal{B}\)-r.  

Proof. Es claro que dicho conjunto es \(\mathcal{B}\)-efectivamente computable (justifique). Por la Tesis de Church tenemos entonces que es \(\mathcal{B}\)-r.  

Proof. Es claro que los predicados en cuestion son \((\mathcal{A}\cup\mathcal{B})\)-efectivamente computables (justifique). Por la Tesis de Church tenemos entonces que dichos predicados son \((\mathcal{A}\cup\mathcal{B})\)-r.  

Proof. Es claro que el predicado en cuestion es \((\mathcal{A}\cup\mathcal{B})\)-efectivamente computable (justifique). Por la Tesis de Church tenemos entonces que dicho predicado es \((\mathcal{A}\cup\mathcal{B})\)-r.  

Dada una teoria de la forma \((\Sigma,\tau_{A})\), diremos que una prueba formal \((\boldsymbol{\varphi},\mathbf{J})\) de \(\varphi\) en \((\Sigma,\tau_{A})\) es normal si solo usa nombres de ctes auxiliares de \(Aux\), es decir si \(\boldsymbol{\varphi}\in S^{\tau_{A}^{e}+}\). Definamos \[Pruebas_{(\Sigma,\tau_{A})}=\{(\boldsymbol{\varphi},\mathbf{J}):\exists\varphi\ (\boldsymbol{\varphi},\mathbf{J})\text{ es una prueba normal de }\varphi\text{ en }(\Sigma,\tau_{A})\}\]

Proof. Supongamos que \(\Sigma\) es \(\mathcal{A}\)-r.e.. Claramente entonces \(\Sigma\) es \(\mathcal{A}\)-efectivamente computable por lo cual hay una funcion \(g:\omega\rightarrow\Sigma\) la cual es \(\mathcal{A}\)-efectivamente computable y suryectiva. Sea \(\leq\) un orden total sobre \(\mathcal{A}\cup\mathcal{B}\). A continuacion describimos como hacer un procedimiento efectivo que enumere a \(Pruebas_{(\Sigma,\tau_{A})}\). Dejamos al lector completar los detalles. Dada una prueba formal \((\boldsymbol{\varphi},\mathbf{J})\) cualquiera, definamos \[Ax((\boldsymbol{\varphi},\mathbf{J}))=\{\boldsymbol{\varphi}_{i}:\text{existe }\alpha\text{ tal que }\mathbf{J}_{i}=\alpha\mathrm{AXIOMAPROPIO}\}\]

Etapa 1

Si \(x=0\), detenerse y dar como salida \(((0\equiv0),\mathrm{AXIOMALOGICO})\). En caso contrario ir a Etapa 2

Etapa 2.

Si \((\ast^{\leq}((x)_{1}),\ast^{\leq}((x)_{2}))\) es una prueba formal y \(Ax((\ast^{\leq}((x)_{1}),\ast^{\leq}((x)_{2})))\subseteq\{g(0),...,g((x)_{3})\}\), entonces detenerse y dar como salida \((\ast^{\leq}((x)_{1}),\ast^{\leq}((x)_{2}))\). Caso contrario detenerse y dar como salida \(((0\equiv0),\mathrm{AXIOMALOGICO})\)

Por la Tesis de Church tenemos entonces que \(Pruebas_{(\Sigma,\tau_{A})}\) es \((\mathcal{A}\cup\mathcal{B})\)-r.e.  

Dada una teoria \((\Sigma,\tau_{A})\), definamos \[Teo_{(\Sigma,\tau_{A})}=\{\varphi\in S^{\tau_{A}}:(\Sigma,\tau_{A})\vdash\varphi\}\]

Proof. Como se vio en el lema anterior, tenemos que \(Pruebas_{(\Sigma,\tau_{A})}\) es \((\mathcal{A}\cup\mathcal{B})\)-efectivamente enumerable. Es facil ahora, usando un procedimiento efectivo que enumere a \(Pruebas_{(\Sigma,\tau_{A})}\), diseñar un procedimiento efectivo que enumere a \(Teo_{(\Sigma,\tau_{A})}\). Es decir que \(Teo_{(\Sigma,\tau_{A})}\) es \(\mathcal{A}\)-efectivamente enumerable, lo cual por la Tesis de Church nos dice que es \(\mathcal{A}\)-r.e.

A continuacion daremos una prueba que no usa la Tesis de Church. Ya que \(Pruebas_{(\Sigma,\tau_{A})}\) es \((\mathcal{A}\cup\mathcal{B})\)-r.e. (lema anterior) tenemos que hay una funcion \(F:\omega\rightarrow S^{\tau_{A}^{e}+}\times Just^{+}\) la cual cumple que \(p_{1}^{0,2}\circ F\) y \(p_{2}^{0,2}\circ F\) son \((\mathcal{A}\cup\mathcal{B})\)-r. y ademas \(I_{F}=Pruebas_{(\Sigma,\tau_{A})}\). Sea \[\begin{array}{rcl} g:S^{\tau_{A}^{e}+} & \rightarrow & S^{\tau_{A}^{e}}\\ \boldsymbol{\varphi} & \rightarrow & \boldsymbol{\varphi}_{n(\boldsymbol{\varphi})} \end{array}\] Por lemas anteriores \(g\) es \(\mathcal{A}\)-r.. Notese que \(I_{(g\circ p_{1}^{0,2}\circ F)}=Teo_{(\Sigma,\tau_{A})}\), lo cual dice que \(Teo_{(\Sigma,\tau_{A})}\) es \((\mathcal{A}\cup\mathcal{B})\)-r.e. (Teorema 4.12). Por el teorema de independencia del alfabeto tenemos que \(Teo_{(\Sigma,\tau_{A})}\) es \(\mathcal{A}\)-r.e..  

7.14.2 Funciones representables

Sea \(n\geq1\). Una funcion \(f:D_{f}\subseteq\omega^{n}\rightarrow\omega\) sera llamada representable si hay una formula \(\varphi=_{d}\varphi(v_{1},...,v_{n},v)\in F^{\tau_{A}}\), la cual cumpla \[\mathbf{\omega}\models\varphi\left[k_{1},...,k_{n},k\right]\mathrm{\ si\ y\ solo\ si\ }f(k_{1},...,k_{n})=k\] cualesquiera sean \(k_{1},...,k_{n},k\in\omega\). En tal caso diremos que la formula \(\varphi\) representa a la funcion \(f\), con respecto a la declaracion \(\varphi=_{d}\varphi(v_{1},...,v_{n},v)\). Notese que cuando \((k_{1},...,k_{n})\notin D_{f}\) entonces debera suceder que \(\mathbf{\omega}\nvDash\varphi\left[k_{1},...,k_{n},k\right]\), cualquiera sea \(k\in\omega\). Cabe destacar que una formula \(\varphi\) puede representar a \(f\), con respecto a una declaracion y con respecto a otra declaracion puede no representarla. Por ejemplo la formula \((x_{3}\equiv x_{1}+x_{2})\) representa a la operacion suma con respecto a las declaraciones \(\varphi=_{d}\varphi(x_{1},x_{2},x_{3})\) y \(\varphi=_{d}\varphi(x_{2},x_{1},x_{3})\) pero con respecto a la declaracion \(\varphi=_{d}\varphi(x_{3},x_{2},x_{1})\) no representa a dicha operacion. Para dar otro ejemplo, tomemos \(\varphi=(x_{5}\equiv1)\). Entonces

1. adhocprefix-adhocsufix Con respecto a la declaracion \(\varphi=_{d}\varphi(x_{2},x_{5})\) la formula \(\varphi\) representa a la funcion con dominio \(\omega\) y valor constantemente 1

2. adhocprefix-adhocsufix Con respecto a la declaracion \(\varphi=_{d}\varphi(x_{10},x_{5})\) la formula \(\varphi\) representa a la funcion con dominio \(\omega\) y valor constantemente 1

3. adhocprefix-adhocsufix Con respecto a la declaracion \(\varphi=_{d}\varphi(x_{2},x_{6},x_{5})\) la formula \(\varphi\) representa a la funcion con dominio \(\omega^{2}\) y valor constantemente 1

El concepto de funcion representable sera clave en nuestra prueba del teorema de incompletitud. El resultado clave desde el cual sale facilmente el teorema de incompletitud es la Proposicion 7.6 en la que se prueba que el conjunto \(Verd_{\mathbf{\omega}}\) no es \(\mathcal{A}\)-r.e..Para probar dicha proposicion primero probaremos que toda funcion \(\emptyset\)-recursiva es representable. Aqui es clave una funcion introducida por Godel. Sea \[\beta=\lambda xyi[R(x,y(i+1)+1)]\] donde \[\begin{array}[t]{rll} R:\omega\times\mathbf{N} & \rightarrow & \omega\\ (x,y) & \rightarrow & \text{resto de la division de }x\text{ por }y \end{array}\] Notese que \(D_{\beta}=\omega^{3}\). Esta funcion, conocida como la funcion \(\beta\) de Godel, es representable ya que por ejemplo la formula \[\varphi=\exists x_{5}\;(x_{1}\equiv x_{5}.(x_{2}.(x_{3}+1)+1)+x_{4}\wedge x_{4}<x_{2}.(x_{3}+1)+1)\] la representa, con respecto a la declaracion \(\varphi=_{d}\varphi(x_{1},x_{2},x_{3},x_{4})\). Ahora veremos un lema que muestra que la funcion \(\beta\) tiene una propiedad sorprendente en el sentido de que cualquier sucesion finita de elementos de \(\omega\) es producida por \(\beta\) si fijamos adecuadamente sus dos primeras entradas. Dados \(x,y\in\omega\), diremos que \(x\) e \(y\) son coprimos cuando \(1\) sea el unico elemento de \(\omega\) que divide a ambos. Notese que \(x\) e \(y\) no son son coprimos sii existe un numero primo \(p\in\omega\) que los divide a ambos

Proof. Dados \(x,y,m\in\omega\) con \(m\geq1\), usaremos \(x\equiv y(m)\) para expresar que \(x\) es congruente a \(y\) modulo \(m\), es decir para expresar que \(x-y\) es divisible por \(m\). Usaremos en esta prueba el Teorema Chino del Resto:

1. adhocprefix-adhocsufix Dados \(m_{0},...,m_{n},z_{0},...,z_{n}\in\omega\) tales que \(m_{0},...,m_{n}\) son coprimos de a pares, hay un \(x\in\omega\) tal que \(x\equiv z_{i}(m_{i})\), para \(i=0,...,n.\)

Sea \(y=\max(z_{0},...,z_{n},n)!\). Sean \(m_{i}=y(i+1)+1\), \(i=0,...,n\). Veamos que \(m_{0},...,m_{n}\) son coprimos de a pares. Supongamos \(p\) divide a \(m_{i}\) y a \(m_{j}\) con \(i<j\). Entonces \(p\) divide a \(m_{j}-m_{i}=y(j-i)\) y ya que \(p\) no puede dividir a \(y\), tenemos que \(p\) divide a \(j-i\). Pero ya que \(j-i<n\) tenemos que \(p<n\) lo cual es absurdo ya que implicaria que \(p\) divide \(y\).

Por el Teorema Chino del Resto hay un \(x\) tal que \(x\equiv z_{i}(m_{i})\), para \(i=0,...,n\). Ya que \(z_{i}<m_{i}\), tenemos que \[\beta(x,y,i)=R(x,y(i+1)+1)=R(x,m_{i})=z_{i}\text{, }i=0,...,n\text{.}\]  

El lema anterior nos permite probar:

Proof. Supongamos \(f:S_{1}\times...\times S_{n}\rightarrow\omega\) y \(g:\omega\times\omega\times S_{1}\times...\times S_{n}\rightarrow\omega\) son representables, con \(S_{1},...,S_{n}\subseteq\omega\) y \(n\geq0\). Probaremos que entonces \(R(f,g):\omega\times S_{1}\times...\times S_{n}\rightarrow\omega\) lo es. Para esto primero notese que para \(t,x_{1},...,x_{n},z\in\omega\), las siguientes son equivalentes

1. adhocprefix(1)adhocsufix \(R(f,g)(t,\vec{x})=z\)

2. adhocprefix(2)adhocsufix Hay \(z_{0},...,z_{t}\in\omega\) tales que \[\begin{aligned} z_{0} & =f(\vec{x})\\ z_{i+1} & =g(z_{i},i,\vec{x})\text{, }i=0,...,t-1\\ z_{t} & =z \end{aligned}\]

3. adhocprefix(3)adhocsufix Hay \(x,y\in\omega\) tales que \[\begin{aligned} \beta(x,y,0) & =f(\vec{x})\\ \beta(x,y,i+1) & =g(\beta(x,y,i),i,\vec{x})\text{, }i=0,...,t-1\\ \beta(x,y,t) & =z \end{aligned}\]

Sean \(\varphi_{\beta}\), \(\varphi_{f}\) y \(\varphi_{g}\) formulas que representen a las funciones \(\beta\), \(f\) y \(g\), con respecto a las declaraciones \[\begin{aligned} \varphi_{\beta} & =_{d}\varphi_{\beta}(x_{1},x_{2},x_{3},x_{4})\\ \varphi_{f} & =_{d}\varphi_{f}(x_{1},...,x_{n},x_{n+1})\\ \varphi_{g} & =_{d}\varphi_{g}(x_{1},...,x_{n+2},x_{n+3}) \end{aligned}\] respectivamente. Sean \(v_{1},...,v_{n+1},v\), \(y_{1},y_{2},y_{3},y_{4},z_{1},z_{2}\) variables todas distintas y tales que cada una de las variebles libres de \(\varphi_{\beta}\), \(\varphi_{f}\) y \(\varphi_{g}\) es sustituible por cada una de las variables \(v_{1},...,v_{n+1},v\), \(y_{1},y_{2},y_{3},y_{4},z_{1},z_{2}\). Sea \(\varphi_{R(f,g)}\) la siguiente formula

1. adhocprefix adhocsufix \(\exists z_{1},z_{2}\;(\exists y_{1}\varphi_{\beta}(z_{1},z_{2},0,y_{1})\wedge\varphi_{f}(v_{2},...,v_{n+1},y_{1}))\wedge\)

2. adhocprefix adhocsufix \(\ \ \ \ \ \ \ \ \ \varphi_{\beta}(z_{1},z_{2},v_{1},v)\wedge\forall y_{2}(y_{2}<v_{1}\rightarrow\exists y_{3},y_{4}\;\varphi_{\beta}(z_{1},z_{2},y_{2}+1,y_{3})\wedge\)

3. adhocprefix adhocsufix \(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \varphi_{\beta}(z_{1},z_{2},y_{2},y_{4})\wedge\varphi_{g}(y_{4},y_{2},v_{2},...,v_{n+1},y_{3}))\)

Es facil usando (3) ver que la formula \(\varphi_{R(f,g)}\) representa a \(R(f,g)\), con respecto a la declaracion \(\varphi_{R(f,g)}=_{d}\varphi_{R(f,g)}(v_{1},...,v_{n+1},v)\).

En forma analoga se puede probar que las reglas de composicion y minimizacion preservan representabilidad por lo cual ya que los elementos de \(\mathrm{R}_{0}^{\emptyset}\) son representables, por induccion tenemos que lo es toda funcion \(\emptyset\)-r.

7.14.3 Prueba del teorema de incompletitud

Nuestra estrategia sera probar que \(Verd_{\mathbf{\omega}}\) no es \(\mathcal{A}\)-r.e., para lo cual necesitamos los siguientes dos lemas. El primero consiste en dar una funcion total numerica la cual codifique al predicado \("\)el programa \(\mathcal{P}\) se detiene luego de \(t\) pasos, partiendo del estado \(((0,0,...),(\mathcal{P},\varepsilon,...))"\).

Proof. Sea \(\Sigma=\Sigma_{p}\). Recordemos que el predicado \[P_{1}=\lambda t\mathcal{P}\left[i^{0,1}(t,\mathcal{P},\mathcal{P})=n(\mathcal{P})+1\right]\] es \(\Sigma_{p}\)-p.r. ya que la funcion \(i^{0,1}\) lo es. Notese que el dominio de \(P_{1}\) es \(\omega\times\mathrm{Pro}^{\Sigma_{p}}\). Por Lema 4.60 tenemos que \[AutoHalt^{\Sigma_{p}}=\lambda\mathcal{P}\left[(\exists t\in\omega)\;P_{1}(t,\mathcal{P})\right]\] no es \(\Sigma_{p}\)-recursivo. Sea \(\leq\) un orden total sobre \(\Sigma_{p}\). Definamos \(P:\omega\times\omega\rightarrow\omega\) de la siguiente manera \[P(t,x)=\left\{ \begin{array}{ccc} P_{1}(t,\ast^{\leq}(x)) & \text{si} & \ast^{\leq}(x)\in\mathrm{Pro}^{\Sigma_{p}}\\ 0 & \text{si} & \ast^{\leq}(x)\notin\mathrm{Pro}^{\Sigma_{p}} \end{array}\right.\] Claramente \(P\) es \(\Sigma_{p}\)-p.r., por lo cual el teorema de independencia del alfabeto nos dice que \(P\) es \(\emptyset\)-p.r.. Sea \(Q=\lambda x\left[(\exists t\in\omega)P(t,x)\right]\). Notese que \[AutoHalt^{\Sigma_{p}}=Q\circ\#^{\leq}\mathrm{|}_{\mathrm{Pro}^{\Sigma_{p}}}\] lo cual dice que \(Q\) no es \(\Sigma_{p}\)-r. ya que de serlo, el predicado \(AutoHalt^{\Sigma_{p}}\) lo seria. Por el teorema de independencia del alfabeto tenemos entonces que \(Q\) no es \(\emptyset\)-recursivo.  

Proof. Dejamos como ejercicio para el lector probar que el predicado \(Q\) del lema anterior es representable, lo cual completa la prueba de este corolario ya que \(Q\) no es \(\emptyset\)-recursivo.  

Recordemos que para \(\alpha\in\Sigma^{\ast}\), definimos \[^{\curvearrowright}\alpha=\left\{ \begin{array}{lll} \left[\alpha\right]_{2}...\left[\alpha\right]_{\left\vert \alpha\right\vert } & \text{si} & \left\vert \alpha\right\vert \geq2\\ \varepsilon & \text{si} & \left\vert \alpha\right\vert \leq1 \end{array}\right.\]

Proof. Supongamos \(Verd_{\mathbf{\omega}}\) es \(\mathcal{A}\)-r. e. Sea \(f:\omega\rightarrow Verd_{\mathbf{\omega}}\) una funcion suryectiva y \(\mathcal{A}\)-r. Sea \(g:S^{\tau_{A}}\rightarrow S^{\tau_{A}}\), dada por \[g(\varphi)=\left\{ \begin{array}{ccc} ^{\curvearrowright}\varphi & \;\; & \text{si }\left[\varphi\right]_{1}=\lnot\\ \lnot\varphi & \;\; & \text{caso contrario} \end{array}\right.\] Notar que \(g\) es \(\mathcal{A}\)-p.r. por lo cual \(g\circ f\) es \(\mathcal{A}\)-r. Ya que \(I_{g\circ f}=S^{\tau_{A}}-Verd_{\mathbf{\omega}}\) (justifique), tenemos que \(S^{\tau_{A}}-Verd_{\mathbf{\omega}}\) es \(\mathcal{A}\)-r. e., por lo cual \[\mathcal{A}^{\ast}-Verd_{\mathbf{\omega}}=(\mathcal{A}^{\ast}-S^{\tau_{A}})\cup(S^{\tau_{A}}-Verd_{\mathbf{\omega}})\] lo es. Es decir que \(Verd_{\mathbf{\omega}}\) y su complemento son \(\mathcal{A}\)-r.e. por lo cual \(Verd_{\mathbf{\omega}}\) es \(\mathcal{A}\)-r.  

Ahora podemos probar el importante resultado anunciado.

Proof. Por el Lema 7.72 hay un predicado \(\emptyset\)-p.r., \(P:\omega\times\omega\rightarrow\omega\) tal que el predicado \(Q=\lambda x\left[(\exists t\in\omega)P(t,x)\right]:\omega\rightarrow\omega\) no es \(\emptyset\)-recursivo. Notese que \(Q\) tampoco es \(\mathcal{A}\)-recursivo. Ya que \(P\) es representable, hay una formula \(\varphi=_{d}\varphi(v_{1},v_{2},v)\in F^{\tau_{A}}\) la cual cumple \[\mathbf{\omega}\models\varphi\left[t,x,k\right]\text{ si y solo si }P(t,x)=k\] cualesquiera sean \(t,x,k\in\omega.\) Sea \(\psi=\varphi(v_{1},v_{2},1)\). Declaremos \(\psi=_{d}\psi(v_{1},v_{2})\). Tenemos entonces \[\mathbf{\omega}\models\psi\left[t,x\right]\text{ si y solo si }P(t,x)=1\] cualesquiera sean \(t,x\in\omega.\) Sea \(\psi_{0}=\exists v_{1}\ \psi(v_{1},v_{2})\). Declaremos \(\psi_{0}=_{d}\psi_{0}(v_{2})\). Tenemos entonces \[\mathbf{\omega}\models\psi_{0}\left[x\right]\text{ si y solo si }Q(x)=1\] cualesquiera sea \(x\in\omega\). Por el lema de reemplazo tenemos que para \(x\in\omega\), \[\mathbf{\omega}\models\psi_{0}\left[x\right]\text{ si y solo si }\mathbf{\omega}\models\psi_{0}(\widehat{x})\] (justifique), por lo cual \[\mathbf{\omega}\models\psi_{0}(\widehat{x})\text{ si y solo si }Q(x)=1\] cualesquiera sea \(x\in\omega\). Ya que \(\psi_{0}(\widehat{x})\) es una sentencia, \[\psi_{0}(\widehat{x})\in Verd_{\mathbf{\omega}}\text{ si y solo si }Q(x)=1\] Sea \(h:\omega\rightarrow\mathcal{A}^{\ast}\), dada por \(h(x)=\psi_{0}(\widehat{x})\). Es facil ver que \(h\) es \(\mathcal{A}\)-recursiva. Ya que \(Q=\chi_{Verd_{\mathbf{\omega}}}^{\mathcal{A}^{\ast}}\circ h\) y \(Q\) no es \(\mathcal{A}\)-recursivo, tenemos que \(\chi_{Verd_{\mathbf{\omega}}}^{\mathcal{A}^{\ast}}\) no es \(\mathcal{A}\)-recursiva, es decir que \(Verd_{\mathbf{\omega}}\) es un conjunto no \(\mathcal{A}\)-recursivo. El lema anterior nos dice entonces que es \(Verd_{\mathbf{\omega}}\) no es \(\mathcal{A}\)-r.e..  

Ahora si, estamos en condiciones de probar facilmente el famoso resultado de Godel.

Proof. Ya que \(\mathbf{\omega}\) es un modelo de \((\Sigma,\tau_{A})\), por el Teorema de Correccion, tenemos que \(Teo_{(\Sigma,\tau_{A})}\subseteq Verd_{\mathbf{\omega}}\). Ya que \(Teo_{(\Sigma,\tau_{A})}\) es \(\mathcal{A}\)-r.e (Proposicion 7.4) y \(Verd_{\mathbf{\omega}}\) no lo es, tenemos que \(Teo_{(\Sigma,\tau_{A})}\neq Verd_{\mathbf{\omega}}\).  

Proof. Dejamos al lector la prueba de que el conjunto \(\Sigma_{A}\) es \(\mathcal{A}\)-r.e.. Una ves probado esto, podemos aplicar el teorema anterior a la teoria \(Arit=(\Sigma_{A},\tau_{A})\), lo cual nos dice que \(Teo_{Arit}\subsetneq Verd_{\mathbf{\omega}}\). Sea \(\varphi\in Verd_{\mathbf{\omega}}-Teo_{Arit}\). O sea que \(Arit\nvdash\varphi\) y \(\varphi\in Verd_{\mathbf{\omega}}\). Ya que \(\lnot\varphi\notin Verd_{\mathbf{\omega}}\), tenemos que \(\lnot\varphi\notin Teo_{Arit}\), es decir \(Arit\nvdash\lnot\varphi\).