Non-well-founded set theory


Non-well-founded set theory

Non-well-founded set theories are variants of axiomatic set theory which allow sets to contain 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.

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.[1]

Contents

Details

A set, x0, is well-founded iff it has no infinite descending membership sequence:
· · ·  \in x_2 \in x_1 \in x_0.

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 AA is non-well-founded.

One early non-well-founded set theory was Willard Van Orman Quine’s New Foundations. Another was introduced by Maurice Boffa,[citation needed] with the idea of making 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.

Another, more recent, approach to non-well-founded set theory, pioneered by M. Forti and F. Honsell, 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 non-equivalent anti-foundation axioms are well-known:

  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.

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 following axiom 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. [2]

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.

Notes

  1. ^ Ballard & Hrbáček (1992)
  2. ^ Nitta,Okada,Tsouvaras (2003)

References

See also

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Well-founded relation — In mathematics, a binary relation, R, is well founded (or wellfounded) on a class X if and only if every non empty subset of X has a minimal element with respect to R; that is, for every non empty subset S of X, there is an element m of S such… …   Wikipedia

  • set theory — the branch of mathematics that deals with relations between sets. [1940 45] * * * Branch of mathematics that deals with the properties of sets. It is most valuable as applied to other areas of mathematics, which borrow from and adapt its… …   Universalium

  • Set theory — This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects …   Wikipedia

  • Zermelo–Fraenkel set theory — Zermelo–Fraenkel set theory, with the axiom of choice, commonly abbreviated ZFC, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics.ZFC consists of a single primitive ontological notion, that of… …   Wikipedia

  • Alternative set theory — Generically, an alternative set theory is an alternative mathematical approach to the concept of set. It is a proposed alternative to the standard set theory. Some of the alternative set theories are: *the theory of semisets; *rough set theory;… …   Wikipedia

  • List of set theory topics — Logic portal Set theory portal …   Wikipedia

  • Scott–Potter set 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… …   Wikipedia

  • Minimal model (set theory) — In set theory, a minimal model is a minimal standard model of ZFC. Minimal models were introduced by (Shepherdson 1951, 1952, 1953). The existence of a minimal model cannot be proved in ZFC, even assuming that ZFC is consistent, but follows… …   Wikipedia

  • Well-order — In mathematics, a well order relation (or well ordering) on a set S is a total order on S with the property that every non empty subset of S has a least element in this ordering.Equivalently, a well ordering is a well founded total order.The set… …   Wikipedia

  • Theory of mind — is the ability to attribute mental states beliefs, intents, desires, pretending, knowledge, etc. to oneself and others and to understand that others have beliefs, desires and intentions that are different from one s own.[1] Though there are… …   Wikipedia