7.14 Teorema de incompletitud

Sea Verdω={φ∈SτA:ω⊨φ}. Notese que por el Teorema de Correccion tenemos que todo teorema de Arit pertenece a Verdω. 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ω son en realidad teoremas de Arit. Sin envargo Godel probo en su famoso teorema de incompletitud (1931) que hay una sentencia de Verdω la cual no es un teorema de Arit. Por años nadie fue capaz de dar una sentencia de Verdω 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 ω, una pregunta interesante es

1. - Hay un conjunto "razonable" de axiomas Γ⊆Verdω tal que toda sentencia de Verdω es un teorema de (Γ,τ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 τA. Los resultados obtenidos valen para un tipo cualquiera y hemos elejido a τA solo para facilitar la exposicion.

Analizaremos la recursividad del concepto de prueba formal en una teoria de la forma (Σ,τA), donde Σ 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={△◻△,△◻◻△,△◻◻◻△,...} Esto no afectara nuestro analisis ya que es claro que toda prueba formal de una teoria de la forma (Σ,τ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 τeA donde τeA=({0,1}∪Aux,{+2,.2},{≤2},a) Sea A el alfabeto formado por los siguientes simbolos ∀  ∃  ¬  ∨  ∧  →  ↔  (  )  ,  ≡  0  1  +  .  ≤  △  ◻  X  0  1  ...  9  0  1  ...  9 Notese que los simbolos del alfabeto A son justamente los simbolos que ocurren en las formulas y terminos de tipo τeA, es decir que TτeA y FτeA son conjuntos A-mixtos. Mas aun tenemos:

Proof. Notese que los conjuntos TτeA, FτeA, TτA y FτA son A-efectivamente computables (justifique). Entonces la Tesis de Church nos garantiza que dichos conjuntos son A-recursivos.

En realidad dichos conjuntos son A-recursivos primitivos. Veamos por ejemplo que TτeA es A-recursivo primitivo. Fijemos un orden total ≤ sobre A. Sea P=λx[∗≤(x)∈TτeA]. Notese que P(0)=0 y P(x+1)=1 si y solo si se da alguna de las siguientes

1. - ∗≤(x+1)∈{0,1}∪Aux

2. - (∃u,v∈ω)∗≤(x+1)=+(∗≤(u),∗≤(v))∧(P↓(x))u+1∧(P↓(x))v+1

3. - (∃u,v∈ω)∗≤(x+1)=.(∗≤(u),∗≤(v))∧(P↓(x))u+1∧(P↓(x))v+1

Por el Lema 4.37 tenemos que P es A-p.r., por lo cual χA∗TτeA=P∘#≤ lo es. Notese que t∈TτA sii t∈TτeA∧△ no ocurre en t∧◻ no ocurre en t por lo cual TτA es A-p.r.  

Recordemos que en la Subseccion [VariablesLibres] definimos cuando "v ocurre libremente en φ a partir de i", para el caso en que v∈Var, φ∈Fτ y i∈{1,...,|φ|}. Extendamos esta definicion diciendo que cuando v∈Var, φ∈Fτ y i∈ω−{1,...,|φ|}, se da que v no ocurre libremente en φ a partir de i.

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

En realidad dichos predicados son A-p.r.. Veamos por ejemplo que P:ω×Var×FτeA→ω, dado por P(i,v,φ)={1si v ocurre libremente en φ a partir de i0caso contrario es A-p.r.. Sea R:N×Var→ω el predicado dado por R(x,v)=1 si y solo si ∗≤((x)1)∈FτeA y v ocurre libremente en ∗≤((x)1) a partir de (x)2. Sea ˉR=R∪C1,10|{0}×Var. Nex={∧,∨,→,↔}. Notese que FτeA0 es A-p.r. ya que FτeA0=FτeA∩(A−{∀,∃,¬,∨,∧,→,↔})∗ Notese que ˉR(0,v)=0, para cada v∈Var y que ˉR(x+1,v)=1 si y solo si (x+1)2≥1 y se da alguna de las siguientes:

1. - ∗≤((x+1)1)∈FτeA0∧v ocurre en ∗≤((x+1)1) a partir de (x+1)2

2. - (∃φ1,φ2∈FτeA)(∃η∈Nex)∗≤((x+1)1)=(φ1ηφ2)∧

                 ((ˉR↓(x,v))⟨#≤(φ1),(x+1)2−1⟩+1=1∨(ˉR↓(x,v))⟨#≤(φ2),(x+1)2−|(φ1η|⟩+1=1)

3. - (∃φ1∈FτeA)∗≤((x+1)1)=¬φ1∧(ˉR↓(x,v))⟨#≤(φ1),(x+1)2−1⟩+1=1

4. - (∃φ1∈FτeA)(∃w∈Var)(Q∈{∀,∃})w≠v∧

                             ∗≤((x+1)1)=Qwφ1∧(ˉR↓(x,v))⟨#≤(φ1),(x+1)2−|(Qw|⟩+1=1

Es decir que por el Lema 4.37 tenemos que ˉR es A-p.r.. Notese que para (i,v,φ)∈ω×Var×FτeA, tenemos P(i,v,φ)=ˉR(⟨#≤(φ),i⟩,v). Ahora es facil obtener la funcion P haciendo composiciones adecuadas con ˉR.  

Dados v∈Var y t,s∈TτeA, usaremos ↓tv(s) para denotar el resultado de reemplazar simultaneamente cada ocurrencia de v en s por t. Similarmente, si φ∈FτeA, usaremos ↓tv(φ) para denotar el resultado de reemplazar simultaneamente cada ocurrencia libre de v en φ por t.

Proof. Notese que las funciones λsvt[↓tv(s)] y λφvt[↓tv(φ)] son A-efectivamente computables (justifique). Entonces la Tesis de Church nos garantiza que dichas funciones son A-recursivas.

En realidad son A-p.r.. Veamos por ejemplo que λsvt[↓tv(s)] es A-p.r.. Sea ≤ un orden total sobre A. Sea h:ω×Var×TτeA→ω dada por h(x,v,t)={#≤(↓tv(∗≤(x)))si ∗≤(x)∈TτeA0caso contrario Sea P:N×ω×Var×TτeA×A∗→ω tal que P(A,x,v,t,α)=1 si y solo si se da alguna de las siguientes

1. - ∗≤(x+1)∉TτeA∧α=ε

2. - ∗≤(x+1)=v∧α=t

3. - ∗≤(x+1)∈({0,1}∪Aux)−{v}∧α=∗≤(x+1)

4. - (∃r,s∈TτeA)∗≤(x+1)=+(r,s)∧α=+(∗≤((A)#≤(r)+1),∗≤((A)#≤(s)+1))

5. - (∃r,s∈TτeA)∗≤(x+1)=.(r,s)∧α=.(∗≤((A)#≤(r)+1),∗≤((A)#≤(s)+1))

Sea ˉP=P∪C2,20|{0}×ω×Var×TτeA×A∗. Notese que ˉP(h↓(x,v,t),x,v,t,α)=1 si y solo si ya sea ∗≤(x+1)∉TτeA y α=ε o ∗≤(x+1)∈TτeA y α=↓tv(∗≤(x+1)). Tenemos entonces h(0,v,t)=0h(x+1,v,t)=#≤(≤minαˉP(h↓(x,v,t),x,v,t,α)), por lo cual el Lema 4.37 nos dice que h es A-p.r. Ahora es facil obtener la funcion λsvt[↓tv(s)]:TτeA×Var×TτeA→TτeA haciendo composiciones adecuadas con h.  

Proof. Notese que el predicado R es A-efectivamente computable. Entonces la Tesis de Church nos garantiza que R es A-recursivo.

En realidad R es A-p.r. y esto puede verse facilmente ya que R(α,β,γ,ζ)=1 sii existen α1,α2 tales que α=α1γα2 y β=α1ζα2.  

Proof. Dejamos al lector una prueba via la Tesis de Church. En realidad dichos conjuntos son A-p.r.. Veremos, por ejemplo que ReemτeA es A-p.r.. Basta con ver que Reem1τeA y Reem2τeA lo son. Veremos que Reem2τeA es A-p.r.. Sea Q:FτeA×FτeA×FτeA→ω el predicado tal que Q(ψ,φ,σ)=1 si y solo si

1. (∃α∈(∀Var)∗)(∃ψ1,ψ2∈FτeA) ψ=α(ψ1↔ψ2)∧

2.      Li(ψ1)=Li(ψ2)∧((∀v∈Var) v∉Li(ψ1)∨v ocurre en α)

3.           ((∀v∈Var) v no ocurre en α∨v∈Li(ψ1))∧R(φ,σ,ψ1,ψ2)

(R es el predicado dado por el Lema 7.60). Es facil ver que Q es A-p.r. y que χA4Reem2τeA=Q|SτeA×SτeA×SτeA.  

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

Para probar que en realidad dicho predicado es A-p.r., notese que: ψ se deduce de φ por generalizacion con constante c si y solo si hay una formula γ y una variable v tales que

1. - Li(γ)={v}

2. - c no ocurre en γ

3. - φ=↓cv(γ)∧ψ=∀vγ

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

Dejamos al lector probar que en realidad dicho predicado es A-p.r.  

Recordemos que AxLogτeA={φ∈SτeA:φ es un axioma logico de tipo τeA}

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

Dejamos al lector probar que en realidad dicho conjunto es A-p.r. La prueba es completamente analoga a la prueba de que InsΣ es un conjunto (Σ∪Σp)-p.r. (Lema 4.45)

Proof. Ya que S es Σ-r., tenemos que S es Σ-efectivamente computable. Es facil ver que entonces S+ es Σ-efectivamente computable. Por la Tesis de Church tenemos entonces que S es Σ-recursivo.

Ya que α∈S+ si y solo si (∃z∈N)(∀i∈N)i≤Lt(z)∗≤((z)i)∈S∧α=⊂Lt(z)i=1∗≤((z)i) se puede probar tambien este lema sin usar la Tesis de Church. Dejamos al lector los detalles.  

Recordemos que dada φ∈SτeA+, usamos n(φ) y φ1,...,φn(φ) para denotar los unicos n y φ1,...,φn tales que φ=φ1...φn (la unicidad es garantizada en Lema 7.35). Extendamos esta notacion definiendo φi=ε para i=0 o i>n(φ).

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

Dejamos al lector probar que en realidad dicho conjunto es A-p.r. La prueba es completamente analoga a la prueba de que λP[n(P)] y λiP[IPi] son funciones (Σ∪Σp)-p.r. (Lema 4.47)  

Recordemos que dada J∈Just+, usamos n(J) y J1,...,Jn(J) para denotar los unicos n y J1,...,Jn tales que J=J1...Jn (la unicidad es garantizada en Lema 7.34). Extendamos esta notacion definiendo Ji=ε para i=0 o i>n(J).

Sea B el alfabeto que consiste en todos los simbolos que ocurren en alguna palabra de Just. Es decir B consiste de los simbolos ( ) , 0 1 2 3 4 5 6 7 8 9 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 B-efectivamente computables (justifique). Por la Tesis de Church tenemos entonces que son B-r.  

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

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

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

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

Dada una teoria de la forma (Σ,τA), diremos que una prueba formal (φ,J) de φ en (Σ,τA) es normal si solo usa nombres de ctes auxiliares de Aux, es decir si φ∈SτeA+. Definamos Pruebas(Σ,τA)={(φ,J):∃φ (φ,J) es una prueba normal de φ en (Σ,τA)}

Proof. Supongamos que Σ es A-r.e.. Claramente entonces Σ es A-efectivamente computable por lo cual hay una funcion g:ω→Σ la cual es A-efectivamente computable y suryectiva. Sea ≤ un orden total sobre A∪B. A continuacion describimos como hacer un procedimiento efectivo que enumere a Pruebas(Σ,τA). Dejamos al lector completar los detalles. Dada una prueba formal (φ,J) cualquiera, definamos Ax((φ,J))={φi:existe α tal que Ji=αAXIOMAPROPIO}

Etapa 1

Si x=0, detenerse y dar como salida ((0≡0),AXIOMALOGICO). En caso contrario ir a Etapa 2

Etapa 2.

Si (∗≤((x)1),∗≤((x)2)) es una prueba formal y Ax((∗≤((x)1),∗≤((x)2)))⊆{g(0),...,g((x)3)}, entonces detenerse y dar como salida (∗≤((x)1),∗≤((x)2)). Caso contrario detenerse y dar como salida ((0≡0),AXIOMALOGICO)

Por la Tesis de Church tenemos entonces que Pruebas(Σ,τA) es (A∪B)-r.e.  

Dada una teoria (Σ,τA), definamos Teo(Σ,τA)={φ∈SτA:(Σ,τA)⊢φ}

Proof. Como se vio en el lema anterior, tenemos que Pruebas(Σ,τA) es (A∪B)-efectivamente enumerable. Es facil ahora, usando un procedimiento efectivo que enumere a Pruebas(Σ,τA), diseñar un procedimiento efectivo que enumere a Teo(Σ,τA). Es decir que Teo(Σ,τA) es A-efectivamente enumerable, lo cual por la Tesis de Church nos dice que es A-r.e.

A continuacion daremos una prueba que no usa la Tesis de Church. Ya que Pruebas(Σ,τA) es (A∪B)-r.e. (lema anterior) tenemos que hay una funcion F:ω→SτeA+×Just+ la cual cumple que p0,21∘F y p0,22∘F son (A∪B)-r. y ademas IF=Pruebas(Σ,τA). Sea g:SτeA+→SτeAφ→φn(φ) Por lemas anteriores g es A-r.. Notese que I(g∘p0,21∘F)=Teo(Σ,τA), lo cual dice que Teo(Σ,τA) es (A∪B)-r.e. (Teorema 4.12). Por Independencia del Alfabeto tenemos que Teo(Σ,τA) es A-r.e..  

7.14.2 Funciones representables

Sea n≥1. Una funcion f:Df⊆ωn→ω sera llamada representable si hay una formula φ=dφ(v1,...,vn,v)∈FτA, la cual cumpla ω⊨φ[k1,...,kn,k] si y solo si f(k1,...,kn)=k cualesquiera sean k1,...,kn,k∈ω. En tal caso diremos que la formula φ representa a la funcion f, con respecto a la declaracion φ=dφ(v1,...,vn,v). Notese que cuando (k1,...,kn)∉Df entonces debera suceder que ω⊭φ[k1,...,kn,k], cualquiera sea k∈ω. Cabe destacar que una formula φ puede representar a f, con respecto a una declaracion y con respecto a otra declaracion puede no representarla. Por ejemplo la formula (x3≡x1+x2) representa a la operacion suma con respecto a las declaraciones φ=dφ(x1,x2,x3) y φ=dφ(x2,x1,x3) pero con respecto a la declaracion φ=dφ(x3,x2,x1) no representa a dicha operacion. Para dar otro ejemplo, tomemos φ=(x5≡1). Entonces

1. - Con respecto a la declaracion φ=dφ(x2,x5) la formula φ representa a la funcion con dominio ω y valor constantemente 1

2. - Con respecto a la declaracion φ=dφ(x10,x5) la formula φ representa a la funcion con dominio ω y valor constantemente 1

3. - Con respecto a la declaracion φ=dφ(x2,x6,x5) la formula φ representa a la funcion con dominio ω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ω no es A-r.e.. Para probar dicha proposicion primero probaremos que toda funcion ∅-recursivas es representable. Aqui es clave una funcion introducida por Godel. Sea β=λxyi[R(x,y(i+1)+1)] donde R:ω×N→ω(x,y)→resto de la division de x por y Notese que Dβ=ω3. Esta funcion, conocida como la funcion β de Godel, es representable ya que por ejemplo la formula φ=∃x5(x1≡x5.(x2.(x3+1)+1)+x4∧x4<x2.(x3+1)+1) la representa, con respecto a la declaracion φ=dφ(x1,x2,x3,x4). Ahora veremos un lema que muestra que la funcion β tiene una propiedad sorprendente en el sentido de que cualquier sucesion finita de elementos de ω es producida por β si fijamos adecuadamente sus dos primeras entradas. Dados x,y∈ω, diremos que x e y son coprimos cuando 1 sea el unico elemento de ω que divide a ambos. Notese que x e y no son son coprimos sii existe un numero primo p∈ω que los divide a ambos

Proof. Dados x,y,m∈ω con m≥1, usaremos x≡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. - Dados m0,...,mn,z0,...,zn∈ω tales que m0,...,mn son coprimos de a pares, hay un x∈ω tal que x≡zi(mi), para i=0,...,n.