Zermelo-Fraenkel set theory

The Zermelo-Fraenkel set theory is a widespread axiomatic set theory that is named after Ernst Zermelo and Abraham Adolf Fraenkel . Today it is the basis of almost all branches of mathematics. The Zermelo-Fraenkel set theory without a choice axiom is abbreviated to ZF , with a choice axiom to ZFC (where the C stands for the English word choice , i.e. choice or choice).

history

The Zermelo-Fraenkel set theory is an extension of the Zermelo set theory from 1907, which is based on axioms and suggestions from Fraenkel from 1921. Fraenkel added to the replacement axiom and advocated regular sets without circular element chains and for a pure set theory whose objects are only sets. In 1930, Zermelo completed the axiom system of the Zermelo-Fraenkel set theory, which he himself referred to as the ZF system: He adopted Fraenkel's substitution axiom and added the foundation axiom to exclude circular element chains, as demanded by Fraenkel. The original ZF system is verbal and also takes into account original elements that are not quantities. Later formalized ZF systems usually do without such original elements and thus fully implement Fraenkel's ideas. Thoralf Skolem created the first precise predicate logic formalization of the pure ZF set theory in 1929 (still without a foundation axiom). This tradition has prevailed, so that today the abbreviation ZF stands for the pure Zermelo-Fraenkel set theory. The version with original elements, which is closer to the original ZF system, is still used today and is called the ZFU for clear differentiation.

meaning

It has been shown - this is an empirical finding - that almost all known mathematical statements can be formulated in such a way that provable statements can be derived from ZFC. The ZFC set theory has therefore become a tried and tested and widely accepted framework for all of mathematics. Exceptions can be found wherever you have to or want to work with real classes . Certain extensions of ZFC are then used, which provide classes or additional very large sets, for example an extension to ZFC class logic or the Neumann-Bernays-Gödel set theory or a Grothendieck universe . In any case, ZFC is now regarded as the basic system of axioms for mathematics.

Because of the fundamental importance of ZFC set theory for mathematics, a proof of freedom from contradictions for set theory was sought within the Hilbert program since 1918 . Gödel, who made important contributions to this program, was able to show in his Second Incompleteness Theorem in 1930 that such a proof of freedom from contradiction is impossible within the framework of a consistent ZFC set theory. The assumption of consistency by ZFC therefore remains a working hypothesis of mathematicians hardened by experience:

"The fact that ZFC has been studied for decades and used in mathematics without showing any contradiction, speaks for the consistency of ZFC."

- Ebbinghaus u. a., Chapter VII, §4

The axioms of ZF and ZFC

ZF has an infinite number of axioms, since two axiom schemes (8th and 9th) are used, each specifying an axiom for each predicate with certain properties. The predicate logic of the first level with identity and the undefined element predicate serves as the logical basis . ${\displaystyle \in }$

1. Axiom of extensionality : Sets are equal if and only if they contain the same elements.

${\displaystyle \forall A,B\colon (A=B\iff \forall C\colon (C\in A\iff C\in B))}$

The axiom implies that in ZF there are only entities with extension, which are usually called sets. All bound variables therefore automatically refer to quantities in the ZF language.

2. Empty set axiom , obsolete null set axiom : There is a set without elements.

${\displaystyle \exists B\colon \forall A\colon \lnot (A\in B)}$

The uniqueness of this set immediately follows from the axiom of extensionality , which means that there is no more than such a set. This is usually referred to as a written and empty set . That means: The empty set is the only original element in ZF . ${\displaystyle B}$ ${\displaystyle \emptyset }$

3. Pair set axiom : For all and there is a set that has exact and as elements. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle \forall A,B\colon \exists C\colon \forall D\colon (D\in C\iff ((D=A)\lor (D=B)))}$

Apparently this amount is also clearly determined. It is written as . The amount is usually written as. ${\displaystyle C}$ ${\displaystyle \left\{A,B\right\}}$ ${\displaystyle \left\{A,A\right\}}$ ${\displaystyle \left\{A\right\}}$

4. Axiom of union: for every set there is a set that contains exactly the elements of the elements of as elements. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$

${\displaystyle \forall A\colon \exists B\colon \forall C\colon (C\in B\iff \exists D\colon (D\in A\land C\in D))}$

The set is also uniquely determined and is called the union of the elements of , written as . Together with the pair amount Axiom allows the association to define. ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle \bigcup A}$ ${\displaystyle A\cup B:=\bigcup \{A,B\}}$

5. Axiom of infinity : There is a set that contains the empty set and with every element also the set (cf. inductive set ). ${\displaystyle A}$ ${\displaystyle X}$ ${\displaystyle X\cup \{X\}}$

${\displaystyle \exists A\colon (\exists X\in A\colon \forall Y\colon \lnot (Y\in X)\land \forall X\colon (X\in A\Rightarrow X\cup \{X\}\in A))}$

There are many such sets. The intersection of all these sets is the smallest set with these properties and forms the set of natural numbers ; The intersection is formed by applying the axiom of separation (see below). So the natural numbers are represented by

${\displaystyle \mathbb {N} \,:=\,\{\emptyset ,\,\{\emptyset \},\,\{\emptyset ,\{\emptyset \}\},\,\{\emptyset ,\{\emptyset \},\{\emptyset ,\{\emptyset \}\}\}\,\ldots \}}$

6. Power set axiom: For every set there is a set whose elements are exactly the subsets of . ${\displaystyle A}$ ${\displaystyle P}$ ${\displaystyle A}$

${\displaystyle \forall A\colon \exists P\colon \forall B\colon (B\in P\iff \forall C\colon (C\in B\Rightarrow C\in A))}$

The amount is clearly determined. It is called the power set of and is denoted by. ${\displaystyle P}$ ${\displaystyle A}$ ${\displaystyle {{\mathcal {P}}(A)}}$

7. Foundation axiom or regularity axiom : Every nonempty set contains an element such that and are disjoint . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle \forall A\colon (A\neq \emptyset \Rightarrow \exists B\colon (B\in A\land \lnot \exists C\colon (C\in A\land C\in B)))}$

The element that is too disjoint is generally not clearly determined. ${\displaystyle B}$ ${\displaystyle A}$

The foundation axiom prevents there are infinite or cyclic sequences of sets in each of which one is included in the previous ones, because then you could a lot form that contradicts the axiom: for each is , the two sets are therefore not disjoint. This implies that a set cannot contain itself as an element. ${\displaystyle x_{1}\ni x_{2}\ni x_{3}\ni \dots }$ ${\displaystyle A=\{x_{1},x_{2},x_{3},\dots \}}$ ${\displaystyle x_{i}\in A}$ ${\displaystyle x_{i+1}\in x_{i}\cap A}$

8. Disposal axiom : This is an axiom scheme with one axiom for each predicate : For each set there is a subset of which contains exactly the elements of for which is true. ${\displaystyle P}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle C}$ ${\displaystyle A}$ ${\displaystyle P(C)}$

For every single-digit predicate in which the variable does not appear, the following applies: ${\displaystyle P(C)}$ ${\displaystyle B}$ ${\displaystyle \forall A\colon \exists B\colon \forall C\colon (C\in B\iff C\in A\land P(C))}$

From the axiom of extensionality it immediately follows that there is exactly such a set. This is noted with . ${\displaystyle \{C\in A|P(C)\}}$

9. Replacement axiom (Fraenkel): If a set and every element of is uniquely replaced by an arbitrary set, then it becomes a set. The replacement is made more precise by two-place predicates with similar properties to a function , namely as an axiom scheme for each such predicate: ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$

For every predicate in which the variable does not occur: ${\displaystyle F(X,Y)}$ ${\displaystyle B}$

${\displaystyle \forall X,Y,Z\colon (F(X,Y)\land F(X,Z)\Rightarrow Y=Z)\Rightarrow \forall A\colon \exists B\colon \forall C\colon (C\in B\iff \exists D\colon (D\in A\land F(D,C)))}$

The amount is clearly determined and is noted as. ${\displaystyle \,B}$ ${\displaystyle \{Y|D\in A\land F(D,Y)\}}$

In mathematics, the axiom of choice is often used, which ZF extends to ZFC:

10. Axiom of choice : If there is a set of pairwise disjoint nonempty sets, then there is a set that contains exactly one element from each element of . This axiom has a complicated formula that can be simplified a bit with the uniqueness quantifier : ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle \exists !}$

${\displaystyle \forall A\colon {\Big (}((\emptyset \not \in A)\ \wedge \ \forall X,Y,Z\colon ((X\in A\ \wedge \ Y\in A\ \wedge \ Z\in X\ \wedge \ Z\in Y)\Rightarrow (X=Y)))}$

${\displaystyle \Rightarrow \;}$

${\displaystyle \exists B\colon \forall X\colon (X\in A\Rightarrow \exists !\ Y\colon (Y\in X\wedge Y\in B)){\Big )}}$

Another common verbal formulation of the axiom of choice is: If a set is a non-empty set, then there is a function (of into its union) that assigns an element of to each element of (" selects an element of "). ${\displaystyle A}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$

With the ZF axioms one can derive the equivalence of the axiom of choice with the well-order theorem and the lemma of Zorn .

ZF with original elements

Zermelo formulated the original ZF system for quantities and primary elements. He defined sets as things containing elements or the zero set. Primordial elements are then things without elements, namely, he considered the zero set as a distinctive primitive element which, as a given constant, extends the ZF language. Quantities and primitive elements can thus be precisely defined: ${\displaystyle \emptyset }$

${\displaystyle M{\text{ ist Menge}}\colon \iff (M=\emptyset )\lor \exists X\colon (X\in M)}$

${\displaystyle U{\text{ ist Urelement}}\colon \iff \lnot \exists X\colon (X\in U)}$

The set theory with primitive elements is distinguished from the usual pure ZF set theory by the appended U. The axioms of ZFU and ZFCU are verbal, apart from the empty set axiom, like the axioms of ZF or ZFC, but are formalized differently because of the different framework conditions; deducible quantity conditions can be omitted.

ZFU

ZFU comprises the following axioms:

Empty set axiom :

${\displaystyle \emptyset {\text{ ist Urelement}}}$

Axiom of determinateness (weakened axiom of extensionality):

${\displaystyle A{\text{ ist Menge }}\land B{\text{ ist Menge }}\Rightarrow (A=B\iff \forall C\colon (C\in A\iff C\in B))}$

Association axiom :

${\displaystyle \forall A\colon \exists B\colon (B{\text{ ist Menge }}\land \forall C\colon (C\in B\iff \exists D\colon (D\in A\land C\in D)))}$

Power set axiom :

${\displaystyle \forall A\colon \exists P\colon \forall B\colon (B\in P\iff (B{\text{ ist Menge }}\land \forall C\colon (C\in B\Rightarrow C\in A)))}$

Infinity axiom :

${\displaystyle \exists A\colon (\exists X\in A\colon \forall Y\in A\colon \lnot (Y\in X)\land \forall X\colon (X\in A\Rightarrow X\cup \{X\}\in A))}$

Foundation axiom :

${\displaystyle \exists X\colon (X\in A)\Rightarrow \exists B\colon (B\in A\land \lnot \exists C\colon (C\in A\land C\in B))}$

Replacement axiom for two-digit predicates : ${\displaystyle F(X,Y)}$

${\displaystyle \forall X,Y,Z\colon (F(X,Y)\land F(X,Z)\Rightarrow Y=Z)\Rightarrow \forall A\colon \exists B\colon (B{\text{ ist Menge }}\wedge \ \forall C\colon (C\in B\iff \exists D\colon (D\in A\wedge \ F(D,C))))}$

The ZF axioms obviously follow from the ZFU axioms and the axiom . Because from the replacement axiom , as in ZF (see below), the pair set axiom can be derived and also the exclusion axiom , the latter here in the following form for each one-digit predicate : ${\displaystyle \forall X\colon X{\text{ ist Menge}}}$ ${\displaystyle P}$

${\displaystyle \forall A\colon \exists B\colon (B{\text{ ist Menge }}\land \forall C\colon (C\in B\iff C\in A\land P(C)))}$

ZFCU

ZFCU comprises the axioms of ZFU and the following axiom of choice :

${\displaystyle \forall A\colon ((\forall X\colon (X\in A\Rightarrow \exists Y\colon (Y\in X))\ \wedge \ \forall X,Y,Z\colon ((X\in A\ \wedge \ Y\in A\ \wedge \ Z\in X\ \wedge \ Z\in Y)\Rightarrow (X=Y)))}$

${\displaystyle \Rightarrow \;}$

${\displaystyle \exists B\colon \forall X\colon (X\in A\Rightarrow \exists !\ Y\colon (Y\in X\wedge Y\in B))}$

Simplified ZF system (redundancy)

The ZF system is redundant, that is, it has dispensable axioms that can be derived from others. ZF or ZFU is already fully described by the axiom of extension, union, power set axiom, infinity axiom, foundation axiom and replacement axiom. This applies to the following points:

• The axiom of exclusion follows from the axiom of substitution (Zermelo).
• The void set axiom follows from the exclusion axiom and the existence of some set, which results from the infinity axiom.
• The pair set axiom follows from the replacement axiom and the power set axiom (Zermelo).

Pair set axiom, union axiom and power set axiom can also be obtained from the statement that every set is an element of a level . The axiom of infinity and the axiom of substitution are equivalent to the reflection principle within the framework of the other axioms . By combining these two insights, Dana Scott reformulated ZF into the equivalent Scott system of axioms .

ZF system without equality

ZF and ZFU can also be based on a predicate logic without equality and define equality. The derivation of all axioms of equality only ensures the definition of identity that is customary in logic :

${\displaystyle A=B:\iff \forall C\colon (A\in C\iff B\in C)\land \forall C\colon (C\in A\iff C\in B)}$

The axiom of extensionality is not suitable for the definition! The definition of identity does not make this axiom superfluous because it cannot be derived from the definition. As an alternative, a definition of equality by extensionality would only be possible in ZF if the axiom was included, which ensures the deducibility of the above formula. This option is of course ruled out at ZFU. ${\displaystyle A=B:\iff \forall C\colon (C\in A\iff C\in B)}$ ${\displaystyle A=B\Rightarrow \forall C\colon (A\in C\iff B\in C)}$

Infinite axiomatizability

The substitution axiom is the only axiom scheme in ZF if one removes the redundancies of the axioms and restricts oneself to a system of independent axioms. It cannot be replaced by a finite number of individual axioms. In contrast to the theories of Neumann-Bernays-Gödel (NBG) and New Foundations (NF), ZF can not finally be axiomatized.

literature

Primary sources (chronological)

• Ernst Zermelo: Investigations into the basics of set theory. 1907, In: Mathematische Annalen. 65 (1908), pp. 261-281.
• Adolf Abraham Fraenkel: To the basics of Cantor-Zermeloschen set theory. 1921, In: Mathematische Annalen. 86: 230-237 (1922).
• Adolf Fraenkel: Ten lectures on the foundations of set theory. 1927. Unchanged reprographic reprint Scientific Book Society Darmstadt 1972.
• Thoralf Skolem: About some fundamental questions in mathematics. 1929, In: selected works in logic. Oslo 1970, pp. 227-273.
• Ernst Zermelo: About limit numbers and quantity ranges. In: Fundamenta Mathematicae. 16 (1930) (PDF; 1.6 MB), pp. 29-47.

Secondary literature

• Oliver Deiser: Introduction to set theory: Georg Cantor's set theory and its axiomatization by Ernst Zermelo . Springer, Berlin / Heidelberg 2004, ISBN 3-540-20401-6 .
• Heinz-Dieter Ebbinghaus: Introduction to set theory . Spectrum Academic Publishing House, Heidelberg / Berlin 2003, ISBN 3-8274-1411-3 .
• Adolf Fraenkel: Introduction to set theory . Springer Verlag, Berlin / Heidelberg / New York 1928. (Reprint: Dr. Martin Sendet oHG, Walluf 1972, ISBN 3-500-24960-4 ).
• Paul R. Halmos: Naive set theory . Vandenhoeck & Ruprecht, Göttingen 1968, ISBN 3-525-40527-8 .
• Felix Hausdorff: Fundamentals of set theory . Chelsea Publ. Co., New York 1914, 1949, 1965.
• Arnold Oberschelp : General set theory. BI-Wissenschaft, Mannheim / Leipzig / Vienna / Zurich 1994, ISBN 3-411-17271-1 .

Individual evidence

1. ↑ Ebbinghaus , chap. VII, §4
2. ↑ David Hilbert : Axiomatic Thinking. In: Mathematical Annals. 78: 405-415 (1918). There, on page 411, the fundamental importance of the consistency of Zermelo set theory for mathematics is discussed.
3. ↑ Verbalization based on: Fraenkel: To the basics of Cantor-Zermeloschen set theory. 1921, In: Mathematische Annalen. 86 (1922), p. 231.
4. ↑ Ernst Zermelo : Investigations on the basics of set theory. In: Mathematical Annals. 65 (1908), p. 262, §1 (2.) Definition of quantities.
5. ↑ Ernst Zermelo: limit numbers and quantity ranges. In: Fundamenta Mathematicae. 16 (1930), p. 30, remark in Axiom U: “Instead of the“ zero set ”there is an arbitrarily selected primordial element”.
6. ↑ ^{a b} Ernst Zermelo: Limits and quantity ranges. In: Fundamenta Mathematicae. 16 (1930), remark p. 31.
7. ^ Walter Felscher : Naive sets and abstract numbers I, Mannheim / Vienna / Zurich 1978, p. 62.
8. ↑ ^{a b} Wolfgang Rautenberg : Basic course set theory , version Berlin 2008, p. 26. (PDF; 1.0 MB)
9. ^ Walter Felscher: Naive sets and abstract numbers I. Mannheim / Vienna / Zurich 1978, p. 78f.
10. ^ Robert Mac Naughton, A non standard truth definition , in: Proceedings of the American Mathematical Society, Vol. 5 (1954), pp. 505-509.
11. ↑ Richard Montague, Fraenkel's addition to the axioms of Zermelo , in: Essays on the Foundation of Mathematics, pp. 91-114, Jerusalem 1961. Inadequate evidence was given in 1952 by Mostowski and Hao Wang.

Web links

• Laura Crosilla:  Set Theory: Constructive and Intuitionistic ZF. In: Edward N. Zalta (Ed.): Stanford Encyclopedia of Philosophy .
• mathematik.de: Set theory