Basic Set Theory

$$\newcommand{\<}{\langle} \newcommand{\>}{\rangle} \newcommand{\P}{\mathcal P} $$

This notes mainly refer to CC.Chang’s Model Theory book Appendix A.

1. Orders and Ordinals

Definition. Ordered pair
The ordered pair of $x$ and $y$ is defined by $\<x,y\>=\{\{x\}, \{x,y\}\}$

Definition. Ordered $n$-tuples
The ordered $n$-tuples of $x_1, x_2,\ldots,x_n$ is recursively defined as

$$\begin{aligned} \<x\>&=x\\ \<x_1,x_2,\ldots,x_n\>&=\<\<x_1,x_2,\ldots,x_{n-1}\>,x_n\> \end{aligned} $$

We’ll now define a bunch of classes of orderings

Definition. Partial ordering
Given a set $X$, a binary relation $R\subset X\times X$ is said to be a partial ordering if $R$ is

• reflexive: $\forall x\in X.xRx$
• antisymmetric: $\forall x,y\in X.xRy\land yRx\implies x=y$
• transitive: $\forall x,y,z\in R.xRy\land yRz\implies xRz$

Definition. Simple / linear / total / full ordering
Given a set $X$, a binary relation $R\subset X\times X$ is said to be a simple ordering if $R$ is

• a partial ordering
• connected: $\forall x,y\in R.xRy\lor yRx$

Definition. Well ordering
Given a set $X$, a binary relation $R\subset X\times X$ is said to be a well ordering if $R$ is

• a simple ordering
• every nonempty subset $Y$ of $X$ has a least element:

$$\exists y_0\in Y.\forall y\in Y.y_0Ry $$

Definition. Strict well ordering
Given a set $X$, a binary relation $R\subset X\times X$ is said to be a strict well ordering if $R$ is

• irreflexive: $\forall x\in X.x\not R x$
• $R\cup \{\<x,x\>\mid x\in X\}$ is a well ordering

Definition. Chain
A set $X$ is said to be a chain if $X$ is simply ordered by $\subset$

Definition. Ordinal
A set $\alpha$ is said to be an ordinal / ordinal number if $\alpha$ satisfies

• $\bigcup{\alpha}\subset \alpha$
• $\alpha$ is strictly well-ordered by the $\in$ relation

Definition. limit ordinal

Definition. sequence
A function whose domain is an ordinal $\alpha$ is called an $\alpha$-termed sequence

Definition. sum of ordinals
The sum $\alpha+\beta$ of two ordinals $\alpha$ and $\beta$ is the ordinal $\gamma\geq \alpha$ with the property that the chain $\gamma\setminus \alpha$ is isomorphic to the chain $\beta$

It takes transfinite induction to show that $\alpha+\beta$ exists and is unique.

Definition. concatenation of sequences
Let $f$ be an $\alpha$-termed sequence, $g$ be a $\beta$-termed sequence. The concatenation $f^\frown g$ of $f$ and $g$ is a $\alpha+\beta$-termed sequence defined by

$$\begin{aligned} f^\frown g(\xi)&=f(\xi)\quad\quad \text{for }\xi<\alpha\\ f^\frown g(\alpha+\xi)&=g(\xi)\quad\quad \text{for }\xi<\beta\\ \end{aligned} $$

2. Cardinalities and Cardinals

Definition. Cardinality
The cardinality (sometimes called power) of a set $X$, denoted by $|X|$, is the least ordinal $\alpha$ such that $X$ is enumerated by an $\alpha$-termed sequence.

Definition. Cardinal
An ordinal $\alpha$ is said to be a cardinal, or initial ordinal, if $\alpha=|\alpha|$

Definition. Regular cardinal
An uncountable cardinal number $\lambda$ is said to be regular if for every $\kappa<\lambda$, every set $S$ of cardinality $\lambda$ and every function $f:S\to \kappa$ there exists a subset $H\subset S$ of cardinal $\lambda$ such that the function $f$ is constant on the set $H$.

Definition. successor of a cardinal
The successor of a cardinal $\alpha$, denoted by $\alpha^+$, is the least cardinal greater than $\alpha$.

Definition. $\xi$-th infinite carinal
Denote the $\xi$-th infinite cardinal as $\aleph_\xi$

Definition. Limit cardinal
A cardinal $\alpha$ is said to be a limit cardinal if its not the successor of a cardinal.

Definition. Rank function $R$
The rank function $R$ is obtained by iterating the operation of forming power sets. We define inductively

$$\begin{aligned} R(0)&=0\\ R(\xi+1)&=\P(R(\xi)) \end{aligned} $$

If $\xi>0$ and is a limit ordinal,

$$R(\xi):=\bigcup_{\eta<\xi}R(\eta) $$

Lemma. Properties of the rank function

Axiom. The axiom of regularity
for every set $x$ there’s a ordinal $\xi$ such that $x\in R(\xi)$

3. Zermelo-Fraenkel Set Theory