Axioms of set theory (ZFC)
This is my note of the video https://youtu.be/AAJB9l-HAZs. It’s not a full guide of axiomatic set theory.
Relation
Relation is a predicate of two variables.
$\in$-relation
Set theory is built on the postulate that there is a fundamental relation called $\in$ (epsilon relation).
There will be no definition of what $\in$ is, or of what a set is. Instead, we’ll define 9 axioms, that spesk of $\in$ and sets.
We call $x$ as an element of $y$ if $x\in y$ is a proposition.
Using the $\in$-relation, we can define:
$$ \begin{aligned} &\notin(x, y) := x \notin y :\Leftrightarrow \neg(x\in y) \\\ &x\subseteq y:\Leftrightarrow \forall a: (a\in x \Rightarrow a\in y) \\\ &x=y :\Leftrightarrow x\subseteq y \land y\subseteq x \end{aligned} $$
The third relation is called “Axiom of extensionality”.
Note that you can prove the transitivity of $\in$-relation.
Overview of axioms
Axioms:
- $\in$-relation
- Existence of an empty set
- Pair sets
- Union sets
- Axiom of replacement
- Existence of power sets
- Infinity
- Axiom of choice
- Axiom of foundation
- 1 and 2 are basic existence axioms.
- 3, 4, 5, 6 are construction axioms.
- 7, 8 are furthur existence/construction axioms.
- 9 is a non-existence axiom.
ZFC set theory
1. Axiom on $\in$-relation
$x\in y$ is a proposition if and only if $x$ and $y$ are both sets.
$$ \forall x: \forall y: (x\in y) \veebar \neg(x\in y) $$
We didn’t explicitly defined what is a set, but by possibility that we can regards $x\in y$ as a proposition or not.
Counter example - Russell’s paradox:
Assume there is some $R$ that contains all sets that don’t contain themselves as an element. To be precise, the proposition is as follows:
$$ \exists R: \forall z: z\in R \Leftrightarrow z\notin z \text{ ,where } z \text{ is a set.} $$
$z\notin z$ looks unfamiliar at first, because “elementary school math” trained us to distinguish “set” and “element”. But so far, we defined a set as a proposition of $\in$-relation, and there is no definition of an “element”. Hence, $z\notin z$ could be a proposition (we didn’t tell that this is true or false).
The question is, is $R$ a set?
Suppose $R$ is a set. (The statement “$R$ is a set” is true.) Then, $z\in R$ is a proposition, hence the whole statement is a proposition. Since $R$ is supposed to be a set, we can substitute $z$ as $R$ in the proposition:
$$ \exists R: R\in R \Leftrightarrow R\notin R \text{ ,where } R \text{ is a set.} $$
The proposition is always false, so there is no such $R$. Since by law of excluded middle of propositional logic, $R$ is not a set.$\blacksquare$
As you can see from this counter example, thie axiom can eliminate such “ill-defined sets”.
2. Axiom of existence of an empty set
There exists a set that contains no elements, i.e.:
$$ \exists x: \forall y: y\notin x \text{ ,where } y \text{ is a set.} $$
Theorem: There is only one empty set (in ZFC axiom), so we denote this set $x$ as $\varnothing$.
Proof:
Assume $x$ and $x’$ are both empyt sets. Then, the following two propositions are true by ex falso quodlibet:
$$ \begin{aligned} \forall y: (y\in x) &\Rightarrow (y\in x’) \\\ \forall y: (y\in x’) &\Rightarrow (y\in x) \end{aligned} $$
The first equation yields $x\subseteq x’$ and the second equation yields $x’\subseteq x$, hence $x=x’$.$\blacksquare$
3. Axiom on pair sets
Let $x$ and $y$ be sets. Then there exists a set that contains as its elements precisely $x$ and $y$.
$$ \forall x: \forall y: \exists m: \forall u: u\in m \Leftrightarrow u=x \lor u=y $$
The $m$ in the axiom is denoted by $\{x, y\}$.
Note that,
- $\{x, y\} = \{y, x\}$.
- $\{x\} := \{x, x\} $
4. Axiom on union sets
Let $x$ be a set. Then there exists a set where elements are precisely the elements of the elements of $x$.
$$ \forall x: \exists u: \forall y: \left[y\in u \Leftrightarrow \exists s: (y\in s \land s\in x) \right] $$
We denote the set $u$ as $\bigcup x$.
This axiom is required to construct a set which has more than 3 elements.
Let $a$, $b$, $c$ be sets. By axiom of pair sets, $x:=\{\{a\}, \{b\}\}$ is a set. In this example, $\bigcup x = \{a, b\}$. Assume another example $y:=\{\{a\}, \{b, c\}\}$.
$$ \bigcup y := \{a, b, c\} $$
Using pre-mathmatical number, we can generalize this definition. Let $a_1, a_2, \cdots, a_{N}$ be sets. Define recursively for all $N\geq3$:
$$ \{a_1, a_2, \cdots, a_{N}\} := \bigcup\{\{a_1, a_2, \cdots, a_{N-1}\}, \{a_N\}\} $$
5. Axiom of replacement
Functional relation
Define a functional relation as follows:
$$ R \text{ is called functional relation.} \Leftrightarrow \forall x: \exists! y: R(x,y) $$
The sign $\exists!$ is uniqueness quantifier and read “unituely exists”, “there is exactly one y exist”.
Axiom of replacement
Let $A$ be a set and $x\in A$ be a first parameter of a functional relation $R(x,\cdot)$.
The axiom of replacement states, there exist a set $B$ such that for all $y\in B$, $R(x,y)$ holds. In general, there is no garantee that the “image” of a set under a functional relation forms a set. This axiom garanties that the image is a set.
The reason this axiom is named “replacement” is, we can replace some matters in original set $A$ into a new matters in a new set $B$ by using a functional relation.
The formal definition is as follows:
$$ \forall x,y,z: (R(x,y)\land R(x,z)\Rightarrow y=z) \Rightarrow \forall A: \exists B: \forall y: (y\in B \Leftrightarrow \exists x: x\in A\land R(x,y)) $$
$y\in B$ of the RHS represent the main point of this axiom. The LHS $\forall x,y,z: (R(x,y)\land R(x,z)\Rightarrow y=z)$ is another representation that the relation $R$ is a functional relation. More precisely, this LHS is stronger definition compare to the definition of a functional relation above, because this condition includes $x$ such that there is no $y$ where $R(x,y)$.
Axiom schema of restricted comprehension
Let $P$ be a predicate of one variable $P(\cdot)$, and $m$ be a set. Then those elements $x\in m$ for which $P(x)$ holds constitute a set.
This set is usually denoted as $\{x\in m|P(x)\}$.
This axiom is also reffered as “axiom schema of specification” or “axiom schema of separation”.
Axiom of replacement implies axiom schema of restricted comprehension.
Proof:
From arbitrary proposition $P(x)$, let $x\in m$ and $R(x,y):=[(x=y)\land P(y)]$. From axiom of replacement, the following holds:
$$ \forall x,y,z: [(x=y) \land P(y) \land (x=z) \land P(z)] \Rightarrow y=z \\\ \Downarrow \\\ \forall m: \exists B: \forall y: (y\in B \Leftrightarrow \exists x: x\in m\land x=y \land P(y)) $$
In LHS, $\in$-relation is transitivie, so $y=z$. LHS is always true independently of $P(x)$ (tautology. $R$ is a relational function so LHS is true).
RHS states the existence ot the set $B$ such that $B =\{x\in m|P(x)\}$.$\blacksquare$
Axiom schema of unrestricted comprehension
Let $P$ be a predicate of one variable $P(\cdot)$. Then those variables $y$ for which $P(x)$ holds constitute a set.
This set is usually denoted as $\{x|P(x)\}$.
Historically, naïve set theory failed because of this unrestricted comprehension. Remind that $\{x|x\notin x\}$ in Russell’s paradox.
Axiomatic set theory “restricts” the possible sets by $\in$-relation.
Conclusions from axiom schema of restricted comprehension,
By axiom schema of restricted comprehension, we can define new sets from original set $m$
Example 1. compelement set:
$$ m \backslash u := \{x \in m | x \notin u \}. $$
Example 2. intersection of set:
$$ \bigcap x := \left\{a\in \bigcup x \ \bigg|\ \forall b\in x: a\in b \right\} $$
6. Axiom of existence of power sets
Let $m$ be a set. There exists a set, denoted $\mathcal{P}(m)$ whose elements are precisely the subsets of $m$:
$$ \forall m: \exists \mathcal{P}(m) : \forall a : (a \in \mathcal{P}(m) \Leftrightarrow a \subseteq m) $$
Wrong definition of power sets by unrestricted comprehension
$$ \mathcal{P}(m) := \{y|y\subseteq m\} $$
As we mentioned at “Axiom schema of unrestricted comprehension”, this is a inconsistent definition of set. Once we adopt this definition in our axioms, such set theories lead to Russell’s paradox.
Ordered pairs and cartesian product
Now-accepted formal definition of an ordered pair (Kuratowski’s definition) is the following:
$$ (a,b) := \{\{a\}, \{a,b\}\} \in A\times B \\\ A\times B:= \left\{x\in\mathcal{P}\left(\mathcal{P}\left(\bigcup \{A,B\}\right)\right)\bigg|\ \exists a\in A: \exists b\in B: x=(a,b)\right\} $$
In the next lecture (note), Prof. Frederic use ordered pairs to define $\mathbb{Z}$ from $\mathbb{N}$.
7. Axiom of infinity
This definition is bit different from normal definition of the axiom. The normal definition is follows later. There exists a set that contains the empty set and with every of its elements $y$ it also contains $\{y\}$ as an element (original definition by Zermelo).
$$ \exists x : \varnothing\in x \land \forall y : (y \in x \Rightarrow \{y\} \in x) $$
From axiom of pair sets, you can construct $\{\varnothing\}$ from $\varnothing$, and $\{\{\varnothing\}\}$, and so on. But the problem is, the axiom of pair sets guarantees only a “finite elements” set, e.g., $\{\varnothing, \{\varnothing\}\}$. By axiom of infinity, you we introduced the concept of “recursion”, hence we implicitly defined infinity.
From the definition the existing set would be like:
$$ x := \{\varnothing, \{\varnothing\}, \{\{\varnothing\}\}, \cdots \} $$
In this manner (called Zermelo ordinals), we can define a set of natural numbers as $\mathbb{N}:= x$
Modern definition
The modern definition of the axiom is as follows:
$$ \exists \mathbb{I} : \varnothing\in \mathbb{I} \land \forall x : \left[x \in \mathbb{I} \Rightarrow (x\cup\{x\})\in \mathbb{I}\right] $$
where $x\cup y := \{x, y\}$.
While The definition in the lecture constructs the “next” elements by its pair set, this precise definition, on the other hand, constructs the “next” elements by pair set (to define the one-element set $\{\phi\}$) and the union of the pair set.
The set $\mathbb{I}$ is called “inductive set”.
Under this axiom, we can define natural numbers as follows (construction of natural numbers by John von Neumann):
$$ \begin{aligned} 0 &:= \varnothing \\\ 1 &:= 0 \cup \{0\} = \{\varnothing\} \\\ 2 &:= 1 \cup \{1\} = \{\varnothing, \{\varnothing\}\} \\\ 3 &:= 2 \cup \{2\} = \{\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\} \} \\\ &\cdots \end{aligned} $$
This definition is called “von Neumann ordinals”.
By this modern definition, the set of natural numbers is defined as a subset of $\mathbb{I}$. You can find the proof here.
8. Axiom of choice
Let $x$ be a set whose elements are
- non-empty and
- pairwise disjoint.
Then, there exists a set $y$ which contains exactly one element of each element of $x$.
$$ \forall x: P(x) \Rightarrow \exists y: \forall a \in x : \exists !b \in a : a \in y \\\ \text{ where } P(x) \Leftrightarrow \underbrace{(\exists a: a\in x)}_{\text{non-epmty}} \land \underbrace{(\forall a:\forall b:(a\in x \land b \in x) \Rightarrow \{a, b\} = \varnothing)}_{\text{pairwise disjoint}} $$
You can define the axiom of choice using choice function, but we tried to avoid using the function because we didn’t defined what the “function” is yet.
The axiom of choice is independent of the other 8 axioms, which means that one could have set theory with or without the axiom of choice.
In case that the collection of nonempty sets is finite, that case is a theorem of ZF set theory.
Here are some equivalent theorems:
- Every vector space has a basis.
- Zorn’s lemma
- Well-ordering theorem
Axiom of choice can be used when proving:
- Banach–Tarski paradox.
- existence of non-measurable subsets of $\mathbb{R}$.
- existence of a complete system of representatives of an equivalence relation.
9. Axiom of foundation
Every non-empty set $x$ contains an element $y$ that has none of its elements in common with $x$:
$$ \forall x: (x\neq \varnothing) \Rightarrow \exists y\in x : \bigcap\{x, y\} = \varnothing. $$
This axiom as also known as “axiom of regularity”. Note that this axiom also eliminate the Russel’s irregular “set”.
No set is an element of itself
Let $A$ be a set, and apply the axiom of regularity to $\{A\}$. We see that there must be an element of $\{A\}$ which is disjoint from $\{A\}$. Since the only element of $\{A\}$ is $A$, it must be that $A$ is disjoint from $\{A\}$. So, since $A\cap \{A\}=\varnothing$, we cannot have $A\in A$.
Remarks
- There is no concrete set except the empty set, which mean, we can construct all required set from the only empty set.