Set Theory

Lemmas & Theorems

Lemma 1 (Zorn’s lemma). If $X$ is a partially ordered set such that every chain in $X$ has an upper bound, then $X$ contains a maximal element.

Theorem 1 (Recursion). If $a$ is an element of a set $X$, and if $f$ is a function from $X$ to $X$, then there exists a function $u$ from $w$ to $X$ such that $u(0) = a$ and such that $u(n^+) = f(u(n))$ for all $n$ in $w$.

Theorem 2 (Well ordering). Every set can be well ordered.

Theorem 3 (Transfinite recursion). If $W$ is a well ordered set, and if $f$ is a sequence function of type $W$ in a set $X$, then there exists a unique function $U$ from $W$ into $X$ such that $U(a) = f(U^a)$ for each $a$ in $W$.

Theorem 4 (Counting). Each well ordered set is similar to a unique ordinal number.

Theorem 5 (Schröder-Bernstein theorem). If $X \precsim Y$ and $Y \precsim Z$, then $X \sim Y$.

Theorem 6. Every set is strictly dominated by its power set, or, in other words,

\[X \prec \mathcal{P}(X)\]

for all $X$.