Teoremas de Incompletitud de Gödel

Primer Teorema

El primer teorema de Gödel demuestra que es imposible axiomatizar completamente la aritmética. Esto significa que, dada una teoría aritmética T que sea correcta, no existe una fórmula GT tal que ni GT ni ¬GT sean deducibles. En otras palabras, no podemos demostrar ni refutar GT. Por lo tanto, no se pueden demostrar todas las verdades aritméticas.

El teorema también demuestra que toda teoría aritmética es incompletable además de incompleta. Si derivamos el problema a una teoría T’ (una teoría que pudiera abarcar más para intentar demostrar GT), nos daría igual, porque también existiría una GT’ que no podría ser demostrada ni refutada.

Aritmetización de la Sintaxis

La aritmetización de la sintaxis consiste en tener, para cada una de las afirmaciones sobre la aritmética, afirmaciones aritméticas equivalentes, expresables en el lenguaje formal de la aritmética.

Lema Diagonal

El lema diagonal establece que, dada cualquier fórmula A(x), con una variable libre, existe una sentencia GA que predica A de su propio número; es decir, mi nº cumple la propiedad A.

Si aplicamos esto a la fórmula ¬Demos(x), obtendremos una sentencia que dice de su propio número, que es el número de una fórmula no demostrable (yo no soy demostrable), lo cual remite a la fórmula G de Gödel.

Segundo Teorema

El segundo teorema de Gödel establece que, dada una teoría axiomatizada T, existe una sentencia aritmética que contiene T CONT, que expresa la consistencia de T. Por lo tanto, se demuestra que si T es consistente, es decir, la fórmula CONT es verdadera, entonces CONT no es demostrable en T.

Aunque la teoría sea consistente, la fórmula no puede ser demostrada, aunque sea verdadera. Demostrabilidad y verdad no son equivalentes.

Teoría de Conjuntos: Russell

La teoría de conjuntos surge en la segunda mitad del siglo XIX con los trabajos de George Cantor. Es una de las partes fundamentales de las matemáticas y una teoría a partir de la cual se puede explicar el concepto matemático de infinito. Así, sirve como base para construir la mayor parte de las matemáticas.

Los matemáticos intentaron precisarla y sistematizarla formulándola axiomáticamente; es decir, establecer una serie de principios básicos a partir de los cuales extraer todo lo demás. Cantor no formula de forma axiomática. El primero fue Frege, a partir de dos principios básicos: el principio de extensionalidad y el de comprensión.

Principio de Comprensión

El principio de comprensión establece que, dada una propiedad P, existe siempre un conjunto formado por las cosas que cumplen P. A partir de este principio, se crean conjuntos que son demasiado grandes, lo cual tiene como consecuencia la aparición de contradicciones. Así aparece la conocida paradoja de Russell.

Paradoja de Russell

Imaginemos la propiedad de no pertenecer a sí mismo. Por el principio de comprensión, tenemos un conjunto R={x:x es un conjunto que no pertenece a sí mismo}. Al preguntarnos si este conjunto R pertenece a sí mismo, nos encontramos con una contradicción. Si R pertenece a sí mismo, entonces no pertenece a R, lo cual es absurdo. Por el contrario, si R no pertenece a sí mismo, entonces no pertenece a R, y por tanto cumple la condición que define al conjunto y pertenecería a él. Esto es también absurdo.

Teoría Axiomática de Conjuntos

Para resolver el surgimiento de estos conjuntos contradictorios”demasiado grande”, se lleva a cabo un intento de reformular la teoría de conjuntos. Para ello, lo fundamental es reformular el principio de comprensión. Dicha empresa es emprendida por lo que se conoce como la teoría axiomática de conjuntos, quien además de contar con el principio de extensionalidad, reemplaza el principio de comprensión por una serie de axiomas que permite formar menos conjuntos que aquél. Así, se forman todos los conjuntos que necesitamos desde el punto de vista matemático, sin construir conjuntos que resulten contradictorios.

Axioma de Infinito

La teoría de conjuntos sirve de base fundamental para construir la mayor parte de las matemáticas, como es el caso de la aritmética que estudia los números naturales.

La idea es que se representen a los números naturales a partir de conjuntos, de manera que las relaciones y propiedades que cumplan los números sean relaciones y propiedades entre conjuntos. La idea de Von Neumann es representar a cada número n por un conjunto que tenga exactamente n elementos. Cada número natural es el conjunto de todos los números naturales menor que él. 3={0,1,2}, 4={0,1,2,3}… Así, tenemos un procedimiento recursivo para construir números naturales: 0= Ø // N+1=nu {n}

Transitividad

Una propiedad importante de los números naturales es la denominada transitividad, es decir, si m≤n, mϵn y mϛn. Así el orden de los números queda representado por la relación de pertenencia.

Teniendo en cuenta esto, parece necesario un conjunto que tenga todos los números naturales como sus elementos, es decir, un conjunto infinito. Sin embargo, ninguno de los axiomas que forman parte de la teoría axiomática de conjuntos nos permite obtener tal conjunto. Es por ello por lo que se hace necesario el denominado axioma del conjunto infinito, que viene a decir que existe un conjunto del que son elementos todos los números naturales. Una definición más frecuente es:

I que cumple las dos siguientes condiciones: a) ØϵI // b) siempre que xϵI, ocurre que xu {v} ϵ I“

Este conjunto de los números naturales es llamado N u ω y es el primer ordinal infinito. Al igual que los números naturales, este conjunto cumple la propiedad de la transitividad, puesto que cualquier elemento de ω es a la vez un subconjunto de ω. Este conjunto es esencial en la teoría de conjuntos porque a partir de él podemos tener otros muchos conjuntos infinitos a partir de los axiomas de separación, unión y conjunto potencia.

Pertenencia e Inclusión

La pertenencia es una relación entre conjuntos. Se dice que un conjunto xϵy, syss x es un elemento de y: y={z,p,x…}. Por otro lado, dados dos conjuntos x e y, se dice que xϛy, o que x es un subconjunto de y, syss todos los elementos de x son también elementos de y. x={1,2,3}. y={1,2,3,4}. En los números naturales ocurre precisamente que un conjunto pertenece a otro y está incluido en él. Una propiedad importante de los números naturales es la denominada transitividad, es decir, si m≤n, mϵn, y mϛn. Así en el orden de los números queda representado por la relación de pertenencia. 3={0,1,2} // 4={0,1,2,3}////// 3ϵ4, porque 3 está dentro del conjunto de 4, es un elemento de 4. Al mismo tiempo, 3ϛ4, porque los elementos de 3 son a la vez los elementos de 4.

Ordinales

Los ordinales son cualquier conjunto transitivo, cuyos elementos son transitivos y que está bien ordenado por pertenencia. Transitividad significa que todo número mayor que otro pertenece y está incluido. 3ϵ4 Pertenece/////3ϛ4 está incluido. Ambos tienen los mismos elementos {0,1,2}//// Es una generación transfinita, porque cualquier nº está formado por los anteriores; es una definición recursiva [Von Neumann] El axioma de infinito nos dice que hay un conjunto formado por todos los números naturales, que es omega ω, al que se le sigue aplicando la definición de Von Neumann: Ω+1, ω+2, ω+3… No existe un conjunto formado por todos los ordinales porque a ese conjunto también podemos aplicarle la definición de Von Neumann, por lo que este conjunto aumentaría, no sería limitado o acotado.

Lógica de Primer Orden

En la lógica de primer orden no va a existir ninguna fórmula que exprese la finitud ni la infinitud, porque si existiese una fórmula de 1er orden que expresase infinitos objetos, se daría una contradicción. Ante estos límites expresivos, surge la lógica de 2º orden, que es una extensión de la primera. Ejemplo: El conjunto de Г nos dice que hay infinitos elementos, pero no hay ningún elemento dentro de Г que demuestre por sí mismo que hay infinitos elementos. No podemos demostrar con ninguna fórmula que hay infinitos elementos, debido a una reducción al absurdo. Imaginemos: A= Hay infinitos elementos.////// Г= {Hn : nϵN}///Г ╞ A. Por el teorema de la compacidad determinamos que si A es consecuencia de Г, entonces también lo va a ser de un subconjunto de Г, llamémosle Г’. ////Г’ = A //// Г’ va a ser un modelo finito, por lo que es satisfecho por un modelo finito y ha de satisfacer a A, pero A ha de ser satisfecha por un modelo infinito (reducción al absurdo).

Lógica de Segundo Orden

Ante la incapacidad expresiva de la lógica de primer orden para dar cuenta de ciertos conceptos matemáticos, como la finitud o la infinitud, surge la lógica de segundo orden, que se constituye como una ampliación en el lenguaje de la de primer orden. Así, en primer lugar, la lógica de segundo orden logra incrementar la capacidad expresiva con respecto a la de primer orden.

Lenguaje de Segundo Orden

En lo que respecta al lenguaje, si en la lógica de primer orden se hablaba de individuos, predicados sobre ellos y se cuantificaba sobre los individuos; en la lógica de segundo orden, se cuenta con la posibilidad de cuantificar también propiedades relaciones. Así, en el lenguaje de segundo orden se añaden las llamadas variables predicativas unarias X,Y,Z… variables predicativas binarias (X2, Y2, Z2…), ternatias… Así podemos cuantificar sobre propiedades diciendo V Xn A. Así ampliamos nuestra definición de fórmulas bien formadas y decimos:

  • Si Xn es una variable relacional n-aria y t1…tn son términos, entonces Xn t1…tn es una fórmula atómica.
  • Si A es una fórmula y Xn una variable relacional n-aria, entonces V Xn A es una fórmula.

Semántica de Segundo Orden

En lo que respecta a la semántica, es similar a la de primer orden pero se añade un tratamiento adecuado a las nuevas variables comentadas. Se mantiene la idea de Modelo. Tenemos, pues, un Dominio (los objetos de los que hablamos) y una función de interpretación que interpreta las constantes individuales y los símbolos relacionales que ahora llamamos constantes de predicado o constantes de relación. Ahora también las funciones de asignación (σ) asignarán también valores a variables predicativas, así que una asignación es ahora una función σ tal que:

  • Para cada variable individual x, σ(x) ϵ D
  • Y también, para cada variable predicativa n-aria Xn, σ(Xn) ϛ Dn

Así, M, σ╞ Xnt1…tn, syss t1)… Iσ(tn)> ϵ(Xn)

Diferencias con la Lógica de Primer Orden

Otra diferencia importante, como hemos dicho, es que en lógica de segundo orden podemos expresar a partir de una fórmula la finitud y la infinitud. Mientras en la de primer orden, la infinitud es expresable por medio de un conjunto de fórmulas, pero no con una Г={Hn: n>2}, en la lógica de segundo orden tenemos una única fórmula. Así, la demostración mediante el teorema de compacidad no puede hacerse en esta lógica, en tanto que no se cumple dicho teorema. También nos permite formular los llamados axiomas de Peano que caracterizan el modelo estándar de la aritmética.

Por último, en lógica de segundo orden no existen sistemas deductivos que sean completos ni siquiera en sentido débil como ocurría en la de primer orden. Se llama “completitud en sentido fuerte” cuando para cualquier Г, A. si Г╞A, entonces Г├A. “Completitud débil” se da cuando ara cualquier A, si ╞A, entonces ├A.