Editing Non-well-founded set theory

{{Short description|Theory that allows sets to be elements of themselves}}
'''Non-well-founded set theories''' are variants of [[axiomatic set theory]] that allow sets to be elements of themselves and otherwise violate the rule of [[well-foundedness]]. In non-well-founded set theories, the [[axiom of regularity|foundation axiom]] of [[ZFC]] is replaced by axioms implying its negation.

The study of non-well-founded sets was initiated by [[Dmitry Mirimanoff]] in a series of papers between 1917 and 1920, in which he formulated the distinction between well-founded and non-well-founded sets; he did not regard well-foundedness as an [[axiom]]. Although a number of axiomatic systems of non-well-founded sets were proposed afterwards, they did not find much in the way of applications until the book Non-Well-Founded Sets by [[Peter Aczel]] introduces [[Non-well-founded set theory#Applications|hyperset theory]] in 1988.{{sfnp|Pakkan|Akman|1994|loc=[http://tinf2.vub.ac.be/~dvermeir/mirrors/www.cs.bilkent.edu.tr/%257Eakman/jour-papers/air/node8.html section link]}}{{sfnp|Rathjen|2004|p=}}{{sfnp|Sangiorgi|2011|pp=17–19, 26}}

The theory of non-well-founded sets has been applied in the [[logic]]al [[model (abstract)|modelling]] of non-terminating [[Computing|computational]] processes in computer science ([[process algebra]] and [[final semantics]]), [[linguistics]] and [[natural language]] [[semantics]] ([[situation theory]]), philosophy (work on the [[Liar Paradox]]), and in a different setting, [[non-standard analysis]].{{sfnp|Ballard|Hrbáček|1992|p=}}

== Details ==
In 1917, Dmitry Mirimanoff introduced{{sfnp|Levy|2012|p=68}}{{sfnp|Hallett|1986|p=[https://books.google.com/books?id=TM3AKPYdQVgC&pg=PA186 186]}}{{sfnp|Aczel|1988|p=105}}{{sfnp|Mirimanoff|1917|p=}} the concept of [[well-founded set|well-foundedness]] of a set:

:A set, x<sub>0</sub>, is well-founded if it has no infinite descending membership sequence <math> \cdots \in x_2 \in x_1 \in x_0. </math>

In ZFC, there is no infinite descending ∈-sequence by the [[axiom of regularity]]. In fact, the axiom of regularity is often called the ''foundation axiom'' since it can be proved within ZFC<sup>−</sup> (that is, ZFC without the axiom of regularity) that well-foundedness implies regularity. In variants of ZFC without the [[axiom of regularity]], the possibility of non-well-founded sets with set-like ∈-chains arises. For example, a set ''A'' such that ''A'' ∈ ''A'' is non-well-founded.

Although Mirimanoff also introduced a notion of isomorphism between possibly non-well-founded sets, he considered neither an axiom of foundation nor of anti-foundation.{{sfnp|Aczel|1988|p=105}} In 1926, [[Paul Finsler]] introduced the first axiom that allowed non-well-founded sets. After Zermelo adopted Foundation into his own system in 1930 (from previous work of [[John von Neumann|von Neumann]] 1925–1929) interest in non-well-founded sets waned for decades.{{sfnp|Aczel|1988|p=107}} An early non-well-founded set theory was [[Willard Van Orman Quine]]’s [[New Foundations]], although it is not merely ZF with a replacement for Foundation.

Several proofs of the independence of Foundation from the rest of ZF were published in 1950s particularly by [[Paul Bernays]] (1954), following an announcement of the result in an earlier paper of his from 1941, and by [[Ernst Specker]] who gave a different proof in his [[Habilitationsschrift]] of 1951, proof which was published in 1957. Then in 1957 [[Rieger's theorem]] was published, which gave a general method for such proof to be carried out, rekindling some interest in non-well-founded axiomatic systems.{{sfnp|Aczel|1988|pp=107–8}} The next axiom proposal came in a 1960 congress talk of [[Dana Scott]] (never published as a paper), proposing an alternative axiom now called [[Scott's anti-foundation axiom|SAFA]].{{sfnp|Aczel|1988|pp=108–9}} Another axiom proposed in the late 1960s was [[Maurice Boffa]]'s axiom of [[superuniversality]], described by Aczel as the highpoint of research of its decade.{{sfnp|Aczel|1988|p=110}} Boffa's idea was to make foundation fail as badly as it can (or rather, as extensionality permits): Boffa's axiom implies that every [[extensionality|extensional]] [[binary relation|set-like]] relation is isomorphic to the elementhood predicate on a transitive class.

A more recent approach to non-well-founded set theory, pioneered by M. Forti and F. Honsell in the 1980s, borrows from computer science the concept of a [[bisimulation]]. Bisimilar sets are considered indistinguishable and thus equal, which leads to a strengthening of the [[axiom of extensionality]]. In this context, axioms contradicting the axiom of regularity are known as '''anti-foundation axioms''', and a set that is not necessarily well-founded is called a '''hyperset'''.

Four mutually [[Independence (mathematical logic)|independent]] anti-foundation axioms are well-known, sometimes abbreviated by the first letter in the following list:
# '''A'''FA ("Anti-Foundation Axiom") – due to M. Forti and F. Honsell (this is also known as [[Aczel's anti-foundation axiom]]);
# '''S'''AFA ("Scott’s AFA") – due to [[Dana Scott]],
# '''F'''AFA ("Finsler’s AFA") – due to [[Paul Finsler]],
# '''B'''AFA ("Boffa’s AFA") – due to [[Maurice Boffa]].
They essentially correspond to four different notions of equality for non-well-founded sets. The first of these, AFA, is based on [[accessible pointed graph]]s (apg) and states that two hypersets are equal if and only if they can be pictured by the same apg.  Within this framework, it can be shown that the equation ''x'' = {''x''} has one and only one solution, the unique [[Quine atom]] of the theory.

Each of the axioms given above extends the universe of the previous, so that: [[Von Neumann universe|V]] ⊆ A ⊆ S ⊆ F ⊆ B. In the Boffa universe, the distinct Quine atoms form a proper class.{{sfnp|Nitta|Okada|Tzouvaras|2003}}

It is worth emphasizing that hyperset theory is an extension of classical set theory rather than a replacement: the well-founded sets within a hyperset domain conform to classical set theory.

== Applications ==
In published research, non-well-founded sets are also called hypersets, in parallel to the [[Hyperreal number|hyperreal numbers]] of [[nonstandard analysis]].<ref name=":0">{{Citation |last=Moss |first=Lawrence S. |title=Non-wellfounded Set Theory |date=2018 |encyclopedia=The Stanford Encyclopedia of Philosophy |editor-last=Zalta |editor-first=Edward N. |url=https://plato.stanford.edu/archives/sum2018/entries/nonwellfounded-set-theory/ |access-date=2024-05-30 |edition=Summer 2018 |publisher=Metaphysics Research Lab, Stanford University}}</ref><ref>Hypersets (ucsd.edu)</ref>

The hypersets were extensively used by [[Jon Barwise]] and [[John Etchemendy]] in their 1987 book ''The Liar'', on the [[liar's paradox]]. The book's proposals contributed to the [[theory of truth]].<ref name=":0" /> The book is also a good introduction to the topic of non-well-founded sets.<ref name=":0" />

== See also ==
* [[Alternative set theory]]
* [[Universal set]]
* [[Turtles all the way down]]

== Notes ==
{{reflist|30em}}

== References ==
* {{citation |last=Aczel |first=Peter |title=Non-Well-Founded Sets |series=CSLI Lecture Notes |volume=14 |publisher=Stanford University, Center for the Study of Language and Information |place=Stanford, CA |year=1988 |pages=[https://archive.org/details/nonwellfoundedse0000acze/page/ xx+137] |isbn=0-937073-22-9 |url=https://archive.org/details/nonwellfoundedse0000acze/page/ |postscript=. |mr=0940014}}
* {{citation |first1=David |last1=Ballard |first2=Karel |last2=Hrbáček |title=Standard foundations for nonstandard analysis |journal=Journal of Symbolic Logic |volume=57 |year=1992 |pages=741–748 |postscript=. |jstor=2275304 |issue=2|doi=10.2307/2275304|s2cid=39158351 }}
* {{citation |last1=Barwise |first1=Jon |last2=Etchemendy |first2=John |year=1987 |title=The Liar: An Essay on Truth and Circularity |publisher=Oxford University Press |url=https://books.google.com/books?id=L3M8DwAAQBAJ |isbn=9780195059441}}
* {{citation |first1=Jon |last1=Barwise |first2=Lawrence S.  |last2=Moss |title=Vicious circles. On the mathematics of non-wellfounded phenomena |series=CSLI Lecture Notes |volume=60 |publisher=CSLI Publications |year=1996 |isbn=1-57586-009-0 }}
* {{citation |last=Boffa. |first=M. |title=Les ensembles extraordinaires |journal=Bulletin de la Société Mathématique de Belgique |volume=20 |pages=3–15 |year=1968 |zbl=0179.01602}}
* {{citation |last=Boffa |first=M. |title=Forcing et négation de l'axiome de Fondement |journal=Acad. Roy. Belgique, Mém. Cl. Sci., Coll. 8∘ |series=Série II |volume=40 |issue=7 |year=1972 |zbl=0286.02068}}
* {{citation |last=Devlin |first=Keith |author1-link=Keith Devlin |title=The Joy of Sets: Fundamentals of Contemporary Set Theory |year=1993 |publisher=Springer |isbn=978-0-387-94094-6|edition=2nd |chapter=§7. Non-Well-Founded Set Theory }}
* {{citation |last=Finsler |first=P. |title=Über die Grundlagen der Mengenlehre. I: Die Mengen und ihre Axiome |journal=Math. Z. |volume=25 |year=1926 |pages=683–713 |jfm=52.0192.01|doi=10.1007/BF01283862 }}; translation in {{cite book |last1=Finsler |first1=Paul |last2=Booth |first2=David |title=Finsler Set Theory: Platonism and Circularity : Translation of Paul Finsler's Papers on Set Theory with Introductory Comments |year=1996 |publisher=Springer |isbn=978-3-7643-5400-8}}
* {{citation |first=Michael |last=Hallett |title=Cantorian set theory and limitation of size |publisher=Oxford University Press |year=1986 |postscript=. |url=https://books.google.com/books?id=TM3AKPYdQVgC |isbn=9780198532835}}
* {{citation| last1=Kanovei |first1=Vladimir |author1-link=Vladimir Kanovei |last2=Reeken |first2=Michael |title=Nonstandard Analysis, Axiomatically|year=2004  |publisher=Springer |isbn=978-3-540-22243-9}}
* {{citation |first=Azriel |last=Levy |title=Basic set theory |publisher=Dover Publications |orig-year=2002 |postscript=. |url=https://books.google.com/books?id=zbGjAQAAQBAJ |year=2012 |isbn=9780486150734}}
* {{citation |last1=Mirimanoff |first1=D. |title=Les antinomies de Russell et de Burali-Forti et le probleme fondamental de la theorie des ensembles |year=1917 |journal=L'Enseignement Mathématique |volume=19 |pages=37–52 |postscript=. |jfm=46.0306.01}}
* {{citation
 | last1 = Nitta | first1 = Takashi <!-- publisher/MR metadata swapped -->
 | last2 = Okada | first2 = Tomoko <!-- publisher/MR metadata swapped -->
 | last3 = Tzouvaras | first3 = Athanassios
 | doi = 10.1002/malq.200310018
 | issue = 2
 | journal = Mathematical Logic Quarterly
 | mr = 1961461
 | pages = 187–200
 | title = Classification of non-well-founded sets and an application
 | url = https://users.auth.gr/~tzouvara/Texfiles.htm/non-well.pdf
 | volume = 49
 | year = 2003}}
* {{citation |last1=Pakkan |first1=M. J. |last2=Akman |first2=V. |author2-link=Varol Akman |doi=10.1007/BF00849061 |title=Issues in commonsense set theory |journal=Artificial Intelligence Review |volume=8 |issue=4 |pages=279–308 |year=1994|url=http://repository.bilkent.edu.tr/bitstream/11693/25955/1/Issues%20in%20commonsense%20set%20theory.pdf |hdl=11693/25955 |s2cid=6323872 |hdl-access=free }}
* {{citation|editor1-first=Godehard |editor1-last=Link|title=One Hundred Years of Russell ́s Paradox: Mathematics, Logic, Philosophy|year=2004|publisher=Walter de Gruyter|isbn=978-3-11-019968-0 |chapter=Predicativity, Circularity, and Anti-Foundation |last=Rathjen |first=M. | chapter-url=http://www1.maths.leeds.ac.uk/~rathjen/russelle.pdf}}
* {{citation |first=Davide |last=Sangiorgi | year=2011 |chapter=Origins of bisimulation and coinduction | editor1-first = Davide | editor1-last = Sangiorgi | editor2-first = Jan |editor2-last=Rutten |title=Advanced Topics in Bisimulation and Coinduction |publisher=Cambridge University Press| isbn=978-1-107-00497-9}}
* {{citation |last=Scott |first=Dana |title=A different kind of model for set theory |work=Unpublished paper, talk given at the 1960 Stanford Congress of Logic, Methodology and Philosophy of Science |year=1960}}

== Further reading ==
* {{cite encyclopedia |last=Moss |first=Lawrence S. |url=http://plato.stanford.edu/entries/nonwellfounded-set-theory/ | title=Non-wellfounded Set Theory |encyclopedia=Stanford Encyclopedia of Philosophy |date=2018 }}

== External links ==
* [[Metamath]] page on the [http://us.metamath.org/mpegif/ax-reg.html axiom of Regularity.] Fewer than 1% of that database's theorems are ultimately dependent on this axiom, as can be shown by a command ("show usage") in the Metamath program.

{{Mathematical logic}}
{{Set theory}}

[[Category:Self-reference]]
[[Category:Systems of set theory]]
[[Category:Wellfoundedness]]