Non-well-founded Set Theory - Details

Details

In 1917, Dmitry Mirimanoff introduced the concept of well-foundedness of a set:

A set, x₀, is well-founded iff 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. 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. 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 the 1950's particularly by Paul Bernays (1954), following an announcement of the result in earlier paper of his from 1941, and by Ernst Specker who gave a different proof in his Habilitationschrift 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. 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. 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. 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 axiom 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.

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.