Teorema de incomplentitud

[Fenrir]

Bueno, que se me iba la pelota, me he puesto aleer el post de religión-ciencia y me olvidaba de a que había entrado en el subforo.

Hay va la bomba! Alguno de los aquí presentes podría hacer una explicación para dummies del teorema de incomplentitud de Godel? Por que se me escapa, ¿Que demonios es eso de que la aritmetica no puede demostrar enunciados verdaderos? 1+1=2 no es demostrable?

Saludos.

[kyv]

Pues ahora mismo no lo tengo muy fresco ni tengo lectura al respecto cerca, pero lo que si te puedo decir es que Godel diferenció entre demostrabilidad y verdad y aunque 1+1=2 es verdad pues se ha construido así no es demostrable dentro del sistema. También demostró que si la aritmética formal es consistente (consistente= sólo las proposiciones verdaderas pueden ser demostradas) la consistencia no puede tampoco ser demostrada dentro de la misma aritmética formal.

Vaya cacao jejej es que todo esto tiene que ver con los algebras de predicados y demás y no lo tengo muy fresco jejej

[nandorroloco]

Bueno, yo no lo entiendo así...

No sé si conoces la lógica de primer orden, es eso que dice para todo x que pertenece a un conjunto tal que cumple unas condiciones, y usa los existenciales y cosas de ese estilo. Es parte de la lógica matemática... bueno, pues... el teorema este se expresa en ese campo...
Eso no significa que 1+1=2 no se pueda demostrar, sino que entra en otro tipo de cuestiones sobre la propia definición de los conjuntos. Porque el número 1, qué es, es un ¿elemento del conjunto de los números naturales N?... y el 2, qué es ¿otro elemento de este conjunto?...+1 es una operación de elementos de este conjunto que significa el siguiente..... pero... y ahí es donde el Godel este pone el dedo en la llaga, si quieres expresar de manera formal a través de axiomas (p.e. los axiomas de Peano) el conjunto de números naturales... pues hay algo que no acaba de funcionar... y ahí hay que darle más al coco... acaba diciendo que necesitas de otro sistema para demostrar la completitud de este. Eso es más o menos.

1+1=0 (y esto es cierto para el conjunto Z2) donde Z2 son los números enteros módulo 2. El 0 representaría a todos los numeros pares, y el 1 a todos los impares, para entendernos.
Claro, siempre que hable de números, tengo que hablar de qué numeros son, para definirlos tendré que aplicar alguna descripción y suele usarse la lógica de primer orden... y resulta... que en muchas ocasiones... tendremos predicados que no podremos demostrar que sean ciertos, sin escarpar de ese mismo mundo.

Vaya rollo, quizá ni yo mismo me aclaro... pero la idea es que las cosas son más complicadas de lo que parece, y la matemática que es un producto exclusivo de la razón humana... esta misma razón es capaz de darle tantas vueltas hasta acabar mareados...

Bueno, igual hay alguien que nos lo aclare mejor... algún matemático por ejemplo, o igual nos lía más de lo que estamos.

Saludos y no me hagas mucho caso por si acaso.

[acafar]

Hola,

El teorema de Gödel se aplica a la "demostrabilidad" en lógica, y se aplica posteriormente a la aritmética, a la computabilidad y en general a cualquier ciencia exacta que pueda ser representada mediante sistemas formales.

Un sistema formal está formada por una lógica concreta + unos cuantos axiomas. La lógica permite derivar nuevos resultados a partir de los axiomas. Por ejemplo en aritmética se utiliza la llamada lógica de primer orden y axiomas del estilo:

a) 0+x=0 para todo x natural
b) x+y=y+x para todo x,y números naturales
c) Si a=b y b=c entonces a=c para cualesquiera valores a,b y c.

Además en un sistema formal se tienen unos criterios de validez (en realidad modelos e interpretaciones válidas, pero simplifico un poco). Por ejemplo nosotros sabemos que la igualdad "3+4=7" es válida según nuestro criterio intuitivo de "si pongo 3 bolitas y al lado 4 bolitas y cuento cuantas hay tengo 7 bolitas". Formalmente se utilizan otros criterios, pero así nos vale.

Ahora viene la gracia del asunto. Consideramos por ejemplo "3+0" ¿a qué valor es igual? Tengo 2 formas de saberlo:

- Según la definición de la suma: pongo 3 bolitas, al lado 0 bolitas, cuento, y veo que tengo 3 bolitas. Por tanto 3+0=0. Por tanto la fórmula "3+0=0" es "verdad" en mi modelo de la aritmética.

- Según los axiomas. Por b) 3+0=0+3, y por a) 0+3=0. De estas dos igualdades por c) llego a que 3+0=0. Por tanto la fórmula "3+0=0" es "demostrable" con respecto a los axiomas a), b) y c) y la lógica de primer orden.

Esta es la diferencia entre verdad y demostrabilidad a la que se refiere kyv. Por supuesto el método de contar bolitas parece más fácil, pero no es tan fácil en general. Por ejemplo, si yo quiero probar que a(b+c)=ab+ac para números cualesquiera a,b y c el método de las bolitas se complica porque tendría que pensar en agrupaciones de bolitas para todos los posibles valores de a,b y c, lo que no es posible, o hacer otro tipo de razonamientos más generales y no tan intuitivos (por ejemplo demostraciones por inducción si me limito a los números naturales). Por eso se usan los axiomas.

Ahora viene lo interesante. Lo que Gödel se planteó es ¿todo lo que es verdad en el mundo de la aritmética puede deducirse de los axiomas de la aritmética (que incluyen a), b), c) y unos cuantos más)? . Con otras palabras, ¿Todo lo que es válido en mi interpretación con bolitas es deducible a partir de los axiomas? Si es así se dice que el conjunto de axiomas es completo. Hasta Gödel se pensaba que había 2 posibles respuestas, ambas optimistas:

- Sí, el sistema de la aritmética es completo. Los matemáticos son listos y han sabido encontrar el conjunto de axiomas justo para deducir todo lo que es "verdad".

- No, puede que haya alguna fórmula válida en la aritmética que no se pueda deducir de los axiomas, es decir los axiomas se quedan "cortos" o "incompletos", pero esto se solucionará cuando se encuentre dicha fórmula; seguro que entonces podemos añadir esa fórmula como axioma y lo mismo con cualquier otra. Parece trampa, pero esta trampa de hace de vez en cuando en matemáticas y es aceptada.

Gödel, por un medio curiosísimo e ingenioso, encontro una fórmula válida en el modelo de la aritmética pero que no podía deducirse de los axiomas. Lo que es muchísimo más interesante, demostró que el asunto no se solucionaba incluyendo la fórmula de las narices como un nuevo axioma, porque si se hacía esto el sistema aritmético se volviía incorrecto, es decir, permitía deducir cosas no válidas, que es lo peor que le puede pasar a un sistema.

Así que la aritmética es incompleta, y esto no se puede arreglar porque la única forma de hacerlo provocaría que fuera incorrecta, es decir absurda. Nos quedamos con la incompletitud como mal menor.

Gödel probó este teorema no sólo para la aritmética, sino para un sistema formal general del que la aritmética es un caso particular.

Desde Gödel la matemática, cienca exacta por excelencia y que parecía que todo lo podá representar con precisión, pasó a ser una ciencia con su propio "principio de incertidumbre". Eso sí, en realidad la aritmética es completa salvo para el tipo de formulas -rarísimas- como la que construyó Gödel.

Razonamientos similares a los de Gödel se han utilizado después en computabilidad para probar las limitaciones de los ordenadores, es decir para delimitar qué puede y qué no puede hacer un ordenador (al menos unos basado en el modelo conocido de Turing).


Saludos

[denon]

Muy bien acafar. Se nota que eres matemático. Igual que alguno más de los que responden...

Por el bien de fenrir y alguno más, añadiré una explicación más sencilla:

Gödel demostró que en cualquier estructura formal, pide que sea al menos tan compleja como el conjunto de los número naturales, se puede enunciar una proposición de la que no se puede afirmar, utilizando sólo la estructura formal, sí es cierta o falsa.
Conclusión: todas las estructuras formales son incompletas. (es mejor decir eso que decir que todas fallan)

NOTA 1: Exigir un cierto nivel de complejidad es necesario, si no se podrían definir estructuras triviales que sí serían completas.
NOTA 2: No quiere decir que 1+1=2 sea falso. De hecho es verdadero en una construcción habitual de N. Quierer decir que hay proposiciones de las que no se puede afirmar si son cierta o falsas. Proposiciones raras, muy muy raras. pero en lógica-matemáticas el adjetivo raro no tiene ningún sentido.

Saludos veraniegos desde el ciber del chiringuito

[nandorroloco]

Hola acafar, es curioso tu axioma a) para definir la suma, y las explicaciones que das al respecto.

un elemento determinado el "0" que operado con cualquier número natural es él mismo... vale, es la definición que haces de la suma, pero no es la suma que conocemos habitualmente, la que conozco yo, trata al "0" como elemento neutro y el axioma que define esta aritmética sería de este estilo.

a') 0+x=x para todo x natural.

Así, que según mi concepción de la suma y su elemento neutro... no sería demostrable la fórmula "3+0=0"

Tus axiomas me llevan a una reflexión... iba a demostrar que no es posible que exista más de un elemento el conjunto que llamas de los números naturales.... Pero es que me he dado cuenta que este elemento neutro, el 0, no indicas si pertenece o no a los números naturales. Esto era básico para mi reducción al absurdo... partía de la premisa de que dos números eran distintos y los operaba con tu suma con el "0", a través de la propiedad conmutativa y asociativa descritas en los axiomas b y c, hacía que a y b fueran iguales, pero, había supuesto que eran distintos y ello me llevaba a afirmar que no existen dos elementos distintos en ese conjunto (cosa que no ocurre con los naturales), con lo cual debían ser el mismo número, pero el único número que conocía de este conjunto era el elemento neutro(?) -me pregunto- porque no sé si estamos deacuerdo en llamarle elemento neutro. Esto... sigo con mis divagaciones... así que si sólo conozco un elemento del conjunto y demuestro que no existen elementos distintos... mi conclusión es que sólo hay un elemento. Cosa que me hace bailar la cabeza... Por cierto, porqué le has llamado "0", le podrías haber llamado "e" y escrito el axioma

a) e+x=e para todo x natural.

Porque le llamas suma a una cosa que no me parece una suma, y 0 a un elemento que me evoca el elemento neutro de la suma con sus propiedades pero no se comporta como tal. Me condiciona el pensamiento y acabo divagando para sufrimiento de toda la concurrencia.

Bueno... no me hagas mucho caso... que lo que no sé.. me lo invento.


Saludos.

[kyv]

Vaya cacao que me tengo jejeje, en cualquier caso no es de mis "partes" de la matemática preferidas, solo curse una asignatura donde se hablaba de estas cosas, "teoría de la computabilidad" y lo único que saque en claro es que se perdía mucho tiempo mareando la perdiz, ¡con el sinfin de cosas más entretenidas que nos brindan las matemáticas! jejeje.

Por cierto cundo yo me refería a que 1+1=2 es verdad lo decía dentro del contexto de los números naturales), entendiendo el 1 como el siguiente del 0 siendo "0 es un número natural" el primero de los cinco axiomas de peano), habiendolos construido con los axiomas de Peano, que ya nos dan la noción de siguiente (que tambien es un número natural), la noción de 0 es el primero, la inyectividad de la aplicación que asigna a cada numero natural su siguiente y por últimoel método de inducción completa; a partir de los cuales ya se pueden demostrar todas sus propiedades hasta llegar que son un semianillo con la operación interna a la que hemos llamado suma. Y lo que viene ahora ya me gusta un poquillo más, que es solo teniendo los axiomas de peano o lo que es lo mismo los números naturales, poder construir de ahí hasta los complejos. Ya se que todo esto tiene poco que ver con el tema pero es que no puedo evitar divagar para intentar explicarme.

PD. Espero no haber dicho muchas tonterías... porque estoy pelín espeso hoy jeje

Un saludo

[acafar]

Hola,

Se me coló el axioma nando Por supuesto quería poner 0+x=x, o e+x=x para cierto natural e. Luego al menos fui coherente y así definí mi propio conjunto de los "números antinaturales"

Espero que el "resbalón" axiomático no impida que se entienda lo que quería deciir. Por lo menos ha servido para tu interesante disgresión....por cierto que no veo que en el conjunto este de los antinaturales que me inventé sin querer tenga que haber sólo un número -el 0- aunque supongas que el 0 está en el conjunto. Si te he entendido bien estás peensando en algo como:

a = a+0 = 0 = b+0=b, y por tanto a=b para todo a.b, pero es que ningún axioma (de los de mi sistema) te permite probar que a=a+0 ni que b+0=b. De hecho los axiomas a) y b) son ciertos en la aritmética sustituyendo + por * y esto no significa qie los naturales sean un conjunto unitario.


Aprovecho y añado un par de cosas:

1) denon esto que dices

Conclusión: todas las estructuras formales son incompletas. (es mejor decir eso que decir que todas fallan)

es un poco exagerado. Hay muchas estructuras formales complejas y completas. Por ejemplo:

- La geometría euclídea admite una axiomatización completa. Y es una estructura muy compleja.

- Los números reales y los números complejos tienen axiomatizaciones completas. Esto último suena raro porque ambos "contienen" a los naturales en cierto sentido, pero es que contener a los naturales no representa ningún problema, sólo contener su axiomatización tal cual.

2) kyv, en efecto la computabilidad tiene mucho que ver con el teorema de Gödel y aunque seguramente tus profes no supieron explicarlo es sumamente importante, y curiosamente muy práctica. La computabilidad permite saber que problemas son decidibles o no, desde el punto de vista de que exista un programa que sea capaz de resolverlo. El más conocido es el "problema de la parada":

- Todos sabemos que hay programas que se quedan "colgados", es decir que para ciertos valores introducidos por el usuario no acaban y tenemos que reiniciar el ordenador...este es un comportamiento no deseable y se debe normalmente a que se ha colado un error al escribir un programa. Sería muy interesante disponer de una aplicación informática que fuera capaz de detectar cuando un programa se va a quedar colgado para ciertas entradas/acciones del usuario, para señalar así que hay un error y corregirlo antes de, por ejemplo, poner el programa a la venta. La teoría de la computabilidad, prueba que NO existe tal aplicación, y que es imposible construirla (al menos basándonos en el modelo de cómputo que usamos habitualmente y en que se basan nuestros ordenadores).

Igual que esta hay otro montón de propiedades sobre los programas que son indecidibles. Siempre que quiero hacer un programa para probar ciertas propiedades de los programas, o para optimizar su comportamiento tengo que preguntarme ¿no estaré tratando de construir un programa para un problema computacionalemten no decidible? porque en ese caso estoy perdiendo el tiempo, es imposible.

Para acabar decir que el pobre Gödel, como otros muchos matemáticos, acabó con serios problemas mentales. Pensaba que querían envenenarle (una paranoia típica) y sólo consentía en probar los alimentos cocinados por su mujer. Cuando su mujer, enferma, ya no pudo cocinar, en 1978, Gödel dejó de comer. Y murió de malnutrición pesando menos de 30 kilos.

Saludos

[nandorroloco]

Cierto, tus axiomas no me permiten probar que a=b, la demostración iría en la línea que decía... o como había pensado hacerloo
b+0=0
a+0=a+b+0=b+a+0=b+0
de lo cual...
a+0=b+0

pero aquí no puedo decir a=b, además me haría falta que hubieras axiomatizado la propiedad asociativa de esa operación tan curiosa que llamabas suma.

Tiene aspecto de producto... pero... lo curioso es que el 0 tal como lo definiste en tu famoso axioma a)... se comporta como un elemento antisimétrico. Podríamos decir que el elemento antisimetrico se diferencia del simetrico porque operado por cualquier número no obtienes el elemento neutro, sino el propio antisimétrico... osea que es un elemento pesao en sí mismo. ¿como se llama el 0 con respecto al producto? es que ya ni me acuerdo...

Bueno, ha estado interesante. Al menos ejercitamos un poco el músculo gris.

Saludotes.

[acafar]

Buena idea la "del elemento antisimétrico" que al ser operado con cualquiera se lo "traga"... es verdad.

Lo que decías de que todos los elementos sean igual al 0, ocurre si en un anillo supones que el 0 tiene inverso con respecto al producto, es decir que existe un valor u tal que u*0 = 1. En este caso se tiene 0 = u*0 = 1, y de 0=1 se tiene que a=a*1 = a*0 = 0.

Por cierto, x*0 = 0 no se suele incluir como axioma al definir la suma y el producto sobre los enteros, es un teorema que se puede probar a partir de los axiomas:

x*0 = (0 elemento neutro de la suma)
x*(0+0) = (distributiva)
x*0+ x*0

Y de x*0 = x*0 +x*0, por la existencia del simétrico para la suma, es decir restando -x*0 en ambos lados 0 = x*0.

Axiomas para un sábado por la noche ... vaya piraos

Saludos