Teoría ω-consistente

Teoría matemática

En lógica matemática , una teoría ω-consistente (o omega-consistente , también llamada numéricamente segregativa ) ^[1] es una teoría (colección de oraciones ) que no solo es (sintácticamente) consistente ^[2] (es decir, no prueba una contradicción ), sino que 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 en el curso de la prueba del teorema de incompletitud . ^[3]

Definición

Se dice que una teoría T interpreta el lenguaje de la aritmética si existe una traducción de fórmulas aritméticas al lenguaje de T de modo que T es 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), y así sucesivamente (es decir, para cada número natural estándar n , T prueba que P ( n ) se cumple), pero T también prueba que hay algún número natural n tal que P ( n ) falla . ^[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 ) falla, 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.

Hay una propiedad más débil pero estrechamente relacionada con la Σ ₁ -solidez. Una teoría T es Σ ₁ -solidez (o 1-consistencia , en otra terminología) ^[5] si cada Σ ⁰ ₁ -oración ^[6] demostrable en T es verdadera en el modelo estándar de aritmética N (es decir, la estructura de los números naturales habituales con adición 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 ω-consistencia es Σ ₁ -solidez, 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 enunciados aritméticos (típicamente Σ ⁰ _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 Γ-sólida se llama simplemente solidez (aritmética) . Si el lenguaje de T consiste únicamente en el lenguaje de la aritmética (en oposición a, por ejemplo, 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 ω-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 en realidad se detiene.

Ejemplos

Teorías consistentes y ω-inconsistentes

Escriba PA para la teoría aritmética de Peano y Con(PA) para el enunciado de la 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 por sí sola probaría ¬Con(PA)→0=1, y un reductio ad absurdum en PA produciría una prueba de Con(PA). Por 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 es consistente. Sin embargo, no sería ω-consistente. Esto se debe a que, para cualquier n particular , PA, y por lo 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 solo una reformulación directa de la afirmación ¬Con(PA)).

En este ejemplo, el axioma ¬Con(PA) es Σ ₁ , por lo tanto, el sistema PA + ¬Con(PA) es de hecho Σ ₁ -inexacto, no solo ω-inconsistente.

Teorías aritméticamente sólidas y ω-inconsistentes

Sea T PA junto con los axiomas c  ≠  n para cada número natural n , donde c es una nueva constante añadida al lenguaje. Entonces T es aritméticamente correcto (ya que cualquier modelo no estándar de PA puede expandirse a un modelo de T ), pero ω-inconsistente (ya que demuestra , y c  ≠  n para cada número n ). ${\displaystyle \exists x\,c=x}$

Las teorías Σ ₁ -sonoras ω-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 A su único axioma, y ​​considere la teoría T  =  I Σ _n  + ¬ A . Podemos suponer que A es una instancia del esquema de inducción, que tiene la forma

${\displaystyle \forall w\,[B(0,w)\land \forall x\,(B(x,w)\to B(x+1,w))\to \forall x\,B(x,w)].}$

Si denotamos la fórmula

${\displaystyle \forall w\,[B(0,w)\land \forall x\,(B(x,w)\to B(x+1,w))\to B(n,w)]}$

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 otra parte, T prueba la fórmula , porque es lógicamente equivalente al axioma ¬ A . Por lo tanto, T es ω-inconsistente. ${\displaystyle \exists x\,\neg P(x)}$

Es posible demostrar que T es Π _{n  + 3} -correcta. De hecho, es Π _{n  + 3} - conservadora respecto de la teoría (obviamente correcta) 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} ).

Teorías aritméticamente erróneas y ω-consistentes

Sea ω-Con(PA) la oración aritmética que formaliza la afirmación "PA es ω-consistente". Entonces la teoría PA + ¬ω-Con(PA) es incorrecta (Σ ₃ -incorrecta, para ser precisos), pero ω-consistente. El argumento es similar al del primer ejemplo: una versión adecuada de las condiciones de derivabilidad de Hilbert – Bernays – Löb se cumple para el "predicado de demostrabilidad" ω-Prov( A ) = ¬ω-Con(PA + ¬ A ), por lo que satisface un análogo del segundo teorema de incompletitud de Gödel.

ω-lógica

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 los nombres especificados 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 en sí 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 de primer orden habitual, junto con, para cada T -fórmula P ( x ) con una variable libre especificada x , una ω-regla infinitaria de la forma:

De inferir . ${\displaystyle P(0),P(1),P(2),\ldots }$ ${\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 mediante la contraparte evidente, finita y cuantificada universalmente de los antecedentes infinitos de la regla. Para una teoría de la aritmética, es decir, una con dominio previsto de 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 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 del lenguaje, entonces se requiere que lo que habría sido el dominio de N sea el del modelo, es decir, el modelo contiene solo 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 ω sea válida en cada ω-modelo. Como corolario del teorema de omisión de tipos , también se cumple lo inverso: la teoría T tiene un ω-modelo si y solo si es consistente en la ω-lógica.

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

Relación con otros principios de consistencia

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 sólo si es consistente. ${\displaystyle T+\mathrm {RFN} _{T}+\mathrm {Th} _{\Pi _{2}^{0}}(\mathbb {N} )}$

Aquí, es el conjunto de todas las oraciones Π ⁰ ₂ 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 ${\displaystyle \mathrm {Th} _{\Pi _{2}^{0}}(\mathbb {N} )}$ ${\displaystyle \mathrm {RFN} _{T}}$

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

para cada fórmula 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 -correcta. ${\displaystyle \varphi }$ ${\displaystyle \Sigma _{2}^{0}}$

Notas

1. WVO Quine (1971), Teoría de conjuntos y su lógica .
2. SC Kleene, Introducción a las metamatemáticas (1971), pág. 207. Bibliotheca Mathematica: una serie de monografías sobre matemáticas puras y aplicadas , vol. I, Wolters-Noordhoff, Holanda Septentrional 0-7204-2103-9, Elsevier 0-444-10088-1.
3. Smorynski, "Los teoremas de incompletitud", Manual de lógica matemática , 1977, pág. 851.
4. Floyd, Putnam, Una nota sobre el "párrafo notorio" de Wittgenstein acerca del teorema de Gödel (2000)
5. H. Friedman, "Adventures in Gödel Incompleteness" (2023), p.14. Consultado el 12 de septiembre de 2023.
6. La definición de este simbolismo se puede encontrar en jerarquía aritmética .
7. Esta formulación utiliza 0=1 en lugar de una contradicción directa; eso da el mismo resultado, porque PA ciertamente prueba ¬0=1, así que si probara también 0=1 tendríamos una contradicción, y por otro lado, si PA prueba una contradicción, entonces prueba cualquier cosa , incluyendo 0=1.
8. J. Barwise (ed.), Manual de lógica matemática , Holanda Septentrional, Ámsterdam, 1977.
9. Smoryński, Craig (1985). Autorreferencia y lógica modal. Berlín: Springer. ISBN 978-0-387-96209-2.Reseñado en Boolos, G.; Smorynski, C. (1988). "Autorreferencia y lógica modal". The Journal of Symbolic Logic . 53 : 306. doi :10.2307/2274450. JSTOR  2274450.

Bibliografía

• 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 .