¿Cuál es la relación entre la lógica de primer orden y la teoría de primer orden?

8

Pensé que cualquier FOT es un subconjunto de FOL, pero ese no parece ser el caso, porque FOL está completo (cada fórmula es válida o inválida), mientras que algunos FOT (como la aritmética de enteros lineales) no están completos.

Entonces, ¿es FOL más expresivo que cualquiera de FOT? O incomparable?

Además, la afirmación "hay afirmaciones que son válidas en LIA pero que no pueden probarse utilizando axiomas de LIA" es extraña. ¿Cómo puede ser válida la declaración si no podemos probar su validez? Siempre pensé que si no puede probar la validez de la declaración, no puede afirmar que es válida.

Ayrat
fuente
Creo que la afirmación "hay afirmaciones que son válidas en LIA pero que no pueden probarse utilizando axiomas de LIA" es falsa. El teorema de completitud del godel asegura que una declaración válida pueda ser probada en una cantidad de tiempo finita. Creo que estás confundiendo validez lógica con verdad lógica. Esas son dos cosas diferentes. El significado de integridad que se usa en el teorema de integridad de godel y el que se usa en el teorema de incompletitud no es el mismo.
rotia

Respuestas:

12

Lógica de primer orden es un tema matemático que define muchos conceptos diferentes, tales como la fórmula de primer orden , la estructura de primer orden , teoría de primer orden , y muchos más. Uno de estos conceptos es la teoría de primer orden : es un conjunto de fórmulas de primer orden. A menudo consideramos la teoría de primer orden generada por un número finito de axiomas y esquemas de axiomas. Dicha teoría está cerrada con respecto a las derivaciones lógicas , y generalmente solo consideramos teorías que satisfacen esta condición.

Una teoría de primer orden está completa si para cada enunciadoσ, contiene cualquiera σo su negación. No todas las teorías están completas. De hecho, el teorema de incompletitud de Gödel destaca el hecho de que muchas teorías interesantes de primer orden son necesariamente incompletas.

Un modelo de una teoría de primer orden es una interpretación válida de la teoría (dejamos la definición exacta para los libros de texto). Por ejemplo, la teoría de los grupos de primer orden consiste en todas las declaraciones que se derivan de los axiomas grupales. Cada grupo es un modelo de la teoría de los grupos de primer orden.

Para cada modelo dado, una oración muy dada es verdadera o falsa. El teorema de integridad de Gödel establece que si una oración de primer orden es verdadera en todos los modelos de una teoría de primer orden, entonces es demostrable a partir de un número finito de oraciones en la teoría. Por ejemplo, cada declaración de primer orden en el lenguaje de grupos que se cumple para todos los grupos es demostrable a partir de los axiomas de grupo.

LIA es (presumiblemente) una teoría de primer orden que es lo suficientemente interesante como para estar incompleta debido al teorema de incompletitud de Gödel. Sin embargo, en el modelo estándar, los enteros "verdaderos", cada oración es verdadera o falsa. En particular, siσ es una declaración tal que ninguno σ ni ¬σ pertenecer a LIA, entonces σ o ¬σ vale para los verdaderos enteros, pero este hecho no es demostrable en LIA.

Yuval Filmus
fuente
¿Qué tienen de especial las teorías "completas"? ¿Por qué son interesantes? 'por supuesto', muchas teorías están incompletas, porque la definición de completitud pregunta si una oración es verdadera para todos los modelos. Sobre lo incompleto: en el "modelo de enteros estándar", no nos interesan todos los modelos que satisfacen los axiomas, solo tenemos uno, el "modelo de enteros estándar". ¿El teorema de incompletitud no sugiere que la forma en que definimos la validez (especialmente, nuestra consideración de todos los modelos que satisfacen los axiomas) es inapropiada?
Ayrat
2
Las teorías completas son especiales ya que dan un valor de verdad definido para cada declaración. Esto es algo que te gustaría tener. El resto de sus preguntas pertenecen al ámbito de la filosofía. Dicho esto, el teorema de integridad de Gödel equipara la validez en todos los modelos con la demostrabilidad.
Yuval Filmus
todavía no veo la utilidad: considere FOL, que está completo: suponga que desea verificar si F es válido o no: la 'integridad' no ayuda mucho si F no es válido, porque la validez de FOL es semi-decidible. ¿Echo de menos algo?
Ayrat
La afirmación "la lógica de primer orden está completa" no tiene sentido o es falsa.
Yuval Filmus
2
No es cierto que una teoría de primer orden sea un conjunto consistente de oraciones de primer orden. Lo correcto es decir: una teoría de primer orden es un conjunto de fórmulas de primer orden que se cierra bajo deducción. Puedo perfectamente formular una teoría inconsistente. Pueden pasar años antes de que descubramos que es inconsistente. Y una teoría puede contener fórmulas, no solo oraciones (que son fórmulas cerradas).
Andrej Bauer
7

La frase "lógica de primer orden" tiene dos significados:

  1. Es un capítulo de lógica matemática en el que estudiamos ciertos tipos de sistemas formales y todo lo relacionado con ellos.

  2. Es un tipo especial de teoría de primer orden, es decir, la generada por una firma vacía y un conjunto vacío de axiomas.

Su pregunta se refiere al segundo significado, pero para entender esto, necesitamos construir cosas:

  1. Existe cierto lenguaje formal llamado lenguaje de lógica de primer orden . Hablando informalmente, es lo que puedes construir a partir de variables, igualdad,, , ¬, , y . Estas cosas se conocen como fórmulas de primer orden .

  2. Hay un cierto sistema formal llamado lógica de primer orden que nos dice qué significa que demostremos una fórmula de primer orden. El sistema se proporciona como un conjunto de reglas de inferencia.

  3. Una teoría de primer ordenT es dado por:

    • una firmaΣTque consiste en un conjunto de constantes, símbolos de función y símbolos de relación. Piense en esto como extensiones del lenguaje básico de la lógica de primer orden. Lo llamamos el lenguaje deT.
    • Un conjunto deductivamente cerrado de fórmulas de primer orden escritas en el lenguaje extendido por la firma.

Un conjunto Sde fórmulas se dice que está deductivamente cerrado si alguna aplicación de reglas de inferencia de lógica de primer orden a fórmulas enS da fórmulas que están nuevamente en S. En otras palabras,Scontiene todas sus consecuencias lógicas. Una forma común de crear tal conjuntoS es: comenzar con algún conjunto de fórmulas elegido UNA, y agréguele todas sus consecuencias lógicas, y las consecuencias de esas consecuencias, y así sucesivamente. Esto se llama cierre deductivo deUNA. A menudo llamamos a las fórmulas enUNA axiomas .

Una teoría puede o no ser completa. No es importante saber qué significa "completo" aquí, pero es importante saber que puede suceder lo siguiente: podemos tener dos conjuntos de fórmulasUNA y sital que UNAsi, el cierre deductivo de UNA es una teoría completa, y el cierre deductivo de siNo es una teoría completa.

Ahora estamos listos para responder su pregunta. DejarTser la teoría cuya firma está vacía y cuyo conjunto de fórmulas es el cierre deductivo del conjunto vacío. DejarPAGS ser la teoría cuya firma es la de la aritmética de Peano (constante 0 0operación unaria S, operaciones binarias + y ×) y las fórmulas son el cierre deductivo de los axiomas de Peano. Es un hecho que

  1. T está contenido en PAGS (de hecho T está contenido en cada teoría),
  2. T Esta completo,
  3. PAGS no está completo.

La teoría Tse llama popularmente "lógica de primer orden", pero esto realmente es un nombre inapropiado. Algunas personas son un poco más precisas y lo llaman "la teoría pura de la lógica de primer orden".

En resumen, su pregunta reveló lo siguiente:

  1. No sabía que la "lógica de primer orden" puede referirse a la teoría con firma vacía generada por los axiomas vacíos.
  2. Una teoría completa puede quedar incompleta cuando la extendemos.
  3. Usaste la definición incorrecta de integridad. La definición correcta es: una teoría está completa si, cada oración o su negación es un teorema de la teoría.

NB: una oración es una fórmula cerrada (una que no contiene ninguna variable libre).

Por último, permítame abordar su pregunta sobre la validez:

  • una fórmula es demostrable si hay una prueba de ello
  • una fórmula es válida si es cierta en todos los modelos

Un metateorema básico sobre la lógica de primer orden es que toda fórmula demostrable es válida. Lo contrario también es válido y se conoce como el teorema de integridad de Gödel .

Sin embargo, a menudo sucede que en alguna situación particular, uno deliberadamente hace una falta de coincidencia entre validez y demostrabilidad por una buena razón. Por ejemplo, si limitamos la atención solo a los modelos finitos , puede suceder fácilmente que haya declaraciones válidas que no tengan pruebas. ¿Por qué uno haría eso? En ciencias de la computación podría ser por razones algorítmicas, o porque uno está interesado solo en una clase particular de modelos.

Dices "la única forma de saber que una oración es válida es probarla". Este puede ser el caso en algún nivel informal (creo que Dios no estaría de acuerdo con usted), pero tenga en cuenta que cualquier prueba de validez se produce fuera de la teoría, en el nivel meta. De hecho, dado que establecer la validez requiere que uno hable sobre todos los modelos, esto ciertamente no es algo que esperaríamos realizar dentro de la teoría.

Andrej Bauer
fuente
Parece que te has confundido sobre el teorema de integridad de Godel y los teoremas de incompletitud de Godel. Lo que usted llama "teorema de incompletitud de Godel" parece ser una negación directa del teorema de integridad de Godel. El primer teorema de incompletitud de Godel trata sobre oraciones que no pueden ser probadas ni refutadas, no oraciones que son válidas pero no demostrables.
user2357112 es compatible con Monica el
Gracias, acabo de eliminar ese bit porque no agrega nada a la explicación.
Andrej Bauer
@AndrejBauer, ¿podría aclarar la siguiente 'paradoja' con "1. T está contenido en PAGS" ? : Ya que PAGS está incompleto, entonces existe s tal que sPAGS y ¬sPAGS. Ahora pregunta "sT"? Ya que TPAGS (cierres deductivos de sus axiomas), entonces debería haber sT o ¬sT, pero ambos violan el supuesto de existencia de tales s!
Ayrat
Otra pregunta: ¿tiene un ejemplo de declaración válida que no tiene una prueba?
Ayrat
3

Una aclaración menor:

Puede estar pensando que la teoría con firma vacía es una teoría vacía, es decir, no contiene fórmulas cerradas. Eso es incorrecto. La lógica de primer orden permite probar, sin apelar a los axiomas , ciertas fórmulas cerradas conocidas como tautologías. Estos son "verdaderos" debido únicamente a su forma; no tienen contenido significativo como tal. El Teorema de la integridad de Godel dice que la colección de tautologías está completa, es decir, todas las fórmulas cerradas que son válidas (es decir, "verdaderas en todos los modelos") son realmente derivables en la lógica de primer orden. [La prueba es interesante y decididamente no trivial.]

PMar
fuente