7.15 Teorema de Incompletitud

Sea \[Verd_{\mathbf{\boldsymbol{\omega}}}=\{\varphi\in S^{\tau_{A}}:\mathbf{\boldsymbol{\omega}}\models\varphi\}.\] Nótese que por el Teorema de Corrección tenemos que todo teorema de \(Arit\) pertenece a \(Verd_{\mathbf{\boldsymbol{\omega}}}\). Como puede notarse a medida que uno se va familiarizando con la teoría \(Arit\), todos los resultados clásicos de la aritmética los cuales pueden ser enunciados por medio de una sentencia de \(Verd_{\mathbf{\boldsymbol{\omega}}}\) son en realidad teoremas de \(Arit\). Sin embargo Godel probo en su famoso Teorema de Incompletitud (1931) que hay una sentencia de \(Verd_{\mathbf{\boldsymbol{\omega}}}\) la cual no es un teorema de \(Arit\). Por años nadie fue capaz de dar una sentencia de \(Verd_{\mathbf{\boldsymbol{\omega}}}\) la cual tenga un genuino interés aritmético y la cual no sea un teorema de \(Arit\). Recién 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{\boldsymbol{\omega}}\), una pregunta interesante es

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

Una respuesta negativa a este problema también es dada por el Teorema de Incompletitud de Godel. En esta sección daremos una prueba basada en las ideas de la computabilidad.

7.15.1 Análisis de Recursividad del Lenguaje de Primer Orden

En esta sección estudiaremos la recursividad de la sintaxis de \(\tau_{A}\). Los resultados obtenidos valen para un tipo cualquiera y hemos elegido a \(\tau_{A}\) solo para facilitar la exposición.

Analizaremos la recursividad del concepto de prueba formal en una teoría 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 estarán siempre en el conjunto \[Aux=\{\triangle\Box\triangle,\triangle\Box\Box\triangle,\triangle\Box\Box\Box\triangle,...\}\] Esto no afectara nuestro análisis ya que es claro que toda prueba formal de una teoría de la forma \((\Sigma,\tau_{A})\) puede ser reemplazada por una que sus nombres de constante auxiliares estén en \(Aux\). Es decir que las sentencias involucradas en las pruebas formales que consideraremos serán 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 símbolos \[\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}\] Nótese que los símbolos del alfabeto \(\mathcal{A}\) son justamente los símbolos que ocurren en las fórmulas y términos 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. Nótese 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.

En realidad dichos conjuntos son \(\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}}]\). Nótese 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.37 tenemos que \(P\) es \(\mathcal{A}\)-p.r., por lo cual \(\chi_{T^{\tau_{A}^{e}}}^{\mathcal{A}^{\ast}}=P\circ\#^{\leq}\) lo es. Nótese 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 Sección Variables Libres 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 definición 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. Nótese 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\}\). Nótese 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}\] Nótese 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.37 tenemos que \(\bar{R}\) es \(\mathcal{A}\)-p.r.. Nótese 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 fácil obtener la función \(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 simultáneamente 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 simultáneamente cada ocurrencia libre de \(v\) en \(\varphi\) por \(t\).

Proof. Nótese 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}}\). Nótese 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.37 nos dice que \(h\) es \(\mathcal{A}\)-p.r. Ahora es fácil obtener la función \(\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. Nótese 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 fácilmente 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 vía 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.66). Es fácil 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 cuestión 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., nótese que: \(\psi\) se deduce de \(\varphi\) por generalización con constante \(c\) si y solo si hay una fórmula \(\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 cuestión 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 cuestión 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 análoga a la prueba de que \(\mathrm{Ins}^{\Sigma}\) es un conjunto \((\Sigma\cup\Sigma_{p})\)-p.r. (Lema 4.47)

Proof. Ya que \(S\) es \(\Sigma\)-r., tenemos que \(S\) es \(\Sigma\)-efectivamente computable. Es fácil 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 también 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 únicos \(n\) y \(\varphi_{1},...,\varphi_{n}\) tales que \(\boldsymbol{\varphi}=\varphi_{1}...\varphi_{n}\) (la unicidad es garantizada en Lema 7.40). Extendamos esta notación definiendo \(\boldsymbol{\varphi}_{i}=\varepsilon\) para \(i=0\) o \(i>n(\boldsymbol{\varphi})\).

Proof. Es claro que la funciones en cuestión 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 análoga 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.49)  

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

Sea \(\mathcal{B}\) el alfabeto que consiste en todos los símbolos que ocurren en alguna palabra de \(Just\). Es decir \(\mathcal{B}\) consiste de los símbolos \[(\ )\ ,\ 0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ \mathrm{A}\ \mathrm{B\ C\ D}\mathrm{\ 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 cuestión 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 cuestión 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 cuestión 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 teoría 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 función \(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 continuación 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 teoría \((\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 fácil 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 continuación 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 función \(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 además \(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.. Nótese 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 Independencia del Alfabeto tenemos que \(Teo_{(\Sigma,\tau_{A})}\) es \(\mathcal{A}\)-r.e..  

7.15.2 Funciones Representables

Una función \(f\) es llamada numérica si hay un \(n\in\omega\) tal que \(f:D_{f}\subseteq\omega^{n}\rightarrow\omega\). Nótese que cuando \(f\) es no vacía, \(n\) esta determinado por \(f\). Una función numérica \(f:D_{f}\subseteq\omega^{n}\rightarrow\omega\) será llamada representable si hay una fórmula \(\varphi=_{d}\varphi(v_{1},...,v_{n},v)\in F^{\tau_{A}}\), la cual cumpla

1. adhocprefix(R)adhocsufix \(\mathbf{\boldsymbol{\omega}}\models\varphi\left[k_{1},...,k_{n},k\right]\mathrm{\ si\ y\ solo\ si\ }(k_{1},...,k_{n})\in D_{f}\text{ y }f(k_{1},...,k_{n})=k\), cualesquiera sean \(k_{1},...,k_{n},k\in\omega\).

En tal caso diremos que la fórmula \(\varphi\) representa a la función \(f\), con respecto a la declaración \(\varphi=_{d}\varphi(v_{1},...,v_{n},v)\). Nótese que cuando \((k_{1},...,k_{n})\notin D_{f}\) entonces deberá suceder que \(\mathbf{\boldsymbol{\omega}}\nvDash\varphi\left[k_{1},...,k_{n},k\right]\), cualquiera sea \(k\in\omega\). Nótese esta definición de función representable para el caso \(f=\emptyset\) tiene a priori cierta ambigüedad ya que cualesquiera sea \(n\in\omega\) tenemos que \(\emptyset:\emptyset\subseteq\omega^{n}\rightarrow\omega\). De todas maneras, cualesquiera sea el \(n\) elegido, siempre podemos tomar \(\varphi=_{d}\varphi(v_{1},...,v_{n},v)=\neg(v\equiv v)\) la cual es claro que cumpe (R) para \(f=\emptyset\). Es decir que la función \(\emptyset\) es representable y además cualquier fórmula insatisfacible la representa.

Cabe destacar que una fórmula \(\varphi\) puede representar a \(f\), con respecto a una declaración y con respecto a otra declaración puede no representarla. Por ejemplo la fórmula \((x_{3}\equiv x_{1}+x_{2})\) representa a la operación 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 declaración \(\varphi=_{d}\varphi(x_{3},x_{2},x_{1})\) no representa a dicha operación. Para dar otro ejemplo, tomemos \(\varphi=(x_{5}\equiv1)\). Entonces

1. adhocprefix-adhocsufix Con respecto a la declaración \(\varphi=_{d}\varphi(x_{2},x_{5})\) la fórmula \(\varphi\) representa a la función con dominio \(\omega\) y valor constantemente 1

2. adhocprefix-adhocsufix Con respecto a la declaración \(\varphi=_{d}\varphi(x_{10},x_{5})\) la fórmula \(\varphi\) representa a la función con dominio \(\omega\) y valor constantemente 1

3. adhocprefix-adhocsufix Con respecto a la declaración \(\varphi=_{d}\varphi(x_{2},x_{6},x_{5})\) la fórmula \(\varphi\) representa a la función con dominio \(\omega^{2}\) y valor constantemente 1

A continuación veremos que toda función recursiva clásica es representable. Repasemos un poco el cocepto de función recursiva clásica. Una función numérica \(f\) sera llamada total cuando \(D_{f}=\omega^{n}\), para algún \(n\in\omega\). Sea \(C_{0}^{0}:\{\lozenge\}\rightarrow\omega\) dada por \(C_{0}^{0}(\lozenge)=0\). Para \(1\leq j\leq n\) sea \(p_{j}^{n}:\omega^{n}\rightarrow\omega\) dada por \(p_{j}^{n}(x_{1},...,x_{n})=x_{j}\). Nótese que cuando tenemos un alfabeto fijado, \(C_{0}^{0}=C_{0}^{0,0}\) y \(p_{j}^{n}=p_{j}^{n,0}\).

Definamos los conjuntos \(\mathrm{R}_{0}^{\#}\subseteq\mathrm{R}_{1}^{\#}\subseteq\mathrm{R}_{2}^{\#}\subseteq...\subseteq\mathrm{R}^{\#}\) de la siguiente manera \[\begin{array}{lll} \mathrm{R}_{0}^{\#} & = & \left\{ Suc,Pred,C_{0}^{0}\right\} \cup\left\{ p_{j}^{n}:1\leq j\leq n\right\} \\ \mathrm{R}_{k+1}^{\#} & = & \mathrm{R}_{k}^{\#}\cup\left\{ f\circ[f_{1},...,f_{r}]:f,f_{1},...,f_{r}\in\mathrm{R}_{k}^{\#}\text{, }r\geq1\right\} \cup\\ & & \;\;\;\;\;\;\;\;\left\{ R(f,g):R(f,g)\text{ está definida y }f,g\in\mathrm{R}_{k}^{\#}\right\} \cup\\ & & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left\{ M(P):M(P)\text{ está definida, }P\text{ es un predicado total y }P\in\mathrm{R}_{k}^{\#}\right\} \\ & & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\ \mathrm{R}^{\#} & = & \bigcup_{k\geq0}\mathrm{R}_{k}^{\#} \end{array}\] Una función será llamada recursiva clásica si y solo si pertenece a \(\mathrm{R}^{\#}\). Cabe destacar que el conjunto \(\mathrm{R}^{\emptyset}\) de las funciones \(\emptyset\)-recursivas contiene propiamente al conjunto \(\mathrm{R}^{\#}\). Por ejemplo \(C_{\varepsilon}^{1,1}\) es \(\emptyset\)-recursiva pero no es recursiva clásica.

La función \(\beta\) de Godel

Para probar que toda función recursiva clásica es representable será clave una función 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}\] Nótese que \(D_{\beta}=\omega^{3}\). Esta función, conocida como la función \(\beta\) de Godel, es representable ya que por ejemplo la fórmula \[\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 declaración \(\varphi=_{d}\varphi(x_{1},x_{2},x_{3},x_{4})\). Ahora veremos un lema que muestra que la función \(\beta\) tiene una propiedad sorprendente en el sentido de que cualquier sucesión 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 único elemento de \(\omega\) que divide a ambos. Nótese que \(x\) e \(y\) no son son coprimos sii existe un número 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 \(R(x,m_{i})=R(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 implicaría que \(p\) divide \(y\).

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

Los tres lemas siguientes garantizan que los constructores de recursión primitiva, composición y minimización preservan la representabilidad.

Proof. Nótese 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}\) fórmulas 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 variables 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 fórmula

1. adhocprefixadhocsufix \(\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. adhocprefixadhocsufix \(\ \ \ \ \ \ \ \ \ \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. adhocprefixadhocsufix \(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \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 fácil usando \((1)\Leftrightarrow(3)\) ver que la fórmula \(\varphi_{R(f,g)}\) representa a \(R(f,g)\), con respecto a la declaración \(\varphi_{R(f,g)}=_{d}\varphi_{R(f,g)}(v_{1},...,v_{n+1},v)\).  

Proof. Usaremos la Regla de Inducción desde 0. Para cada \(k\in\omega\) sea \(\mathrm{Enu}_{k}\) el siguiente enunciado:

1. adhocprefix\(\mathrm{Enu}_{k}\):adhocsufix Si \(h\in\mathrm{R}_{k}^{\#}\), entonces \(h\) es representable.

Hagamos entonces lo que nos encomienda la Regla de Inducción desde \(0\).

Prueba de que \(\mathrm{Enu}_{0}\) es verdadero. Fácil.

Prueba de que si \(\mathrm{Enu}_{k}\) es verdadero entonces \(\mathrm{Enu}_{k+1}\) lo es. Supongamos entonces que vale \(\mathrm{Enu}_{k}\). Sea \(h\in\mathrm{R}_{k+1}^{\#}\). Por la definición de \(\mathrm{R}_{k+1}^{\#}\) hay 4 casos.

Caso \(h\in\mathrm{R}_{k}^{\#}\). Trivial ya que vale \(\mathrm{Enu}_{k}\).

Caso \(h=R(f,g)\), con \(f,g\in\mathrm{R}_{k}^{\#}\). Sigue directo de \(\mathrm{Enu}_{k}\) y el primero de los tres lemas anteriores.

Caso \(h=f\circ[f_{1},...,f_{r}]\), con \(r\in\mathbf{N}\) y \(f,f_{1},...,f_{r}\in\mathrm{R}_{k}^{\#}\). Sigue directo de \(\mathrm{Enu}_{k}\) y el tercero de los tres lemas anteriores.  

7.15.3 Prueba del Teorema de Incompletitud

Nuestra estrategia será probar que \(Verd_{\mathbf{\boldsymbol{\omega}}}\) no es \(\mathcal{A}\)-r.e. lo cual contrastará con el hecho ya probado de que \(Teo_{(\Sigma,\tau_{A})}\) es \(\mathcal{A}\)-r.e., para cada teoría \((\Sigma,\tau_{A})\) tal que \(\Sigma\) es \(\mathcal{A}\)-r.e.. Necesitaremos varios lemas. El primero consiste en dar una predicado representable el 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 función \(i^{0,1}\) lo es. Nótese que el dominio de \(P_{1}\) es \(\omega\times\mathrm{Pro}^{\Sigma_{p}}\). Por Lema 4.64 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.\] Por el Lema de División por Casos tenemos que \(P\) es \(\Sigma_{p}\)-p.r.. Ya que \(P\) es \(\Sigma_{p}\)-recursivo y es una función numérica, el Lema 4.42 nos dice que \(P\) es recursiva clásica lo cual por la Proposición 7.5 nos dice que \(P\) es representable. Sea \(Q=\lambda x\left[(\exists t\in\omega)P(t,x)\right]\). Nótese que \[AutoHalt^{\Sigma_{p}}=Q\circ\#^{\leq}\mathrm{|}_{\mathrm{Pro}^{\Sigma_{p}}}\] lo cual dice que \(Q\) no es \(\Sigma_{p}\)-recursivo ya que de serlo, el predicado \(AutoHalt^{\Sigma_{p}}\) lo sería. Por 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{\boldsymbol{\omega}}}\) es \(\mathcal{A}\)-r. e. Sea \(f:\omega\rightarrow Verd_{\mathbf{\boldsymbol{\omega}}}\) una función 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{\boldsymbol{\omega}}}\) (justifique), tenemos que \(S^{\tau_{A}}-Verd_{\mathbf{\boldsymbol{\omega}}}\) es \(\mathcal{A}\)-r. e., por lo cual \[\mathcal{A}^{\ast}-Verd_{\mathbf{\boldsymbol{\omega}}}=(\mathcal{A}^{\ast}-S^{\tau_{A}})\cup(S^{\tau_{A}}-Verd_{\mathbf{\omega}})\] lo es. Es decir que \(Verd_{\mathbf{\boldsymbol{\omega}}}\) y su complemento son \(\mathcal{A}\)-r.e. por lo cual \(Verd_{\mathbf{\boldsymbol{\omega}}}\) es \(\mathcal{A}\)-r.  

Ahora podemos probar el importante resultado anunciado.

Proof. Por el Lema 7.83 hay un predicado representable, \(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. Nótese que \(Q\) tampoco es \(\mathcal{A}\)-recursivo. Ya que \(P\) es representable, hay una fórmula \(\varphi=_{d}\varphi(v_{1},v_{2},v)\in F^{\tau_{A}}\) la cual cumple \[\mathbf{\boldsymbol{\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{\boldsymbol{\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{\boldsymbol{\omega}}\models\psi_{0}\left[x\right]\text{ si y solo si }Q(x)=1\] cualesquiera sea \(x\in\omega\). Por el Teorema de Reemplazo para Términos tenemos que para \(x\in\omega\), \[\mathbf{\boldsymbol{\omega}}\models\psi_{0}\left[x\right]\text{ si y solo si }\mathbf{\boldsymbol{\omega}}\models\psi_{0}(\widehat{x})\] (justifique), por lo cual \[\mathbf{\boldsymbol{\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{\boldsymbol{\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 fácil ver que \(h\) es \(\mathcal{A}\)-recursiva. Ya que \(Q=\chi_{Verd_{\mathbf{\boldsymbol{\omega}}}}^{\mathcal{A}^{\ast}}\circ h\) y \(Q\) no es \(\mathcal{A}\)-recursivo, tenemos que \(\chi_{Verd_{\mathbf{\boldsymbol{\omega}}}}^{\mathcal{A}^{\ast}}\) no es \(\mathcal{A}\)-recursiva, es decir que \(Verd_{\mathbf{\boldsymbol{\omega}}}\) es un conjunto no \(\mathcal{A}\)-recursivo. El lema anterior nos dice entonces que es \(Verd_{\mathbf{\boldsymbol{\omega}}}\) no es \(\mathcal{A}\)-r.e..  

Ahora sí, estamos en condiciones de probar fácilmente el famoso resultado de Godel.

Proof. Ya que \(\mathbf{\boldsymbol{\omega}}\) es un modelo de \((\Sigma,\tau_{A})\), por el Teorema de Corrección, tenemos que \(Teo_{(\Sigma,\tau_{A})}\subseteq Verd_{\mathbf{\boldsymbol{\omega}}}\). Ya que \(Teo_{(\Sigma,\tau_{A})}\) es \(\mathcal{A}\)-r.e (Proposición 7.4) y \(Verd_{\mathbf{\boldsymbol{\omega}}}\) no lo es, tenemos que \(Teo_{(\Sigma,\tau_{A})}\neq Verd_{\mathbf{\boldsymbol{\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 a la teoría \(Arit=(\Sigma_{A},\tau_{A})\), lo cual nos dice que \(Teo_{Arit}\subsetneq Verd_{\mathbf{\boldsymbol{\omega}}}\). Sea \(\varphi\in Verd_{\mathbf{\boldsymbol{\omega}}}-Teo_{Arit}\). O sea que \(Arit\nvdash\varphi\) y \(\varphi\in Verd_{\mathbf{\boldsymbol{\omega}}}\). Ya que \(\lnot\varphi\notin Verd_{\mathbf{\boldsymbol{\omega}}}\), tenemos que \(\lnot\varphi\notin Teo_{Arit}\), es decir \(Arit\nvdash\lnot\varphi\).  

Bibliografía

• Burris, S. and Sankapannavar, H. P., A course in Universal algebra (1981)

• Davis, M. D. and Weyuker, E. J., Computability, complexity, and languages: Fundamentals of theoretical computer science (1983).

• Chang, C. C. and Keisler, H. J., Model Theory (1973).

• Bell, J. L. and Machover, M., A course in mathematical logic (1977).

• Hopcroft, J. E.; and Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979).

• Davis, M. D., The Universal Computer: The Road from Leibniz to Turing (2018).

• Ebbinghaus, H. D., Flum, J. and Thomas, W., Mathematical Logic (1994).

• Mendelson, E., Introduction to mathematical logic (1979).