teoría ω-consistente

En lógica matemática , una teoría ω-consistente (u omega-consistente o numéricamente segregativa ) ^{[ 1 ]} es una teoría (colección de enunciados ) que no solo es consistente (sintácticamente) ^{[ 2 ]} (es decir, no demuestra una contradicción ), sino que también evita demostrar ciertas combinaciones infinitas de enunciados que son intuitivamente contradictorias. El nombre se debe a Kurt Gödel , quien introdujo el concepto al demostrar el teorema de incompletitud . ^{[ 3 ]}

Se dice que una teoría T interpreta el lenguaje de la aritmética si existe una traducción de las fórmulas aritméticas al lenguaje de T de tal manera que T pueda 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 ) no se cumple . ^{[ 2 ]} Esto puede no generar una contradicción dentro de T porque T puede no ser capaz de probar para cualquier valor específico de n que P ( n ) no se cumple, solo que existe tal n . En particular, tal n es necesariamente un entero no estándar en cualquier modelo para T ( Quine ha llamado a tales teorías "numéricamente insegregativas"). ^{[ 4 ]}

T es ω-consistente si no es ω-inconsistente.

Existe una propiedad más débil pero estrechamente relacionada de la solidez Σ _1. Una teoría T es Σ _1- sólida (o 1-consistente , en otra terminología) ^{[ 5 ]} si toda Σ ⁰ ₁ -sentencia ^{[ 6 ]} demostrable en T es verdadera en el modelo estándar de la aritmética N (es decir, la estructura de los números naturales usuales con suma y multiplicación). Si T es lo suficientemente fuerte como para formalizar un modelo razonable de computación , la solidez Σ ₁ es equivalente a exigir que siempre que T demuestre que una máquina de Turing C se detiene, entonces C se detiene realmente. Toda teoría ω-consistente es Σ ₁ -sólida, pero no a la inversa.

De forma más general, podemos definir un concepto análogo para niveles superiores de la jerarquía aritmética . Si Γ es un conjunto de proposiciones aritméticas (típicamente Σ ⁰ _n para algún n ), una teoría T es Γ-sólida si toda proposición Γ demostrable en T es verdadera en el modelo estándar. Cuando Γ es el conjunto de todas las fórmulas aritméticas, la Γ-corrección se denomina simplemente corrección (aritmética) . Si el lenguaje de T consiste únicamente en el lenguaje de la aritmética (a diferencia, por ejemplo, de la teoría de conjuntos ), entonces un sistema sólido es aquel cuyo modelo puede considerarse como el conjunto ω, el conjunto usual de números naturales matemáticos. El caso de T general es diferente; véase la ω-lógica más adelante.

La solidez Σ _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.

El concepto de teorías de la aritmética cuyos enteros son los verdaderos enteros matemáticos se captura mediante la lógica ω . ^{[ 8 ]} Sea T una teoría en un lenguaje contable que incluye un símbolo predicado unario N destinado a contener solo los números naturales, así como nombres específicos 0, 1, 2, ..., uno para cada número natural (estándar) (que pueden ser constantes separadas o términos constantes como 0, 1, 1+1, 1+1+1, ..., etc.). Nótese que T mismo podría estar refiriéndose a objetos más generales, como números reales o conjuntos; por lo tanto, en un modelo de T los objetos que satisfacen N ( x ) son aquellos que T interpreta como números naturales, no todos los cuales necesitan ser nombrados por uno de los nombres especificados.

El sistema de lógica ω incluye todos los axiomas y reglas de la lógica de predicados usual de primer orden , junto con, para cada T -fórmula P ( x ) con una variable libre x especificada , una regla ω infinitaria de la forma:

De${\displaystyle P(0),P(1),P(2),\ldots }$inferir${\displaystyle \forall x\,(N(x)\to P(x))}$.

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 el consecuente de la regla para cada P simplificándose a${\displaystyle \forall x\,P(x)}$.

Un modelo ω de T es un modelo de T cuyo dominio incluye los números naturales y cuyos nombres y símbolo N se interpretan de forma estándar, respectivamente, como esos números y como el predicado cuyo dominio son precisamente esos números (por lo que no existen números no estándar). Si N está ausente del lenguaje, entonces se requiere que el dominio de N coincida con el del modelo, es decir, que el modelo contenga únicamente los números naturales. (Otros modelos de T pueden interpretar estos símbolos de forma no estándar; por ejemplo, el dominio de N ni siquiera tiene por qué ser numerable). Estos requisitos hacen que la regla ω sea válida en todo modelo ω. Como corolario del teorema de omisión de tipos , también se cumple lo contrario: la teoría T tiene un modelo ω si y solo si es consistente en lógica ω.

Existe una estrecha relación entre la lógica ω y la consistencia ω. Una teoría consistente en lógica ω también es consistente en ω (y aritméticamente correcta). Lo contrario es falso, ya que la consistencia en lógica ω es un concepto mucho más fuerte que la consistencia ω. Sin embargo, se cumple la siguiente caracterización: una teoría es consistente en ω si y solo si su cierre bajo aplicaciones no anidadas de la regla ω es consistente.

Si la teoría T es recursivamente axiomatizable , la ω-consistencia tiene la siguiente caracterización, debida a Craig Smoryński : ^{[ 9 ]}

T es ω -consistente si y solo si${\displaystyle T+\mathrm {RFN} _{T}+\mathrm {Th} _{\Pi _{2}^{0}}(\mathbb {N} )}$es consistente.

Aquí,${\displaystyle \mathrm {Th} _{\Pi _{2}^{0}}(\mathbb {N} )}$es el conjunto de todas las sentencias Π ⁰ ₂ válidas en el modelo estándar de aritmética, y${\displaystyle \mathrm {RFN} _{T}}$es el principio de reflexión uniforme para T , que consta de los axiomas

${\displaystyle \forall x\,(\mathrm {Prov} _{T}(\ulcorner \varphi ({\dot {x}})\urcorner )\to \varphi (x))}$

para cada fórmula${\displaystyle \varphi }$con una variable libre. En particular, una teoría T finitamente axiomatizable en el lenguaje de la aritmética es ω-consistente si y solo si T  +  PA es${\displaystyle \Sigma _{2}^{0}}$-sonido.

• Kurt Gödel (1931). 'Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I'. En Monatshefte für Mathematik . Traducido al inglés como Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados .