Non-well-founded set theory
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 logic
al 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
.
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.
One early non-well-founded set theory was Willard Van Orman Quine
’s New Foundations
.
Another was introduced by Maurice Boffa, 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:
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.
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.
Axiom of regularity
In mathematics, the axiom of regularity is one of the axioms of Zermelo-Fraenkel set theory and was introduced by...
of ZFC is replaced by axioms implying its negation.
The theory of non-well-founded sets has been applied in the logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
al modelling of non-terminating computational
Computational
Computational may refer to:* Computer* Computational algebra* Computational Aeroacoustics* Computational and Information Systems Laboratory* Computational and Systems Neuroscience* Computational archaeology* Computational auditory scene analysis...
processes in computer science (process algebra and final semantics), linguistics
Linguistics
Linguistics is the scientific study of human language. Linguistics can be broadly broken into three categories or subfields of study: language form, language meaning, and language in context....
and natural language
Natural language
In the philosophy of language, a natural language is any language which arises in an unpremeditated fashion as the result of the innate facility for language possessed by the human intellect. A natural language is typically used for communication, and may be spoken, signed, or written...
semantics
Semantics
Semantics is the study of meaning. It focuses on the relation between signifiers, such as words, phrases, signs and symbols, and what they stand for, their denotata....
(situation theory
Situation theory
Situation theory provides the mathematical foundations to situation semantics, and was developed by writers such as Jon Barwise and Keith Devlin in the 1980s. Due to certain foundational problems, the mathematics was framed in a non-well-founded set theory...
), philosophy (work on the Liar Paradox
Liar paradox
In philosophy and logic, the liar paradox or liar's paradox , is the statement "this sentence is false"...
), and in a different setting, non-standard analysis
Non-standard analysis
Non-standard analysis is a branch of mathematics that formulates analysis using a rigorous notion of an infinitesimal number.Non-standard analysis was introduced in the early 1960s by the mathematician Abraham Robinson. He wrote:...
.
Details
- A set, x0, is well-founded iffIFFIFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...
it has no infinite descending membership sequence:- · · ·
- · · ·
In ZFC, there is no infinite descending ∈-sequence by the axiom of regularity
Axiom of regularity
In mathematics, the axiom of regularity is one of the axioms of Zermelo-Fraenkel set theory and was introduced by...
. 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
Axiom of regularity
In mathematics, the axiom of regularity is one of the axioms of Zermelo-Fraenkel set theory and was introduced by...
, 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.
One early non-well-founded set theory was Willard Van Orman Quine
Willard Van Orman Quine
Willard Van Orman Quine was an American philosopher and logician in the analytic tradition...
’s New Foundations
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
.
Another was introduced by Maurice Boffa, with the idea of making foundation fail as badly as it can (or rather, as extensionality permits): Boffa's axiom implies that every extensional
Extensionality
In logic, extensionality, or extensional equality refers to principles that judge objects to be equal if they have the same external properties...
set-like
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
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
Bisimulation
In theoretical computer science a bisimulation is a binary relation between state transition systems, associating systems which behave in the same way in the sense that one system simulates the other and vice-versa....
. Bisimilar sets are considered indistinguishable and thus equal, which leads to a strengthening of the axiom of extensionality
Axiom of extensionality
In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of extensionality, or axiom of extension, is one of the axioms of Zermelo-Fraenkel set theory.- Formal statement :...
. 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:
- AFA (‘Anti-Foundation Axiom’) — due to M. Forti and F. Honsell (this is also known as Aczel's anti-foundation axiomAczel's anti-foundation axiomAczel's anti-foundation axiom is an axiom set forth by Peter Aczel in . It states that every accessible pointed directed graph corresponds to a unique set. In particular, the graph consisting of a single vertex with a loop corresponds to a set which contains only itself as element, i.e...
); - SAFA (‘Scott’s AFA’) — due to Dana ScottDana ScottDana Stewart Scott is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California...
, - FAFA (‘Finsler’s AFA’) — due to Paul FinslerPaul FinslerPaul Finsler was a German and Swiss mathematician.Finsler did his undergraduate studies at the Technische Hochschule Stuttgart, and his graduate studies at the University of Göttingen, where he received his Ph.D. in 1919 under the supervision of Constantin Carathéodory...
, - 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
Von Neumann universe
In set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted V, is the class of hereditary well-founded sets...
⊆ A ⊆ S ⊆ F ⊆ B. In the Boffa universe, the distinct Quine atoms form a proper class.
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.
External links
- MetamathMetamathMetamath is a computer-assisted proof checker. It has no specific logic embedded and can simply be regarded as a device to apply inference rules to formulas...
page on the axiom of Regularity. Scroll to the bottom to see how few Metamath theorems invoke this axiom.