[Gustavo Piñeiro]

Estimado argentinator,

Acerca de la cita de Hilbert, se refiere a lo siguiente: en el momento en que Gödel demostró su teorema (lo demostró en 1930 y lo publicó en 1931) todavía no se había dado una definición precisa de "método finitario", por lo que no quedaba claro si el teorema de Gödel se aplicaba a todos los métodos finitarios posibles. El mismo Gödel comenta esta circunstancia en su artículo, diciendo que tal vez había métodos permitido por el programa de Hilbert que su demostración no llegaba a abarcar.

Cuando, en 1936-1937, Church y Turing definen rigurosamente el concepto de algoritmo, quedó claro entonces que la demostración de Gödel sí se aplica a cualquier método finitario y que el programa de Hilbert era imposible de realizar. Gödel apunta esta circunstancia en una posdata que agrega a su artículo original (y que aparece en las ediciones actuales del artículo.)

Acerca del libro, la demostración que allí se da se ajusta a las ideas originales de Gödel, con algunas modificaciones introducidas posteriormente por Raymond Smullyan, las que facilitan algunos detalles técnicos sin modificar la idea original.

Existen, en efecto, demostraciones alternativas del teorema basadas en máquinas de Turing, pero no es una de ellas la que se desarrolla en el libro. Una demostración de ese estilo puede verse en: http://eltopologico.blogspot.com/2005/12/gdel-y-turing-parte-1.html

Saludos!

G.P.

<<                >>

[argentinator]

Existen, en efecto, demostraciones alternativas del teorema basadas en máquinas de Turing, pero no es una de ellas la que se desarrolla en el libro. Una demostración de ese estilo puede verse en: http://eltopologico.blogspot.com/2005/12/gdel-y-turing-parte-1.html

OK. Entonces no sé cómo se me metió en la cabeza que ustedes usaban teoremas basado en máquinas de Turing.
A lo mejor leí algún párrafo sobre máquinas de Turing y me quedó dando vueltas en la cabeza una conclusión errónea.

Lo de los métodos finitarios ha sido más que claro.

[Numerarius]

Es curioso. Gregory Chaitin (que al parecer es un lógico bastante distinguido) escribió sobre el teorema de Gödel lo siguiente:

It was love at first sight! Mad love, crazy love[...]There was only one small, tiny problem, fortunately, which was that for the life of me I couldn't understand Gödel's proof of this wonderful metamathematical result. It's called that because it's not a mathematical problem result, it's a theorem about mathematics itself, about the limitations of mathematical methods

 I wasn't an idiot, so why couldn 't I understand Gödel's proof? Well, I could follow it step by step, but it  was like trying to mix oil and water. My mind  kept resisting. In other words, I just plain didn't like Godel's proof of his faboulous result. His original proof seemed, too fragile! It didn't seem to get to the heart of the matter, because it was far from clear how prevalent inclompleteness might in fact be.

(Gegory Chaitin, Meta Math. The Quest for Omega. Random House. Toronto( Canadá), 2005, pags. 26, 27).

Por cierto, este mismo autor afirma que prefiere la versión de la incompletud demostrada por Turing. Lo que demostró Turing se podría explicar (aproximadamente) así: no existe ningún procedimiento para verificar si un programa P con un dato k  contiene un bucle infinito (o alternativamente, si una máquina de Turing T, con un dato k no parará nunca). Esto se llama el "problema de la parada" ("The halting problem").

[LauLuna]

Efectivamente, Hilbert no había dejado claro lo que se debía entender por 'método finitario'. Cuando Church y Turing formalizaron el concepto de computable, se tendió a pensar que había que entender lo finitario como lo computable o recursivo.

Como todas las funciones recursivas están representadas en la aritmética cuya consistencia se quiere probar, esta interpretación implicaba la imposibilidad del programa de Hilbert.

A pesar de eso, Gödel propuso en 1958 una ampliación del concepto de finitario ("Sobre una ampliación todavía no utilizada del punto de vista finitario" en Dialectica 12, 280-287); aceptando esa ampliación puede probarse la consistencia de la aritmética intuicionista que Gödel mismo había probado en 1932 equivalente a la aritmética clásica.

En cuanto a la cita de Chaitin. Hace tiempo planteé en otro hilo algo parecido y precisamente relacionado con la prueba de Gödel. Uno puede seguir la prueba paso a paso y entenderla, y luego quedarse pensando: bueno ¿qué es exactamente lo que sucede aquí?. Es decir, uno intenta captar la esencia de la prueba, el paso crucial, el hecho fundamental detrás de ella, algo que permita apoderarse intelectualmente del asunto. Y eso no es tan fácil.

Chaitin lo intentó formalizando el concepto de 'contenido de información' y reproduciendo el resultado de incompletitud sobre la base de que ningún sistema de axiomas puede demostrar que una fórmula contiene más información que los axiomas (esta descripción es sólo una aproximación). Es como si le pidieses a los axiomas que encontrasen la primera fórmula que ellos no pueden demostrar, que está más allá de su alcance; lógicamente, no podrán encontrarla, si son consistentes. Así que Chaitin dio una versión 'cuantitativa' del resultado de Gödel.

Para mí el hecho fundamental que hace posible la prueba de Gödel es la circunstancia de que la naturaleza recursiva de los sistema formales axiomáticos permite establecer un isomorfismo entre su estructura y ciertas estructuras aritméticas. Esto hace a su vez posible que los sistemas formales que contienen la aritmética (o una parte suficiente de ella: la aritmética recursiva) sean capaces de tratar parte de su propia metateoría. Es decir, esto hace que estos sistemas se vuelvan en cierto sentido autorreferentes. Y llegados aquí es donde entran en juego los métodos basados en las paradojas, claro.

¿Cuál diríais cada uno de vosotros que es el hecho fundamental que hace incompleta la aritmética y hace posible el resultado de Gödel? Porque esto de elegir un 'hecho fundamental' es muy subjetivo, depende de la forma personal que cada uno tiene de organizar las ideas.

[Gustavo Piñeiro]

En el libro Gödel para Todos sostenemos la tesis (y ése es uno de los aportes originales que el libro intenta hacer al tema) de que el hecho fundamental que está detrás de la prueba de Gödel es que la operación de concatenar símbolos es expresable en la aritmética.

Me explico: Cuando se define el lenguaje formal de la aritmética, primero se indican los símbolos que se van a usar (por ejemplo \(  \forall{}  \), \(  \Rightarrow{}  \), etc.) Las expresiones del lenguaje se obtienen concatenando los símbolos entre sí (es decir, pegándolos). Por ejemplo, \(  \forall{x}  \) se obtiene concatenando el símbolo \(  \forall{}  \) con la variable \( x \).

Existe una concatenación similar entre los números, al concatenar el 2 y el 3 obtenemos el número 23. En el libro damos una definición abstracta de la operación de concatenación (esencialmente que sea una operación isomorfa a la concatenación de símbolos) y vemos que ésta no es la única concatenación posible.

Cuando se define la numeración de Gödel, asignamos un número a cada símbolo y a la concatenación de dos o más símbolos le asignamos la concatenación de sus números correspondientes. Por ejemplo, si a \(  \forall{}  \) le corresponde el 2 y a la variable \( x \) le corresponde el 3, entonces a \(  \forall{x}  \) le corresponderá el 23.

En su paper de 1931 Gödel mismo lo hace de esta manera (aunque sin ser conciente de eso). Él usa una concatenación basada en la descomposición en primos de los números enteros.

Como la concatenación es expresable en la aritmética entonces todas las operaciones sintácticas en el lenguaje se pueden traducir a operaciones expresables en la aritmética y en consecuencias las condiciones "Ser el número de Gödel de una fórmula" (resp. "de un enunciado", "de una demostración" y "de un teorema") son expresables en la aritmética y la prueba del teorema de Gödel puede llevarse adelante.

De hecho, probamos en el lbro que en cualquier teoría en la que pueda definirse una concatenación abstracta vale el equivalente del teorema de Gódel y damos, además, condiciones algebraicas que permiten verificar la existencia de una tal concatenación.

Un problema aún abierto es si la existencia de una concatenación es equivalente a la incompletitud. Nuestra conjetura es que no, pero no hemos podido dar un contraejemplo que zanje la cuestión.

<<                >>

[argentinator]

Aprovecho para preguntar ¿qué es una teoría?

[LauLuna]

Argentinator, técnicamente (en Teoría de Modelos) una teoría es un conjunto C de sentencias en un lenguaje lógico formal con la condición de que C esté cerrado bajo la relación de consecuencia lógica: para todo p y q, si p pertenece a C y q es consecuencia lógica de p, q pertenece a C.

Pero en un sentido más amplio es usual llamar también teorías a los sistemas formales axiomáticos. En algunos de estos sistemas el conjunto de los teoremas es efectivamente una teoría, particularmente en los sistemas de primer orden: como la lógica de primer orden es completa (Gödel 1930), toda consecuencia lógica de los axiomas es también un teorema del sistema. Pero en algunos de ellos, como la aritmética de Peano de segundo orden, el conjunto de los teoremas no es una teoría en el sentido más estricto, porque no toda consecuencia lógica de los axiomas es un teorema.

Como sabes, los sistemas formales axiomáticos están compuestos por axiomas o esquemas axiomáticos y reglas de inferencia. El conjunto de los axiomas puede ser infinito (sobre todo cuando se emplean esquemas axiomáticos) pero ha de ser recursivamente enumerable porque lo esencial es que el conjunto de los teoremas sea recursivamente enumerable, sin eso no se puede hablar de un sistema formal en sentido estricto (aunque tales sistemas en sentido más amplio también existen).

Gustavo, no entiendo muy bien lo de la concatenación. Imagino que no siempre se podrán expresar las fórmulas como números a través de la simple concatenación. Por ejemplo, si los símbolos primitivos son cien, no puedo asociarles números naturales del 0 al 99 y luego representar las fórmulas mediante ssimple concatenación porque el número 19 representaría tanto al vigésimo símbolo como a la concatenación de los símbolos segundo y décimo.

Evidentemente podríamos inventar más símbolos para los números y expresarlos en base 100, y tal vez haya algín otro modo de hacer posible la gödelización por simple concatenación ¿Pero es realmente esencial la posibilidad de concatenar o basta con que haya una manera de representar los símbolos, las fórmulas y las derivaciones como números, aunque no pueda hacerse por simple concatenación?

De todas maneras, como no he leído el libro, sólo intuyo confusamente lo que dices: ¿sugerís los autores que lo que posibilita el teorema no es la estructura y naturaleza de los números mismos sino la naturaleza de nuestra manera de representarlos? No sé si estoy entendiendo bien.

Un saludo

[Gustavo Piñeiro]

Explicaré mejor la cuestión de la concatenación. Empiezo por la definición: una concatenación en un conjunto \( D\subseteq{} N \) con dos átomos (que llamaré \( a \) y \( b \)) es una operación binaria (que indicaré \( \circ{} \)) tal que:

1) Los átomos están en \( D \). La concatenación de dos elementos de \( D \) está en \( D \).
2) La operación es asociativa.
3) Todo elemento de \( D \) es, o bien un átomo, o bien la concatenación de una cantidad finita de átomos.
4) La descomposición en átomos es única (la unicidad incluye a los átomos que aparecen y al orden en que están escritos).

Ejemplos de concatenación:

1) Sea \( D \) el conjunto de todos los números (enteros positivos) cuya escritura en base 10 contiene solamente las cifras 1 y 2. Estas cifras son los átomos y concatenar es escribr un número a continuación del otro.

Como dice LauLuna esta concatenación no es intrínseca y depende de la escritura de los números. Una concatenación que sí es intrínseca es la siguiente:

2) Sea \( D \) el conjunto de todos los enteros mayores que 1 que cumplen estas condiciones:

a) No son divisibles por el cubo de un primo (podríamos llamarlos números libres de cubos).
b) Son múltiplos de 2.
c) Si \( p \) y \( q \) son primos con \( p < q \) y el número es divisible por \( q \) entonces también es divisible por \( p \).

La definición de la concatenación la daré a través de un ejemplo, creo que se entenderá bien:

La concatenación entre el número \( 2\cdot{}3\cdot{}5 \) y \( 2^2\cdot{}3^2\cdot{}5^2\cdot{}7 \) es \( 2\cdot{}3\cdot{}5\cdot{}7^2\cdot{}11^2\cdot{}13^2\cdot{}17 \) (obsérvense los exponentes).

Tomemos ahora un lenguaje formal cualquiera para la aritmética (que tendrá una cantidad a lo sumo numerable de símbolos, los cuales suponemos que están ordenados según algún criterio). Dada una concatenación cualquiera con dos átomos, definimos una codificación de Gödel del siguiente modo:

Al primer símbolo del lenguaje le corresponde el número \( a\circ{}b \).
Al segundo le corresponde \( a\circ{}b\circ{}b \)
Al tercero le corresponde \( a\circ{}b\circ{}b\circ{}b \)

Y así sucesivamente.

A la concatenación de dos o más símbolos le corresponde la concatenación de sus correspondientes números de Gödel.

Para codificar sucesiones de fórmulas, Raymond Smullyan usa la convención (que nosotros adoptamos) de incorporar un símbolo adicional para separar entre sí las las fórmulas de la sucesión.

A partir de aquí se puede desarrollar la prueba del teorema Gödel.

<<                >>

[argentinator]

técnicamente (en Teoría de Modelos) una teoría es un conjunto C de sentencias en un lenguaje lógico formal con la condición de que C esté cerrado bajo la relación de consecuencia lógica: para todo p y q, si p pertenece a C y q es consecuencia lógica de p, q pertenece a C.

Lo que deseo es entender exactamente el objeto de estudio que estamos discutiendo.
Estoy acostumbrado a los sistemas axiomáticos, los conozco bastante porque me he estado peleando con ellos para entender cómo es que se construye la teoría de conjuntos.
Pero me tiene muy confundido el hecho de que se esté trabajando en el terreno de la metamatemática.
¿Los teoremas de Godel son metamatemáticos? Por lo que sé del tema, sí lo son.
Luego, en ese caso, ¿cuáles son las reglas del juego?

Dijiste algo de un ''conjunto de sentencias'', pero asumo que el término conjunto no se refiere a lo que se entiende por ''conjunto'' dentro de la teoría de conjuntos.
Después mencionaste un sistema lógico formal, pero no entiendo cómo puede uno estar seguro de qué es un objeto de ese tipo. ¿Hay definiciones más precisas de todo esto?
Porque mis dudas creo que empiezan por ahí.
No estoy convencido de si está bien definido el objeto de estudio, o sea, si está bien precisado aquello de qué estamos hablando.

Sin eso, no sé si pueda avanzar en la prueba de Godel, porque no me termina de cerrar qué es aquello de lo que se habla, ni cual es la hipótesis, ni cuál es la tesis, ni cuáles son las reglas válidas de inferencia.
Como no hay reglas, parece que todo el mundo está de acuerdo en que deben usarse fórmulas lógicas finitas, y que uno pueda seguir en su construcción paso a paso, sin duda alguna.
Eso al menos lo comprendo, pero quisiera que ustedes me digan exactamente en qué terreno nos movemos.

-----------

En cuanto a lo de la concatenación, bueno, tengo una percepción más filosófica que técnica, porque aún no entiende los detalles de todo esto.
Pero me parece que la operacion de concatenar, que es algo que Hilbert ya se creía autorizado a hacer, involucra la posibilidad de poner uno al lado de otro infinitos signos, o al menos, una cantidad no limitada de signos.
Eso vendría a decir que tengo una ''memoria'' (digamos, la de una computadora) con suficiente capacidad de almacenamiento, o sea, capacidad no finita.
Además, esas celdas de memoria están ordenadas según el orden de los números naturales, porque los signos se escriben uno a la derecha del otro, siguiendo ''un buen orden''.
Así que en realidad el esquema de los números naturales ya lo traemos incorporado incluso antes de haberlo construido como parte de alguna teoría lógica.
Mi conclusión es que el sistema de los naturales ya es parte de nuestro propios esquema de pensamiento, y que cuando construimos la teoría de los números naturales tenemos la ilusión de que estamos construyendo las cosas desde cero,
pero en realidad estamos reflejando algo ya existente en nuestra propia mentalidad.
Las cosas ''ya existentes'' son como ''axiomas''. Recordemos que Euclides asumía hechos ''naturales'' en su teoría, pero que con el tiempo hubo que formalizar esas ''creencias'' de Euclides y explicitarlas como axiomas de la geometría.
Tengo la sospecha de que con los números naturales nos pasa algo parecido a nosotros, ahora en el siglo 21.
Usamos ciertos ''axiomas'' sin darnos cuenta.

¿Qué construcciones u operaciones se asumen como válidas, y cuáles son no válidas?

[Gustavo Piñeiro]

Argentinator tiene razón: si la intención de este hilo es entender la demostración del Teorema de Gödel, entonces el modo correcto de empezar es enunciando el teorema.

Antes del enunciado en sí, es necesario hacer alguna aclaración filosófica (en relación a lo que también decía argentinator). Ni Hlbert ni Gödel creían que los axiomas creaban los números naturales "desde cero". De hecho, Hilbert consideraba imposible el intento de Frege y Russell de definir a los números naturales desde la lógica y la teoría de conjuntos, pues consideraba (y en esto coincidía con los intuicionistas) que la secuencia natural es esencial a nuestro pensamiento y, de hecho, el lenguaje mismo implica la idea de secuencia.

La idea general de Hilbert era dar métodos "seguros" (es decir, que garantizaran la no aparición de paradojas) para determinar si una afirmación aritmética es "verdadera" (siendo este último un término problemático y aún a definir).

En "Acerca del infinito" Hilbert propone que representemos a los números naturales mediante palotes: |, ||, |||, etc. Algunas afirmaciones aritméticas, dice Hilbert, son en realidad afirmaciones empíricas, cuya verdad o falsedad puede verificarse mecánicamente en una cantidad finita de pasos.

Un ejemplo es 2 + 3 = 5 que, traducida a palotes, dice que al concatenar dos palotes con tres palotes se obtienen cinco palotes. A estas afirmaciones empíricas las llamaremos aquí finitarias.

En realidad Hilbert extendía esta condición de finitaria a otras afirmaciones que, aunque no verificables empíricamente, eran intuitivamente evidentes, tales como el esquema de inducción.

Podemos entonces hablar de la verdad o falsedad de afirmaciones finitarias. ¿Qué pasa con las afirmaciones no finitarias? Hilbert dice que no está claro qué significa decir que es "verdadera" o "falsa" una afirmación no verificable empíricamente (ni ecintuitivamente evidente) y trata de reemplazar el concepto semántico de "verdad" por los conceptos sintácticos de "consistencia" y "demostrabilidad".

Tomemos un conjunto de axiomas formado por enunciados finitarios. Un enunciado P es demostrable a partir de esos axiomas si existe una sucesión finita de enunciados que termina en P y en el que cada enunciado es, o bien un axioma, o bien se obtiene de enunciados anteriores por aplicación de las reglas de inferencia. (Habitualmente estas reglas de inferencia son: modus ponens y generalización.)

Los axiomas, además, deben ser elegidos de modo tal que se cumpla esta condición: dado un enunciado cualquiera debe ser posible verificar mecánicamente en una cantidad finita de pasos si ese enunciado es, o no, un axioma. Enunciaremos esta condición diciendo que el conjunto de axiomas es recursivo. (Esta condición limita de tal modo los conjuntos posibles de axiomas que no es necesario recurrir a la teoría de conjuntos par definir qué es un "conjunto de axiomas".)

La propuesta de programa de Hilbert era encontrar un conjunto recursivo de axiomas tal que:

1) El conjunto de axiomas fuera consistente (es decir, dado cualquier enunciado P, nunca sucedería que P y su negación fueran a la vez demostrables).
2) El conjunto de axiomas fuera completo (es decir, dado cualquier enunciado P, o bien él o bien su negación sería demostrable).
3) Fuera posible demostrar la condición 1) mediante demostraciones "seguras" (para ello, decía Hilbert, debería desarrollarse una teoría de la demostración o metamatemática).

El enunciado del Teorema de Gödel, tal como Gödel lo enunció, es:

Teorema: Si un conjunto recursivo de axiomas cumple:

1) El sistema es \( \omega  \)-consistente. (Más abajo explico´qué es esto.)
2) Todo enunciado finitario es demostrable.

Entonces es incompleto. Es decir, existe un enunciado P tal que ni P ni su negación son demostrables. Además (y éste es el llamado Segundo Teorema de Gödel) el hecho de que el sistema es consistente es expresable y no demostrable en el sistema.

(Cuando digo sistema es que incluyo a las reglas de inferencia, si éstas son fijadas de antemano, como habitualmente se hace, entonces "sistema de axiomas" y "conjunto de axiomas" son virtualmente sinónimos).

Un sistema de axiomas es \( \omega  \)-consistente si para toda fórmula \( P(x) \) sucede que si \( P(n) \) es demostrable para todo \( n \) entonces \( \exists{x}-P(x) \) (donde \( -P(x) \) es la negación de \( P(x) \)) no es demostrable.

(Puede probarse que todo sistema \( \omega  \)-consistente es consistente, pero no vale la recíproca.)

En 1936 John B. Rosser modificó la demostración de Gödel de modo que la hipótesis de ser \( \omega  \)-consistente se pudo reemplazar por la de ser consistente.

<<                >>