Aczel's anti-foundation axiom
Encyclopedia
Aczel'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. a Quine atom.
in the directed graph from the root to that node.
The antifoundation axiom postulates that each such directed graph corresponds to the membership structure of a unique set. For example, the directed graph with only one node and an edge from that node to itself corresponds to a set of the form x = {x}. A directed cycle graph
of length 2 corresponds to a set of the form x = { {x} }.
Axiom
In traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...
set forth by Peter Aczel
Peter Aczel
Peter Aczel is a British mathematician, logician and computer scientist based at the University of Manchester. He is known for his work in non-well-founded set theory and constructive mathematics.-External links:*http://www.cs.man.ac.uk/~petera/...
in . It states that every accessible pointed directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
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. a Quine atom.
Accessible pointed graphs
An accessible pointed graph is a directed graph with a distinguished element (the "root") such that for any node in the graph there is at least one pathPath (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
in the directed graph from the root to that node.
The antifoundation axiom postulates that each such directed graph corresponds to the membership structure of a unique set. For example, the directed graph with only one node and an edge from that node to itself corresponds to a set of the form x = {x}. A directed cycle graph
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
of length 2 corresponds to a set of the form x = { {x} }.
See also
- Axiom of foundation
- von Neumann universeVon Neumann universeIn 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...
- Non-well-founded set theoryNon-well-founded set theoryNon-well-founded set theories are variants of axiomatic set theory which allow sets to contain themselves and otherwise violate the rule of well-foundedness...