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 so-called "anti-foundation axioms".
The theory of hypersets 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 ), and philosophy (work on the Liar Paradox).
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 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. When working in such a system, a set that is not necessarily well-founded is called a hyperset. Clearly, if A ∈ A, then A is a non-well-founded hyperset.
Three distinct anti-foundation axioms are well-known:
- AFA (‘Anti-Foundation Axiom’) — due to M. Forti and F. Honsell;
- FAFA (‘Finsler’s AFA’) — due to P. Finsler;
- 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.