Lógica infinita

Una lógica infinitaria es una lógica que permite enunciados infinitamente largos y/o demostraciones infinitamente largas . ^{[ 1 ]} El concepto fue introducido por Zermelo en la década de 1930. ^{[ 2 ]}

Algunas lógicas infinitas pueden tener propiedades diferentes a las de la lógica estándar de primer orden . En particular, las lógicas infinitas pueden no ser compactas ni completas . Las nociones de compacidad y completitud que son equivalentes en la lógica finita a veces no lo son en las lógicas infinitas. Por lo tanto, para las lógicas infinitas, se definen las nociones de compacidad fuerte y completitud fuerte. Este artículo aborda las lógicas infinitas de tipo Hilbert , ya que han sido ampliamente estudiadas y constituyen las extensiones más directas de la lógica finita. Sin embargo, estas no son las únicas lógicas infinitas que se han formulado o estudiado.

Considerar si una cierta lógica infinitaria llamada lógica Ω es completa promete arrojar luz sobre la hipótesis del continuo . ^{[ 3 ]}

Como se está presentando un lenguaje con fórmulas infinitamente largas, no es posible escribir dichas fórmulas explícitamente. Para sortear este problema, se utilizan varias conveniencias de notación que, estrictamente hablando, no forman parte del lenguaje formal . se utiliza para señalar una expresión que es infinitamente larga. Cuando no está claro, la longitud de la secuencia se indica posteriormente. Cuando esta notación se vuelve ambigua o confusa, se utilizan sufijos como para indicar una disyunción infinita sobre un conjunto de fórmulas de cardinalidad . La misma notación puede aplicarse a cuantificadores, por ejemplo . Esto pretende representar una secuencia infinita de cuantificadores: un cuantificador para cada donde . ${\displaystyle \cdots }$${\displaystyle \bigvee _ {\gamma <\delta }{A_{\gamma }}}$${\displaystyle \delta }$${\displaystyle \forall _{\gamma <\delta }{V_{\gamma }:}}$${\displaystyle V_{\gamma }}$${\displaystyle \gamma <\delta}$

Todo uso de sufijos y no forma parte de los lenguajes infinitarios formales. ${\displaystyle \cdots }$

Se da por sentado el axioma de elección (como suele hacerse al hablar de lógica infinitaria), ya que es necesario para tener leyes de distributividad sensatas.

Un lenguaje infinitario de primer orden , regular o , tiene el mismo conjunto de símbolos que una lógica finita y puede usar todas las reglas para la formación de fórmulas de una lógica finita junto con algunas adicionales: ^{[ 4 ]}${\displaystyle L_{\kappa,\lambda}}$${\displaystyle \kappa }$${\displaystyle \lambda =0}$${\displaystyle \omega \leq \lambda \leq \kappa }$

• Dada una serie de fórmulas con , entonces y son fórmulas. (En cada caso, la secuencia tiene longitud .)${\displaystyle A=\{A_{\gamma }|\gamma <\delta <\alpha \}}$${\displaystyle |\alpha |<\kappa }$${\displaystyle (A_{0}\lor A_{1}\lor \cdots)}$${\displaystyle (A_{0}\land A_{1}\land \cdots )}$${\displaystyle \delta }$
• Dado un conjunto de variables con y una fórmula, entonces y son fórmulas. (En cada caso, la secuencia de cuantificadores tiene longitud .)${\displaystyle V=\{V_{\gamma }|\gamma <\delta <\beta \}}$${\displaystyle |\beta |<\lambda }$${\displaystyle A_{0}}$${\displaystyle \forall V_{0}:\forall V_{1}\cdots (A_{0})}$${\displaystyle \exists V_{0}:\exists V_{1}\cdots (A_{0})}$${\displaystyle \delta }$

El lenguaje también puede tener símbolos de función, relación y predicado de aridad finita . ^{[ 5 ]} Karp también definió lenguajes con un cardinal infinito y algunas restricciones más complejas que permiten símbolos de función y predicado de aridad infinita, controlando la aridad máxima de un símbolo de función y controlando los símbolos de predicado. ^{[ 6 ]}${\displaystyle L_{\kappa \,\lambda o\pi }}$${\displaystyle \pi \leq \kappa }$${\displaystyle \mathrm {o} }$${\displaystyle \mathrm {o} }$${\displaystyle \pi }$

Los conceptos de variables libres y ligadas se aplican de la misma manera a las fórmulas infinitas. Al igual que en la lógica finita, una fórmula cuyas variables están todas ligadas se denomina sentencia .

Una teoría en lenguaje infinitario es un conjunto de enunciados en la lógica. Una demostración en lógica infinitaria a partir de una teoría es una secuencia (posiblemente infinita) de enunciados que obedece las siguientes condiciones: Cada enunciado es un axioma lógico, un elemento de , o se deduce de enunciados anteriores mediante una regla de inferencia . Como antes, se pueden usar todas las reglas de inferencia en lógica finita, junto con una adicional: ${\displaystyle T}$${\displaystyle L_{\alfa,\beta }}$${\displaystyle T}$${\displaystyle T}$

• Dado un conjunto de afirmaciones que han aparecido previamente en la demostración, entonces la afirmación puede inferirse. ^{[ 7 ]}${\displaystyle A=\{A_{\gamma }|\gamma <\delta <\alpha \}}$${\displaystyle \land _{\gamma <\delta }{A_{\gamma }}}$

Si bien la formación de cierres universales no siempre es posible, se pueden agregar símbolos constantes adicionales para cada variable, manteniendo la misma relación de satisfacibilidad. ^{[ 8 ]} Para evitar esto, algunos autores utilizan una definición diferente del lenguaje que prohíbe que las fórmulas tengan más de variables libres. ^{[ 9 ]}${\displaystyle \beta <\alpha}$${\displaystyle L_{\alfa,\beta }}$${\displaystyle \beta }$

A continuación se presentan los esquemas de axiomas lógicos específicos de la lógica infinitaria. Variables de esquemas globales: y tales que . ${\displaystyle \delta }$${\displaystyle \gamma }$${\displaystyle 0<\delta <\alpha}$

• ${\displaystyle ((\land _{\epsilon <\delta }{(A_{\delta }\implies A_{\epsilon })})\implies (A_{\delta }\implies \land _{\epsilon <\delta }{A_{\epsilon }}))}$
• Para cada uno ,${\displaystyle \gamma <\delta}$${\displaystyle ((\land _{\epsilon <\delta }{A_{\epsilon }})\implies A_{\gamma })}$
• Leyes de distributividad de Chang (para cada ): , donde o , y${\displaystyle \gamma }$${\displaystyle (\lor _{\mu <\gamma }{(\land _{\delta <\gamma }{A_{\mu ,\delta }})})}$${\displaystyle \forall \mu \forall \delta \exists \epsilon <\gamma :A_{\mu ,\delta }=A_{\epsilon }}$${\displaystyle A_{\mu,\delta}=\neg A_{\epsilon }}$${\displaystyle \forall g\in \gamma ^{\gamma }\exists \epsilon <\gamma :\{A_{\epsilon },\neg A_{\epsilon }\}\subseteq \{A_{\mu ,g(\mu )}:\mu <\gamma \}}$
• Para , , donde hay un buen ordenamiento de${\displaystyle \gamma <\alpha }$${\displaystyle ((\land _{\mu <\gamma }{(\lor _{\delta <\gamma }{A_{\mu ,\delta }})})\implies (\lor _{\epsilon <\gamma ^{\gamma }}{(\land _{\mu <\gamma }{A_{\mu ,\gamma _{\epsilon }(\mu )})}}))}$${\displaystyle \{\gamma _{\epsilon }:\epsilon <\gamma ^{\gamma }\}}$${\displaystyle \gamma ^{\gamma }}$

Los dos últimos esquemas axiomáticos requieren el axioma de elección porque ciertos conjuntos deben ser bien ordenables . El último esquema axiomático es estrictamente hablando innecesario, ya que las leyes de distributividad de Chang lo implican, ^{[ 10 ]} sin embargo, se incluye como una forma natural de permitir debilitamientos naturales de la lógica.

Una teoría es cualquier conjunto de enunciados. La veracidad de los enunciados en los modelos se define mediante recursión y coincidirá con la definición de lógica finita cuando ambas estén definidas. Dada una teoría T , se dice que un enunciado es válido para la teoría T si es verdadero en todos los modelos de T.

Una lógica en el lenguaje es completa si para cada enunciado S válido en cada modelo existe una prueba de S. Es fuertemente completa si para cualquier teoría T , para cada enunciado S válido en T existe una prueba de S a partir de T. Una lógica infinitaria puede ser completa sin ser fuertemente completa. ${\displaystyle L_{\alpha ,\beta }}$

Un cardinal es débilmente compacto cuando para cada teoría T en que contiene como máximo muchas fórmulas, si cada S T de cardinalidad menor que tiene un modelo, entonces T tiene un modelo. Un cardinal es fuertemente compacto cuando para cada teoría T en , sin restricción de tamaño, si cada S T de cardinalidad menor que tiene un modelo, entonces T tiene un modelo. ${\displaystyle \kappa \neq \omega }$${\displaystyle L_{\kappa ,\kappa }}$${\displaystyle \kappa }$${\displaystyle \subseteq }$${\displaystyle \kappa }$${\displaystyle \kappa \neq \omega }$${\displaystyle L_{\kappa ,\kappa }}$${\displaystyle \subseteq }$${\displaystyle \kappa }$

En el lenguaje de la teoría de conjuntos, la siguiente afirmación expresa fundamento :

${\displaystyle \forall _{\gamma <\omega }{V_{\gamma }:}\neg \land _{\gamma <\omega }{V_{\gamma +}\in V_{\gamma }}.\,}$

A diferencia del axioma de fundación, esta afirmación no admite interpretaciones no estándar. El concepto de buena fundación solo puede expresarse en una lógica que permita un número infinito de cuantificadores en una afirmación individual. En consecuencia, muchas teorías, incluida la aritmética de Peano , que no pueden axiomatizarse adecuadamente en lógica finita, pueden expresarse en una lógica infinita apropiada. Otros ejemplos incluyen las teorías de cuerpos no arquimedianos y grupos libres de torsión . Estas tres teorías pueden definirse sin el uso de cuantificación infinita; solo se necesitan uniones infinitas ^{[ 11 ]} .

Los predicados de verdad para lenguajes contables son definibles en . ^{[ 12 ]}${\displaystyle {\mathcal {L}}_{\omega _{1},\omega }}$

Dos lógicas infinitarias destacan por su completitud. Estas son las lógicas de y . La primera es una lógica finitaria de primer orden estándar y la segunda es una lógica infinitaria que solo admite enunciados de tamaño contable. ${\displaystyle L_{\omega ,\omega }}$${\displaystyle L_{\omega _{1},\omega }}$

La lógica de también es fuertemente completa, compacta y fuertemente compacta. ${\displaystyle L_{\omega ,\omega }}$

La lógica no es compacta, pero es completa (bajo los axiomas dados anteriormente). Además, satisface una variante de la propiedad de interpolación de Craig . ${\displaystyle L_{\omega _{1},\omega }}$

Si la lógica de es fuertemente completa (bajo los axiomas dados anteriormente), entonces es fuertemente compacta (porque las demostraciones en estas lógicas no pueden usar o más de los axiomas dados). ${\displaystyle L_{\alpha ,\alpha }}$${\displaystyle \alpha }$${\displaystyle \alpha }$

• Karp, Carol R. (1964). Lenguajes con expresiones de longitud infinita . North-Holland Publishing Company. doi : 10.1016/S0049-237X(08)70423-3 . ISBN 978-0-444-53401-9.{{cite book}}: ISBN / Date incompatibility (help)
• Barwise, Jon (1969). "Lógica infinita y conjuntos admisibles". The Journal of Symbolic Logic . 34 (2): 226– 252. doi : 10.2307/2271099 . JSTOR  2271099 .