Calculus

Set Theory

Set Theory Logo

Axiomatic Set Theory

Axiomatic set theories were proposed in the early \(20\text{th}\) century to address paradoxes discovered in naive set theory. This topic describes the most popular axiomatic set theory, known as Zermelo-Fraenkel set theory.

Zermelo-Fraenkel Axioms

The first axiomatic set theory was published in \(1908\) by the German mathematician Ernst Friedrich Ferdinand Zermelo \(\left( {1871 – 1953} \right).\) Later, the German-Israeli mathematician Abraham Fraenkel \(\left( {1891 – 1965} \right)\) and the Norwegian mathematician Thoralf Skolem \(\left( {1887 – 1963} \right)\) improved the system of axioms by including the axiom of replacement. The resulting theory became known as Zermelo-Fraenkel set theory. It is denoted \(ZF\) and contains \(8\) axioms. The complete axiomatic set theory, denoted \(ZFC,\) is formed by adding the axiom of choice.

\(1.\) Axiom of Extensionality

Let \(A\) and \(B\) be any two sets. If the sets \(A\) and \(B\) have the same elements, then \(A = B.\) Using the logic notation, we can write the axiom in the form

\[{{\forall x\left( {x \in A \Leftrightarrow x \in B} \right) }\Rightarrow{ A = B},}\]

where \(x\) is an element of \(A\) and \(B.\)

Example:

\[{A = \left\{ {1,2,3,4} \right\},\;}\kern0pt{B = \left\{ {4,2,3,1} \right\},}\; \Rightarrow {A = B.}\]

\(2.\) Axiom of Pairing

For any sets \(A\) and \(B,\) there exists a set \(C\) whose members are exactly \(A\) and \(B.\) Formally,

\[{\forall A\,\forall B \,\exists C\left[ {\forall x\left( {x \in C }\right.}\right.}\kern0pt{\left.{\left.{\Leftrightarrow \left( {x = A \vee x = B} \right)} \right)} \right],}\]

where \(x\) is a set.

Example:

\[{A = \left\{ {1,2,3} \right\},\;}\kern0pt{B = \left\{ {a,b} \right\},\;}\kern0pt{C = \left\{ {\left\{ {1,2,3} \right\},\left\{ {a,b} \right\}} \right\}.}\]

Here \(x \in C\) if only \(x = \left\{ {1,2,3} \right\}\) or \(x = \left\{ {a,b} \right\}.\)

The set \(\left\{ {A,A} \right\}\) is denoted by \(\left\{ {A} \right\}.\) It contains \(A\) as its only element.

\(3.\) Axiom of Union

For any set \(A,\) there exists a set \(U = \cup A,\) called the union of \(A\) and containing all elements of all members of \(A.\)

\[{\forall A\,\exists U\left[ {\forall x\left( {x \in U }\right.}\right.}\kern0pt{\left.{\left.{\Leftrightarrow \exists B\left( {B \in A \wedge x \in B} \right)} \right)} \right],}\]

where \(B\) is a set (a member of \(A\)), \(x\) is an element of \(B.\)

Example:

\[{A = \left\{ {\left\{ {1,2,3} \right\},\left\{ {3,4} \right\}} \right\},\;}\kern0pt{U = \left\{ {1,2,3,4} \right\}.}\]

Here the set \(B\) is \({\left\{ {1,2,3} \right\}}\) or \({\left\{ {3,4} \right\}}.\)

Thus, the axiom of union allows to “unpack” a set of sets and represent it as a flatter set.

\(4.\) Axiom of Power Set

For every set \(A,\) there exists a set \(\mathcal{P}\left( A \right),\) called the power set of \(A,\) that contains every subset of \(A.\)

\[{\forall A\,\exists \mathcal{P}\left( A \right)\left[ {\forall x\left( {x \in \mathcal{P}\left( A \right) }\right.}\right.}\kern0pt{\left.{\left.{\Leftrightarrow x \subseteq A} \right)} \right],}\]

where \(x\) is a subset of \(A.\)

Example:

\[\require{AMSsymbols}{A = \left\{ {a,b} \right\},\;}\kern0pt{\mathcal{P}\left( A \right) = \left\{ {\varnothing,\left\{ a \right\},\left\{ b \right\},\left\{ {a,b} \right\}} \right\}.}\]

\(5.\) Axiom of Infinity

There exists an infinite set. In formal language,

\[{\exists S\left[ {\varnothing \in S }\right.}\kern0pt{\left.{\wedge \,\forall x \in S\left( {\left( {x \cup \left\{ x \right\}} \right) \in S} \right)} \right],}\]

where \(S\) is an infinite set.

Example:

The axiom of infinity asserts that there exists at least one infinite set consisting of \(\varnothing,\) \(\varnothing \cup \left\{ \varnothing \right\},\) \(\varnothing \cup \left\{ \varnothing \right\} \cup \left\{ {\varnothing \cup \left\{ \varnothing \right\}} \right\}, \ldots .\) These elements are used to construct the set of natural numbers \(\mathbb{N}\) (including zero):

\[0 = \left\{ \right\} = \varnothing\]

\[1 = \left\{ 0 \right\} = \left\{ \varnothing \right\}\]

\[2 = \left\{ {0,1} \right\} = \left\{ {\varnothing,\left\{ \varnothing \right\}} \right\}\]

\[{3 = \left\{ {0,1,2} \right\} }={ \left\{ {\varnothing,\left\{ \varnothing \right\},\left\{ {\varnothing,\left\{ \varnothing \right\}} \right\}} \right\}}\]

\[ \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots\]

\(6.\) Axiom of Specification

Let \(P\) be a property of an element \(x.\) For any set \(A,\) there exists a set \(B\) that contains all those elements \(x \in A\) that have the property \(P.\)

\[{\forall A\,\exists B\,\forall x\left[ \left({x \in B }\right)\right.}\kern0pt{\left.{\Leftrightarrow \left(x \in A \wedge P\left( x \right)\right)} \right].}\]

This axiom is also known as the axiom of separation, axiom of subsets, or axiom of comprehension.

Example:

Suppose \(A = \mathbb{N_0}\) and the property \(P\) defines numbers divisible by \(3,\) so

\[P\left( x \right) : x \equiv 0\;\left( {\text{mod } 3} \right).\]

Then the subset \(B\) is a set containing all non-negative integers divisible by \(3:\)

\[{B = \left\{ {x \in \mathbb{N_0} \mid P\left( x \right)} \right\} }={ \left\{ {x \in \mathbb{N_0} \mid x \equiv 0\;\left( {\text{mod } 3} \right)} \right\} }={ \left\{ {0,3,6,9, \ldots } \right\}.}\]

Notice that the set \(B\) is defined as a subset of the previously given set \(A.\) This approach excludes sets of kind \(\left\{ {x \mid x \not\in x} \right\}\) leading to the Russell’s paradox.

\(7.\) Axiom of Replacement

If \(A\) and \(B\) are sets and \(f : A \to B\) is a function from \(A\) to \(B,\) then the image \(f\left( A \right)\) is also a set.

Recall that a function is a binary relation of a special sort. Therefore, a function can be defined by a formula in the language of set theory like \(P\left( {x,y,p_1,\dots,p_n} \right)\) where \(x \in A,\) \(y \in B,\) and \(p_1,\dots,p_n\) are parameters. For simplicity, consider a non-parametric formula \(P\left( {x,y} \right).\) Then

\[{\forall A\left[ {\left( {\left( {\forall x \in A} \right)\left( {\exists !y} \right)P\left( {x,y} \right)} \right) }\right.}\Rightarrow{\left.{ \exists B\,\forall y\left( {y \in B \Leftrightarrow \left( {\exists x \in A} \right)P\left( {x,y} \right)} \right)} \right].}\]

The axiom of replacement was suggested in \(1922\) by Fraenkel and Skolem. Together with the initial set of axioms of Zermelo set theory \(\left(Z\right),\) they form the standard Zermelo-Fraenkel set theory \(\left(ZF\right).\)

The axiom of replacement expands the possibilities of constructing infinite sets.

Example:

Given the ordinal number \(\omega = \left\{ {0,1,2,3, \ldots } \right\},\) the next limit ordinal \(\omega \cdot 2\) can be obtained as follows: Let \(A = \omega\) and \(B = \omega \cdot 2.\) The function

\[{f:A \to B }={ f:w \to w \cdot 2},\]

defined as \(f\left( n \right) = w + n\) maps each finite number \(n\) in \(\omega\) to \(\omega + n.\) The replacement axiom guarantees that we get a set.

\(8.\) Axiom of Regularity

Every non-empty set \(A\) has an element that is disjoint from \(A.\)

\[{\forall A\left[ {\left( {A \ne \varnothing} \right) }\right.}\Rightarrow{\left.{ \exists x\left( {\left( {x \in A} \right) \wedge \left( {x \cap A = \varnothing} \right)} \right)} \right].}\]

The axiom of regularity is also known as the axiom of foundation. This axiom does not guarantee the existence of any sets, but it excludes the existence of the set of all sets.

Example:

Let \(A\) be an arbitrary set. Consider the set \(\left\{ A \right\}\) which contains only one element – the set \(A\) itself. Then we have \(A \in \left\{ A \right\}.\) By the regularity axiom, \(A\) must be disjoint from \(\left\{ A \right\},\) that is, \(A \cap \left\{ A \right\} = \varnothing.\) This means that \(A \not\in A.\) In other words, no set can be an element of itself.

Axiom of Choice

The axiom of choice or \(AC\) states that for any family of non-empty disjoint sets, it is possible to choose one element from each set of the family.

In fact, the axiom of choice has several equivalent formulations. In terms of the choice function, it states that for any family \(A\) of non-empty sets, there exists a function \(f: A \to \cup A\) such that for every set \(B \in A,\) the image of \(f\left( B \right)\) is an element of \(B.\)

\[{\forall A\left[ {\left( {\varnothing \in A} \right) }\right.}\Rightarrow{\left.{ \exists \left( {f:A \to \cup A} \right)}\right.}\kern0pt{\left.{\left( {\forall B \in A\left( {f\left( B \right) \in B} \right)} \right)} \right].}\]

Axiom of choice
Figure 1.

Today the axiom of choice is recognized by most mathematicians. The system of axiom \(1-8\) together with the axiom of choice is denoted \(ZFC\) and is the standard form of axiomatic set theory.