Teoría de conjuntos sin fundamento

Las teorías de conjuntos no bien fundadas (a veces sin guion , como nonwellfounded ; ^{[ 1 ]} o poorly foundation ^{[ 2 ]} ) son variantes de la teoría axiomática de conjuntos que permiten que los conjuntos sean elementos de sí mismos y, por lo demás, violan la regla de buena fundación . En las teorías de conjuntos no bien fundadas, el axioma de fundación de ZFC se reemplaza por axiomas que implican su negación.

El estudio de los conjuntos no bien fundados fue iniciado por Dmitry Mirimanoff en una serie de artículos publicados entre 1917 y 1920, en los que formuló la distinción entre conjuntos bien fundados y no bien fundados; no consideró la buena fundación como un axioma . Aunque posteriormente se propusieron varios sistemas axiomáticos de conjuntos no bien fundados, no tuvieron mucha aplicación hasta que el libro Non-Well-Founded Sets de Peter Aczel introdujo la teoría de hiperconjuntos en 1988. ^{[ 3 ] [ 4 ] [ 5 ]}

La teoría de conjuntos no bien fundados se ha aplicado en el modelado lógico de procesos computacionales no terminantes en ciencias de la computación ( álgebra de procesos y semántica final ), lingüística y semántica del lenguaje natural ( teoría de la situación ), filosofía (trabajo sobre la paradoja del mentiroso ) y en un contexto diferente, análisis no estándar . ^{[ 6 ]}

En 1917, Dmitry Mirimanoff introdujo ^{[ 7 ] [ 8 ] [ 9 ] [ 10 ]} el concepto de buena fundamentación de un conjunto:

Un conjunto, x ₀ , está bien fundado si no tiene una secuencia de pertenencia descendente infinita.${\displaystyle \cdots \in x_{2}\in x_{1}\in x_{0}.}$

En ZFC, no existe una secuencia ∈ descendente infinita según el axioma de regularidad . De hecho, el axioma de regularidad se suele denominar axioma fundamental, ya que se puede demostrar dentro de ZFC ⁻ (es decir, ZFC sin el axioma de regularidad) que la buena fundamentación implica regularidad. En variantes de ZFC sin el axioma de regularidad , surge la posibilidad de conjuntos no bien fundados con cadenas ∈ de tipo conjunto. Por ejemplo, un conjunto A tal que A ∈ A no está bien fundado.

Aunque Mirimanoff también introdujo una noción de isomorfismo entre conjuntos posiblemente no bien fundados, no consideró ni un axioma de fundación ni de antifundación. ^{[ 9 ]} En 1926, Paul Finsler introdujo el primer axioma que permitía conjuntos no bien fundados. Después de que Zermelo adoptara Fundación en su propio sistema en 1930 (a partir del trabajo de von Neumann de 1925-1929), el interés en los conjuntos no bien fundados disminuyó durante décadas. ^{[ 11 ]} Una teoría temprana de conjuntos no bien fundados fue Nuevas Fundaciones de Willard Van Orman Quine , aunque no es simplemente ZF con un reemplazo para Fundación.

Varias pruebas de la independencia de Foundation del resto de ZF fueron publicadas en la década de 1950, particularmente por Paul Bernays (1954), luego de un anuncio del resultado en un artículo anterior suyo de 1941, y por Ernst Specker, quien dio una prueba diferente en su Habilitationsschrift de 1951, prueba que fue publicada en 1957. Luego, en 1957, se publicó el teorema de Rieger , que dio un método general para llevar a cabo dicha prueba, reavivando cierto interés en los sistemas axiomáticos no bien fundados. ^{[ 12 ]} La siguiente propuesta de axioma llegó en una charla de congreso de 1960 de Dana Scott (nunca publicada como artículo), proponiendo un axioma alternativo ahora llamado SAFA . ^{[ 13 ]} Otro axioma propuesto a finales de la década de 1960 fue el axioma de superuniversalidad de Maurice Boffa , descrito por Aczel como el punto culminante de la investigación de su década. ^{[ 14 ]} La idea de Boffa era hacer que la fundación fallara lo peor posible (o más bien, como lo permita la extensionalidad): el axioma de Boffa implica que toda relación extensional de tipo conjunto es isomorfa al predicado de elemento en una clase transitiva .

Un enfoque más reciente de la teoría de conjuntos no bien fundados, impulsado por M. Forti y F. Honsell en la década de 1980, toma prestado de la informática el concepto de bisimulación . Los conjuntos bisimilares se consideran indistinguibles y, por lo tanto, iguales, lo que fortalece el axioma de extensionalidad . En este contexto, los axiomas que contradicen el axioma de regularidad se conocen como axiomas de antifundación , y un conjunto que no necesariamente está bien fundado se denomina hiperconjunto .

Se conocen cuatro axiomas antifundamentales mutuamente excluyentes, a veces abreviados por la primera letra de la siguiente lista:

1. A FA ("Axioma Antifundacional") – debido a M. Forti y F. Honsell (esto también se conoce como el axioma antifundacional de A czel );
2. S AFA ("AFA de Scott") – debido a Dana Scott ,
3. F AFA ("Finsler's AFA") – debido a Paul Finsler ,
4. B AFA ("AFA de Boffa") - debido a Maurice Boffa .

En esencia, corresponden a cuatro nociones diferentes de igualdad para conjuntos no bien fundados. La primera de ellas, AFA, se basa en grafos accesibles con puntos (apg) y establece que dos hiperconjuntos son iguales si y solo si pueden representarse mediante el mismo apg. Dentro de este marco, se puede demostrar que la ecuación x = { x } tiene una única solución: el átomo de Quine único de la teoría.

Cada uno de los axiomas dados anteriormente extiende el universo del anterior, de modo que: V ⊆ A ⊆ S ⊆ F ⊆ B . En el universo de Boffa, los distintos átomos de Quine forman una clase propia . ^{[ 15 ]}

Cabe destacar que la teoría de hiperconjuntos es una extensión de la teoría clásica de conjuntos, y no un reemplazo: los conjuntos bien fundados dentro de un dominio de hiperconjuntos se ajustan a la teoría clásica de conjuntos.

En las investigaciones publicadas, los conjuntos no bien fundados también se denominan hiperconjuntos, en paralelo a los números hiperreales del análisis no estándar . ^{[ 16 ] [ 17 ]}

Los hiperconjuntos fueron ampliamente utilizados por Jon Barwise y John Etchemendy en su libro de 1987 , El mentiroso , sobre la paradoja del mentiroso . Las propuestas del libro contribuyeron a la teoría de la verdad . ^{[ 16 ]} El libro también es una buena introducción al tema de los conjuntos no bien fundados. ^{[ 16 ]}

• Teoría de conjuntos alternativa
• Conjunto universal
• Tortugas hasta el fondo

• Aczel, Peter (1988), Non-Well-Founded Sets , CSLI Lecture Notes, vol.  14, Stanford, CA: Stanford University, Center for the Study of Language and Information, pp. xx+137 , ISBN  0-937073-22-9, MR 0940014 . 
• Ballard, David; Hrbáček, Karel (1992), "Fundamentos estándar para el análisis no estándar", Journal of Symbolic Logic , 57 (2): 741– 748, doi : 10.2307/2275304 , JSTOR 2275304 , S2CID 39158351 .  
• Barwise, Jon; Etchemendy, John (1987), El mentiroso: Un ensayo sobre la verdad y la circularidad , Oxford University Press, ISBN 9780195059441
• Barwise, Jon; Moss, Lawrence S. (1996), Círculos viciosos. Sobre las matemáticas de los fenómenos no bien fundamentados , CSLI Lecture Notes, vol.  60, CSLI Publications, ISBN 1-57586-009-0
• Boffa., M. (1968), "Les ensembles extraordinaires", Bulletin de la Société Mathématique de Belgique , 20 : 3– 15, Zbl 0179.01602 
• Boffa, M. (1972), "Forcing et négation de l'axiome de Fondement", Acad. Roy. Bélgica, Mém. Cl. Ciencia, col. 8∘ , Serie II, 40 (7), Zbl 0286.02068 
• Devlin, Keith (1993), "§7. Teoría de conjuntos no bien fundamentada", The Joy of Sets: Fundamentals of Contemporary Set Theory (2.ª  ed.), Springer, ISBN 978-0-387-94094-6
• Finsler, P. (1926), "Über die Grundlagen der Mengenlehre. I: Die Mengen und ihre Axiome", Math. Z. , 25 : 683– 713, doi : 10.1007/BF01283862 , JFM 52.0192.01 ; traducción en Finsler, Paul; Booth, David (1996). Finsler Set Theory: Platonism and Circularity : Translation of Paul Finsler's Papers on Set Theory with Introductory Comments . Springer. ISBN  978-3-7643-5400-8.
• Hallett, Michael (1986), Teoría de conjuntos cantorianos y limitación del tamaño , Oxford University Press, ISBN 9780198532835.
• Kanovei, Vladimir ; Reeken, Michael (2004), Análisis no estándar, axiomáticamente , Springer, ISBN 978-3-540-22243-9
• Levy, Azriel (2012) [2002], Teoría básica de conjuntos , Dover Publications, ISBN 9780486150734.
• Mirimanoff, D. (1917), "Les antinomies de Russell et de Burali-Forti et le probleme fondamental de la theorie des ensembles", L'Enseignement Mathématique , 19 : 37– 52, JFM 46.0306.01 . 
• Nitta, Takashi; Okada, Tomoko; Tzouvaras, Athanassios (2003), "Clasificación de conjuntos no bien fundados y una aplicación" (PDF) , Mathematical Logic Quarterly , 49 (2): 187–200 , doi : 10.1002/malq.200310018 , MR 1961461 
• Pakkan, MJ; Akman, V. (1994), "Problemas en la teoría de conjuntos de sentido común" (PDF) , Artificial Intelligence Review , 8 (4): 279–308 , doi : 10.1007/BF00849061 , hdl : 11693/25955 , S2CID 6323872 
• Rathjen, M. (2004), "Predicatividad, circularidad y antifundación" (PDF) , en Link, Godehard (ed.), Cien años de la paradoja de Russell: matemáticas, lógica y filosofía , Walter de Gruyter, ISBN 978-3-11-019968-0
• Sangiorgi, Davide (2011), «Orígenes de la bisimulación y la coinducción», en Sangiorgi, Davide; Rutten, Jan (eds.), Temas avanzados en bisimulación y coinducción , Cambridge University Press, ISBN 978-1-107-00497-9
• Scott, Dana (1960), "Un tipo diferente de modelo para la teoría de conjuntos", Documento inédito, ponencia presentada en el Congreso de Lógica, Metodología y Filosofía de la Ciencia de Stanford de 1960.

• Moss, Lawrence S. (2018). "Teoría de conjuntos no bien fundamentada" . Enciclopedia de filosofía de Stanford .

• Página de Metamath sobre el axioma de regularidad. Menos del 1% de los teoremas de esa base de datos dependen en última instancia de este axioma, como se puede comprobar con el comando ("show usage") del programa Metamath.