Lógica infinita

Una lógica infinita es una lógica que permite declaraciones infinitamente largas y/o pruebas 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 o completas . Las nociones de compacidad y completitud que son equivalentes en lógica finita a veces no lo son en lógica infinitaria. Por lo tanto, para la lógica infinita, se definen nociones de compacidad fuerte y completitud fuerte. Este artículo aborda las lógicas infinitarias de tipo Hilbert , ya que han sido ampliamente estudiadas y constituyen las extensiones más sencillas de la lógica finita. Sin embargo, éstas no son las únicas lógicas infinitas que se han formulado o estudiado.

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

Unas palabras sobre la notación y el axioma de elección.

Como se presenta un lenguaje con fórmulas infinitamente largas, no es posible escribir dichas fórmulas explícitamente. Para solucionar este problema se utilizan una serie de ventajas 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 duración de la secuencia se anota 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 se puede aplicar a los cuantificadores, por ejemplo . Esto pretende representar una secuencia infinita de cuantificadores: un cuantificador para cada lugar . ${\displaystyle \cdots }$ ${\displaystyle \bigvee _{\gamma <\delta }{A_{\gamma }}}$ ${\displaystyle \delta }$ ${\displaystyle \forall _{\gamma <\delta }{V_{\gamma }:}}$ ${\displaystyle V_{\gamma }}$ ${\displaystyle \gamma <\delta }$

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

Se asume el axioma de elección (como se hace a menudo cuando se habla de lógica infinita) ya que es necesario para tener leyes de distributividad sensibles.

Definición de lógicas infinitas de tipo Hilbert

Un lenguaje infinito de primer orden L _{α , β} , α regular , β = 0 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 algunos adicionales:

• Dado un conjunto de fórmulas entonces y son fórmulas. (En cada caso, la secuencia tiene una longitud ). ${\displaystyle A=\{A_{\gamma }|\gamma <\delta <\alpha \}}$ ${\displaystyle (A_{0}\lor A_{1}\lor \cdots )}$ ${\displaystyle (A_{0}\land A_{1}\land \cdots )}$ ${\displaystyle \delta }$
• Dado un conjunto de variables y una fórmula, entonces y son fórmulas. (En cada caso, la secuencia de cuantificadores tiene una longitud .) ${\displaystyle V=\{V_{\gamma }|\gamma <\delta <\beta \}}$ ${\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 }$

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

Una teoría T en lenguaje infinito es un conjunto de oraciones en la lógica. Una prueba en lógica infinitaria de una teoría T es una secuencia (posiblemente infinita) de enunciados que obedece a las siguientes condiciones: Cada enunciado es un axioma lógico, un elemento de 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: ${\displaystyle L_{\alpha ,\beta }}$

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

Los esquemas de axiomas lógicos específicos de la lógica infinita se presentan a continuación. 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 , ${\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 , , ¿dónde 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 de axiomas requieren el axioma de elección porque ciertos conjuntos deben poder ordenarse bien . El último esquema de axioma es estrictamente innecesario, como lo implican las leyes de distributividad de Chang, ^[5] sin embargo se incluye como una forma natural de permitir debilitamientos naturales de la lógica.

Completitud, compacidad y gran integridad.

Una teoría es cualquier conjunto de oraciones. La verdad de las declaraciones en los modelos se define por recursividad y estará de acuerdo con la definición de lógica finita donde ambas están definidas. Dada una teoría T, se dice que una oración es válida para la teoría T si es cierta en todos los modelos de T.

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

Un cardinal es débilmente compacto cuando para cada teoría T 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 toda 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 }$

Conceptos expresables en lógica infinita

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 fundamento, esta afirmación no admite interpretaciones no estándar. El concepto de fundamento sólo puede expresarse en una lógica que permita infinitos cuantificadores en una declaración individual. Como consecuencia, muchas teorías, incluida la aritmética de Peano , que no pueden axiomatizarse adecuadamente en lógica finita, pueden hacerlo en una lógica infinita adecuada. Otros ejemplos incluyen las teorías de campos no arquimedianos y grupos libres de torsión . ^{[6] [ se necesita una mejor fuente ]} Estas tres teorías se pueden definir sin el uso de cuantificación infinita; sólo se necesitan infinitas uniones ^{[7] .}

Los predicados de verdad para lenguajes contables se pueden definir en . ^[8] ${\displaystyle {\mathcal {L}}_{\omega _{1},\omega }}$

Lógicas infinitas completas

Dos lógicas infinitas destacan en su plenitud. Estas son las lógicas de y . La primera es lógica finita estándar de primer orden y la segunda es una lógica infinita que solo permite declaraciones 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 de no logra ser compacta, pero es completa (según 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 (según los axiomas dados anteriormente), entonces es fuertemente compacta (porque las pruebas en estas lógicas no pueden usar o más de los axiomas dados). ${\displaystyle L_{\alpha ,\alpha }}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

Referencias

1. Moore, Gregory H. (1997). "La prehistoria de la lógica infinita: 1885-1955". En Dalla Chiara, María Luisa ; Doets, Kees; Mundici, Daniele; van Benthem, Johan (eds.). Estructuras y normas en la ciencia . Springer-Science+Business Media. págs. 105-123. doi :10.1007/978-94-017-0538-7_7. ISBN 978-94-017-0538-7.
2. Kanamori, Akihiro (2004). «Zermelo y la teoría de conjuntos» (PDF) . El Boletín de Lógica Simbólica . 10 (4): 487–553. doi : 10.2178/bsl/1102083759 . Consultado el 22 de agosto de 2023 .
3. Woodin, W. Hugh (2011). "La hipótesis del continuo, el multiverso genérico de conjuntos y la conjetura Ω". En Kennedy, Juliette ; Kossak, romano (eds.). Teoría de conjuntos, aritmética y fundamentos de las matemáticas: teoremas, filosofías . Prensa de la Universidad de Cambridge. págs. 13–42. doi :10.1017/CBO9780511910616.003. ISBN 978-0-511-91061-6. Consultado el 1 de marzo de 2024 .
4. Karp 1964, págs. 39–54.
5. Chang, CC (1957). "Sobre la representación de álgebras booleanas α-completas". Transacciones de la Sociedad Matemática Estadounidense . 85 (1): 208–218. doi : 10.1090/S0002-9947-1957-0086792-1 .
6. Rosinger, Elemer E. (2010). "Cuatro salidas en Matemáticas y Física". arXiv : 1003.0360 . CiteSeerX 10.1.1.760.6726 . 
7. Bennett, David W. (1980). "Uniones". Revista de lógica formal de Notre Dame . 21 (1): 111-118. doi : 10.1305/ndjfl/1093882943 .
8. Pogonowski, Jerzy (10 de junio de 2010). "Anhelo inexpresable por el modelo previsto" (PDF) . Zakład Logiki Stosowanej . Uniwersytet im. Adama Mickiewicza en Poznaniu . pag. 4 . Consultado el 1 de marzo de 2024 .

Fuentes

• Karp, Carol R. (1964). Lenguajes con expresiones de longitud infinita . Compañía editorial de Holanda Septentrional. doi :10.1016/S0049-237X(08)70423-3. ISBN 978-0-444-53401-9.
• Barwise, Jon (1969). "Lógica infinita y conjuntos admisibles". La revista de lógica simbólica . 34 (2): 226–252. doi :10.2307/2271099. JSTOR  2271099.