Foundation axiom

The axiom of foundation (also: axiom of regularity ) is an axiom of the set theory of John von Neumann from 1925, which was incorporated into the Neumann-Bernays-Gödel set theory (NBG), and an axiom of the widely used Zermelo-Fraenkel set theory (ZF) from 1930. Ernst Zermelo gave it the name and a simple formulation for a range of quantities and primordial elements with the following wording:

Each non-empty sub-area contains at least one element that has no element in . ${\displaystyle \,T}$ ${\displaystyle \,t_{0}}$ ${\displaystyle \,t}$ ${\displaystyle \,T}$

Formalized, the axiom of foundations for the area in the sense of the class of all sets and primitive elements ( all-class ) reads : ${\displaystyle \,{B}}$

${\displaystyle \emptyset \neq T\subseteq {B}\implies \exists t_{0}\in T:\lnot \exists t\in T:t\in t_{0}}$

In pure set theory, in which all variables denote sets, there are shorter formulations of the axiom of foundations in which the formula is eliminated, for example the following version: ${\displaystyle \,{B}}$

${\displaystyle \forall T:(T\neq \emptyset \implies \exists x\in T:(x\cap T)=\emptyset )}$

The element existing here is also called the ∈-minimal element of , since there is no element with . The axiom of foundation thus ensures the existence of a ∈-minimal element of every non-empty set. ${\displaystyle x\in T}$ ${\displaystyle T}$ ${\displaystyle y\in x}$ ${\displaystyle y\in T}$

Admissible inferences

The foundation axiom prevents cyclical element chains: . The set , the existence of which is secured with the help of the pair set and the union axiom, would then contradict the axiom of foundation that it has no ∈-minimal element. There is therefore no set that contains itself as elements ( ). Furthermore, the axiom of the foundation prevents the existence of a function defined on (understood as a set), including for all , since the image of this function, which exists as a set due to the replacement scheme , would not have a ∈-minimal element. Note, however, that no contradiction can be derived from the formula set , provided that ZFC is free of contradictions, because with such a proof of contradiction only a finite number of formulas could be used, which obviously would not lead to a contradiction. In other words, due to the compactness theorem there are, if there are models of ZFC, also models the element relation ∈ not respect sound are. If you consider a model of the formula set constructed above, there cannot be a set in this model that contains exactly that as an element. This set would contradict the axiom of foundation (it would not have a ∈-minimal element). ${\displaystyle x_{1}\in x_{2}\in \cdots \in x_{n}\in x_{1}}$ ${\displaystyle \{x_{1},x_{2},\dots ,x_{n}\}}$ ${\displaystyle \forall x:x\notin x}$ ${\displaystyle \omega }$ ${\displaystyle f}$ ${\displaystyle f(n+1)\in f(n)}$ ${\displaystyle n\in \omega }$ ${\displaystyle \mathrm {ZFC} \cup \left\{x_{n+1}\in x_{n}\mid n\in \mathbb {N} \right\}}$ ${\displaystyle x_{n}}$

Set theories without foundation axiom

There are also set theories without a foundation axiom. This includes the original Zermelo set theory , in which Zermelo explicitly calculated circular (or circular ) sets (with cyclic element chains, for example ), or the Ackermann set theory . In both cases, however, the axiom of foundation can be added without creating a contradiction (which did not exist before). Also to be mentioned is the set theory of Quine , who defined sets of individuals through , so that these are circular and the axiom of foundation definitely does not apply. In such set theories without a foundation axiom, circular sets are possible, which shows that they do not necessarily create a contradiction. The formation of certain circular sets like the universal set or the set of ordinal numbers , which generate contradictions in naive set theory , is already excluded in Zermelo set theory without a foundation axiom. In general, adding an axiom cannot prevent contradictions that would have existed without the axiom, since adding an axiom can only increase, but not decrease, the set of provable propositions. ${\displaystyle x\in x}$ ${\displaystyle \,x}$ ${\displaystyle \,\{x\}=x}$

prehistory

The idea of ​​considering ∈-based sets as normal sets goes back to Dmitry Mirimanoff , who in 1916 described the circular sets allowed in the original Zermelo set theory as extraordinary . Abraham Fraenkel wanted to eliminate these extraordinary sets from set theory in 1921 by means of an axiom of limitation , "which imposes the smallest extent compatible with the other axioms on the set domain". His axiom of limitation cannot be formulated in the language of set theory. The first correct formula that reached the exclusion of extraordinary sets was given by Neumann in his axiom of limitation in 1925 , but it is more complicated than the widespread foundation axiom of Zermelo.

Individual evidence

1. ↑ ^{a b} John von Neumann : An axiomatization of set theory. In: Journal for pure and applied mathematics. Vol. 154, 1925, pp. 219-240, there § 5 VI.4., P. 239, digitized .
2. ↑ Ernst Zermelo : About limit numbers and quantity ranges. In: Fundamenta Mathematicae . Vol. 16, 1930, pp. 29–47, there p. 31, digital version (PDF; 1.5 MB) .
3. ↑ Arnold Oberschelp : General set theory. BI-Wissenschafts-Verlag, Mannheim et al. 1994, ISBN 3-411-17271-1 , p. 261.
4. ↑ Ernst Zermelo: Investigations on the basics of set theory. I. In: Mathematical Annals . Vol. 65, 1908, pp. 261-281, there p. 265 .
5. ↑ Willard van Orman Quine : Set theory and their logic (= logic and foundations of mathematics. Vol. 10). Vieweg, Braunschweig 1973, ISBN 3-528-08294-1 , p. 24.
6. ↑ D. Mirimanoff : Les antinomies de Russell et de Burali-Forti et leproblemème fondamental de le théorie des ensembles. (1916). In: L'Enseignement Mathématique. Vol. 19, 1917, ISSN  0013-8584 , pp. 37-52, digitized .
7. ↑ Abraham Fraenkel : To the basics of Cantor-Zermeloschen set theory. (1921). In: Mathematical Annals. Vol. 86, 1922, pp. 230-237, there p. 233 .