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<m 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

Addition:

    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 \deltasequence (\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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: