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 (es decir, no prueba una contradicción ), pero también evita probar ciertas combinaciones infinitas de oraciones intuitivamente contradictorias. El nombre se debe a Kurt Gödel , quien introdujo el concepto mientras probaba el teorema de incompletitud . [2]
Una teoría T se dice que interpretar el lenguaje de la aritmética si hay una traducción de fórmulas aritméticas en el lenguaje de la T de manera que T es capaz de probar los axiomas básicos de los números naturales en virtud de esta traducción.
Un T que interpreta 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 se cumple P ( n )), pero T también prueba que hay algún número natural n (necesariamente no estándar en cualquier modelo para T ) tal que P ( n) falla . Esto puede no generar una contradicción dentro de T porque T puede no ser capaz de probar para ningún valor específico de n que P ( n ) falla, solo que existe tal n .
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) si cada Σ 0 1- oración [3] demostrable en T es verdadera en el modelo estándar de 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 de cálculo razonable , la solidez de Σ 1 es equivalente a exigir que siempre que T demuestre que una máquina de Turing Cse detiene, entonces C realmente se detiene. Toda teoría coherente con ω es sólida con Σ 1 , 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 algunos 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, Γ-solidez se llama simplemente (aritmética) solidez . Si el lenguaje de T consiste solo en el lenguaje de la aritmética (a diferencia de, por ejemplo, la teoría de conjuntos), entonces un sistema de sonido es aquel cuyo modelo puede considerarse como el conjunto ω, el conjunto habitual de números naturales matemáticos. El caso de la T general es diferente, consulte la lógica ω a continuación.
Σ n- soundness tiene la siguiente interpretación computacional: si la teoría prueba que un programa C que usa un oráculo Σ n −1 - se detiene, entonces C realmente se detiene.