eternalStudent

Set Theory

Models of Set Theory

Table of contents

The Axioms

Following the discovery of considerable paradoxes in Cantor's naive set theory, a movement grew among mathematicians and logicians to find a more rigorous basis for mathematics. In 1908 Ernst Zermelo proposed the first axiomatic system, and later Abraham Fraenkel proposed refinements to it. Together their axiomatic system is often referred to as Zermelo-Fraenkel, and is denoted by \(ZF\).

In the beginning there was math. And math was without form, and structure; and uncertainty was upon the face of the Congress. And the spirit of Cantor moved upon the discarded drafts.
And Zermelo said, Let there be an empty set, and there was an empty set, and it was unique.

This is not the start, but it's a start: Let there be \(a\), and let \(\varphi(a)\) be a statement about \(a\), then if \(\varphi(a)\) is true, \(\varphi\) is called a property of \(a\), or a formula. The collection of all \(a\), such that the statement \(\varphi(a)\) is true, is called a class and is denoted by \(\{a : \varphi(a)\}\). If we have \(A:=\{a : \varphi(a)\}\), we can denote that \(\varphi(a_{0})\) is true by \(a_{0} \in A\), or false by \(a_{0} \notin A\).

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.

Notation:

Let \(A\in{\cal M},B\in{\cal M}\). If for every \(a\in{\cal M}\) such that \(a\in A\), we also have \(a\in B\), then we write \(A\subseteq B\). If, in addition, there exists \(b\in{\cal M}\) such that \(b\in B\) but \(b\notin A\), then we write \(A\subset B\).

Corollaries:

  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\).

Corollary:

Let \(E\in{\cal M}\) and \(E'\in{\cal M}\) be empty. Then \(E'=E\). We denote it by \(\emptyset\), and call it the empty set.

Notation:

Let \(a,b\) be classes. We write:

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

Corollaries:

  1. \(\{A,B\}=\{B,A\}\).
  2. \(\{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\).

Notation:

Let \(A\) be a class, and let \(\varphi\) be a property. Then \[ \{a\in A:\varphi(a)\}:=\{a:a\in A\text{ and }\varphi(a)\}. \]

4. Axiom of Separation:

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

Corollaries:

  1. \(\{A,B\}\in{\cal M}\)
  2. \(\{A\}\in{\cal M}\)

Notation:

Let \({\cal A}\in{\cal M}\). We write:

  1. \(\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\).
  2. For \({\cal A}\neq\emptyset\), define \(\bigcap{\cal A}:=\{a:\text{for all }A\in{\cal A}\text{ h.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}\).

Notation:

Let \(A\in{\cal M},B\in{\cal M}\). We write:

  1. \(A\cap B:=\bigcap\{A,B\}\).
  2. \(A\cup B:=\bigcup\{A,B\}\). If \(A\cap B=\emptyset\), we also write \(A\uplus B\), and say that \(A,B\) are disjoint.
  3. \(A\setminus B:=\{a\in A:a\notin B\}\).
  4. \(A\triangle B:=(A\setminus B)\cup(B\setminus A)\).

Corollaries:

Let \(A\in{\cal M},B\in{\cal M}\). Then:

  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}\).

Corollaries:

Let \(A\in{\cal M},B\in{\cal M},C\in{\cal M}\). Then:

  1. Commutativity:
    1. \(A\cup B=B\cup A\).
    2. \(A\cap B=B\cap A\).
    3. \(A\triangle B=B\triangle A\).
  2. Associativity:
    1. \((A\cup B)\cup C=A\cup(B\cup C)\). We also write \(A\cup B\cup C\).
    2. \((A\cap B)\cap C=A\cap(B\cap C)\). We also write \(A\cap B\cap C\).
    3. \((A\triangle B)\triangle C=A\triangle(B\triangle C)\). We also write \(A\triangle B\triangle C\).
  3. Distributivity:
    1. \(A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\).
    2. \(A\cup(B\cap C)=(A\cup B)\cap(A\cup C)\).
  4. De Morgan's laws:
    1. \(C\setminus(A\cap B)=(C\setminus A)\cup(C\setminus B)\).
    2. \(C\setminus(A\cup B)=(C\setminus A)\cap(C\setminus B)\).

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\).

Corollary:

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

  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\).

Claims:

Let \(A\in\mathcal{M},B\in\mathcal{M}\). Then:

  1. \(A\notin A\).
  2. \(A\notin B\) or \(B\notin A\).

Proof:

  1. \(A\in\mathcal{M}\), hence \(\{A\}\in\mathcal{M}\), and therefore by the axiom of foundation \(A\cap\{A\}=\emptyset\). Hence \(A\notin A\).
  2. \(A\in\mathcal{M},B\in\mathcal{M}\), hence \(\{A,B\}\in\mathcal{M}\), and therefore by the axiom of foundation \(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.