View source for Axiomatic set theory

<!--
a0143101.png
$#A+1 = 184 n = 0
$#C+1 = 184 : ~/encyclopedia/old_files/data/A014/A.0104310 Axiomatic set theory
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

The branch of mathematical logic in which one deals with fragments of the informal theory of sets by methods of mathematical logic. Usually, to this end, these fragments of set theory are formulated as a formal axiomatic theory. In a more narrow sense, the term  "axiomatic set theory"  may denote some axiomatic theory aiming at the construction of some fragment of informal ( "naive" ) set theory.

Set theory, which was formulated around 1900, had to deal with several paradoxes from its very beginning. The discovery of the fundamental paradoxes of G. Cantor and B. Russell (cf. [[Antinomy|Antinomy]]) gave rise to a widespread discussion and brought about a fundamental revision of the foundations of mathematical logic. The axiomatic direction of set theory may be regarded as an instrument for a more thorough study of the resulting situation.

The construction of a formal axiomatic theory of sets begins with an accurate description of the language in which the propositions are formulated. The next step is to express the principles of  "naive"  set theory in this language, in the form of axioms and axiom schemes. A brief description of the most widespread systems of axiomatic set theory is given below. In this context, an important part is played by the language which contains the following primitive symbols: 1) the variables  $  x, y, z, u , v, x _ {1} \dots $
which play the part of common names for the sets in the language; 2) the predicate symbols  $  \in $(
sign of incidence) and  $  = $(
sign of equality); 3) the description operator  $  \iota $, 
which means  "an object such that …" ; 4) the logical connectives and quantifiers:  $  \aHB $(
equivalent),  $  \rightarrow $(
implies),  $  \lor $(
or),  $  \wedge $(
and),  $  \neg $(
not),  $  \forall $(
for all),  $  \exists $(
there exists); and 5) the parentheses ( and ). The expressions of a language are grouped into terms and formulas. The terms are the names of the sets, while the formulas express propositions. Terms and formulas are generated in accordance with the following rules.

$  \mathbf{R1} $. 
If  $  \tau $
and  $  \sigma $
are variables or terms, then  $  ( \tau \in \sigma ) $
and  $  ( \tau = \sigma ) $
are formulas.

$  \mathbf{R2} $. 
If  $  A $
and  $  B $
are formulas and  $  x $
is a variable, then  $  (A \aHB B) $, 
$  (A \rightarrow B) $, 
$  (A \lor B) $, 
$  (A \wedge B) $, 
$  \neg A $, 
$  \forall  xA $, 
$  \exists  xA $
are formulas and  $  \iota x A $
is a term; the variable  $  x $
is a term.

For instance, the formula  $  \forall x ( x \in y \rightarrow x \in z ) $
is tantamount to the statement  "y is a subset of z" , and can be written as  $  y \subseteq z $; 
the term  $  \iota w \forall  y ( y \in w \aHB y \subseteq z ) $
is the name of the set of all subsets  $  z $
and, expressed in conventional mathematical symbols, this is  $  Pz $. 
Let the symbol  $  \iff $
mean  "the left-hand side is a notation for the right-hand side" . Below a number of additional notations for formulas and terms will be presented.

The empty set:

$$ 
\emptyset  \iff  \iota x \forall  y \neg y \in x .
$$

The set of all  $  x $
such that  $  A(x) $

$$ 
\{ {x } : {A ( x ) } \}
 \iff  \iota z \forall x(x \in z  \aHB  A ( x ) ),
$$

where  $  z $
does not enter freely in  $  A(x) $(
i.e. is not a parameter of the formula  $  A(x) $).

The unordered pair  $  x $
and  $  y $:

$$ 
\{ x , y \}  \iff  \{ {z } : {z= x  \lor  z = y } \}
.
$$

The single-element set consisting of  $  x $:

$$ 
\{ x \}  \iff  \{ x , x \} .
$$

The ordered pair  $  x $
and  $  y $:

$$ 
\langle  x , y \rangle  \iff  \{ \{ x \} , \{ x , y \} \} .
$$

The union of  $  x $
and  $  y $:

$$ 
x \cup y  \iff  \{ {z } : {z \in x  \lor  z \in y } \}
.
$$

The intersection of  $  x $
and  $  y $:

$$ 
x \cap y  \iff  \{ {z } : {z \in x  \wedge  z \in y } \}
.
$$

The union of all elements of  $  x $:

$$ 
\cup x  \iff  \{ {z } : {\exists v ( z \in v  \lor  v \in x ) } \}
.
$$

The Cartesian product of  $  x $
and  $  y $:

$$ 
x \times y  \iff  \{ {z } : {\exists u v ( z = \langle  u , v \rangle
 \wedge  u \in x  \wedge  v \in y ) } \}
.
$$

Notation for:  $  w $
is a function:

$$ 
 \mathop{\rm Fnc} ( w )  \iff  \exists v ( w \subseteq v \times v ) \wedge
$$

$$ 
\wedge 
\forall u v _ {1} v _ {2} ( \langle  u , v _ {1} \rangle \in w  \wedge  \langle  u , v _ {2} \rangle
\in w  \rightarrow  v _ {1} = v _ {2} ) .
$$

The values of the function  $  w $
on the element  $  x $:

$$ 
w  ^  \mrp  x  \iff  \iota y \langle  x , y \rangle \in w .
$$

The standard infinite set  $  z $

$$ 
 \mathop{\rm Inf} ( z )  \iff  \emptyset \in z  \wedge  \forall u ( u \in z  \rightarrow \ 
u \cup \{ u \} \in z ) .
$$

The axiomatic theory  $  A $
that follows is the most complete representation of the principles of  "naive"  set theory. The axioms of  $  A $
are:

$  \mathbf{A1} $. 
Axiom of extensionality:

$$ 
\forall x ( x \in y \aHB x \in z )  \rightarrow  y = z
$$

( "if the sets x and y contain the same elements, they are equal" );

$  \mathbf{A2} $. 
Axiom scheme of comprehension:

$$ 
\exists y  \forall x ( x \in y \aHB A ) ,
$$

where  $  A $
is an arbitrary formula not containing  $  y $
as a parameter ( "there exists a set y containing only elements x for which A" ).

This system is self-contradictory. If, in  $  \mathbf{A2} $, 
the formula  $  \neg x \in x $
is taken as  $  A $, 
the formula  $  \forall x ( x \in y \aHB \neg x \in x ) $
readily yields  $  y \in y \aHB \neg y \in y $, 
which is a contradiction.

The axiomatic systems of set theory may be subdivided into the following four groups.

a) The construction of axiomatic systems in the first group is intended to restrict the comprehension axioms so as to obtain the most natural means of formalization of conventional mathematical proofs and, at the same time, to avoid the familiar paradoxes. The first axiomatic system of this type was the system Z, due to E. Zermelo (1908). However, this system does not allow a natural formalization of certain branches of mathematics, and the supplementation of Z by a new principle — the axiom of replacement — was proposed by A. Fraenkel in 1922. The resulting system is known as the Zermelo–Fraenkel system and is denoted by ZF.

b) The second group is constituted by systems the axioms of which are selected in the context of giving some explanations for paradoxes, for example, as a consequence of non-predicative definitions. The group includes Russell's ramified theory of types, the simple theory of T-types, and the theory of types with transfinite indices (cf. [[Types, theory of|Types, theory of]]).

c) The third group is characterized by the use of non-standard means of logical deduction, multi-valued logic, complementary conditions of proofs and infinite derivation laws. Systems in this group have been developed to the least extent.

d) The fourth group includes modifications of systems belonging to the first three groups and is aimed at attaining certain logical and mathematical objectives. Only the system NBG of Neumann–Gödel–Bernays (1925) and the system NF of W. Quine (1937) will be mentioned here. The construction of the system NBG was motivated by the desire to have a finite number of axioms of set theory, based on the system ZF. The system NF represents an attempt to overcome the stratification of the concepts in the theory of types.

The systems Z, ZF and NF can be formulated in the language described above. The derivation rules, and also the so-called logical axioms, of these systems are identical, and form an applied predicate calculus of the first order with equality and with a description operator. Here are the axioms of equality and of the description operator:

$$ 
x  =  x ,\  x = y  \rightarrow  ( A ( x ) \rightarrow A ( y ) ) ,
$$

where  $  A(x) $
is a formula not containing the bound variable  $  y $(
i.e. it has no constituents of the type  $  \forall y, \exists y, \iota y $), 
while  $  A(y) $
is obtained from the formula  $  A(x) $
by replacing certain free entries of the variable  $  x $
with  $  y $:

$$ 
\exists ! x  A ( x )  \rightarrow  A ( \iota x A ( x ) ) ,
$$

where the quantifier  $  \exists ! x $
means that  "there exists one and one only x" , while the formula  $  A ( \iota xA (x)) $
is obtained from the formula  $  A(x) $
by replacing all free entries of the variable  $  x $
with the term  $  \iota xA(x) $. 
The quantifier  $  \exists ! x $
can be expressed in terms of the quantifiers  $  \forall $
and  $  \exists $
and equality.

Non-logical axioms of the system Z:

$  \mathbf{Z1} $. 
The axiom of extensionality  $  \mathbf{A1} $.

$  \mathbf{Z2} $. 
The pair axiom:

$$ 
\exists u  \forall z ( z \in u  \aHB  z = x  \lor  z = y )
$$

( "the set x, y exists" );

$  \mathbf{Z3} $. 
The union axiom:

$$ 
\exists y  \forall x ( x \in y  \aHB  \exists t ( t \in z  \wedge \ 
x \in t ) )
$$

( "the set  z exists" );

$  \mathbf{Z4} $. 
The power set axiom:

$$ 
\exists y  \forall x ( x \in y  \aHB  x \subseteq z )
$$

( "the set Pz exists" );

$  \mathbf{Z5} $. 
The separation axiom scheme:

$$ 
\exists y  \forall x ( x \in y  \aHB  x \in z  \wedge  A ( x ) )
$$

( "there exists a subset z consisting of the elements x in z for which Ax is true" ); the axioms  $  \mathbf{Z2} $–
$  \mathbf{Z5} $
are examples of axioms of comprehension;

$  \mathbf{Z6} $. 
The axiom of infinity:

$$ 
\exists z   \mathop{\rm Inf} ( z ) ;
$$

$  \mathbf{Z7} $. 
The axiom of choice:

$$ 
\forall z  \exists w (  \mathop{\rm Fnc} ( w )  \wedge  \forall x
( x \in z  \wedge  \neg x = \emptyset  \rightarrow  w  ^  \mrp  x \in x ) )
$$

( "for any set z there exists a function w which selects, out of each non-empty element x of the set z, a unique element w`x" ). The above axioms are complemented by the regularity axiom:

$  \mathbf{Z8} $.

$$ 
\forall x ( \neg x = \emptyset  \rightarrow  \exists y ( y \in x  \wedge  y \cap x= \emptyset )),
$$

which is intended to postulate that there are no descending chains  $  x _ {2} \in x _ {1} , x _ {3} \in x _ {2} , x _ {4} \in x _ {3} , .  .  . $. 
Axiom  $  \mathbf{Z8} $
simplifies constructions in Z, and its introduction does not result in contradictions.

The system Z is suitable for developing arithmetic, analysis, functional analysis and for studying cardinal numbers smaller than  $  \aleph _  \omega  $. 
However, if the alephs are defined in the usual manner, it is no longer possible to demonstrate the existence in Z of  $  \aleph _  \omega  $
and higher cardinal numbers.

The system ZF is obtained from Z by adding Fraenkel's replacement axiom scheme, which may be given in the form of the comprehension axiom scheme:

$  \mathbf{ZF9} $.

$$ 
\exists y  \forall x ( x \in y  \aHB  \exists v ( v \in z  \wedge \ 
x = \iota t A ( t , v ) ))
$$

( "there exists a set y consisting of x, x=i tAt, v, where v runs through all the elements of a set z" ). In other words,  $  y $
is obtained from  $  z $
if each element  $  v $
of  $  z $
is replaced with  $  \iota tA (t, v) $.

The system ZF is a very strong theory. All ordinary mathematical theorems can be formalized in terms of ZF.

The system NBG is obtained from ZF by adding a new type of variables — the class variables  $  X, Y, Z ,\dots $— 
and a finite number of axioms for forming classes, by means of which it is possible to prove formulas of the type

$$ 
\exists Y  \forall x ( x \in Y \aHB A ( x ) ) ,
$$

where  $  A(x) $
is a formula of NBG which does not countain bound class variables or the symbol  $  \iota $. 
Since any formula  $  A(x) $
can be used to form a class, the infinite number of ZF axioms can be replaced by a finite number of axioms containing a class variable. The axiom of choice has the form:

$$ 
\exists X (  \mathop{\rm Fnc} ( X )  \wedge  \forall x ( \neg x = \emptyset
 \rightarrow  X  ^  \mrp  x \in x ) )
$$

and confirms the existence of a selection function, which is unique for all sets and which constitutes a class.

The system NF has a simpler axiomatic form, viz.: 1) the axiom of extensionality; and 2) the axioms of comprehension in which a formula  $  A $
can be stratified, i.e. it is possible to assign to all variables of the formula  $  A $
superscript indices so as to obtain a formula of the theory of T-types, i.e. in the subformulas of type  $  x \in y $
the index of  $  x $
is one lower than the index of  $  y $.

The system NF has the following characteristics:

a) the [[Axiom of choice|axiom of choice]] and the generalized [[Continuum hypothesis|continuum hypothesis]] are disprovable;

b) the axiom of infinity is demonstrable (cf. [[Infinity, axiom of|Infinity, axiom of]]);

c) the extensionality axiom plays a very important role. Thus, if the extensionality axiom is replaced by the slightly weaker axiom:

$$ 
( \exists u ( u \in y )  \wedge  \forall u ( u \in y  \aHB  u \in
z ) )  \rightarrow  y = z ,
$$

which permits a large number of empty sets, while the comprehension axioms of NF remain unchanged, a fairly weak theory is obtained: The consistency of the resulting system can be proved even in formal arithmetic.

Results concerning the interrelationships between the systems just described are given below.

a) Any formula of ZF is demonstrable in NBG if and only if it is demonstrable in ZF.

b) In ZF it is possible to establish the consistency of Z, completed by any finite number of examples of the axiom scheme of replacement  $  \mathbf{ZF9} $. 
Thus, ZF is much stronger than Z.

g) The consistency of T is demonstrable in Z, so that Z is stronger than T.

d) NF is not weaker than T in the sense that it is possible to develop the entire theory of types in NF.

The axiomatic approach to the theory of sets has made it possible to state a proposition on the unsolvability in principal (in an exact sense) of certain mathematical problems and has made it possible to demonstrate it rigorously. The general procedure for the utilization of the axiomatic method is as follows. Consider a formal axiomatic system  $  S $
of the theory of sets (as a rule, this is ZF or one of its modifications) that is sufficiently universal to contain all the conventional proofs of classical mathematics, and for all ordinary mathematical facts to be deducible from it. A given problem  $  A $
may be written down as a formula in the language  $  S $. 
It is then established by mathematical methods that neither  $  A $
nor its negation can be deduced in  $  S $. 
It follows that problem  $  A $
cannot be solved (in either way) by tools of the theory  $  S $, 
but since this theory  $  S $
was assumed to contain all ordinary methods of proof, the result means that  $  A $
cannot be solved by ordinary methods of conclusion, i.e.  $  A $
is  "transcendental" .

Results which state that a proof cannot be performed in the theory  $  S $
are usually obtained under the assumption that  $  S $, 
or some natural extension of  $  S $, 
is consistent. This is because on the one hand, the problem can be non-deducible in  $  S $
only if  $  S $
is consistent, but such consistency cannot be established by the tools offered by  $  S $(
cf. [[Gödel incompleteness theorem|Gödel incompleteness theorem]]), i.e. cannot be derived by ordinary methods. On the other hand, the consistency of  $  S $
is usually a very likely hypothesis; the very theory  $  S $
is based on its truth.

Furthermore, the axiomatic approach to the theory of sets made it possible to accurately pose and solve problems connected with effectiveness in the theory of sets, which had been intensively studied during the initial development of the theory by R. Baire, E. Borel, H. Lebesgue, S.N. Bernstein [S.N. Bernshtein], N.N. Luzin and W. Sierpiński. It is said that an object in the theory of sets which satisfies a property  $  \mathfrak A $
is effectively defined in the axiomatic theory  $  S $
if it is possible to construct a formula  $  A(x) $
of  $  S $
for which it can be demonstrated in  $  S $
that it is fulfilled for a unique object, and that this object satisfies property  $  \mathfrak A $. 
Because of this definition it is possible to show in a rigorous manner that for certain properties  $  \mathfrak A $
in  $  S $
it is impossible to effectively specify an object which satisfies  $  \mathfrak A $, 
while the existence of these objects in  $  S $
can be established. But since the chosen theory  $  S $
is sufficiently universal, the fact that the existence of certain objects in  $  S $
is ineffective is also a proof of the fact that their existence cannot be effectively established by ordinary mathematical methods.

Finally, the methods of the axiomatic theory of sets make it possible to solve a number of difficult problems in classical branches of mathematics as well: in the theory of cardinal and ordinal numbers, in descriptive set theory and in topology.

Some of the results obtained by the axiomatic theory of sets are given below. Most of the theorems concern the axiomatic set theory of Zermelo–Fraenkel (ZF), which is now the most frequently employed. Let  $   \mathop{\rm ZF}  ^ {-} $
be the system ZF without the axiom of choice  $  \mathbf{Z7} $. 
In view of a), the results can be readily adapted to the system NBG as well.

1) It was shown in 1939 by K. Gödel that if  $   \mathop{\rm ZF}  ^ {-} $
is consistent, it will remain consistent after the axiom of choice and the continuum hypothesis have been added. It follows that it is impossible to disprove the axiom of choice or the continuum hypothesis in ZF. In order to prove this result, Gödel constructed a model of the theory ZF consisting of the so-called Gödel constructive sets (cf. [[Gödel constructive set|Gödel constructive set]]), this model plays an important role in modern axiomatic set theory.

2) The problem as to whether or not the axiom of choice or the continuum hypothesis is deducible in ZF remained open until 1963, when it was shown by P.J. Cohen, using his [[Forcing method|forcing method]], that if  $   \mathop{\rm ZF}  ^ {-} $
is consistent, it will remain consistent after the addition of any combination of the axiom of choice, the continuum hypothesis or their negations. Thus, these two problems are independent in ZF.

The principal method used for establishing that a formula  $  A $
is not deducible in ZF is to construct a model of ZF containing the negation of  $  A $. 
Cohen's forcing method, which was subsequently improved by other workers, strongly extended the possibilities of constructing models of set theory, and now forms the basis of almost all subsequent results concerning non-deducibility. For instance:

3) It has been shown that one can add to ZF, without obtaining (additional) inconsistencies, the hypothesis stating that the cardinality of the set of subsets of a set  $  x $
may be an almost arbitrary pre-given function of the cardinality of  $  x $
on regular cardinals (the only substantial restrictions are connected with König's theorem).

4) M.Ya. Suslin (1920) formulated the following hypothesis. Any linearly totally ordered set such that any pairwise non-intersecting family of non-empty open intervals in it is at most countable must contain a countable everywhere-dense subset. The non-deducibility of Suslin's hypothesis in ZF was established by Cohen's method.

5) It was shown that the following postulate:  "Any subset of the set of real numbers is Lebesgue measurable"  is unsolvable in  $   \mathop{\rm ZF}  ^ {-} $(
without the axiom of choice).

6) The interrelationship of many important problems of descriptive set theory with ZF was clarified. The first results relating to this problem were demonstrated by P.S. Novikov [[#References|[5]]]. The methods of axiomatic set theory made it possible to discover previously unknown connections between the problems of  "naive"  set theory. It was proved, for example, that the existence of a Lebesgue non-measurable set of real numbers of the type  $  \Sigma _ {2}  ^ {1} $(
i.e.  $  A _ {2} $) 
implies the existence of an uncountable  $  \Pi _ {1}  ^ {1} $(
i.e.  $  C {\mathcal A} $) 
set without a perfect subset.

7) It was proved that an effectively totally ordered continuum is absent in ZF. Numerous results proved the absence of effectively defined objects in the descriptive theory of sets and in the theory of ordinal numbers.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A. Levy,   "Foundations of set theory" , North-Holland  (1973)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  P.J. Cohen,   "Set theory and the continuum hypothesis" , Benjamin  (1966)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  T.J. Jech,   "Lectures in set theory: with particular emphasis on the method of forcing" , ''Lect. notes in math.'' , '''217''' , Springer  (1971)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  F.R. Drake,   "Set theory: an introduction to large cardinals" , North-Holland  (1974)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  P.S. Novikov,   "On the consistency of certain propositions of the descriptive theory of sets"  ''Amer. Math. Soc. Transl.'' , '''29'''  (1963)  pp. 51–89  ''Trudy Mat. Inst. Steklov.'' , '''38'''  (1951)  pp. 279–316</TD></TR></table>

====Comments====
Gödel's book [[#References|[a4]]] contains his proof of the statement in 1) above.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  T.J. Jech,   "Set theory" , Acad. Press  (1978)  (Translated from German)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  E.J. Lemmon,   "Introduction to axiomatic set theory" , Routledge &amp; Kegan Paul  (1968)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G. Takeuti,   W.M. Zaring,   "Introduction to axiomatic set theory" , Springer  (1971)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  K. Gödel,   "The consistency of the axiom of choice and of the generalized continuum hypothesis with the axioms of set theory" , Princeton Univ. Press  (1940)</TD></TR></table>