2. Axiomatization of logic and set theory

2.1 Axiomatization of mathematical logic

2.2 Zermelo-Fraenkel set theory

2.1 Axiomatization of mathematical logic

2.1.1 Introduction

Video tutorial

2.1.2 What is a proof?

...

Video tutorial

2.1.3 Axiom system of Shoenfield

Shoenfield's axiom system consists of one axiom, the law of the excluded middle, and four rules of inference.

Axiom:

Rules of inference:

We finally add two abbreviations in form of two definitions.

Definitions:

Video tutorial

2.1.4 Derived rules of inference I

For proving the rules of double negation we need the following

Proposition: Commutativity of \( \vee \) (COM)

1. \( \displaystyle\vdash\ \genfrac{}{}{1pt}{}{a\vee b}{b\vee a} \)

Proof: (see → R.E. Hodel, page 81)

The statement is proved.\( \qquad\Box \)

Video tutorial

2.1.5 Rules of double negation

We start from the hypothesis \( a \) and prove that we can immediately infer \( \neg\neg a. \)

Proposition: First rule of double negation (DN1)

1. \( \displaystyle\vdash\ \genfrac{}{}{1pt}{}{a}{\neg\neg a} \)

Proof: (see → R.E. Hodel, page 81)

The statement is proved.\( \qquad\Box \)

Now we come to a proof of the inverse, that is, given the hypothesis \( \neg\neg a, \) we can infer \( a. \)

Proposition: First rule of double negation (DN2)

1. \( \displaystyle\vdash\ \genfrac{}{}{1pt}{}{\neg\neg a}{a} \)

Proof:

The statement is proved.\( \qquad\Box \)

Video tutorial

2.1.6 Derived rules of inference II

In the next paragraph we want to prove the rule of contradiction. For this goal we need certain generalizations of the rule of expansion and of the contraction rule.

Proposition: Generalized rule of expansion (GEXP)

1. \( \displaystyle\vdash\ \genfrac{}{}{1pt}{}{a\vee b}{a\vee(c\vee b)} \)

Proof: (see → R.E. Hodel, page 91)

The statement is proved.\( \qquad\Box \)

In the next paragraph we want to prove the rule of contradiction. For this goal we need certain generalizations of the rule of expansion and of the contraction rule.

Proposition: Generalized rule of double negation (GDN)

1. \( \displaystyle\vdash\ \genfrac{}{}{1pt}{}{a\vee b}{\neg\neg a\vee b} \)

Proof:

The statement is proved\( \qquad\Box \)

Video tutorial

2.1.7 Rule of contraposition

Now we come to the rule of contraposition and a possible proof using the foregoing generalized rule of double negation (GDN).

Proposition: Rule of contraposition

1. \( \displaystyle\vdash\ \genfrac{}{}{1pt}{}{a\to b}{\neg b\to\neg a} \)

Proof:

The statement is proved.\( \qquad\Box \)

Video tutorial

2.1.8 Syllogism

We will use the modus tollendo ponens for our proof of the second de Morgan rule in the next paragraph. But beside this classical syllogism we present and prove three further syllogisms which we already learned in → this section.

Proposition: modus ponens

1. \( \displaystyle\vdash\ \genfrac{}{}{1pt}{}{a,\ a\to b}{b} \)

Proof:

The statement is proved.\( \qquad\Box \)

Proposition: modus tollendo ponens (MTP)

1. \( \displaystyle\vdash\ \genfrac{}{}{1pt}{}{a\vee b,\ \neg a}{b} \)

Proof:

The statement is proved.\( \qquad\Box \)

Proposition: Chain rule for implication

1. \( \displaystyle\vdash\ \genfrac{}{}{1pt}{}{a\to b,\ b\to c}{b\to c} \)

Proof:

The statement is proved.\( \qquad\Box \)

Proposition: modus tollendo tollens

1. \( \displaystyle\vdash\ \genfrac{}{}{1pt}{}{a\to b,\ \neg b}{\neg a} \)

Proof:

The statement is proved.\( \qquad\Box \)

Video tutorial

2.1.9 Derivation of de Morgan rules

We begin with the

Proposition: It holds the first de Morgan rule

1. \( \displaystyle\vdash\ \genfrac{}{}{1pt}{}{\neg(a\wedge b)}{\neg a\vee\neg b} \)

Proof:

The statement is proved.\( \qquad\Box \)

A proof of the second de Morgan involves more effort. We will make use of the modus tollendo ponens from above.

Proposition: It holds the second de Morgan rule

1. \( \displaystyle\vdash\ \genfrac{}{}{1pt}{}{\neg(a\vee b)}{\neg a\wedge\neg b} \)

Proof: (see → D. Moos, chapter 3.)

The statement is proved.\( \qquad\Box \)

Video tutorial

2.1.10 Deduction, replacement, substitution

So far, we have proved important rules only using the axioms or rules which we derived from the axioms by means of the rule of interference. This approach is not suited for the mathematical practice. Rather, we will usually make use of the following three central metarules.

Proposition: (Deduction rule)

If there is a proof of \( b \) under the hypothesis \( a, \) then there exists a proof of the implication \( a\to b. \)

Example: We have proved the rules \[ \genfrac{}{}{1pt}{}{a}{\neg\neg a} \quad\text{and}\quad \genfrac{}{}{1pt}{}{\neg\neg a}{a}\,. \] Thus, from the deduction rule we infer \[ \vdash\ (a\to\neg\neg a)\quad\text{and}\quad\vdash\ (\neg\neg a\to a), \] and, therefore, \[ \vdash\ (a\leftrightarrow\neg\neg a). \] There exists a proof of the equivalence \( a\leftrightarrow\neg\neg a \) which requires no further hypotheses.

Proposition: (Replacement rule)

Let \( a\leftrightarrow b, \) and let \( \varphi \) be a formula. Then it holds \[ \vdash\ \genfrac{}{}{1pt}{}{a\leftrightarrow b}{\varphi(a)\leftrightarrow\varphi[b/a]}\,, \] where \( \varphi[b/a] \) is the result of replacing some or all occurrences of \( a \) by \( b. \)

Example: Consider the formula \( \varphi(c,d)=c\vee d, \) and replace \( c \) by \( \neg\neg c \) to obtain \[ \vdash\ \genfrac{}{}{1pt}{}{c\leftrightarrow\neg\neg c}{(c\vee d)\leftrightarrow(\neg\neg c\vee d)}\,. \]

Proposition: (Substitution rule)

If \( \varphi(a) \) is a tautology, then so \( \varphi[\psi/a], \) where \( \varphi[\psi,a] \) results after substituting all occurrences of \( a \) in \( \varphi(a) \) by the formula \( \psi. \)

Example: Let \( \varphi(a) \) be the tautology \( \neg a\vee a \) and \( \psi (a,b)=a\vee b, \) then \[ \neg(a\vee b)\vee(a\vee b) \] is a tautology.

Video tutorial

2.1.11 Historical axiom systems

Lastly, we want to present some different axiom systems which are of mathematical but also of historical value. It is an informative exercise to prove that these systems are actually equivalent to Shoenfield's axiom system from above.

G. Frege

Taken from: Begriffsschrift (1879); see also Begriffsschrift und andere Aufsätze (2014)

Axioms:

1. \( \quad a\to(b\to a) \)
2. \( \quad [c\to(b\to a)]\to[(c\to b)\to(c\to a)] \)
3. \( \quad [c\to(b\to a)]\to[b\to(c\to a)] \)
4. \( \quad (b\to a)\to(\neg a\to\neg b) \)
5. \( \quad \neg\neg a\to a \)
6. \( \quad a\to\neg\neg a \)

B. Russell, A.N. Whitehead

Taken from: Principia mathematica 1 (1910)

Axioms:

1. \( \quad a\vee a\to a \)
2. \( \quad b\to a\vee b \)
3. \( \quad a\vee b\to b\vee a \)
4. \( \quad a\vee(b\vee c)\to b\vee(a\vee c) \)
5. \( \quad (b\to c)\to(a\vee b\to a\vee c) \)

D. Hilbert

Taken from: Die logischen Grundlagen der Mathematik (1922)

Axioms:

1. \( \quad a\to(b\to a) \)
2. \( \quad [a\to(a\to b)]\to(a\to b) \)
3. \( \quad [a\to(b\to c)]\to[b\to(a\to c)] \)
4. \( \quad (b\to c)\to[(a\to b)\to(a\to c)] \)
5. \( \quad a\to(\neg a\to b) \)
6. \( \quad (a\to b)\to[(\neg a\to b)\to b] \)

Rules of inference:

1. Modus Ponens

W. Ackermann, D. Hilbert

Taken from: Grundzüge der theoretischen Logik (1928)

Axioms:

1. \( \quad a\vee a\to a \)
2. \( \quad a\to a\vee b \)
3. \( \quad a\vee b\to b\vee a \)
4. \( \quad (a\to b)\to(c\vee a\to c\vee b) \)

Rules of inference:

1. Substitution rule
2. Modus Ponens

J. Lukasiewicz, A. Tarski

Taken from: Untersuchungen über den Aussagenkalkül (1930); see also J. Lukasiewicz: Elements of mathematical logic (1963)

Axioms:

1. \( \quad (a\to b)\to[(b\to c)\to(a\to c)] \)
2. \( \quad (\neg a\to a)\to a \)
3. \( \quad a\to(\neg a\to b) \)

J. Lukasiewicz

First alternative, taken from: Elements of mathematical logic (1963)

Axioms:

1. \( \quad (a\to b)\wedge(b\to c)\to(a\to c) \)
2. \( \quad (\neg a\to a)\to a \)
3. \( \quad a\to(\neg a\to b) \)

Rules of inference:

1. Modus Ponens

P. Bernays, D. Hilbert

Taken from: Grundlagen der Mathematik I (1934)

Axioms:

1. \( \quad a\to(b\to a) \)
2. \( \quad [a\to(a\to b)]\to(a\to b) \)
3. \( \quad (a\to b)\to[(b\to c)\to(a\to c)] \)
4. \( \quad a\wedge b\to a \)
5. \( \quad a\wedge b\to b \)
6. \( \quad (a\to b)\to[(a\to c)\to(a\to b\wedge c)] \)
7. \( \quad a\to a\vee b \)
8. \( \quad b\to a\vee b \)
9. \( \quad (a\to c)\to[(b\to c)\to(a\vee b\to c)] \)
10. \( \quad (a\leftrightarrow b)\to(a\to b) \)
11. \( \quad (a\leftrightarrow b)\to(b\to a) \)
12. \( \quad (a\to b)\to[(b\to a)\to(a\leftrightarrow b)] \)
13. \( \quad (a\to b)\to(\neg b\to\neg a) \)
14. \( \quad a\to\neg\neg a \)
15. \( \quad \neg\neg a\to a \)

J.B. Rosser

Taken from: Logic for mathematicians (1953)

Axioms:

1. \( \quad a\to(a\wedge a) \)
2. \( \quad (a\wedge b)\to a \)
3. \( \quad (a\to b)\to[\neg(b\wedge c)\to\neg(c\wedge a)] \)

Rules of inference:

1. Modus Ponens

S.C. Kleene

Taken from: Mathematical logic (1967); see also Mathematical logic (2013);

Axioms:

1. \( \quad a\to(b\to a) \)
2. \( \quad (a\to b)\to\{[a\to(b\to c)]\to(a\to c)\} \)
3. \( \quad a\to(b\to a\wedge b) \)
4. \( \quad a\wedge b\to a \)
5. \( \quad a\wedge b\to b \)
6. \( \quad a\to a\vee b \)
7. \( \quad b\to a\vee b \)
8. \( \quad (a\to c)\to[(b\to c)\to(a\vee b\to c)] \)
9. \( \quad (a\to b)\to[(a\to\neg b)\to\neg a] \)
10. \( \quad \neg\neg a\to a \)
11. \( \quad (a\to b)\to[(b\to a)\to(a\leftrightarrow b)] \)
12. \( \quad (a\leftrightarrow b)\to(a\to b) \)
13. \( \quad (a\leftrightarrow b)\to(b\to a) \)

Rules of inference:

1. Modus Ponens

S. Tanaka

Taken from: On axiom systems of propositional logic XXV (1967)

Axioms:

1. \( \quad (a\to b)\to[(b\to c)\to(a\to c)] \)
2. \( \quad [(a\to b)\to a]\to a \)
3. \( \quad a\to[(a\to b)\to b] \)

E. Mendelson

Taken from: Introduction to mathematical logic (1997)

Axioms:

1. \( \quad a\to(b\to a) \)
2. \( \quad a\to(b\to c)\to[(a\to b)\to(a\to c)] \)
3. \( \quad (\neg b\to\neg a)\to[(\neg b\to a)\to b] \)

Rules of inference:

1. Modus Ponens

Video tutorial

2.2 Zermelo-Fraenkel set theory

2.2.1 Introduction

The first axiomatization of set theory goes back to → E. Zermelo in 1980. It was extended by → A.A. Fraenkel in 1921, but we also want to refer to the monograph → A. Fraenkel, to Fraenkel's autobiography → A.A. Fraenkel, and to the recently published historical monograph M. Wille.

Axiomatic set theory is built on the language of predicate logic. The objects of this theory are sets, written in small letters \( x, \) \( y \) etc., and there exists a relation \( \in \) between two sets: \( x\in y. \) We use the abbreviations \( x\not=y, \) \( x\not\in y, \) \( x\subseteq y \) and \( x\subset y \) which are largely self-explanatory.

Our literature sources for all what follows are → R.E. Hodel, → D.W. Hoffmann, → T.J. Jech, → T.J. Jech, → T. Lian, and → S. Lipschutz

Video tutorial

2.2.2 Axiom of existence

Formulation:

\( \exists x\,\forall y\,\big[y\not\in x\big] \)

This axiom guarantees the existence of at least one set. In particular, we postulate the existence of an empty set, that is a set which has no elements at all. Together with the existence of extensionality we can prove that there exists exactly one empty set. We denote it by the symbol \( \emptyset. \)

Video tutorial

2.2.3 Axiom of extensionality

Formulation:

\( \forall x\,\forall y\,\big[x=y\,\leftrightarrow\,\forall z\,(z\in x\leftrightarrow z\in y)\big] \)

This axiom defines the equality \( x=y \) of two sets \( x \) and \( y. \) Using the symbol \( \subseteq \) we can write \[ x=y\quad\text{if and only if}\quad\quad x\subseteq y\,\wedge\,y\subseteq y. \] Together with the axiom of existence we have the

Proposition: There is exactly one empty set.

Proof: The existence follows from the axiom of existence above. We need to prove the uniqueness. Assume we have \( x=\emptyset \) and \( y=\emptyset. \) Then the implication \[ z\in x\quad\longrightarrow\quad z\in y \] is true since \( z\in x \) is false. Analogously, the implication \[ z\in y\quad\longrightarrow\quad z\in x \] is true since \( z\in y \) is false. We conclude \[ \forall z\,(z\in x\,\leftrightarrow\,z\in y) \] and, therefore, \( x=y. \) Thus, the empty set is unique.\( \qquad\Box \)

Proposition: The empty set is subset of all sets.

Proof: Let \( a \) be any set. Then the following implication is true \[ x\in\emptyset\quad\longrightarrow\quad x\in a \] since \( x\in\emptyset \) is false. This is the statement.\( \qquad\Box \)

Video tutorial

2.2.4 Axiom schema of specification

Formulation:

\( \forall x\,\exists y\,\forall z\,\big[z\in y\,\leftrightarrow\,(z\in x\,\wedge\,\varphi(z))\big] \)

This axiom states that for any set \( x \) chosen arbitrarily, there exists a set \( y \) such that \( z\in y \) is true if and only if \( z\in x \) is true and, in addition, \( z \) has a property \( P(z) \) which is expressed as a formula \( \varphi(z) \) where \( z \) is a free variable and not bounded by any quantifier. We write \[ y=\{z\,:\,\varphi(z)\} \] for this set \( y. \) An example of such a formula \( \varphi(z) \) is \( z\in a. \) Note that this axiom is not just an axiom but an axiom schema, and this means that it contains infinite many axioms depending on the infinite range of possible choices of formulas \( \varphi(z). \)

Proposition: Let \( x \) be any set. Then there is exactly one set \( y \) with the property required in the axiom.

Proof: Assume there is another set \( \widetilde y \) such that \( z\in\widetilde y \) is true if and only if \( z\in x \) and \( \varphi(z) \) holds. Then the two implications \[ \begin{array}{ccccc} z\in y & \quad\longrightarrow\quad & z\in x\,\wedge\,\varphi(z) & \quad\longrightarrow\quad & z\in\widetilde y \\[0.6ex] z\in\widetilde y & \quad\longrightarrow\quad & z\in x\,\wedge\,\varphi(z) & \quad\longrightarrow\quad & z\in y \end{array} \] are true, and we conlude \[ z\in y\quad\longleftrightarrow\quad y\in\widetilde y\,. \] Thus, it holds \( y=\widetilde y \) due to the axiom of extensionality.\( \qquad\Box \)

The axiom of specification permits us to introduce the intersection and the difference of sets.

Definition: The intersection \( a\cap b \) of two sets \( a \) and \( b \) is defined as \[ a\cap b=\{x\,:\,x\in a\,\wedge\,x\in b\}\,. \]

We can immediately proof some of those properties of the intersection we met in the paragraphs before. For example, there hold the idempotence law \[ a\cap a=\{x\,:\,x\in a\,\wedge\,x\in a\}=\{x\,:\,x\in a\}=a \] or the commutative law \[ a\cap b=b\cap a \] where we take into account \[ \begin{array}{lll} x\in a\cap b\quad & \longleftrightarrow & \quad x\in a\,\wedge\,x\in b \\[0.6ex] & \longleftrightarrow & \quad x\in b\,\wedge\,x\in a \\[0.6ex] & \longleftrightarrow & \quad x\in b\cap a. \end{array} \] The statement follows from the axiom of extensionality.

Definition: The difference \( a\setminus b \) of two sets \( a \) and \( b \) is defined as \[ a\setminus b=\{x\,:\,x\in a\,\wedge\,x\not\in b\}\,. \]

Video tutorial

2.2.5 Axiom of pair

Formulation:

\( \forall x\,\forall y\,\exists z\,\forall a\,\big[a\in z\,\leftrightarrow\,(a=x\,\vee\,a=y)\big] \)

This axiom states that for two arbitrary sets \( x \) and \( y \) there exists a set \( z \) which consists only of the two elements \( x \) and \( y. \) We write \[ z=\{x,y\} \] for this set \( z, \) and \( \{x,y\} \) is what we call an unordered pair considering \[ \{x,y\}=\{a\,:\,a=x\,\vee a=y\}=\{a\,:\,a=y\,\vee a=x\}=\{y,x\}\,. \] In case \( x=y \) we write \( \{x\} \) instead of \( \{x,x\}. \) Finally, we set recursively \[ \{x,y,z\}=\{a\,:\,a=x\,\vee\,a=y\,\vee\,a=z\}\quad\text{etc.} \]

Example: Beginning with the empty set \( \emptyset, \) we can successively construct sets like \[ \begin{array}{ll} \{\emptyset\} & \quad\text{by applying the axiom to}\ \emptyset \\[0.6ex] \{\emptyset,\{\emptyset\}\} & \quad\text{by applying the axiom to}\ \emptyset\ \text{and}\ \{\emptyset\} \\[0.6ex] \{\emptyset,\{\emptyset,\{\emptyset\}\}\} & \quad\text{by applying the axiom to}\ \emptyset\ \text{and}\ \{\emptyset,\{\emptyset\}\} \\[0.6ex] \{\{\emptyset\},\{\emptyset,\{\emptyset\}\}\} & \quad\text{by applying the axiom to}\ \{\emptyset\}\ \text{and}\ \{\emptyset,\{\emptyset\}\}\quad\text{etc.} \end{array} \]

Video tutorial

2.2.6 Axiom of union

Formulation:

\( \forall x\,\exists y\,\forall z\,\big[z\in y\,\leftrightarrow\,\exists(w\in x)\,z\in w\big] \)

The set \( y \) is called the union set of \( x. \) It contains all elements of \( x \) and only these elements. We write \[ y=\bigcup x. \]

Example: If \( x=\{a,b\} \) we have \[ \begin{array}{lll} \displaystyle \bigcup\{a,b\}\!\!\! & = & \!\!\!\displaystyle \{z\,:\,\exists(w\in\{a,b\})\,z\in w\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,\exists(w\in\{t\,:\,t=a\,\vee t=b\})\,z\in w\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,\exists w\,(w=a\,\vee w=b)\,z\in w\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,z\in a\,\vee z\in b \}\,. \end{array} \] In case \( a=\emptyset \) and \( b=\{\emptyset\} \) this means \[ \begin{array}{lll} \displaystyle \bigcup\{\emptyset,\{\emptyset\}\}\!\!\! & = & \!\!\!\displaystyle \{z\,:\,z\in\emptyset\,\vee\,z\in\{\emptyset\}\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,z\in\{\emptyset\}\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,z=\emptyset\} \\[0.6ex] & = & \!\!\!\displaystyle \{\emptyset\}\,. \end{array} \]

Example: If \( x=\{a,b,c\} \) we have \[ \begin{array}{lll} \displaystyle \bigcup\{a,b,c\}\!\!\! & = & \!\!\!\displaystyle \{z\,:\,\exists(w\in\{a,b,c\})\,z\in w\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,\exists(w\in\{t\,:\,t=a\,\vee\,t=b\,\vee\,t=c\})\,z\in w\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,\exists w\,(w=a\,\vee\,w=b\,\vee\,w=c)\,z\in w\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,z\in a\,\vee\,z\in b\,\vee\,z\in c\}\,. \end{array} \] In case \( a=\emptyset, \) \( b=\{\emptyset,\{\emptyset\}\} \) and \( c=\{\{\emptyset\}\} \) this means \[ \begin{array}{lll} \displaystyle \bigcup\{\emptyset,\{\emptyset,\{\emptyset\}\},\{\{\emptyset\}\}\}\!\!\! & = & \!\!\!\displaystyle \{z\,:\,z\in\emptyset\,\vee\,z\in\{\emptyset,\{\emptyset\}\}\,\vee\,z\in\{\{\emptyset\}\}\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,z\in\{\emptyset,\{\emptyset\}\}\,\vee\,z\in\{\{\emptyset\}\}\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,z\in\emptyset\,\vee\,z\in\{\emptyset\}\,\vee\,z\in\{\{\emptyset\}\}\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,z\in\{\emptyset\}\,\vee\,z\in\{\{\emptyset\}\}\} \\[0.6ex] & = & \!\!\!\displaystyle \{z\,:\,z=\emptyset\,\vee\,z=\{\emptyset\}\} \\[0.6ex] & = & \!\!\!\displaystyle \{\emptyset,\{\emptyset\}\}\,. \end{array} \]

Definition: The union \( a\cup b \) of two sets \( a \) and \( b \) is defined as the union set of \( \{a,b\}, \) that is, \[ a\cup b=\bigcup\{a,b\}\,. \]

The union \( a\cup b \) satisfies all properties we met in the paragraphs before, for example the idempotence law \[ a\cup a =\{z\,:\,z\in a\,\vee\,z\in a\} =\{z\,:\,z\in a\} =a, \] or the commutativity law \[ a\cup b =\{z\,:\,z\in a\,\vee\,z\in b\} =\{z\,:\,z\in b\,\vee\,z\in a\} =b\cup a. \]

Video tutorial

2.2.7 Axiom of infinity

Formulation:

\( \exists x\,\big[\emptyset\in x\,\wedge\,\forall(y\in x)\,y\cup\{y\}\in x\big] \)

This axioms ensures the existence of a set with infinity many elements.

Example: Since \( \emptyset\in x, \) the following sets \( x \) is such a set \[ x_1=\{\emptyset,\{\emptyset\},\{\emptyset\}\cup\{\{\emptyset\}\},\{\emptyset\}\cup\{\{\emptyset\}\}\cup\{\{\emptyset\}\cup\{\{\emptyset\}\}\},\ldots\}\,. \]

Zermelo's formulation: The origins of this axiom go back to E. Zermelo 1908. Its formulation there was

\( \exists x\,\big[\emptyset\in x\,\wedge\,\forall(y\in x)\,\{y\}\in x\big] \)

Example: Starting with the empty set again, we obtain \[ x_2=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\{\{\emptyset\}\}\},\ldots\} \] as such an infinite set.

We can define a mapping \( f \) from \( x_2 \) to \( x_1 \) (considering the axiom of specification) by means of \[ f(\emptyset)=\emptyset\,,\quad f(\{y\})=f(y)\cup\{f(y)\}\,. \] For example, \[ \begin{array}{rcl} f(\{\emptyset\})\!\!\! & = & \!\!\! f(\emptyset)\cup\{f(\emptyset)\}=\{\emptyset\}\,, \\[0.6ex] f(\{\{\emptyset\}\})\!\!\! & = & \!\!\! f(\{\emptyset\})\cup\{f(\{\emptyset\})\}=\{\emptyset\}\cup\{\{\emptyset\}\}\,, \\[0.6ex] f(\{\{\{\emptyset\}\}\})\!\!\! & = & \!\!\! f(\{\{\emptyset\}\})\cup\{f(\{\{\emptyset\}\})\}=\{\emptyset\}\cup\{\{\emptyset\}\}\cup\{\{\emptyset\}\cup\{\{\emptyset\}\}\} \end{array} \] etc. The images of \( f \) are exactly the elements of \( x_1, \) such that each element of \( x_2 \) is mapped to exactly one element of \( x_1 \) and vice versa. In this sense, Zermelo's original formulation and von Neumanns reformulation of the axiom of infinity are equivalent.

For details regarding the relationship between these two variants of the axiom we refer to → G. Uzquiano who also discusses the following third variant of the axiom of infinity

\( \exists x\,\big[\emptyset\in x\,\wedge\,\forall(y\in x\,\wedge\,z\in x)\,y\cup\{z\}\in x\big] \)

as well as an axiom of infinity in Dedekind form.

Video tutorial

2.2.8 Axiom of power set

Formulation:

\( \forall x\,\exists y\,\forall z\,\big[z\in y\,\leftrightarrow\,z\subseteq x\big] \)

Definition: The set \( y \) is called the power set if \( x, \) denoted by \( {\mathcal P}(x). \)

Example: Consider the set \( x=\{a,b,c\} \) with the three elements \( a,b,c\in x \) such that the following sets are subsets of \( x \) (note that the empty set is subset of all sets) \[ \emptyset,\quad \{a\},\quad \{b\},\quad \{c\},\quad \{a,b\},\quad \{a,c\},\quad \{b,c\},\quad \{a,b,c\}\,. \] Therefore, the power set of \( x \) is \[ {\mathcal P}(x)=\{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}\,. \]

Definition: The cartesian product \( a\times b \) of two sets \( a \) and \( b \) is defined as \[ a\times b=\{t\in{\mathcal P}({\mathcal P}(a\cup b))\,:\,\exists x\,\exists\,y\,(x\in a\,\wedge\,y\in b\,\wedge\,t=(x,y))\} \] where we set \[ (x,y)=\{\{x\},\{x,y\}\}\,. \]

The idea is the following: Start with to sets \( a \) and \( b, \) and let \( x\in a \) and \( y\in b. \) Then, \[ x\in a\quad\longrightarrow\quad\{x\}\subseteq a\quad\longrightarrow\quad\{x\}\subseteq a\cup b\quad\longrightarrow\quad\{x\}\in{\mathcal P}(a\cup b). \] Analogously, \[ x\in a\,\wedge\,y\in b\quad\longrightarrow\quad\{x,y\}\subseteq a\cup b\quad\longrightarrow\quad\{x,y\}\in{\mathcal P}(a\cup b), \] and we infer \[ \{\{x\},\{x,y\}\}\subseteq{\mathcal P}(a\cup b)\quad\longrightarrow\quad\{\{x\},\{x,y\}\}\in{\mathcal P}({\mathcal P}(a\cup b)). \] We finally apply the axiom of specification to define \( a\times b. \) We call \( (a,b) \) an ordered pair considering \[ \begin{array}{l} (a,b)=\{\{a\},\{a,b\}\}\,, \\[0.6ex] (b,a)=\{\{b\},\{b,a\}\}=\{\{b\},\{a,b\}\}\,, \end{array} \] and, therefore, \( (a,b) \) and \( (b,a) \) are different sets unless \( a=b. \)

Video tutorial

2.2.9 Axiom schema of replacement

Formulation:

\( \forall(a\in x)\,\exists!b\,\varphi(a,b)\,\to\,\exists y\,\forall b\,\big[b\in y\,\leftrightarrow\,\exists(a\in x)\,\varphi(a,b)\big] \)

Let a property \( P(u,v) \) be expressed by a formula \( \varphi(u,v). \) Now, suppose that for each \( a\in x \) there exists a unique \( b \) such that \( P(a,b) \) is true. Then, there exists a set \( y \) with the property that whenever \( b\in y, \) there is an element \( a\in x \) such that \( P(a,b) \) is true, and vice versa.

We say \( a\in x \) is the preimage of \( b\in y \) and \( b\in y \) is the image of \( a\in x. \) In other words, \( \varphi \) encodes a function \( f \) in logical terms, and the axiom ensures the existence of a set \( y \) whose elements are the images under \( f \) such that each \( a\in x \) is mapped to exactly one \( b\in y, \) or, in other words, \[ x=\{x_1,x_2,x_3,\ldots\}\,,\quad\text{then there exists}\quad y=\{f(x_1),f(x_2),f(x_3),\ldots\}\,. \] We say that the function \( f \) maps \( x \) surjectively onto \( y. \)

Video tutorial

2.2.10 Axiom of foundation

Formulation:

\( \forall x\,\big[x\not=\emptyset\,\rightarrow\,\exists(y\in x)\,x\cap y=\emptyset\big] \)

The element \( x \) is called an \( \in \)-minimal element of \( x. \) Thus, every nonempty set has such an \( \in \)-minimal element.

We illustrate the axiom by various examples.

Example: The set \[ x=\{\{a,b\},\{a,b,c\}\} \] satisfies the axiom since \[ \begin{array}{lll} x\cap\{a,b\}\!\!\! & = & \!\!\! \{t\,:\,t\in\{a,b\}\,\wedge\,t\in x\} \\[0.6ex] & = & \!\!\! \{t\,:\,(t=a\,\vee\,t=b)\,\wedge\,(t=\{a,b\}\,\vee\,t=\{a,b,c\})\} \\[0.6ex] & = & \!\!\! \emptyset\,. \end{array} \]

Example: The set \[ x=\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\} \] with the three elements \[ y_1=\emptyset,\quad y_2=\{\emptyset\},\quad y_3=\{\emptyset,\{\emptyset\}\} \] satisfies the axiom since \[ x\cap y_1=x\cap\emptyset=\emptyset \] (remember that \( \emptyset \) has no element at all, and, therefore, the intersection doesn't contain any elements), but it is also true \[ \begin{array}{rcl} x\cap y_2\!\!\! & = & \!\!\! \{t\,:\,t=\emptyset\,\wedge\,(t=\emptyset\,\vee\,t=\{\emptyset\}\,\vee\,t=\{\emptyset,\{\emptyset\}\})\} \\[0.6ex] & = & \!\!\! \{t\,:\,t=\emptyset\}\,=\,\{\emptyset\}\,\not=\,\emptyset, \\[0.6ex] x\cap y_3\!\!\! & = & \!\!\! \{t\,:\,(t=\emptyset\,\vee\,t=\{\emptyset\})\,\wedge\,(t=\emptyset\,\vee\,t=\{\emptyset\}\,\vee\,t=\{\emptyset,\{\emptyset\}\})\} \\[0.6ex] & = & \!\!\! \{t\,:\,t=\emptyset\,\vee\,t=\{\emptyset\}\}\,=\,\{\emptyset,\{\emptyset\}\}\,\not=\,\emptyset. \end{array} \]

Example: Suppose there exists a set \( x \) with the property \( x\in x. \) We set \( z=\{x\} \) and calculate \[ z\cap x=\{t\,:\,t\in z\,\wedge\,t\in x\}=\{t\,:\,(t=x)\wedge t\in x\}=\{x\}\not=\emptyset \] since \( x \) and \( z \) have the element \( x \) in common.

Example: Suppose there exist two sets \( x \) and \( y \) such that \( x\in y \) and \( y\in x. \) Let \[ z=\{x,y\}\,, \] that is, \( x\in z \) and \( y\in z. \) Then \[ \begin{array}{rcl} z\cap x=\{t\,:\,t\in z\,\wedge\,t\in x\}=\{y\}\not=\emptyset, \\[0.6ex] z\cap y=\{t\,:\,t\in z\,\wedge\,t\in y\}=\{x\}\not=\emptyset. \end{array} \] This shows that there do not exist sets \( x \) and \( y \) with the property \( x\in y \) and \( y\in x. \) And likewise, sets \( x_1,x_2,x_3,x_4 \) satisfying \[ x_1\in x_2\in x_3\in x_4\in x_1 \] also do not exist. Apply the axiom to the set \( z=\{x_1,x_2,x_3,x_4\} \) to arrive at a contradiction.

Example: Consider sets \( x_1,x_2,x_3,\ldots \) with the property \[ \ldots\in x_3\in x_2\in x_1\,. \] We say they form an \( \in \)-descending chain. Now, let \[ z=\{x_1,x_2,x_3,\ldots\}\,. \] Then we have \[ x_1\cap z=\{x_2\}\,,\quad x_2\cap z=\{x_3\} \quad\text{etc.} \] This shows that sets \( x_1,x_2,x_3,\ldots \) with the mentioned property do not exist. But note that \( \in \)-ascending chains are not in contrast to the axiom, such as \[ \emptyset\in\{\emptyset\}\in\{\{\emptyset\}\}\in\{\{\{\emptyset\}\}\}\in\ldots \] The set \[ z=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\{\{\emptyset\}\}\},\ldots\} \] was proposed by → E. Zermelo in 1908 as a set theoretic realization of the natural numbers.

Video tutorial

2.2.11 Axiom of choice

We begin with Zermelo's form of this axiom which postulates the existence of a choice set.

Formulation (axiom of choice set):

\( \big[x\not=\emptyset\,\wedge\,\forall(u,v\in x)\,(u\not=v\,\to\,u\cap v=\emptyset)\,\wedge\,\forall(u\in x)\,u\not=\emptyset\big]\,\to\,\exists y\,\forall(z\in x)\,\exists!w\in z\cap y \)

First, we make the following assumption about the set nonempty \( x: \)

The statement is:

\[ z\cap y\ \text{contains exactly one element for all}\ z\in x. \]

It is the existence of such a choice set \( y \) which needs to be ensured by means of the axiom of choice.

There are many equivalent forms of this axiom. We cite the following version which postulates the existence of choice function.

Formulation (axiom of choice function): For every nonempty family \( x \) of nonempty sets, there is a choice function \( f, \) i.e. a mapping which assigns each \( u\in x \) to an unique element \( f(u)\in u \) for each set \( u\in x. \)

Note that in our first formulation which goes back to Zermelo, we require the sets to be disjoint, while in the alternative formulation the sets may not be disjoint.

Example: Let \[ x=\{\{1,2\},\{3,4,5\},\{6,7,8,9\}\}\,, \] then we have the possible choice set \[ y=\{1,3,6\} \] meets the requirements of the axiom. We could also define the choice function \[ f(\{1,2\})=1,\quad f(\{3,4,5\})=3,\quad f(\{6,7,8,9\})=6 \] and build the set \( y=\{f(\{1,2\}),f(\{3,4,5\}),f(\{6,7,8,9\}\}. \)

Example: Let \[ x=\{\{1,2\},\{3,4\},\{5,6\},\{7,8\},\ldots\}\,, \] then we have the possible choice set \[ y=\{1,3,5,7,\ldots\}\,. \] The following choice function belongs to this set \[ f(\{a,b\})=\min\{a,b\}\,. \]

Example: Consider the set \[ x=\{\{0,1\},\{1,2\},\{0,2\}\} \] which consists of three sets which are not pairwise disjoint. Then there does not exist a choice set. Namely, \[ \begin{array}{l} \text{if}\quad y=\{0\}\quad\text{then}\quad\{1,2\}\cap y=\emptyset\,, \\ \text{if}\quad y=\{1\}\quad\text{then}\quad\{0,2\}\cap y=\emptyset\,, \\ \text{if}\quad y=\{2\}\quad\text{then}\quad\{0,1\}\cap y=\emptyset\,. \end{array} \] Furthermore, \( y=\{0,1\}, \) \( y=\{0,2\}, \) \( y=\{1,2\}, \) and \( y=\{1,2,3\} \) face the same issue.

Example: Let \( {\mathcal F} \) be the family of all nonempty sets of real numbers. The axiom states that there is a choice function, but what choice function? Does it exist even if we can't find it?

Video tutorial

2.2.12 Indexed families of sets

We consider a family \( x \) of sets \( a,b,c,\ldots, \) where we use the word family as a fuzzy description of collection or set. We assume that there is a surjective function \[ f\colon I\longrightarrow x,\qquad i\mapsto x_i=f(i), \] from an index set \( I \) to \( x \) such that each element of \( x \) gets an index \( i\in I. \)

Definition: The family \( \{x_i\}_{i\in I} \) is called an indexed family of sets.

Example: Let \( x \) be the set \[ x=\{\{1,2\},\{3,4\},\{5,6\}\}\,. \] Then the function \[ \begin{array}{l} f\colon I=\{1,2,3,4\}\longrightarrow x, \\[0.4ex] f(1)=\{1,2\},\quad f(2)=\{3,4\}\,,\quad f(3)=\{5,6\} \end{array} \] defines an indexed set \( \{x_1,x_2,x_3\} \) with \( x_i=f(i). \)

Example: Let \( x \) be the set from the foregoing example. Now, let \( I=\{\{\alpha\},\{\beta\},\{\gamma\}\} \) and \[ f(\{\alpha\})=\{1,2\}\,,\quad f(\{\beta\})=\{3,4\}\,,\quad f(\{\gamma\})=\{5,6\} \] This gives an alternative index assignment of \( x. \)

Example: The set \( x \) can also be indexed by itself by means of the identity map, i.e. \( I=x \) and \[ f\colon x\longrightarrow x,\quad f(a)=a\ \text{for all}\ a\in x. \] We get the indexed family \( \{x_i\}_{i\in x} \) with the property \( i=x_i. \)

Video tutorial

2.2.13 Choice sets versus choice functions

Following → S. Lipschutz, chapter 12, we want to prove that the axiom of choice function is equivalent to the axiom of choice set.

Proposition: The axiom of choice function implies the axiom of choice set.

Proof: Let \( x \) be a nonempty family of nonempty, pairwise disjoint sets \( u,v,w,\ldots \) Furthermore, let \( f \) be a choice function. We set \[ y=\{f(u)\,:\,u\in x\}\,. \] Then it follows that the intersection \[ z\cap y=\{f(z)\}\quad\text{for all}\ z\in x \] consists of the unique element \( f(z) \) since all sets \( u,v,w,\ldots \) from \( x \) are pairwise disjoint and \( f \) is a choice function. Thus, \( y \) represents a choice set from the axiom of choice set.\( \qquad\Box \)

Proposition: The axiom of choice set implies the axiom of choice function.

Proof: Let \( x \) be a nonempty set of nonempty sets which are not necessarily disjoint. Let \( x \) be indexed by itself to obtain an indexed family \( \{x_i\}_{i\in x}. \) Define \[ x_i^*=x_i\times\{i\}\,, \] then \( \{x_i^*\}_{i\in x} \) is a nonempty set of pairwise disjoint sets since \( x_i\times\{i\}\not=x_j\times\{j\} \) for \( i\not j. \) By the axiom of choice set, there exists a set \( y \) such that \[ x_i\cap y=\{(w_i,i)\} \] consists of the unique element \( (w_i,i)\in x_i\times\{i\}. \) It holds \( w_i\in x_i, \) and we define the function \[ f(x_i)=w_i\,,\quad i\in x, \] as the choice function on the set \( x.\qquad\Box \)

Video tutorial

2.2.14 Alternatives to the axiom of choice

We often do not need the axiom of choice in its full generality. Rather, it is enough to assume the following weaker version concerning only countably many sets (countable and uncountable sets become important when we study the construction of real numbers).

Countable axiom of choice: Every countable family of nonempty sets has a choice function.

Countably infinite sets can be indexed by natural numbers, they have the same cardinality as the set of natural numbers. From this point of view it is of interest to check whether a mathematical statement can be proved using the countable axiom of choice alone or if it needs the full axiom of choice.

The countable axiom of choice (on the real line) is a consequence of the so-called axiom of determinateness. This axiom ensures a winning strategy for a certain infinite game. We refer to → T.J. Jech, chapter 12. Is it possible to develop real analysis from a game-theoretic point of view?

Video tutorial