25 votos

Un ejemplo concreto del teorema de Incompletitud de Gödel

El teorema de incompletitud de Gödel dice que "cualquier teoría efectivamente generada capaz de expresar la aritmética elemental no puede ser a la vez consistente y completa". En particular, para cualquier teoría formal consistente y efectivamente generada que demuestre ciertas verdades aritméticas básicas, existe un enunciado aritmético que es verdadero,[1] pero que no es demostrable en la teoría."

Me gustó el teorema, pero me costó encontrar un ejemplo. Aquí propongo un ejemplo para el teorema de Gödel. Por favor, dígame si es correcto o señale los fallos.

Consideremos un sistema axiomático en el que se cumplen todos los axiomas regulares relativos a las funciones de valor real. En particular, este sistema se ocupa de las integrales. Una restricción adicional es que la existencia de cualquier integral es "demostrable" si la integral indefinida puede expresarse en términos de funciones elementales. Ahora bien, dado el hecho de que la integral de la función de error converge, es decir, la existencia es verdadera, pero no puede expresarse en términos de funciones elementales, es decir, no es demostrable, ¿puedo decir que éste es un ejemplo en el que se sabe que una afirmación es verdadera, pero no es demostrable?

0 votos

¿Qué quiere decir con una "restricción adicional"?

0 votos

La "restricción adicional" implica aquí un axioma.

1 votos

¿Alguien conoce una teoría de primer orden donde se pueda expresar esto? En cualquier caso, "demostrable" no es algo que se pueda definir. Significa que una sentencia en el lenguaje de primer orden de su teoría se sigue de los axiomas de la teoría y del axioma lógico de primer orden. Suponiendo que haya una teoría de primer orden que capture lo que quieres decir arriba, un ejemplo de una frase que puede ser demostrable o no es "Toda integral puede expresarse como funciones elementales".

14voto

JoshL Puntos 290

Sí, tu ejemplo da un ejemplo de un sistema incompleto. Esto se debe a que has tomado un sistema de axiomas intencionadamente débil pero una semántica fuerte. Otra forma de obtener un ejemplo es simplemente tomar cualquier semántica y desechar todo las reglas de inferencia. Entonces nada es demostrable.

La razón por la que los teoremas de incompletitud son más interesantes que esto es que se aplican a todo conjunto efectivo de reglas de inferencia para la aritmética, sin importar lo fuertes que intentemos hacer las reglas.


He aquí cómo precisar su pregunta. En general, un sistema formal consiste en:

  • Un lenguaje formal $L$ (conjunto de frases)

  • Un conjunto de reglas de inferencia (y axiomas, que son un tipo de regla de inferencia para este propósito)

  • Una semántica, que proporciona un conjunto de modelos, o al menos un conjunto de funciones de valoración de $L$ a $\{T,F\}$

Completitud del sistema dice que si se envía una sentencia a $T$ por cada función de valoración en la semántica, entonces esa frase es demostrable a partir de las reglas de inferencia.

En el teorema de incompletitud, cuando dice "verdadero", quiere decir "verdadero en un modelo particular, distinguido y estándar". No quiere decir "verdadero en todos los modelos" porque toda teoría de primer orden es completa en ese sentido, con sus reglas de inferencia y su semántica habituales.

En su marco, podría tomar $L$ para ser el lenguaje de ZFC mejorado con un predicado unario adicional $I$ . Para las reglas de inferencia, se toman los axiomas de ZFC, un axioma que dice $I$ sólo puede ser de una función $\mathbb{R}\to\mathbb{R}$ El sistema de la lógica de primer orden se basa en los axiomas que permiten demostrar que toda función elemental es integrable, y en las reglas de inferencia habituales de la lógica de primer orden. Para el modelo distinguido (función de valoración) se toma el modelo estándar de ZFC y se hace $I$ se mantienen todas las funciones integrables.

En esa configuración, hay muchas funciones $f$ para lo cual $I(f)$ es verdadera, y tal que se puede expresar $I(f)$ en el lenguaje en cuestión, pero donde sus reglas de inferencia no pueden probar que $I(f)$ retenciones. Por ejemplo, $\sin(x)$ es definible en ZFC, por lo que podría dejar que $f = \sin(x)$ . Sólo tienes que ser capaz de expresar $I(f)$ sin $f$ en el lenguaje de ZFC con el símbolo extra $I$ .

El siguiente problema es que se podría pensar en hacer las reglas de inferencia más fuertes, en un intento de demostrar que más funciones son integrables. En el contexto de la teoría de conjuntos, esto te llevará a cosas más interesantes, como la distinción entre definiciones extensionales e intensionales.

0 votos

Gracias por la clara aclaración, Carl. Realmente aclara las cosas.

5voto

John Fouhy Puntos 759

Estás confundiendo sintaxis y semántica.

El sistema axiomático que estás esbozando tiene algún predicado $I$ cuyo "significado" es ser integrable. Sus reglas de derivación para $I$ sólo permiten probar $I(f)$ cuando $\int f$ es elemental. Así que sintácticamente, $I(f)$ expresa más bien la propiedad de tener una antiderivada elemental. Aunque la semántica que pretende es diferente, la semántica no forma parte del sistema formal propiamente dicho. Una buena axiomatización de un tema particular tendrá la propiedad de que su teoría corresponde a la semántica requerida. Tu axiomatización, por ejemplo, es mala en ese sentido, si pretendías axiomatizar la integrabilidad.

El carácter incompleto es un fenómeno diferente. Algunos sistemas de axiomas (muy simples) tienen la propiedad de que cada afirmación se deduce de ellos o lo hace su negación. Un ejemplo es el cálculo proposicional: toda fórmula sin cuantificador es verdadera o falsa. Gödel demostró que la aritmética de Peano y sus superconjuntos son no completos (siempre que sean coherentes). Es como la situación de los grupos mencionada en los comentarios: los axiomas de grupo no determinan la conmutatividad. De la misma manera, los axiomas de PA no obligan a que la ontología sea los números naturales - se podría tener un número "infinito" por ejemplo. Si te parece interesante, busca "aritmética no estándar".

0 votos

Interesante reflexión, ¡gracias Yuwal! Sin duda miraré la aritmética no estándar.

5voto

user2820579 Puntos 138

Otro ejemplo del principio de que todo sistema no trivial es inconsistente o incompleto es el de la especificación de una línea (en geometría analítica plana).

Sin embargo, antes de considerar este ejemplo, hay que señalar que el par existencia/unicidad es sinónimo, de manera respectiva, del par completitud/consistencia, y a veces es más apropiado lingüísticamente/conceptualmente. Esto es cierto en el presente ejemplo, por lo que hablaremos de "existencia" y "unicidad" en lugar de "integridad" y "consistencia", respectivamente. Así, una formulación sinónima del principio es que todo sistema no trivial se queda corto en cuanto a existencia o unicidad.

Aunque hay varias formas de especificar una recta, todas se reducen a dos: la forma pendiente-intercepto y la forma general. La forma pendiente-intercepto (y = mx + c) es única, pero se queda corta en cuanto a la existencia, ya que no nos da líneas verticales. Por otro lado, la forma general (ax + by + c = 0) nos da todas las rectas, y por tanto nos da la existencia, pero se queda corta en cuanto a la unicidad, ya que al multiplicarla por cualquier constante distinta de la unidad, se obtiene una ecuación aparentemente distinta de la original, pero que, de hecho, especifica exactamente la misma recta. Por ejemplo, la línea especificada por la ecuación general 3x - 2y + 9 = 0 es exactamente la misma línea especificada por la ecuación general -6x + 4y -18 = 0 (habiendo multiplicado la ecuación original por -2).

1voto

user2820579 Puntos 138

La versión "relajada" del Teorema de Godel es: "Todo sistema no trivial es inconsistente o incompleto".

Un ejemplo real de esta versión "relajada" es la numeración de páginas de un documento. ¿Dónde va a poner los números de página: en la parte superior o en la inferior de la página? Si el documento sólo tiene una página, entonces el documento es trivial (desde el punto de vista de la paginación, por supuesto - ¡me doy cuenta de que muchos grandes artículos de literatura cabrían en una página!) Sin embargo, si el documento tiene más de una página, cualquier paginación completa será incoherente. Como la paginación es completa, eso significa que la primera página, que es la del título, también debe tener un número de página. Sin embargo, no se puede poner el número de página en la parte superior sin ser incoherente, porque nadie pone el número de página en la parte superior de la primera página (por razones estéticas obvias). Por lo tanto, el número de página debe ir al final de la página. Por lo tanto, el número de página de la última página también debe ir al final de la página. Sin embargo, un documento no está completo si no incluye un mensaje, o delimitador, que indique al lector que se ha llegado al final del documento. Sin embargo, el número de página, para que la paginación sea coherente, debe seguir a este mensaje/delimitador (ya que es lo último que aparece en todas las páginas). Pero entonces el mensaje/delimitador no está diciendo la verdad (es decir, es incoherente), porque parte del documento (es decir, el número de página de la última página) está aún por llegar.

1voto

ytg Puntos 256

Puede que quiera echar un vistazo a continúa la lógica (por ejemplo, comprobar los documentos sobre Ben Yaacov ).

La idea es que una lógica no clásica puede captar mejor las estructuras analíticas y evitar al mismo tiempo algunos problemas de la lógica clásica de primer orden.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X