eternalStudent

Set Theory

Models of Set Theory

Table of contents

Basic Concepts in Logic

The main problem with starting mathematics from the beginning is that there is no beginning. In order to start with set theory, one has to know some basic logic, and in order to understand the basic logic, one has to know some basic set theory. This creates a “strange loop.” To break the loop and still find a starting point, I will assume an intuitive understanding of concepts such as “statement,” “truth,” and “identity.” I will wave my hands a little about models, axioms, elements, and rules of inference, all so that I have a basis from which to start speaking in mathematical language.

Definition:

Let \(\varphi(a)\) be a verbal statement about \(a\). Then \(\varphi\) is called a property of \(a\) if the statement \(\varphi(a)\) is true.

Definition:

Let \(\varphi\) be a property. The collection of all \(a\)'s for which the statement \(\varphi(a)\) is true is called a class, and is denoted \(\left\{ a:\varphi(a)\right\}\).

Notation:

Let \(\varphi\) be a property, and write \(A:=\left\{ a:\varphi(a)\right\}\). Let \(a\) be given. If \(\varphi(a)\) is true, we write \(a\in A\); otherwise, we write \(a\notin A\).

Notation:

Let \(a,b\) be given. If they are identical we write \(a=b\); otherwise, \(a\neq b\).

The Axioms

With the discovery of paradoxes in Cantor's naive set theory, a movement began among mathematicians and logicians to find a more rigorous foundation for mathematics. In 1908 Ernst Zermelo proposed the first axiom system, and later Abraham Fraenkel formulated corrections to it. Together this axiom system is called Zermelo-Fraenkel, and is sometimes denoted \(\text{ZF}\).

Let \({\cal M}\) be a collection of classes. Then \({\cal M}\) is called a model of set theory if the following axioms hold:

1. Axiom of Existence:

There exists \(E\in{\cal M}\) such that for every \(x\in{\cal M}\), \(x\notin E\). We call such a class empty.

  1. For every empty \(E\in{\cal M}\), \(E\subseteq A\).
  2. \(A\subseteq A\).
  3. If \(A\subseteq B\) and \(B\subseteq C\), then \(A\subseteq C\), and we also write \(A\subseteq B\subseteq C\).

2. Axiom of Extensionality:

Let \(A\in{\cal M},B\in{\cal M}\). Then \(A=B\) if and only if \(A\subseteq B\) and \(B\subseteq A\).

  1. \(\{a\}:=\{x:x=a\}\)
  2. \(\{a,b\}:=\{x:x=a\text{ or }x=b\}\)
  3. \(\{A,B\}=\{B,A\}\).
  4. \(\{A,A\}=\{A\}\).

3. Axiom of Pairing:

Let \(A\in{\cal M},B\in{\cal M}\). Then there exists \(C\in{\cal M}\) such that \(A\in C\) and \(B\in C\).

4. Axiom of Separation:

Let \(A\in{\cal M}\), and let \(\varphi\) be a property. Then \(\{a\in A:\varphi(a)\}\in{\cal M}\).

  1. \(\{A,B\}\in{\cal M}\)
  2. \(\{A\}\in{\cal M}\)
  3. \(\bigcup{\cal A}:=\{a:\text{exists }A\in{\cal A}\text{ s.t. }a\in A\}\). We also write \(\bigcup\limits _{A\in{\cal A}}A\).
  4. For \({\cal A}\neq\emptyset\), define \(\bigcap{\cal A}:=\{a:\text{for all }A\in{\cal A}\text{ s.t. }a\in A\}\). We also write \(\bigcap\limits _{A\in{\cal A}}A\).

5. Axiom of Union:

Let \(A\in{\cal M}\). Then \(\bigcup A\in{\cal M}\).

  1. \(A\neq\emptyset\Longrightarrow\bigcap A\in{\cal M}\).
  2. \(A\cup B\in{\cal M}\).
  3. \(A\cap B\in{\cal M}\).
  4. \(A\setminus B\in{\cal M}\).
  5. \(A\triangle B\in{\cal M}\).
  6. Commutativity.
  7. Associativity.
  8. Distributivity.
  9. De Morgan's laws.

6. Axiom of Power Set:

Let \(A\in{\cal M}\). Then there exists \(C\in{\cal M}\) such that for every \(B\in{\cal M}\), \(B\in C\) if and only if \(B\subseteq A\). We denote it by \(P(A)\), and call it the power set of \(A\).

  1. \(\emptyset\in P(A)\).
  2. \(A\in P(A)\).
  3. \(\{\emptyset,A\}\subseteq P(A)\).
  4. \(\{\emptyset,\{A\}\}=P(\{A\})\).

7. Axiom of Foundation:

Let \(A\neq\emptyset\). Then there exists \(B\in A\) such that \(A\cap B=\emptyset\).

  1. \(A\notin A\).
  2. \(A\notin B\) or \(B\notin A\).
  3. \(A\in\mathcal{M}\), hence \(\{A\}\in\mathcal{M}\), and therefore by the axiom of foundation \(A\cap\{A\}=\emptyset\). Hence \(A\notin A\).
  4. \(A\in\mathcal{M},B\in\mathcal{M}\), hence \(\{A,B\}\in\mathcal{M}\), and therefore by the axiom of separation \(A\cap\{A,B\}=\emptyset\) or \(B\cap\{A,B\}=\emptyset\). Hence \(A\notin B\) or \(B\notin A\).

8. Axiom of Infinity:

There exists \(I\in{\cal M}\) such that \(\emptyset\in I\), and for every \(x\in I\), \(x\cup\{x\}\in I\).

9. Axiom of Replacement:

Let \(A\in{\cal M}\). Then for every property \(\varphi\) such that for every \(a\in A\) there exists a unique \(b\in{\cal M}\) for which the statement \(\varphi(a,b)\) is true, we have \(\{b:a\in A\text{ and }\varphi(a,b)\}\in{\cal M}\).

Definition:

Let \({\cal M}\) be a model of set theory, and let \(A\in{\cal M}\). Then \(A\) is called a set or a family.

Definition:

Let \(A\) be a set, and let \(B\subseteq A\) be a set. Then \(B\) is called a subset of \(A\).

Definition:

Let \({\cal F}\) be a set such that for every pair of distinct sets \(\{A,B\}\subseteq{\cal F}\), \(A\cap B=\emptyset\). Then we say that \({\cal F}\) is a family of pairwise disjoint sets.