Non-well-founded set theory

From Wikipedia, the free encyclopedia

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.

[edit] Details

In 1917, Dmitry Mirimanov (also spelled Mirimanoff) introduced the concept of well-foundedness:

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 (for a proof see 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 arises. For example, a set A such that A ∈ A is non-well-founded.

The idea of working with variants of ZFC contradicting regularity is probably as old as the axiom of regularity itself. One of the first systematic non-well-founded set theories was introduced by M. Boffa. The 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.

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.

Three 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. FAFA (‘Finsler’s AFA’) — due to P. Finsler;
  3. SAFA (‘Scott’s AFA’) — due to Dana Scott;

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.

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.

[edit] References

Languages