Non-well-founded set theory

Last updated

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 foundation axiom of ZFC is replaced by axioms implying its negation.

Contents

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 Peter Aczel’s hyperset theory in 1988. [1] [2] [3] The theory of non-well-founded sets has been applied in the logical modelling of non-terminating 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. [4]

Details

In 1917, Dmitry Mirimanoff introduced [5] [6] [7] [8] the concept of well-foundedness of a set:

A set, x0, is well-founded if it has no infinite descending membership sequence

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− (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. [7] 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 von Neumann 1925–1929) interest in non-well-founded sets waned for decades. [9] 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. [10] The next axiom proposal came in a 1960 congress talk of Dana Scott (never published as a paper), proposing an alternative axiom now called SAFA. [11] 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. [12] Boffa's idea was to make foundation fail as badly as it can (or rather, as extensionality permits): Boffa's axiom implies that every extensional 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 independent anti-foundation axioms are well-known, sometimes abbreviated by the first letter in the following list:

  1. AFA ("Anti-Foundation Axiom") – due to M. Forti and F. Honsell (this is also known as Aczel's anti-foundation axiom);
  2. SAFA ("Scott’s AFA") – due to Dana Scott,
  3. FAFA ("Finsler’s AFA") – due to Paul Finsler,
  4. BAFA ("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 graphs (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 so-called Quine atom, formally defined by Q={Q}, exists and is unique.

Each of the axioms given above extends the universe of the previous, so that: V ⊆ A ⊆ S ⊆ F ⊆ B. In the Boffa universe, the distinct Quine atoms form a proper class. [13]

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

Aczel’s hypersets were extensively used by Jon Barwise and John Etchemendy in their 1987 book The Liar, on the liar's paradox; The book is also a good introduction to the topic of non-well-founded sets.

Boffa’s superuniversality axiom has found application as a basis for axiomatic nonstandard analysis. [14]

See also

Notes

  1. ↑ Pakkan & Akman (1994), section link.
  2. ↑ Rathjen (2004).
  3. ↑ Sangiorgi (2011), pp. 17–19, 26.
  4. ↑ Ballard & Hrbáček (1992).
  5. ↑ Levy (2002), p. 68.
  6. ↑ Hallett (1986), p.  186.
  7. 1 2 Aczel (1988), p. 105.
  8. ↑ Mirimanoff (1917).
  9. ↑ Aczel (1988), p. 107.
  10. ↑ Aczel (1988), pp. 107–8.
  11. ↑ Aczel (1988), pp. 108–9.
  12. ↑ Aczel (1988), p. 110.
  13. ↑ Nitta, Okada & Tsouvaras (2003).
  14. ↑ Kanovei & Reeken (2004), p. 303.

Related Research Articles

In mathematics, the axiom of regularity is an axiom of Zermelo–Fraenkel set theory that states that every non-empty set A contains an element that is disjoint from A. In first-order logic, the axiom reads:

<span class="mw-page-title-main">Set theory</span> Branch of mathematics that studies sets

Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory — as a branch of mathematics — is mostly concerned with those that are relevant to mathematics as a whole.

In mathematical logic, Russell's paradox is a set-theoretic paradox published by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains an unrestricted comprehension principle leads to contradictions. The paradox had already been discovered independently in 1899 by the German mathematician Ernst Zermelo. However, Zermelo did not publish the idea, which remained known only to David Hilbert, Edmund Husserl, and other academics at the University of Göttingen. At the end of the 1890s, Georg Cantor – considered the founder of modern set theory – had already realized that his theory would lead to a contradiction, as he told Hilbert and Richard Dedekind by letter.

In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. Today, Zermelo–Fraenkel set theory, with the historically controversial axiom of choice (AC) included, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics. Zermelo–Fraenkel set theory with the axiom of choice included is abbreviated ZFC, where C stands for "choice", and ZF refers to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded.

In set theory, several ways have been proposed to construct the natural numbers. These include the representation via von Neumann ordinals, commonly employed in axiomatic set theory, and a system based on equinumerosity that was proposed by Gottlob Frege and by Bertrand Russell.

In set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted by V, is the class of hereditary well-founded sets. This collection, which is formalized by Zermelo–Fraenkel set theory (ZFC), is often used to provide an interpretation or motivation of the axioms of ZFC. The concept is named after John von Neumann, although it was first published by Ernst Zermelo in 1930.

In the foundations of mathematics, von Neumann–Bernays–Gödel set theory (NBG) is an axiomatic set theory that is a conservative extension of Zermelo–Fraenkel–choice set theory (ZFC). NBG introduces the notion of class, which is a collection of sets defined by a formula whose quantifiers range only over sets. NBG can define classes that are larger than sets, such as the class of all sets and the class of all ordinals. Morse–Kelley set theory (MK) allows classes to be defined by formulas whose quantifiers range over classes. NBG is finitely axiomatizable, while ZFC and MK are not.

In set theory, a branch of mathematics, an urelement or ur-element is an object that is not a set, but that may be an element of a set. It is also referred to as an atom or individual. Ur-elements are also not identical with the empty set.

Internal set theory (IST) is a mathematical theory of sets developed by Edward Nelson that provides an axiomatic basis for a portion of the nonstandard analysis introduced by Abraham Robinson. Instead of adding new elements to the real numbers, Nelson's approach modifies the axiomatic foundations through syntactic enrichment. Thus, the axioms introduce a new term, "standard", which can be used to make discriminations not possible under the conventional ZFC axioms for sets. Thus, IST is an enrichment of ZFC: all axioms of ZFC are satisfied for all classical predicates, while the new unary predicate "standard" satisfies three additional axioms I, S, and T. In particular, suitable nonstandard elements within the set of real numbers can be shown to have properties that correspond to the properties of infinitesimal and unlimited elements.

Kenneth Jon Barwise was an American mathematician, philosopher and logician who proposed some fundamental revisions to the way that logic is understood and used.

In mathematical logic, New Foundations (NF) is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica.

In mathematical logic, the Mostowski collapse lemma, also known as the Shepherdson–Mostowski collapse, is a theorem of set theory introduced by Andrzej Mostowski and John Shepherdson.

In the foundations of mathematics, Morse–Kelley set theory (MK), Kelley–Morse set theory (KM), Morse–Tarski set theory (MT), Quine–Morse set theory (QM) or the system of Quine and Morse is a first-order axiomatic set theory that is closely related to von Neumann–Bernays–Gödel set theory (NBG). While von Neumann–Bernays–Gödel set theory restricts the bound variables in the schematic formula appearing in the axiom schema of Class Comprehension to range over sets alone, Morse–Kelley set theory allows these bound variables to range over proper classes as well as sets, as first suggested by Quine in 1940 for his system ML.

Tarski–Grothendieck set theory is an axiomatic set theory. It is a non-conservative extension of Zermelo–Fraenkel set theory (ZFC) and is distinguished from other axiomatic set theories by the inclusion of Tarski's axiom, which states that for each set there is a Grothendieck universe it belongs to. Tarski's axiom implies the existence of inaccessible cardinals, providing a richer ontology than ZFC. For example, adding this axiom supports category theory.

An approach to the foundations of mathematics that is of relatively recent origin, Scott–Potter set theory is a collection of nested axiomatic set theories set out by the philosopher Michael Potter, building on earlier work by the mathematician Dana Scott and the philosopher George Boolos.

In the foundations of mathematics, Aczel's anti-foundation axiom is an axiom set forth by Peter Aczel, as an alternative to the axiom of foundation in Zermelo–Fraenkel set theory. It states that every accessible pointed directed graph corresponds to exactly one set. In particular, according to this axiom, the graph consisting of a single vertex with a loop corresponds to a set that contains only itself as element, i.e. a Quine atom. A set theory obeying this axiom is necessarily a non-well-founded set theory.

In situation theory, situation semantics attempts to provide a solid theoretical foundation for reasoning about common-sense and real world situations, typically in the context of theoretical linguistics, theoretical philosophy, or applied natural language processing,

<span class="mw-page-title-main">Dmitry Mirimanoff</span> Russian-Swiss mathematician (1861–1945)

Dmitry Semionovitch Mirimanoff was a member of the Moscow Mathematical Society in 1897. And later became a doctor of mathematical sciences in 1900, in Geneva, and taught at the universities of Geneva and Lausanne.

In philosophy, specifically metaphysics, mereology is the study of parthood relationships. In mathematics and formal logic, wellfoundedness prohibits for any x.

References

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.