Consistencia

No contradicción de una teoría

En lógica clásica , deductiva , una teoría consistente es aquella que no conduce a una contradicción lógica . ^[1] Una teoría es consistente si no hay una fórmula tal que tanto y su negación sean elementos del conjunto de consecuencias de . Sea un conjunto de oraciones cerradas (informalmente "axiomas") y el conjunto de oraciones cerradas demostrables a partir de algún sistema deductivo formal (especificado, posiblemente implícitamente). El conjunto de axiomas es consistente cuando no hay una fórmula tal que y . Una teoría trivial (es decir, una que prueba cada oración en el lenguaje de la teoría) es claramente inconsistente. Por el contrario, en un sistema formal explosivo (por ejemplo, lógica proposicional o de primer orden clásica o intuicionista) toda teoría inconsistente es trivial. ^[2]^{: 7} La consistencia de una teoría es una noción sintáctica , cuya contraparte semántica es la satisfacibilidad . Una teoría es satisfacible si tiene un modelo , es decir, existe una interpretación bajo la cual todos los axiomas de la teoría son verdaderos. ^[3] Esto es lo que significaba consistente en la lógica aristotélica tradicional , aunque en la lógica matemática contemporánea se utiliza en su lugar el término satisfacible . ${\estilo de visualización T}$ ${\estilo de visualización \varphi}$ ${\estilo de visualización \varphi}$ $\lno \varphi$ ${\estilo de visualización T}$ ${\estilo de visualización A}$ $\langle A\rangle$ ${\estilo de visualización A}$ ${\estilo de visualización A}$ ${\estilo de visualización \varphi}$ $\varphi \en \langle A\rangle$ $\lnot \varphi \in \langle A\rangle$

En un sistema formal sólido , toda teoría satisfacible es consistente, pero lo inverso no se cumple. Si existe un sistema deductivo para el cual estas definiciones semánticas y sintácticas son equivalentes para cualquier teoría formulada en una lógica deductiva particular , la lógica se llama completa . ^{[ cita requerida ]} La completitud del cálculo proposicional fue probada por Paul Bernays en 1918 ^{[ cita requerida ]}^[4] y Emil Post en 1921, ^{[5] mientras que la completitud del}cálculo de predicados (de primer orden) fue probada por Kurt Gödel en 1930, ^[6] y las pruebas de consistencia para aritméticas restringidas con respecto al esquema del axioma de inducción fueron probadas por Ackermann (1924), von Neumann (1927) y Herbrand (1931). ^[7] Las lógicas más fuertes, como la lógica de segundo orden , no son completas.

Una prueba de consistencia es una prueba matemática de que una teoría particular es consistente. ^[8] El desarrollo temprano de la teoría de la prueba matemática fue impulsado por el deseo de proporcionar pruebas de consistencia finita para todas las matemáticas como parte del programa de Hilbert . El programa de Hilbert se vio fuertemente influenciado por los teoremas de incompletitud , que mostraron que las teorías de prueba suficientemente fuertes no pueden probar su consistencia (siempre que sean consistentes).

Aunque la consistencia puede demostrarse utilizando la teoría de modelos, a menudo se hace de una manera puramente sintáctica, sin necesidad de hacer referencia a algún modelo de la lógica. La eliminación de cortes (o equivalentemente, la normalización del cálculo subyacente , si lo hay) implica la consistencia del cálculo: dado que no hay una prueba de falsedad sin cortes, no hay contradicción en general.

Consistencia y completitud en aritmética y teoría de conjuntos

En las teorías aritméticas, como la aritmética de Peano , existe una relación intrincada entre la consistencia de la teoría y su completitud . Una teoría es completa si, para cada fórmula φ en su lenguaje, al menos uno de φ o ¬φ es una consecuencia lógica de la teoría.

La aritmética de Presburger es un sistema axiomático para los números naturales en el marco de la adición. Es coherente y completo.

Los teoremas de incompletitud de Gödel muestran que cualquier teoría de la aritmética recursivamente enumerable suficientemente sólida no puede ser completa y consistente a la vez. El teorema de Gödel se aplica a las teorías de la aritmética de Peano (PA) y la aritmética recursiva primitiva (PRA), pero no a la aritmética de Presburger .

Además, el segundo teorema de incompletitud de Gödel muestra que la consistencia de teorías aritméticas suficientemente fuertes y recursivamente enumerables puede probarse de una manera particular. Tal teoría es consistente si y solo si no prueba una oración particular, llamada la oración de Gödel de la teoría, que es una declaración formalizada de la afirmación de que la teoría es efectivamente consistente. Por lo tanto, la consistencia de una teoría aritmética suficientemente fuerte, recursivamente enumerable y consistente nunca puede probarse en ese sistema en sí. El mismo resultado es válido para teorías recursivamente enumerables que pueden describir un fragmento suficientemente fuerte de aritmética, incluidas las teorías de conjuntos como la teoría de conjuntos de Zermelo-Fraenkel (ZF). Estas teorías de conjuntos no pueden probar su propia oración de Gödel, siempre que sean consistentes, lo que generalmente se cree.

Debido a que la consistencia de ZF no es demostrable en ZF, la noción más débilLa consistencia relativa es interesante en la teoría de conjuntos (y en otros sistemas axiomáticos suficientemente expresivos). SiTes unateoríayAaxiomaadicional,T+Aes consistente con respecto aT(o simplemente queAes consistente conT) si se puede demostrar que siTconsistente entoncesT+Aes consistente. Si tantoAcomo ¬Ason consistentes conT, entoncesse dice queAindependientedeT.

Lógica de primer orden

Notación

En el siguiente contexto de lógica matemática , el símbolo del torniquete significa "demostrable a partir de", es decir, se lee: b es demostrable a partir de a (en algún sistema formal especificado). ${\estilo de visualización \vdash}$ ${\estilo de visualización a\vdash b}$

Definición

Un conjunto de fórmulas en lógica de primer orden es consistente (escrito ) si no existe una fórmula tal que y . En caso contrario es inconsistente (escrito ). ${\estilo de visualización \Phi}$ $\nombre del operador {Con} \Phi$ ${\estilo de visualización \varphi}$ $\Phi \vdash \varphi$ $\Phi \vdash \lnot \varphi$ ${\estilo de visualización \Phi}$ $\operatorname {Inc} \Phi$
${\estilo de visualización \Phi}$ se dice que es simplemente consistente si para ninguna fórmula de , tanto y la negación de son teoremas de . ^[^{aclaración necesaria}^] ${\estilo de visualización \varphi}$ ${\estilo de visualización \Phi}$ ${\estilo de visualización \varphi}$ ${\estilo de visualización \varphi}$ ${\estilo de visualización \Phi}$
${\estilo de visualización \Phi}$ Se dice que es absolutamente consistente o postconsistente si al menos una fórmula en el lenguaje de no es un teorema de . ${\estilo de visualización \Phi}$ ${\estilo de visualización \Phi}$
${\estilo de visualización \Phi}$ Se dice que es máximamente consistente si es consistente y para cada fórmula , implica . ${\estilo de visualización \Phi}$ ${\estilo de visualización \varphi}$ $\operatorname {Con} (\Phi \cup \{\varphi \})$ $\varphi \en \Phi$
${\estilo de visualización \Phi}$ Se dice que contiene testigos si para cada fórmula de la forma existe un término tal que , donde denota la sustitución de cada uno en por un ; véase también Lógica de primer orden . ^[^{cita requerida}^] $\existe x\,\varphi$ ${\estilo de visualización t}$ $(\existe x\,\varphi \a \varphi {t \sobre x})\en \Phi$ $\varphi {t \sobre x}$ ${\estilo de visualización x}$ ${\estilo de visualización \varphi}$ ${\estilo de visualización t}$

Resultados básicos

Los siguientes son equivalentes:
1. $\operatorname {Inc} \Phi$
2. A pesar de $\varphi ,\;\Phi \vdash \varphi .$
Todo conjunto de fórmulas satisfacibles es consistente, donde un conjunto de fórmulas es satisfacible si y sólo si existe un modelo tal que . $\Phi$ ${\mathfrak {I}}$ ${\mathfrak {I}}\vDash \Phi$
Para todos y : $\Phi$ $\varphi$
1. si no , entonces ; $\Phi \vdash \varphi$ $\operatorname {Con} \left(\Phi \cup \{\lnot \varphi \}\right)$
2. si y , entonces ; $\operatorname {Con} \Phi$ $\Phi \vdash \varphi$ $\operatorname {Con} \left(\Phi \cup \{\varphi \}\right)$
3. si , entonces o . $\operatorname {Con} \Phi$ $\operatorname {Con} \left(\Phi \cup \{\varphi \}\right)$ $\operatorname {Con} \left(\Phi \cup \{\lnot \varphi \}\right)$
Sea un conjunto de fórmulas de consistencia máxima y supongamos que contiene testigos . Para todos y : $\Phi$ $\varphi$ $\psi$
1. Si , entonces , $\Phi \vdash \varphi$ $\varphi \in \Phi$
2. o bien o bien , $\varphi \in \Phi$ $\lnot \varphi \in \Phi$
3. $(\varphi \lor \psi )\in \Phi$ si y solo si o , $\varphi \in \Phi$ $\psi \in \Phi$
4. Si y , entonces , $(\varphi \to \psi )\in \Phi$ $\varphi \in \Phi$ $\psi \in \Phi$
5. $\exists x\,\varphi \in \Phi$ si y sólo si existe un término tal que . ^[^{cita requerida}^] $t$ $\varphi {t \over x}\in \Phi$

Teorema de Henkin

Sea un conjunto de símbolos . Sea un conjunto de fórmulas máximamente consistentes que contienen testigos . $S$ $\Phi$ $S$

Defina una relación de equivalencia en el conjunto de términos mediante si , donde denota igualdad . Sea , denote la clase de equivalencia de términos que contienen ; y sea , donde es el conjunto de términos basado en el conjunto de símbolos . $\sim$ $S$ $t_{0}\sim t_{1}$ $\;t_{0}\equiv t_{1}\in \Phi$ $\equiv$ ${\overline {t}}$ $t$ $T_{\Phi }:=\{\;{\overline {t}}\mid t\in T^{S}\}$ $T^{S}$ $S$

Defina la estructura - sobre , también llamada estructura-término correspondiente a , mediante: $S$ ${\mathfrak {T}}_{\Phi }$ $T_{\Phi }$ $\Phi$

Para cada símbolo de relación -ario , defina si ^[9] $n$ $R\in S$ $R^{{\mathfrak {T}}_{\Phi }}{\overline {t_{0}}}\ldots {\overline {t_{n-1}}}$ $\;Rt_{0}\ldots t_{n-1}\in \Phi ;$
Para cada símbolo de función -ario , defina $n$ $f\in S$ $f^{{\mathfrak {T}}_{\Phi }}({\overline {t_{0}}}\ldots {\overline {t_{n-1}}}):={\overline {ft_{0}\ldots t_{n-1}}};$
Para cada símbolo constante , defina $c\in S$ $c^{{\mathfrak {T}}_{\Phi }}:={\overline {c}}.$

Defina una asignación de variable por para cada variable . Sea el término interpretación asociado con . $\beta _{\Phi }$ $\beta _{\Phi }(x):={\bar {x}}$ $x$ ${\mathfrak {I}}_{\Phi }:=({\mathfrak {T}}_{\Phi },\beta _{\Phi })$ $\Phi$

Luego, para cada fórmula : $S$ $\varphi$

{\mathfrak {I}}_{\Phi }\vDash \varphi

si y sólo si ^[^{cita requerida}^]

\;\varphi \in \Phi .

Bosquejo de la prueba

Hay varias cosas que verificar. Primero, que se trate de una relación de equivalencia. Luego, es necesario verificar que (1), (2) y (3) estén bien definidos. Esto se desprende del hecho de que se trata de una relación de equivalencia y también requiere una prueba de que (1) y (2) son independientes de la elección de los representantes de la clase. Finalmente, se puede verificar por inducción sobre fórmulas. $\sim$ $\sim$ $t_{0},\ldots ,t_{n-1}$ ${\mathfrak {I}}_{\Phi }\vDash \varphi$

Teoría de modelos

En la teoría de conjuntos ZFC con lógica clásica de primer orden , ^[10] una teoría inconsistente es aquella en la que existe una oración cerrada que contiene tanto a como a su negación . Una teoría consistente es aquella en la que se cumplen las siguientes condiciones lógicamente equivalentes $T$ $\varphi$ $T$ $\varphi$ $\varphi '$

$\{\varphi ,\varphi '\}\not \subseteq T$ ^[11]
$\varphi '\not \in T\lor \varphi \not \in T$

Véase también

Notas

↑ Tarski 1946 lo expresa de esta manera: "Una teoría deductiva se llama consistente o no contradictoria si no hay dos afirmaciones de esta teoría que se contradigan entre sí, o en otras palabras, si de dos oraciones contradictorias... al menos una no puede probarse", (p. 135), donde Tarski define contradictorio de la siguiente manera: "Con la ayuda de la palabra no , una forma la negación de ninguna oración; dos oraciones, de las cuales la primera es una negación de la segunda, se llaman oraciones contradictorias " (p. 20). Esta definición requiere una noción de "prueba". Gödel 1931 define la noción de esta manera: "La clase de fórmulas demostrables se define como la clase más pequeña de fórmulas que contiene los axiomas y está cerrada bajo la relación "consecuencia inmediata", es decir, la fórmula c de a y b se define como una consecuencia inmediata en términos de modus ponens o sustitución; cf Gödel 1931, van Heijenoort 1967, p. 601. Tarski define "prueba" informalmente como "enunciados que se suceden unos a otros en un orden definido de acuerdo con ciertos principios... y acompañados de consideraciones destinadas a establecer su validez [conclusión verdadera] para todas las premisas verdaderas - Reichenbach 1947, p. 68]" cf Tarski 1946, p. 3. Kleene 1952 define la noción con respecto a una inducción o parafraseando) una secuencia finita de fórmulas tales que cada fórmula en la secuencia es un axioma o una "consecuencia inmediata" de las fórmulas precedentes; " Se dice que una prueba es una prueba de su última fórmula, y se dice que esta fórmula es (formalmente) demostrable o es un teorema (formal)" cf Kleene 1952, p. 83.
^ Carnielli, Walter; Coniglio, Marcelo Esteban (2016). Lógica paraconsistente: consistencia, contradicción y negación . Lógica, epistemología y la unidad de la ciencia. Vol. 40. Cham: Springer. doi :10.1007/978-3-319-33205-5. ISBN . 978-3-319-33203-1.MR 3822731.Zbl 1355.03001 .
^ Hodges, Wilfrid (1997). A Shorter Model Theory . Nueva York: Cambridge University Press. p. 37. Sea una firma, una teoría en y una oración en . Decimos que es una consecuencia de , o que implica , en símbolos , si cada modelo de es un modelo de . (En particular, si no tiene modelos, entonces implica .) Advertencia : no requerimos que si entonces haya una prueba de a partir de . En cualquier caso, con lenguajes infinitarios, no siempre está claro qué constituiría una prueba. Algunos escritores suelen querer decir que es deducible de en algún cálculo de prueba formal particular, y escriben para nuestra noción de implicación (una notación que choca con nuestra ). Para la lógica de primer orden, los dos tipos de implicación coinciden por el teorema de completitud para el cálculo de prueba en cuestión. Decimos que es válido , o es un teorema lógico , en símbolos , si es verdadero en cada -estructura. Decimos que es consistente si es verdadera en alguna estructura. Asimismo, decimos que una teoría es consistente si tiene un modelo. Decimos que dos teorías S y T en L infinito omega son equivalentes si tienen los mismos modelos, es decir, si Mod(S) = Mod(T). $L$ $T$ $L_{\infty \omega }$ $\varphi$ $L_{\infty \omega }$ $\varphi$ $T$ $T$ $\varphi$ $T\vdash \varphi$ $T$ $\varphi$ $T$ $T$ $\varphi$
$T\vdash \varphi$ $\varphi$ $T$ $T\vdash \varphi$ $\varphi$ $T$ $T\models \varphi$ $A\models \varphi$
$\varphi$ $\vdash \varphi$ $\varphi$ $L$ $\varphi$ $\varphi$ $L$ $T$
(Tenga en cuenta la definición de Mod(T) en la pág. 30 ...)
^ van Heijenoort 1967, p. 265 afirma que Bernays determinó la independencia de los axiomas de Principia Mathematica , un resultado no publicado hasta 1926, pero no dice nada acerca de que Bernays probara su consistencia .
^ Post demuestra tanto la consistencia como la completitud del cálculo proposicional de PM, véase el comentario de van Heijenoort y la Introducción de Post de 1931 a una teoría general de proposiciones elementales en van Heijenoort 1967, pp. 264ff. También Tarski 1946, pp. 134ff.
^ cf el comentario de van Heijenoort y Gödel, 1930, La completitud de los axiomas del cálculo funcional de la lógica en van Heijenoort 1967, pp. 582 y siguientes.
^ cf. comentario de van Heijenoort y 1930 de Herbrand Sobre la consistencia de la aritmética en van Heijenoort 1967, págs. 618 y siguientes.
^ Una prueba de consistencia a menudo presupone la consistencia de otra teoría. En la mayoría de los casos, esta otra teoría es la teoría de conjuntos de Zermelo-Fraenkel con o sin el axioma de elección (esto es equivalente, ya que se ha demostrado que estas dos teorías son equiconsistentes; es decir, si una es consistente, lo mismo es cierto para la otra).
^ Esta definición es independiente de la elección de debido a las propiedades de sustitutividad de y la consistencia máxima de . $t_{i}$ $\equiv$ $\Phi$
^ el caso común en muchas aplicaciones a otras áreas de las matemáticas, así como el modo ordinario de razonamiento de las matemáticas informales en el cálculo y las aplicaciones a la física, la química y la ingeniería.
^ según las leyes de De Morgan

Referencias

Gödel, Kurt (1 de diciembre de 1931). "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I". Monatshefte für Mathematik und Physik . 38 (1): 173–198. doi :10.1007/BF01700692.
Kleene, Stephen (1952). Introducción a las metamatemáticas . Nueva York: North-Holland. ISBN 0-7204-2103-9.10ª impresión 1991.
Reichenbach, Hans (1947). Elementos de lógica simbólica . Nueva York: Dover. ISBN 0-486-24004-5.
Tarski, Alfred (1946). Introducción a la lógica y a la metodología de las ciencias deductivas (segunda edición). Nueva York: Dover. ISBN 0-486-28462-X.
van Heijenoort, Jean (1967). De Frege a Gödel: un libro de consulta sobre lógica matemática . Cambridge, MA: Harvard University Press. ISBN 0-674-32449-8.(por favor)
"Consistencia". Diccionario Cambridge de Filosofía .
Ebbinghaus, HD; Flum, J.; Thomas, W. Lógica matemática .
Jevons, WS (1870). Lecciones elementales de lógica .

Enlaces externos

Mortensen, Chris (2017). "Matemáticas inconsistentes". Stanford Encyclopedia of Philosophy .

[1] Tarski 1946 lo expresa de esta manera: "Una teoría deductiva se llama consistente o no contradictoria si no hay dos afirmaciones de esta teoría que se contradigan entre sí, o en otras palabras, si de dos oraciones contradictorias... al menos una no puede probarse", (p. 135), donde Tarski define contradictorio de la siguiente manera: "Con la ayuda de la palabra no , una forma la negación de ninguna oración; dos oraciones, de las cuales la primera es una negación de la segunda, se llaman oraciones contradictorias " (p. 20). Esta definición requiere una noción de "prueba". Gödel 1931 define la noción de esta manera: "La clase de fórmulas demostrables se define como la clase más pequeña de fórmulas que contiene los axiomas y está cerrada bajo la relación "consecuencia inmediata", es decir, la fórmula c de a y b se define como una consecuencia inmediata en términos de modus ponens o sustitución; cf Gödel 1931, van Heijenoort 1967, p. 601. Tarski define "prueba" informalmente como "enunciados que se suceden unos a otros en un orden definido de acuerdo con ciertos principios... y acompañados de consideraciones destinadas a establecer su validez [conclusión verdadera] para todas las premisas verdaderas - Reichenbach 1947, p. 68]" cf Tarski 1946, p. 3. Kleene 1952 define la noción con respecto a una inducción o parafraseando) una secuencia finita de fórmulas tales que cada fórmula en la secuencia es un axioma o una "consecuencia inmediata" de las fórmulas precedentes; " Se dice que una prueba es una prueba de su última fórmula, y se dice que esta fórmula es (formalmente) demostrable o es un teorema (formal)" cf Kleene 1952, p. 83.

[Carnielli-2] Carnielli, Walter; Coniglio, Marcelo Esteban (2016). Lógica paraconsistente: consistencia, contradicción y negación . Lógica, epistemología y la unidad de la ciencia. Vol. 40. Cham: Springer. doi :10.1007/978-3-319-33205-5. ISBN . 978-3-319-33203-1.MR 3822731.Zbl 1355.03001 .

[3] Hodges, Wilfrid (1997). A Shorter Model Theory . Nueva York: Cambridge University Press. p. 37. Sea una firma, una teoría en y una oración en . Decimos que es una consecuencia de , o que implica , en símbolos , si cada modelo de es un modelo de . (En particular, si no tiene modelos, entonces implica .) Advertencia : no requerimos que si entonces haya una prueba de a partir de . En cualquier caso, con lenguajes infinitarios, no siempre está claro qué constituiría una prueba. Algunos escritores suelen querer decir que es deducible de en algún cálculo de prueba formal particular, y escriben para nuestra noción de implicación (una notación que choca con nuestra ). Para la lógica de primer orden, los dos tipos de implicación coinciden por el teorema de completitud para el cálculo de prueba en cuestión. Decimos que es válido , o es un teorema lógico , en símbolos , si es verdadero en cada -estructura. Decimos que es consistente si es verdadera en alguna estructura. Asimismo, decimos que una teoría es consistente si tiene un modelo. Decimos que dos teorías S y T en L infinito omega son equivalentes si tienen los mismos modelos, es decir, si Mod(S) = Mod(T). $L$ $T$ $L_{\infty \omega }$ $\varphi$ $L_{\infty \omega }$ $\varphi$ $T$ $T$ $\varphi$ $T\vdash \varphi$ $T$ $\varphi$ $T$ $T$ $\varphi$
$T\vdash \varphi$ $\varphi$ $T$ $T\vdash \varphi$ $\varphi$ $T$ $T\models \varphi$ $A\models \varphi$
$\varphi$ $\vdash \varphi$ $\varphi$ $L$ $\varphi$ $\varphi$ $L$ $T$
(Tenga en cuenta la definición de Mod(T) en la pág. 30 ...)

[4] van Heijenoort 1967, p. 265 afirma que Bernays determinó la independencia de los axiomas de Principia Mathematica , un resultado no publicado hasta 1926, pero no dice nada acerca de que Bernays probara su consistencia .

[5] Post demuestra tanto la consistencia como la completitud del cálculo proposicional de PM, véase el comentario de van Heijenoort y la Introducción de Post de 1931 a una teoría general de proposiciones elementales en van Heijenoort 1967, pp. 264ff. También Tarski 1946, pp. 134ff.

[6] tario de van Heijenoort y Gödel, 1930, La completitud de los axiomas del cálculo funcional de la lógica en van Heijenoort 1967, pp. 582 y siguientes.

[7] . comentario de van Heijenoort y 1930 de Herbrand Sobre la consistencia de la aritmética en van Heijenoort 1967, págs. 618 y siguientes.

[8] Una prueba de consistencia a menudo presupone la consistencia de otra teoría. En la mayoría de los casos, esta otra teoría es la teoría de conjuntos de Zermelo-Fraenkel con o sin el axioma de elección (esto es equivalente, ya que se ha demostrado que estas dos teorías son equiconsistentes; es decir, si una es consistente, lo mismo es cierto para la otra).

[9] Esta definición es independiente de la elección de debido a las propiedades de sustitutividad de y la consistencia máxima de . $t_{i}$ $\equiv$ $\Phi$

[10] so común en muchas aplicaciones a otras áreas de las matemáticas, así como el modo ordinario de razonamiento de las matemáticas informales en el cálculo y las aplicaciones a la física, la química y la ingeniería.

[11] según las leyes de De Morgan