Lógica infinita

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

Algunas lógicas infinitarias pueden tener propiedades diferentes a las de la lógica estándar de primer orden . En particular, las lógicas infinitarias pueden no ser compactas o completas . Las nociones de compacidad y completitud que son equivalentes en la lógica finitaria a veces no lo son en las lógicas infinitarias. Por lo tanto, para las lógicas infinitarias, se definen las nociones de compacidad fuerte y completitud fuerte. Este artículo aborda las lógicas infinitarias de tipo Hilbert , ya que se han estudiado ampliamente y constituyen las extensiones más sencillas de la lógica finitaria. Sin embargo, estas no son las únicas lógicas infinitarias 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]

Una palabra 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 evitar este problema se utilizan una serie de 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, se anota la longitud de la secuencia después. 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 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 }$

Todos los usos de sufijos y no son parte de los lenguajes infinitarios formales. ${\displaystyle \cdots }$

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

Lenguajes formales

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

• Dado un conjunto de fórmulas, entonces y son fórmulas. (En cada caso, la secuencia tiene 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 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 }$

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 complicadas que permiten símbolos de función y predicado de aridad infinita, con control de la aridad máxima de un símbolo de función y control de símbolos de predicado. ^[6] ${\displaystyle L_{\alpha \beta o\pi }}$ ${\displaystyle \pi \leq \alpha }$ ${\displaystyle \mathrm {o} }$ ${\displaystyle \mathrm {o} }$ ${\displaystyle \pi }$

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

Definición de lógica infinitaria de tipo Hilbert

Una teoría en lenguaje infinitario es un conjunto de oraciones en la lógica. Una prueba 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 utilizando una regla de inferencia. Como antes, se pueden utilizar todas las reglas de inferencia en lógica finitaria, junto con una adicional: ${\displaystyle T}$ ${\displaystyle L_{\alpha ,\beta }}$ ${\displaystyle T}$ ${\displaystyle T}$

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

Si bien no siempre es posible formar cierres universales , se pueden agregar símbolos constantes adicionales para cada variable y la relación de satisfacibilidad resultante permanece igual. ^[8] Para evitar esto, algunos autores usan 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_{\alpha ,\beta }}$ ${\displaystyle \beta }$

A continuación se presentan los esquemas axiomáticos 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 es 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.

Completitud, compacidad y fuerte completitud

Una teoría es cualquier conjunto de oraciones. La verdad de las afirmaciones en los modelos se define por recursión y concordará con la definición de lógica finitaria 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 verdadera 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 completa si para cualquier teoría T para cada oración S válida 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 contenga 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 }$

Conceptos expresables en lógica infinitaria

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 afirmación individual. Como consecuencia, muchas teorías, incluida la aritmética de Peano , que no pueden axiomatizarse adecuadamente en la lógica finitaria, pueden estarlo en una lógica infinitaria adecuada. Otros ejemplos incluyen las teorías de los campos no arquimedianos y los grupos libres de torsión . ^{[11] [ se necesita una mejor fuente ]} Estas tres teorías pueden definirse sin el uso de la cuantificación infinita; sólo se necesitan uniones infinitas ^[12] .

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

Lógicas infinitarias completas

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

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

La lógica de no es compacta, pero sí 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 arriba) entonces es fuertemente compacta (porque las pruebas en estas lógicas no pueden usar uno 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 infinitaria: 1885-1955". En Dalla Chiara, Maria 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, Roman (eds.). Teoría de conjuntos, aritmética y fundamentos de las matemáticas: teoremas, filosofías . Cambridge University Press. págs. 13–42. doi :10.1017/CBO9780511910616.003. ISBN 978-0-511-91061-6Archivado desde el original el 1 de marzo de 2024 . Consultado el 1 de marzo de 2024 .
4. Karp 1964, págs. 1–2.
5. Karp 1964, pág. 1.
6. Karp 1964, págs. 101-102.
7. Karp 1964, págs. 39–54.
8. Karp 1964, pág. 127.
9. JL Bell, "Infinitary Logic". Stanford Encyclopedia of Philosophy, revisada en 2023. Consultado el 26 de julio de 2024.
10. Chang, CC (1957). "Sobre la representación de álgebras booleanas α-completas". Transactions of the American Mathematical Society . 85 (1): 208–218. doi : 10.1090/S0002-9947-1957-0086792-1 .
11. Rosinger, Elemer E. (2010). "Cuatro desviaciones en matemáticas y física". arXiv : 1003.0360 . CiteSeerX 10.1.1.760.6726 . 
12. Bennett, David W. (1980). "Uniones". Notre Dame Journal of Formal Logic . 21 (1): 111–118. doi : 10.1305/ndjfl/1093882943 .
13. 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). Lenguas con expresiones de longitud infinita . North-Holland Publishing Company. doi :10.1016/S0049-237X(08)70423-3. ISBN 978-0-444-53401-9.
• Barwise, Jon (1969). "Lógica infinita y conjuntos admisibles". The Journal of Symbolic Logic . 34 (2): 226–252. doi :10.2307/2271099. JSTOR  2271099.