En lógica matemática , una teoría ω-consistente (u omega-consistente , también llamada numéricamente segregativa ) [1] es una teoría (colección de oraciones ) que no sólo es (sintácticamente) consistente [2] (es decir, no prueba una contradicción ), pero también evita probar ciertas combinaciones infinitas de oraciones que son intuitivamente contradictorias. El nombre se debe a Kurt Gödel , quien introdujo el concepto mientras demostraba el teorema de incompletitud . [3]
Se dice que una teoría T interpreta el lenguaje de la aritmética si hay una traducción de fórmulas aritméticas al lenguaje de T de modo que T sea capaz de demostrar los axiomas básicos de los números naturales bajo esta traducción.
Una T que interpreta la aritmética es ω-inconsistente si, para alguna propiedad P de los números naturales (definida por una fórmula en el lenguaje de T ), T prueba P (0), P (1), P (2), etc. (es decir, para cada número natural estándar n , T prueba que P ( n ) se cumple), pero T también prueba que existe algún número natural n tal que P ( n ) falla . [2] Esto puede no generar una contradicción dentro de T porque es posible que T no pueda probar para ningún valor específico de n que P ( n ) falla, solo que existe tal n . En particular, tal n es necesariamente un número entero no estándar en cualquier modelo para T (Quine ha llamado a tales teorías "numéricamente no segregativas"). [4]
T es ω-consistente si no es ω-inconsistente.
Existe una propiedad más débil pero estrechamente relacionada con la solidez Σ 1 . Una teoría T es Σ 1 -sonido (o 1-consistente , en otra terminología) [5] si cada Σ 0 1 -oración [6] demostrable en T es verdadera en el modelo estándar de aritmética N (es decir, la estructura de la números naturales habituales con suma y multiplicación). Si T es lo suficientemente fuerte como para formalizar un modelo razonable de cálculo , la solidez Σ 1 equivale a exigir que siempre que T demuestre que una máquina de Turing C se detiene, entonces C realmente se detiene. Toda teoría ω-consistente es Σ 1 -sonido, pero no al revés.
De manera más general, podemos definir un concepto análogo para niveles superiores de la jerarquía aritmética . Si Γ es un conjunto de oraciones aritméticas (típicamente Σ 0 n para algún n ), una teoría T es Γ-sólida si cada Γ-oración demostrable en T es verdadera en el modelo estándar. Cuando Γ es el conjunto de todas las fórmulas aritméticas, la Γ-solidez se llama simplemente solidez (aritmética) . Si el lenguaje de T consiste únicamente en el lenguaje de la aritmética (a diferencia de, por ejemplo, la teoría de conjuntos ), entonces un sistema sólido es aquel cuyo modelo puede considerarse como el conjunto ω, el conjunto habitual de números naturales matemáticos. El caso de T general es diferente, consulte la lógica ω a continuación.
La solidez de Σ n tiene la siguiente interpretación computacional: si la teoría demuestra que un programa C que utiliza un oráculo Σ n −1 - se detiene, entonces C realmente se detiene.
Escriba PA para la teoría aritmética de Peano y Con(PA) para el enunciado de aritmética que formaliza la afirmación "PA es consistente". Con(PA) podría tener la forma "Ningún número natural n es el número de Gödel de una prueba en PA de que 0=1". [7] Ahora bien, la consistencia de PA implica la consistencia de PA + ¬Con(PA). De hecho, si PA + ¬Con(PA) fuera inconsistente, entonces PA solo probaría ¬Con(PA)→0=1, y una reductio ad absurdum en PA produciría una prueba de Con(PA). Según el segundo teorema de incompletitud de Gödel , PA sería inconsistente.
Por lo tanto, suponiendo que PA es consistente, PA + ¬Con(PA) también lo es. Sin embargo, no sería ω-consistente. Esto se debe a que, para cualquier n particular , PA, y por tanto PA + ¬Con(PA), demuestra que n no es el número de Gödel de una prueba de que 0=1. Sin embargo, PA + ¬Con(PA) demuestra que, para algún número natural n , n es el número de Gödel de tal prueba (esto es sólo una reformulación directa de la afirmación ¬Con(PA)).
En este ejemplo, el axioma ¬Con(PA) es Σ 1 , por lo tanto, el sistema PA + ¬Con(PA) es de hecho Σ 1 -incorrecto, no sólo ω-inconsistente.
Sea T PA junto con los axiomas c ≠ n para cada número natural n , donde c es una nueva constante agregada al lenguaje. Entonces T es aritméticamente sólido (ya que cualquier modelo no estándar de PA puede ampliarse a un modelo de T ), pero ω-inconsistente (como lo demuestra , y c ≠ n para cada número n ).
Σ 1 -sonido ω-teorías inconsistentes que utilizan únicamente el lenguaje de la aritmética se pueden construir de la siguiente manera. Sea I Σ n la subteoría de PA con el esquema de inducción restringido a Σ n -fórmulas, para cualquier n > 0. La teoría I Σ n + 1 es finitamente axiomatizable, sea por tanto A su único axioma, y consideremos la teoría T = yo Σ norte + ¬ A . Podemos suponer que A es una instancia del esquema de inducción, que tiene la forma
Si denotamos la fórmula
por P ( n ), entonces para cada número natural n , la teoría T (en realidad, incluso el cálculo de predicados puro) prueba P ( n ). Por otro lado, T prueba la fórmula , porque es lógicamente equivalente al axioma ¬ A . Por tanto, T es ω-inconsistente.
Es posible demostrar que T es Π n + 3 -sonido. De hecho, es Π n + 3 - conservador sobre la teoría (obviamente sólida) I Σ n . El argumento es más complicado (se basa en la demostrabilidad del Σ n + 2 - principio de reflexión para I Σ n en I Σ n + 1 ).
Sea ω-Con(PA) la oración aritmética que formaliza el enunciado "PA es ω-consistente". Entonces la teoría PA + ¬ω-Con(PA) es errónea (Σ 3 -incorrecta, para ser precisos), pero ω-consistente. El argumento es similar al primer ejemplo: una versión adecuada de las condiciones de derivabilidad de Hilbert – Bernays – Löb es válida para el "predicado de demostrabilidad" ω-Prov( A ) = ¬ω-Con(PA + ¬ A ), por lo tanto satisface un análogo del segundo teorema de incompletitud de Gödel.
El concepto de teorías de la aritmética cuyos números enteros son los verdaderos números enteros matemáticos es capturado por la lógica ω . [8] Sea T una teoría en un lenguaje contable que incluye un símbolo de predicado unario N destinado a contener solo los números naturales, así como nombres específicos 0, 1, 2, ..., uno para cada natural (estándar). número (que pueden ser constantes separadas o términos constantes como 0, 1, 1+1, 1+1+1, ..., etc.). Tenga en cuenta que la propia T podría estar refiriéndose a objetos más generales, como números reales o conjuntos; así, en un modelo de T, los objetos que satisfacen N ( x ) son aquellos que T interpreta como números naturales, y no todos necesitan ser nombrados con uno de los nombres especificados.
El sistema de lógica ω incluye todos los axiomas y reglas de la lógica de predicados de primer orden habitual, junto con, para cada fórmula T P ( x ) con una variable libre especificada x , una regla ω infinita de la forma:
Es decir, si la teoría afirma (es decir, prueba) P ( n ) por separado para cada número natural n dado por su nombre especificado, entonces también afirma P colectivamente para todos los números naturales a la vez a través de la evidente contraparte finita universalmente cuantificada de los infinitos. Antecedentes de la regla. Para una teoría de la aritmética, es decir, una cuyo dominio previsto son los números naturales, como la aritmética de Peano , el predicado N es redundante y puede omitirse del lenguaje, con la consiguiente simplificación de la regla para cada P a .
Un modelo ω de T es un modelo de T cuyo dominio incluye los números naturales y cuyos nombres especificados y símbolo N se interpretan de manera estándar, respectivamente, como esos números y el predicado que tiene solo esos números como su dominio (de donde no hay números no estándar) . Si N está ausente en el lenguaje, entonces lo que habría sido el dominio de N debe ser el del modelo, es decir, el modelo contiene sólo los números naturales. (Otros modelos de T pueden interpretar estos símbolos de manera no estándar; el dominio de N ni siquiera necesita ser contable, por ejemplo). Estos requisitos hacen que la regla ω suene en cada modelo ω. Como corolario del teorema de tipos omitidos , también se cumple lo contrario: la teoría T tiene un modelo ω si y sólo si es consistente en lógica ω.
Existe una estrecha conexión entre la lógica ω y la consistencia ω. Una teoría consistente en ω-lógica también es ω-consistente (y aritméticamente sólida). Lo contrario es falso, ya que la coherencia en la lógica ω es una noción mucho más fuerte que la coherencia ω. Sin embargo, se cumple la siguiente caracterización: una teoría es ω-consistente si y sólo si su cierre bajo aplicaciones no anidadas de la regla ω es consistente.
Si la teoría T es axiomatizable recursivamente , la consistencia ω tiene la siguiente caracterización, debida a Craig Smoryński: [9]
Aquí, es el conjunto de todas las oraciones Π 0 2 válidas en el modelo estándar de aritmética, y es el principio de reflexión uniforme para T , que consta de los axiomas
para cada fórmula con una variable libre. En particular, una teoría finitamente axiomatizable T en el lenguaje de la aritmética es ω-consistente si y sólo si T + PA es -sonido.
![{\displaystyle \forall w\,[B(0,w)\land \forall x\,(B(x,w)\to B(x+1,w))\to \forall x\,B(x ,w)].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b5e565450e1049cffc3e58a8e1acfc88d5da3cbd)
![{\displaystyle \forall w\,[B(0,w)\land \forall x\,(B(x,w)\to B(x+1,w))\to B(n,w)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee1ba9356c602dc84deae57603043f7407a121a7)
