# Set Theory, Notes 1: Ordinals and Cardinals

Unless otherwise specified, we will assume ZF axioms.  Recall the following ZF axiom:

Axiom of Infinity:

$(\exists\omega)(\varnothing\in\omega\wedge(\forall x\in\omega)(x\cup\{x\}\in\omega)).$

We will call $\omega$ the set of natural numbers.  That is,

$\begin{array}{rcl}0&=&\varnothing\\1&=&0\cup\{0\}=\{0\}\\2&=&1\cup\{1\}=\{0,1\}\\&\vdots&\\n+1&=&n\cup\{n\}\\&\vdots&\end{array}$

We can then define $\omega+1=\omega\cup\{\omega\}$ and iterate as before, whence by applying the axiom of infinity again we can obtain $\omega\cdot 2:=\omega+\omega,$ and so on.  All such sets generated by this process are called ordinals.  This in turn gives us the canonical linear ordering of the ordinals where $n iff $n\in m.$

Definition 1.  An ordinal $\alpha$ is a successor ordinal iff $\alpha=\beta+1.$  A limit ordinal is an ordinal which is not a successor ordinal.

Proposition 2.  (Transfinite Induction)  Let $Ord$ denote the class of all ordinals (in accordance to VBG notion of class) and $C$ be a class.  If

1. $0\in C,$
2. $\alpha\in C\Longrightarrow\alpha+1\in C,$ and
3. if $\gamma$ is a limit ordinal and $\alpha\in C$ for all $\alpha<\gamma,$ then $\gamma\in C,$

then $C=Ord.$

Proof.  Since $<$ is a linear ordering on the ordinals, let $\alpha$ be the least ordinal such that $\alpha\notin C.$  But then $\alpha+1\in C$ which is a contradiction.  Hence $C=Ord.$

We can index ordinals with ordinals to generate the notion of a sequence of ordinals.  We define an nondecreasing (nonincreasing) sequence of ordinals an ordered set $\{\gamma_\alpha\}$ of ordinals where $\gamma_\alpha\leq\gamma_\beta$ iff $\alpha\leq\beta.$

Definition 3.  Let $\{\gamma_\alpha\}$ be an nondecreasing sequence of ordinals and $\xi$ be a limit ordinal and $\alpha<\xi.$  Then we define the limit of the sequence as

$\displaystyle\lim_{\alpha\to\xi}\gamma_\alpha=\sup_{\alpha<\xi}\{\gamma_\alpha\}.$

A dual definition can be defined for nonincreasing sequences, in which case the limits can be respectively distinguished as left and right limits.  A sequence $\{\gamma_\alpha\}$ is continuous if for every limit ordinal $\xi$ in the indexing subclass we have

$\displaystyle\lim_{\alpha\to\xi}\gamma_\alpha=\gamma_\xi.$

An example of a sequence which is not continuous may be one of the form $S=(...,\gamma_{\beta},\gamma_{\beta+1},...)$ where $\gamma_{\beta},\gamma_{\beta+1}$ are both limit ordinals.  So in this case

$\displaystyle\lim_{\alpha\to\beta+1}\gamma_\alpha=\sup_{\alpha<\beta+1}\{\gamma_\alpha\}=\gamma_{\beta}\neq\gamma_{\beta+1}$

(since the sup is actually a max in this case).

Definition 4.  (Ordinal Arithmetic)  We define

1. $\alpha+0=\alpha,$
2. $\alpha+(\beta+1)=(\alpha+\beta)+1,$
3. $\alpha+\beta=\lim_{\gamma\to\beta}\alpha+\gamma.$

Multiplication:

1. $\alpha\cdot 0=0,$
2. $\alpha\cdot(\beta+1)=\alpha\cdot\beta+\alpha,$
3. $\alpha\cdot\beta=\lim_{\gamma\to\beta}\alpha\cdot\gamma.$

Exponentiation:

1. $\alpha^0=1,$
2. $\alpha^{\beta+1}=\alpha^\beta\cdot\alpha,$
3. $\alpha^\beta=\lim_{\gamma\to\beta}\alpha^\gamma.$

It follows that addition and multiplication are both associative, but not commutative.  In particular one can see that

$1+\omega=\omega\neq\omega+1$

and

$2\cdot\omega=\omega\neq\omega\cdot 2=\omega+\omega.$

Definition 5.  For a set $X,$ we define its cardinality, denoted $|X|,$ as the unique ordinal with which the set has a bijection.  The corresponding subclass of ordinals is called the class of cardinals.

Proposition 6.  If $|X|=\kappa,$ then $|P(X)|=2^\kappa.$

Proof.  For every $A\subseteq X,$ define

$\displaystyle\chi_A(x)=\left\{\begin{array}{ll}1&x\in A\\ 0&x\in X-A\end{array}\right..$

Hence the mapping $f:A\mapsto\chi_A(X)$ is a bijection between $P(X)$ and $\{0,1\}^X.$

Hence in this context, Cantor’s theorem immediately follows: $|X|<|P(X)|.$

Proposition 7.  Let $|A|=\kappa,$ $|B|=\lambda,$ and $A\cap B=\varnothing.$  Then

1. $|A\cup B|=\kappa+\lambda,$
2. $|A\times B|=\kappa\cdot\lambda,$
3. $\left|A^B\right|=\kappa^\lambda.$

Proof.  We have

$|A\cup B|=|A\sqcup B|=|\kappa\sqcup\lambda|=\kappa+\lambda.$

Also if $f:A\to\kappa$ and $B\to\lambda$ are bijections, then we can define $h:A\times B\to\kappa\cdot\lambda$ by $h:(a,b)\mapsto f(a)\cdot g(b)\in\kappa\cdot\lambda,$ and this is easily seen to be a bijection.

And if $k\in A^B$ then we can define $h:k\mapsto k(b)^b\in\kappa^\lambda,$ which is also seen to be a bijection.

It thus follows that addition and multiplication of cardinals are commutative (that is, ordinal operations are commutative on this subclass).

Above we said $1+\omega=\omega\neq\omega +1$ and $2\cdot\omega=\omega\neq\omega\cdot 2.$  But

$\omega=|\omega|=|1+\omega|=|\omega+1|$

and

$\omega=|n\cdot\omega|=|\omega\cdot n|=\left|\omega\uparrow\uparrow n\right|$

for any finite ordinal $n$ with Knuth notation

$\displaystyle\omega\uparrow\uparrow n=\omega^{\omega^{\cdot^{\cdot^{\cdot^\omega}}}}$

having $n$ raisings of $\omega.$  Consider the following convention for defining countable infinite ordinals:

$\displaystyle \omega,\omega+1,...,\omega\cdot 2,...,\omega^2,...,\omega^\omega,...,\omega\uparrow\uparrow\omega=\varepsilon_0,...,\varepsilon_1=\varepsilon_0\uparrow\uparrow\varepsilon_0,...,\\\varepsilon_2=\varepsilon_1\uparrow\uparrow\varepsilon_1,...,\varepsilon_\omega,...,\varepsilon_{\varepsilon_0},...,\varepsilon_{\varepsilon_{\ddots}},...$

They are all called countable infinite ordinals since for any one of them $\alpha,$ $|\alpha|=\omega.$  To clarify when we are talking about cardinal numbers versus ordinal numbers, we will use aleph notation: $\aleph_0=\omega.$  From Cantor’s theorem above, we know that if $|X|=\aleph_0,$ then $|P(X)|=2^{\aleph_0}>\aleph_0.$  That is, the ordinal corresponding to $2^{\aleph_0}$ must be greater than all of the countable ordinals above, otherwise its cardinality would be $\aleph_0.$  This necessitates the notion of uncountable ordinals and corresponding uncountable cardinals.  We use subscripts to characterize these: $\aleph_1=\omega_1,\aleph_2=\omega_2,$ etc.

Definition 8.  An infinite cardinal $\aleph_\alpha$ is a successor cardinal iff $\alpha$ is a successor ordinal, and it is a limit cardinal iff $\alpha$ is a limit ordinal.

Definition 9.  Let $\alpha$ be a limit ordinal.  An increasing $\delta$sequence $(\beta_\gamma)_{\gamma<\delta}$ with $\delta$ a limit ordinal is cofinal in $\alpha$ if $\lim_{\gamma\to\delta}\beta_\gamma=\alpha.$  And if $\alpha$ is an ordinal, then we define its cofinality as

$\displaystyle\text{cf}\,\alpha=\inf\left\{\delta:\lim_{\gamma\to\delta}\beta_\gamma=\alpha\right\}.$

It is easy to verify that $\text{cf}\,\alpha=1$ iff $\alpha$ is a successor ordinal.  Also $\text{cf}\,0=0,\text{cf}\,\omega=\omega,$ and $\text{cf}\,\omega_\alpha=\omega_\alpha$ for any finite ordinal $\alpha.$

Proposition 10.  $\mbox{cf}\,\mbox{cf}\,\alpha=\mbox{cf}\,\alpha.$

Proof.  Let $\mbox{cf}\,\alpha=c.$  Then $\lim_{\gamma\to c}\beta_\gamma=\alpha$ (in particular it is the smallest such $c$).  Now if $\mbox{cf}\,\mbox{cf}\,\alpha=\mbox{cf}\,c=d,$ then certainly $d\leq c.$  Now since $(\beta_\gamma)$ is cofinal in $\alpha,$ a subsequence of indices $(\gamma_\delta)$ is cofinal in $c$ (where cofinality can be chosen to be $d$).  So

$\displaystyle\lim_{\delta\to d}\gamma_\delta=c.$

But then $\left(\beta_{\gamma_\delta}\right)$ is cofinal in $\alpha.$  That is,

$\displaystyle\lim_{\delta\to d}\beta_{\gamma_\delta}=\alpha,$

whence $d\geq c.$

Definition 11.  An ordinal $\alpha$ is regular if $\mbox{cf}\,\alpha=\alpha.$  It is singular if it is not regular.

Corollary 12.  If $\alpha$ is a limit ordinal, then $\mbox{cf}\,\alpha$ is a regular cardinal.

Theorem 13.  If $\kappa$ is an infinite cardinal, then $\kappa<\kappa^{\mbox{cf}\,\kappa}.$

[1]  Jech, Thomas.  Set Theory.  3rd Edition.  Springer Monographs in Mathematics.  Springer-Verlag.  2000.