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 ]}

Dado que se presenta un lenguaje con fórmulas infinitamente largas, no es posible escribirlas explícitamente. Para sortear este problema, se utilizan diversas convenciones de notación que, estrictamente hablando, no forman parte del lenguaje formal .${\displaystyle \cdots }$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${\displaystyle \bigvee _{\gamma <\delta }{A_{\gamma }}}$se utilizan para indicar una disyunción infinita sobre un conjunto de fórmulas de cardinalidad${\displaystyle \delta }$La misma notación puede aplicarse a los cuantificadores, por ejemplo${\displaystyle \forall _{\gamma <\delta }{V_{\gamma }:}}$. Esto pretende representar una secuencia infinita de cuantificadores: un cuantificador para cada${\displaystyle V_{\gamma }}$dónde${\displaystyle \gamma <\delta}$.

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

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${\displaystyle L_{\kappa,\lambda}}$,${\displaystyle \kappa }$regular ,${\displaystyle \lambda =0}$o${\displaystyle \omega \leq \lambda \leq \kappa }$, 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 ]}

• Dado un conjunto de fórmulas${\displaystyle A=\{A_{\gamma }|\gamma <\delta <\alpha \}}$con${\displaystyle |\alpha |<\kappa }$entonces${\displaystyle (A_{0}\lor A_{1}\lor \cdots)}$y${\displaystyle (A_{0}\land A_{1}\land \cdots )}$son fórmulas. (En cada caso la secuencia tiene longitud${\displaystyle \delta }$.)
• Dado un conjunto de variables${\displaystyle V=\{V_{\gamma }|\gamma <\delta <\beta \}}$con${\displaystyle |\beta |<\lambda }$y una fórmula${\displaystyle A_{0}}$entonces${\displaystyle \forall V_{0}:\forall V_{1}\cdots (A_{0})}$y${\displaystyle \exists V_{0}:\exists V_{1}\cdots (A_{0})}$son fórmulas. (En cada caso la secuencia de cuantificadores tiene longitud${\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${\displaystyle L_{\kappa \,\lambda o\pi }}$con${\displaystyle \pi \leq \kappa }$un cardinal infinito y algunas restricciones más complicadas en${\displaystyle \mathrm {o} }$que permiten símbolos de función y predicado de aridad infinita, con${\displaystyle \mathrm {o} }$controlar la aridad máxima de un símbolo de función y${\displaystyle \pi }$símbolos de predicado de control. ^{[ 6 ]}

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${\displaystyle T}$en lenguaje infinito${\displaystyle L_{\alfa,\beta }}$es un conjunto de oraciones en la lógica. Una demostración en lógica infinita a partir de una teoría${\displaystyle T}$es una secuencia (posiblemente infinita) de enunciados que obedece las siguientes condiciones: Cada enunciado es un axioma lógico, un elemento de${\displaystyle T}$o se deduce de enunciados anteriores utilizando una regla de inferencia . Como antes, se pueden utilizar todas las reglas de inferencia en lógica finita, junto con una adicional:

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

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

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

• ${\displaystyle ((\land _{\epsilon <\delta }{(A_{\delta }\implies A_{\epsilon })})\implies (A_{\delta }\implies \land _{\epsilon <\delta }{A_{\epsilon }}))}$
• Para cada${\displaystyle \gamma <\delta}$,${\displaystyle ((\land _{\epsilon <\delta }{A_{\epsilon }})\implies A_{\gamma })}$
• Las leyes de distributividad de Chang (para cada${\displaystyle \gamma }$):${\displaystyle (\lor _{\mu <\gamma }{(\land _{\delta <\gamma }{A_{\mu ,\delta }})})}$, dónde${\displaystyle \forall \mu \forall \delta \exists \epsilon <\gamma :A_{\mu ,\delta }=A_{\epsilon }}$o${\displaystyle A_{\mu,\delta}=\neg A_{\epsilon }}$, y${\displaystyle \forall g\in \gamma ^{\gamma }\exists \epsilon <\gamma$ :\{A_{\epsilon },\neg A_{\epsilon }\}\subseteq \{A_{\mu ,g(\mu )}:\mu <\gamma \}}
• Para${\displaystyle \gamma <\alpha}$,${\displaystyle ((\land _{\mu <\gamma }{(\lor _{\delta <\gamma }{A_{\mu ,\delta }})})\implica (\lor _{\epsilon <\gamma ^{\gamma }}{(\land _{\mu <\gamma }{A_{\mu ,\gamma _{\epsilon }(\mu )})}}))}$, dónde${\displaystyle \{\gamma _{\epsilon }:\epsilon <\gamma ^{\gamma }\}}$es un buen orden de${\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${\displaystyle L_{\alfa,\beta }}$Una lógica 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.

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

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${\displaystyle {\mathcal {L}}_{\omega _{1},\omega }}$. ^{[ 12 ]}

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

La lógica de${\displaystyle L_{\omega ,\omega }}$También es muy completo, compacto y muy compacto.

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

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

• 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}}: Incompatibilidad de ISBN/Fecha ( ayuda )
• Barwise, Jon (1969). "Lógica infinita y conjuntos admisibles". The Journal of Symbolic Logic . 34 (2): 226– 252. doi : 10.2307/2271099 . JSTOR 2271099 .