\documentclass{amsart}
\usepackage{amssymb}
\usepackage{amsmath}


\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}



\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exer}{Exercise}


\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{fact}[thm]{Fact}
\newtheorem{hyp}[thm]{Hypothesis}

\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\res}{\restriction}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\cof}{\operatorname{cof}}
\newcommand{\ot}{\text{o.t.}}
\newcommand{\on}{\text{ON}}
\newcommand{\card}{\text{CARD}}
\newcommand{\ac}{\text{AC}}
\newcommand{\zf}{\text{ZF}}
\newcommand{\zfc}{\text{ZFC}}
\newcommand{\sP}{\mathcal{P}}
\newcommand{\ch}{\text{CH}}
\newcommand{\gch}{\text{GCH}}




\begin{document}
\begin{center}
\bf Cardinals
\end{center}
\bigskip

\section{Introduction to Cardinals}



We work in the base theory $\zf$. The definitions and many 
(but not all) of the basic theorems do not require $\ac$; we will 
indicate explicitly when we are using choice. 



\begin{defn} For sets $X$, $Y$, we write $X \preceq Y$ to mean 
there is a one-to-one function from $X$ to $Y$. We write 
$X \sim Y$ to mean there is a bijection from $X$ to $Y$. 
\end{defn}


\begin{thm} (Cantor-Schr\"oder-Bernstein) If $X \preceq Y$ and 
$Y \preceq X$ then $X \sim Y$. 
\end{thm}




\begin{proof}
Let $f \colon X \to Y$ and $g \colon Y \to X$ be one-to-one. 
Let $X_0=X$, $Y_0=Y$ and define recursively 
$X_n= g(Y_{n-1})$, $Y_n=f(X_{n-1})$ for $n \geq 1$. Thus, 
$X_0=X$, $X_1=g(Y)$, $X_2=g\circ f (X)$, $X_3=g \circ f \circ g (Y)$,
etc., and similarly for the $Y_n$. Note that $X_0 \supseteq 
X_1 \supseteq X_2 \supseteq \dots$, and $Y_0 \supseteq 
Y_1 \supseteq Y_2 \supseteq \dots$. 
Let $X_\infty= \bigcap_n X_n$, $Y_\infty= \bigcap_n Y_n$. 
Define $h \colon X \to Y$ by 
$$ h(x) = \begin{cases} f(x) &  \text { if } x \in X_n -X_{n+1} \text{ and } 
n \text{ is even } \\ g^{-1}(x) & \text { if } x \in X_n -X_{n+1} \text{ and } 
n \text{ is odd } \\ f(x) & \text { if } x \in X_\infty 
\end{cases}
$$
Easily $h$ is a bijection between $X_n-X_{n+2}=(X_n - X_{n+1}) \cup 
(X_{n+1}-X_{n+2})$ and $Y_n-Y_{n+2}=(Y_n - Y_{n+1}) \cup 
(Y_{n+1}-Y_{n+2})$ for any even $n$, as $f$ bijects 
$(X_n - X_{n+1})$ and $(Y_{n+1}-Y_{n+2})$ and $g^{-1}$ 
bijects $(X_{n+1}-X_{n+2})$ and $(Y_n - Y_{n+1})$. Thus, $h$
is a bijection between $X-X_\infty$ and $Y-Y_\infty$. It is 
easy to also see that $f$ induces a bijection from $X_\infty$ 
to $Y_\infty$, and thus $h$ is a bijection from $X$ to $Y$.
\end{proof}



Note that the above proof did not use $\ac$. 

\begin{defn} $\kappa$ is a cardinal if $\kappa \in \on$ and 
$\forall \alpha < \kappa \ \neg ( \alpha \sim \kappa)$.
\end{defn}

Note that this definition is easily formalized into 
set-theory, and thus the collection of cardinals is a class. Also,
note that $\ac$ is not used in the definition of cardinal. 
We frequently use $\kappa$, $\lambda$, $\mu$ for cardianls. 

If $\alpha \in \on$, we let $|\alpha |$ denote the least ordinal 
$\beta$ such that $\beta \sim \alpha$. Clearly $| \alpha|$ is 
a cardinal. Also, $|\alpha | \leq \alpha$. Again, $\ac$ 
is not needed to define $|\alpha|$ for $\alpha \in \on$. 
We refer to $|\alpha |$ as the \emph{cardinality} of $\alpha$. 


\begin{exer} Show that every $n \in \omega$, 
$\neg (n+1 \preceq n)$. 
Make sure you are giving a ``real'' proof from within $\zf$; in 
particular, you are using only the official definition of 
integer. 
\end{exer}

\begin{exer} Show that every $n \in \omega$ is a cardinal, and 
$\omega$ is a cardinal. 
\end{exer}



We define addition and multiplication on the cardinals. 
Note that these are different operations that those
defined on the ordinals. Thus, when we write $\kappa \cdot \lambda$, 
it needs to be specified (or be clear from the context) 
whether we are talking about multiplication as ordinals 
or as cardinals. 

\begin{defn} 
for cardinals $\kappa$, $\lambda$:
\begin{enumerate}
\item
$\kappa+ \lambda =| (\kappa \times \{ 0 \}) \cup (\lambda \times \{ 1 \}) |$
\item 
$\kappa \cdot \lambda =| \kappa \times \lambda |$
\end{enumerate}
\end{defn}

Note that $\kappa + \lambda$ is just the cardinality of the 
ordinals sum of $\kappa$ and $\lambda$, and likewise 
for multiplication. 
Thus, these operations are clearly associative (also 
trivial to show directly). They are also clearly commutative, 
unlike the ordinal  operations. 

\begin{lem} Any infinite cardinal is a limit ordinal. 
\end{lem}

\begin{proof}
If $\kappa$ is an infinite cardinal and $\kappa=\alpha +1$, then
$\alpha$ is also infinite. However, if $\alpha$ is an infinite
ordinal then $\alpha =1+\alpha \sim \alpha+1$ and so $|\kappa|=|\alpha|$,
a contradiction. 
\end{proof} 


\begin{exer} Show that for any cardinals $\kappa$, $\lambda$
that $\kappa + \lambda= \max \{ \kappa, \lambda\}$. 
[hint: Say $\lambda \leq \kappa$. Prove by induction on $\beta \in \on$
that if $\alpha \leq \beta$ and $\gamma$ is the mingling of 
$\alpha$ and $\beta$ according to $x_\eta < y_\eta < x_{\eta+1}$
(here $\gamma$ is the order-type of $X \cup Y$, and the $x_\eta$, 
$y_\eta$ enumerate $X$, $Y$ respectively), then $\gamma \leq \beta +n$
for some $n \in \omega$ if $\beta$ is a successor, and $\gamma \leq \beta$
if $\beta$ is a limit]. 
\end{exer}


Using $\ac$, we can the notion of cardinality of an arbitrary set. 

\begin{defn} ($\zfc$) Let $|X|$ denote the least ordinal 
$\alpha$ such that $\alpha \sim X$. 
\end{defn}

Using $\ac$, this definition is well-defined, as every set 
$X$ can be well-ordered, and thus put into bijection with an ordinal. 
Clearly the least such ordinal, namely $|X|$, is a cardinal. 

\begin{exer} Using $\ac$, give another proof of 
the Cantor-Schr\"oder-Bernstein theorem. (hint: First identify
$X$, $Y$ with cardinals, say $\kappa$, $\lambda$. Without loss of 
generality, $\kappa < \lambda$. Show, 
without using Cantor-Schr\"oder-Bernstein, that if there were a one-to-one
map from $\lambda$ to $\kappa$, then $\kappa \sim \lambda$, a contradiction.
Use the previous exercise.)
\end{exer}


 
The next result shows that for infinite cardinals $\kappa$, $\lambda$, 
$\kappa \cdot \lambda= \max\{ \kappa, \lambda \}$, and thus
addition and multiplication on the infinite cardinals coincide. 


\begin{thm} \label{cardmult}
If $\kappa$ is an infinite cardinal, then $\kappa \cdot \kappa = \kappa$.
\end{thm}


\begin{proof}
We prove this by induction on $\kappa$. Consider the following 
ordering (G\"odel ordering) on $\kappa \times \kappa$: 
\begin{equation*}
\begin{split}
 (\alpha, \beta) \triangleleft & (\alpha', \beta') \leftrightarrow
\max\{ \alpha, \beta\} < \max \{\alpha', \beta'\}\ \vee \\ &
[(\max\{ \alpha, \beta\} = \max \{\alpha', \beta'\}) \wedge 
(\alpha, \beta) <_{\text{lex}} (\alpha', \beta') ].
\end{split}
\end{equation*}
This is easily a well-order of $\kappa \times \kappa$. For 
each $(\alpha, \beta) \in \kappa \times \kappa$, the initial 
segment of this order determined by $(\alpha,\beta)$ is 
in bijection with a subset of $\max\{ \alpha, \beta \} \times \max \{ \alpha,
\beta \}$ which by induction has cardinality at most $\max \{
\alpha, \beta \} < \kappa$. Thus, the ordering $\triangleleft$ 
has length at most $\kappa$.
\end{proof}


Note again that the above theorem, which completely
characterizes addition and multiplication on the infinite cardinals,
is proved without $\ac$. The next lemma generalizes theorem~\ref{cardmult},
but now requires the axiom of choice.

\begin{thm} ($\zfc$) \label{regsucc}
Let $\kappa \in \card$. 
Let $X= \bigcup_{\alpha< \kappa} X_\alpha$, where $|X_\alpha| \leq \kappa$
for all $\alpha < \kappa$. Then $|X| \leq \kappa$. 
\end{thm}

\begin{proof}
Using $\ac$, let $f$ be a function with domain $\kappa$ such that 
for all $\alpha < \kappa$, $f(\alpha) \colon \kappa \to X_\alpha$ 
is a bijection. Define $F \colon \kappa \times \kappa \to 
X$ by $F(\alpha,\beta)= f(\alpha)(\beta)$. Clearly $F$ is onto, 
and the result follws by lemma~\ref{cardmult}. 
\end{proof}

\begin{exer} Show that $|\R| =|\omega^\omega| = 2^\omega$. 
\end{exer}






\begin{defn}
We say a set $X$ is \emph{finite} if $|X| < \omega$, 
we say $X$ is \emph{countable} if $|X| \leq \omega$. 
\end{defn}


\begin{exer}
Show that $\Z$, $\Q$, and the set of algebraic numbers are countable. 
Show that the set of formulas is the language of set theory is
countable. 
\end{exer}



To show that there is any uncountable cardinal requires the power
set axiom (this can be stated as a precise theorem; will mention later).
Armed with the power set axiom, however, the following is a basic 
result. 


\begin{thm} (Cantor) For any set $X$, there does not exist 
a map from $X$ onto $\sP(X)$. In particular, $\neg (X \sim \sP(X))$. 
\end{thm}

\begin{proof}
Suppose $f \colon X \to \sP(X)$ were onto. Define $A \subseteq 
X$ by $A= \{ x \in X \colon x \notin f(x)\}$. Since $A \in \sP(X)$, 
let $a \in X$ be such that $f(a)=A$. Then $a \in f(a) \leftrightarrow
a \in A \leftrightarrow a \notin f(a)$, a contradiction.
\end{proof}


With the axiom of choice it follows that for all cardinals $\kappa$ that
$\sP(\kappa)$ has cardinality greater than $\kappa$, and thus 
a cardinal greater than $\kappa$ exists. We would like 
to get this without the axiom of choice. To do this, fix a cardinal 
$\kappa$, and let $W_\kappa= \{ S \in \sP(\kappa \times \kappa) 
\colon S \text{ is a well-ordering }\}$. Note the use of the power set
axiom here. Using the replacement axiom, let 
$A=\{ \alpha \in \on \colon \exists S \in W_\kappa\ (\ot(S)=\alpha) \}$. 
Then $\cup A \in \on$, in fact, $A$ is easily a limit ordinal so 
$\cup A =A$. First note that is $\alpha < A$ then $|\alpha|=\kappa$ 
since by definition $\alpha= \ot(S)$ where $S$ is a well-ordering of
a subset of $\kappa$. Since any well-ordering of $\kappa$
clearly has an order-type which is bijection with $\kappa$, 
we get that $\forall \alpha < A\ (|\alpha| \leq \kappa)$. Next we claim
that $|A| > \kappa$. For suppose $f \colon \kappa \to A$ were a bijection. 
Let $\prec$ be the corresponding well-ordering of $\kappa$ 
defined by $\gamma \prec \delta \leftrightarrow 
f(\gamma) < f(\delta)$. $F$ itself is an order-isomorphism 
between $(\kappa, \prec)$ and $(A \in)$, and so $\ot(\prec)=A$. 
This is a contradiction, since $A$ is a limit (i.e., we can easily 
now define a well-order $\prec'$ of length $A + 1$). 

We have thus shown in $\zf$ the following:

\begin{lem} \label{cardsucc}
For each cardinal $\kappa$ there is a cardinal greater than $\kappa$.
\end{lem}

The following definition is therefore well-defined in $\zf$. 


\begin{defn}
For $\kappa$ a cardinal, we let $\kappa^+$ denote the least cardinal
greater than $\kappa$. 
\end{defn}


\begin{lem} \label{cardlim} If $A \subseteq \card$, then $\sup(A) \in \card$.
\end{lem}


\begin{proof}
Let $\mu= \sup(A)$. Let $\alpha < \mu$. 
Let $\kappa \in A$ be such that $alpha < \kappa$. Since $\kappa$ is 
a cardinal, there does not exist a one-to-one map from $\kappa$
into $\alpha$. Since $\kappa \leq \mu$, there does not therefore
exist a one-to-one map from $\mu$ into $\alpha$. So, 
$\forall \alpha < \mu\ \neg (|\alpha| = \mu)$ and $\mu$ 
is thus a cardinal. 
\end{proof}

We can now describe the general picture of the cardinals. We define
by transfinite recursion on the ordinals for each $\alpha \in \on$
the cardinal $\aleph_\alpha$ which is also denoted $\omega_\alpha$. 

\begin{defn}
$\omega_\alpha$ is defined by transfinite recursion by:
\begin{enumerate}
\item
$\omega_0=\omega$
\item
$\omega_{\alpha+1}=(\omega_\alpha)^+$
\item
For $\alpha$ limit, $\omega_\alpha= \sup_{\beta < \alpha} \omega_\beta$.
\end{enumerate}
\end{defn}


\begin{thm}
$\omega_\alpha$ is defined for all $\alpha \in \on$ and is a cardinal. 
Furthermore, every cardinal is of the form $\omega_\alpha$ for 
some $\alpha \in \on$. 
\end{thm}


\begin{proof}
That $\omega_\alpha$ is well-defined and a cardinal follows from 
the transfinite recursion theorem and lemmas~\ref{cardsucc}, \ref{cardlim}.
Suppose $\kappa \in \card$. Let $\alpha \in \on$ be least such that 
$\omega_\alpha \geq \kappa$. This is well-defined since a trivial
induction gives $\omega_\beta \geq \beta$ for all $\beta \in \on$. 
If $\alpha = \beta +1$ is a successor, then $\omega_\beta < \kappa$ and
so $\omega_\alpha= (\omega_\beta)^+ \leq \kappa$, and thus 
$\omega_\alpha = \kappa$. If $\alpha$ is a limit, then 
$\omega_\alpha= \sup_{\beta< \alpha} \omega_\beta \leq \kappa$ as each 
$\omega_\beta$ for $\beta < \alpha$ is $< \kappa$. So again 
$\omega_\alpha= \kappa$. 
\end{proof}




Finally in this section we introduce cardinal exponentiation. 


\begin{defn}
For $\alpha, \beta \in \on$, let ${}^\alpha\beta=\{ f \colon 
f \text{ is a function from } \alpha \text{ to } \beta\}$. 
For $\kappa$, $\lambda$ cardinals, let $\kappa^\lambda= | {}^\lambda \kappa|$.
Let $\kappa^{< \lambda}=\sup_{\alpha< \lambda} \kappa^\alpha$.
\end{defn}

Note that we need $\ac$ to discuss $\kappa^\lambda$, and we henceforth
assume $\ac$ in discussions where cardinal exponentiation is
involved. 


The following easy lemma says that the ``familiar'' exponent rules
apply to cardinal exponentiation. 


\begin{lem}
For $\kappa$, $\lambda$, $\sigma$ cardinals we have 
$\kappa^{\lambda + \sigma}= \kappa^\lambda \cdot \kappa^\sigma$, 
$(\kappa^\lambda)^\sigma= \kappa^{\lambda \cdot \sigma}$.
\end{lem}

\begin{proof}
This follows from the following facts about sets $A$, $B$, $C$:

1) If $B \cap C= \emptyset$, then there is an obvious bijection 
between ${}^{(B \cup C)} A$ and ${}^B A \times {}^C A$. 

2.) There is an obvious bijection between ${}^C ({}^B A)$ 
and ${}^{(C \times B)} A$.
\end{proof}


Here is one easy computation:

\begin{lem}
If $2 \leq \kappa \leq \lambda$ are cardinals, then 
$\kappa^\lambda = 2^\lambda$. 
\end{lem}

\begin{proof}
Clearly $\kappa^\lambda \geq 2^\lambda$. Also, 
$2^\lambda \leq (2^\kappa)^\lambda=2^{\kappa \cdot \lambda}=
2^\lambda$. 
\end{proof}


We also have the following easy basic fact.

\begin{lem}
For all cardinals $\kappa$, $2^\kappa=|\sP(\kappa)|$.
\end{lem}

\begin{proof}
This follows immediately from the fact that we may identify any 
$A \in \sP(\kappa)$ with its characteristic function 
$f_A(\alpha)=\begin{cases} 
1 & \text{ if } \alpha \in A \\ 0 & \text{ if } \alpha \notin A 
\end{cases}$\ .
\end{proof}






So by Cantor's theorem we have that $2^\kappa > \kappa$ for all 
cardinals $\kappa$. Exactly how big is $2^\kappa$? More 
generally, how do we compute $\kappa^\lambda$? We will 
turn to these questions shortly, but first we introduce some
terminology.

\begin{defn}
The \emph{continuum hypothesis}, $\ch$, is the assertion that 
$2^\omega= \omega_1$. The \emph{generalized continuum hypothesis}, $\gch$, 
is the assertion that $2^{\omega_\alpha}=\omega_{\alpha+1}$ for
all $\alpha \in \on$.
\end{defn}



\begin{exer} Show that there are $2^{2^\omega}$ functions from 
$\R$ to $\R$. Show that there are $2^\omega$ many continuous functions
from $\R$ to $\R$. 
\end{exer}


\begin{exer}
Let $X$ be a second countable space. Show that there are $2^\omega$
open (likewise for closed) subsets of $X$.  Show that there are $2^\omega$
many Borel subsets of $X$. 
\end{exer}

\begin{exer} Let $f \colon \omega_1 \to \R$ be an $\omega_1$ sequence
of reals. Show that for some $\alpha_0 < \alpha_1 < \alpha_2 < \dots$
we have $f(\alpha_0)> f(\alpha_1)> f(\alpha_2) > \dots $ (here we mean in 
the usual ordering on the reals).
\end{exer}


\section{Cofinality}


The following is a basic, important definition.

\begin{defn}
Let $\alpha$ be a limit ordinal. Then $\cof(\alpha)$ is the least
ordinal $\beta$ such that there is a function $f \colon \beta \to \alpha$
which is unbounded (also said to be cofinal) in $\alpha$. That is, 
$\forall \alpha' < \alpha\ \exists \beta' < \beta\ (f(\beta) \geq \alpha')$. 
\end{defn}


Clearly $\cof(\alpha) \leq \alpha$ and is an infinite limit ordinal. 

\begin{defn} 
An ordinal $\alpha$ is said to be \emph{regular} if $\cof(\alpha)=
\alpha$. Otherwise $\alpha$ is said to be \emph{singular}.
\end{defn}



Sometimes the convention is made that for $\alpha$ a successor that 
$\cof(\alpha)=1$, but we generally only refer to  $\cof(\alpha)$
when $\alpha$ is a limit. 



\begin{lem} \label{cof1}
Let $\alpha$ be a limit ordinal. Then there is an 
increasing map $f \colon \cof(\alpha) \to \alpha$ which is cofinal.
\end{lem}

\begin{proof}
Let $g \colon \cof(\alpha) \to \alpha$ be cofinal. Define $f$ by 
$$f(\beta)=\max \{ g(\beta), \sup_{ \gamma< \beta} f(\gamma)+1 \}.$$
\end{proof}

Thus, cofinalities are always witnessed by strictly increasing maps. 
The next fact is a sort of converse to this. 

\begin{lem} \label{cof2}
If $\alpha$, $\beta$ are limit ordinals and $f \colon \alpha \to \beta$
is cofinal and monotonically increasing (i.e., if $\alpha_1 < \alpha_2$ then 
$f(\alpha_1) \leq f(\alpha_2)$), then $\cof(\alpha)=\cof(\beta)$. 
\end{lem}

\begin{proof}
If $g \colon \cof(\alpha) \to \alpha$ is cofinal, then $f \circ g \colon 
\cof(\alpha) \to \beta$ is cofinal, so $\cof(\beta) \leq \cof(\alpha)$. 
Suppose $h \colon \cof(\beta) \to \beta$ is increasing, cofinal. 
Define $k \colon \cof(\beta) \to \alpha$ by $k(\gamma)= 
$ least $\eta$ such that $f(\eta) > g(\gamma)$. This is well-defined,
and easily cofinal into $\alpha$. Thus, $\cof(\alpha) \leq \cof(\beta)$. 
\end{proof}


\begin{lem} If $\alpha$ is a limit ordinal, then $\cof(\alpha)$
is a regular cardinal. 
\end{lem}

\begin{proof}
We have already observed that $\cof(\alpha)$ is an infinite limit
ordinal. We have $\cof(\alpha)$ regular, that is, 
$\cof(\cof(\alpha))=\cof(\alpha)$ as otherwise by composing functions
(as in lemma~\ref{cof2}) we would have a cofinal map from 
$\cof(\cof(\alpha))$ to $\alpha$. It remains to observe that a regular
ordinal is necessarily a cardinal. Suppose $\beta$ is a regular limit
ordinal, but $\kappa=|\beta| < \beta$. Let $f \colon 
\kappa \to \beta$ be a bijection. In particular, $f$ is cofinal, so 
$\cof(\beta) \leq \kappa < \beta$, a contradiction.
\end{proof}


Thus, $\cof(\cof(\alpha))=\cof(\alpha)$ for all (limit) $\alpha$. 

The above lemmas did not use $\ac$. The next lemma does use $\ac$, and
can fail without it. 


\begin{lem} ($\zfc$)
For every cardinal $\kappa$, $\kappa^+$ is regular.
\end{lem}

\begin{proof}
If not, then there would be a cofinal map $f \colon \lambda \to 
\kappa$, where $\lambda \leq \kappa$. This would write $\kappa^+$
as a $\kappa$ union of sets, each of which size $\leq \kappa$. 
This contradicts theorem~\ref{regsucc}.
\end{proof}


Thus, in $\zfc$ all successor cardinals are regular. 
What about limit cardinals?
(note: by ``limit cardinal'' we mean a cardinal not of the form $\kappa^+$.
Of course, all infinite cardinals are limit ordinals.)
The next lemma computes the cofinality of a limit cardinal. 


\begin{lem}
Let $\omega_\alpha$ be a limit cardinal. Then $\alpha$ is a limit ordinal
and $\cof(\omega_\alpha)=\cof(\alpha)$. 
\end{lem}

\begin{proof}
Clearly $\alpha$ must be a limit ordinal as otherwise $\omega_\alpha$
would be a successor cardianl. The map $\beta \mapsto 
\omega_\beta$ is increasing and cofinal from $\alpha$ to $\omega_\alpha$, so by
lemma~\ref{cof2} it follows that $\cof(\omega_\alpha)=\cof(\alpha)$. 
\end{proof}


{\bf Examples}. $\omega$ is regular. Assuming $\zfc$, so are 
$\omega_1$, $\omega_2, \dots, \omega_n, \dots$. $\omega_\omega$ is 
singular of cofinality $\omega$. All limit cardinals below 
$\omega_{\omega_1}$ are singular of cofinality $\omega$. 
$\omega_{\omega_1}$ is singular of cofinality $\omega_1$. 
$\omega_{(\omega_{\omega_2} + \omega_1)}$ is singular of cofinality 
$\omega_1$, while $\cof(\omega_{\omega_{\omega_2}})=\omega_2$.



All the limit cardinals mentioned above are singular. Are there any 
regular limit cardinals? We will see that this question 
is independent of $\zfc$ 
(in fact, the existence of such cardinals has a stronger consistency strength
than $\zfc$). For now, we make this into a definition. 


\begin{defn}
$\kappa$ is \emph{weakly inaccessible} if $\kappa$ is a regular limit
cardinal. $\kappa$ is \emph{strongly inaccessible} if $\kappa$
is regular and $\forall \lambda < \kappa\ (2^\lambda < \kappa)$. 
$\kappa$ is a \emph{strong limit cardinal} if 
$\forall \lambda < \kappa\ (2^\lambda < \kappa)$.
\end{defn}

\begin{exer} Assuming $\gch$, identify the strong limit cardinals, 
and show that $\kappa$ is weakly inaccessible iff $\kappa$ 
is strongly inaccessible. 
\end{exer}



We end this section with a basic result on cardinal arithmetic.


\begin{thm} (K\"onig) \label{konig}
For every infinite cardinal $\kappa$, $\kappa^{\cof(\kappa)} > \kappa$. 
\end{thm}

\begin{proof}
Let $f \colon \cof(\kappa) \to \kappa$ be cofinal. Suppose 
$\{ g_\alpha \}_{\alpha < \kappa}$ enumerated ${}^{(\cof(\kappa))} \kappa$. 
Define $g \in {}^{(\cof(\kappa))} \kappa$ by 
$g(\beta)=$ the least element of $\kappa- \{ g_\alpha(\beta) \colon 
\beta < f(\beta) \}$. Clearly $ g \neq g_\alpha$ for any $\alpha$, a 
contradiction.
\end{proof}



\begin{cor} 
For every infinite cardinal $\kappa$, $\cof(2^\kappa) > \kappa$. 
More generally, $\cof(\kappa^\lambda)>\lambda$. 
\end{cor}

\begin{proof}
Since $(\kappa^\lambda)^\lambda=\kappa^\lambda$, theorem~\ref{konig} 
gives that $\cof(\kappa^\lambda)$ must be greater than $\lambda$. 
\end{proof}


We can also state K\"onig's theorem in a slightly more general form.
First, we define the infinitary sum and products operations. 

\begin{defn}
If $\{ \kappa_\alpha\}_{\alpha < \delta}$ is a sequence of cardinals,
we define $\sum_{\alpha < \delta}  \kappa_\alpha$ to be the 
cardinality of the disjoint union of sets $X_\alpha$, $\alpha < \delta$, 
where $|X_\alpha|=\kappa_\alpha$. We define $\prod_{\alpha< \delta}
\kappa_\alpha$ to the cardinality of the functions $f$ with domain 
$\delta$ such that $f(\alpha) \in \kappa_{\alpha}$ for all 
$\alpha < \delta$. 
\end{defn}



\begin{exer}
Show that $\sum_{\alpha < \delta}  \kappa_\alpha 
= \delta \cdot \sup_{\alpha< \delta} ( \kappa_\alpha )$.
\end{exer}


The same diagonal argument used in theorem~\ref{konig} 
also shows the following.


\begin{thm} (K\"onig) \label{konig2}
Let $\kappa_\alpha < \lambda_\alpha$ for all $\alpha < \delta$. 
Then $\sum_{\alpha< \delta} \kappa_\alpha < \prod_{\alpha< \delta}
\lambda_\alpha$.
\end{thm}

\begin{proof}
Let $X_\alpha \subseteq \prod_{\alpha< \delta}
\lambda_\alpha$, for $\alpha < \delta$, and $|X_\alpha|= \kappa_\alpha$. 
We must show that 
$\bigcup_{\alpha < \delta} X_\alpha \neq \prod_{\alpha< \delta}
\lambda_\alpha$. For each $\alpha < \delta$, let $f(\alpha)$
be an element of $\lambda_\alpha$ which is not in 
$\{ g(\alpha) \colon g \in X_\alpha\}$. This exists since 
$|X_\alpha| = \kappa_\alpha < \lambda_\alpha$. Clearly, 
$g \notin \bigcup_{\alpha < \delta} X_\alpha$.
\end{proof}

Note that theorem~\ref{konig2} implies theorem~\ref{konig}
by taking $\kappa_\alpha=\kappa$ for all $\alpha < \delta=\cof(\kappa)$.




\section{Cardinal Arithmetic Under the $\gch$}

Assuming $\zfc+\gch$ we can readily compute $\kappa^\lambda$ for 
all $\kappa$ and $\lambda$. 

\begin{thm}
Assume $\zfc + \gch$. Let $\kappa$ be an infinite cardinal. 
Then:
\begin{enumerate}
\item
If $\lambda < \cof(\kappa)$, then $\kappa^\lambda = \kappa$. 
\item
If $\cof(\kappa) \leq \lambda \leq \kappa$, then $\kappa^\lambda =\kappa^+$.
\item
If $\lambda > \kappa$ then $\kappa^\lambda = \lambda^+$.
\end{enumerate}
\end{thm}

\begin{proof}
If $\lambda < \cof(\kappa)$, then any function $f: \lambda \to \kappa$
has bounded range. Thus, $\kappa^\lambda = \bigcup_{\alpha<\kappa}
\alpha^\lambda$. Also, $\alpha^\lambda \leq 2^{\max(\alpha,\lambda)}
\leq \kappa$ since $\alpha, \lambda < \kappa$, using the $\gch$. 

If $\cof(\kappa) \leq \lambda \leq \kappa$, then $\kappa^\lambda \geq \kappa$
by theorem~\ref{konig}. Also, $\kappa^\lambda \leq \kappa^\kappa = \kappa^+$
by $\gch$. 

If $\lambda > \kappa$, then $\kappa^\lambda \leq 2^\lambda= \lambda^+$.
Also, clearly $\kappa^\lambda \geq 2^\lambda = \lambda^+$.
\end{proof}




\section{Cardinal Arithmetic in General}

We discuss now some properties of cardinal arithmetic assuming 
only $\zfc$. We only scratch the surface here, aiming toward one
specific result. We first introduce two cardinal functions. 

\begin{defn} The \emph{beth} function $\beth_\alpha$ is defined for 
$\alpha \in \on$ by recursion on $\alpha$ as follows:
$\beth_0=\omega$, $\beth_{\alpha+1}=2^{\beth_\alpha}$, 
and for $\alpha$ limit, $\beth_\alpha= \sup_{\beta < \alpha}
\beth_\beta$. 
\end{defn}



\begin{defn} The \emph{gimel} function $\gimel_\alpha$ is defined
by $\gimel(\kappa)=\kappa^{\cof(\kappa)}$, for all cardinals $\kappa$.
\end{defn}


\begin{exer}
Show that $\gimel(\kappa)> \kappa$ and $\cof(\gimel(\kappa))>
\cof(\kappa)$.
\end{exer}



We now show that cardinal exponentiation is determined etirely 
from the gimel function and the cofinality function. From
these two functions we compute $\kappa^\lambda$ by induction on 
$\kappa$ as follows.



\begin{thm} 
For all infinite cardinals $\kappa$, $\lambda$ we have:
\begin{enumerate}
\item \label{a1}
If $\lambda \geq \kappa$ then $\kappa^\lambda = 2^\lambda$. 
\item \label{a2}
If for some $\mu < \kappa$ we have $\mu^\lambda \geq \kappa$, then 
$\kappa^\lambda= \mu^\lambda$. 
\item \label{a3}
If for all $\mu < \kappa$ we have $\mu^\lambda< \kappa$, then:
\begin{itemize}
\item
If $\lambda < \cof(\kappa)$ then $\kappa^\lambda =\kappa$.
\item
If $\cof(\kappa) \leq \lambda < \kappa$, then $\kappa^\lambda=
\gimel(\kappa)$.
\end{itemize}
\end{enumerate}
\end{thm}


\begin{proof}
(\ref{a1}) is clear, and (\ref{a2}) follows from 
$\kappa^\lambda \leq (\mu^\lambda)^\lambda = \mu^\lambda$.
The first case of (\ref{a3}) follows from the fact that 
$\kappa^\lambda= \sup_{\mu < \kappa} \mu^\lambda= \kappa$ from the
assumption of the case. 
For the second case of (\ref{a3}), clearly we have 
$\kappa^\lambda \geq \kappa^{\cof(\kappa)}=\gimel(\kappa)$. 
The upper bound follows from the following lemma.
\end{proof}



\begin{lem} \label{cl1}
If $\lambda \geq \cof(\kappa)$, then $\kappa^\lambda 
=(\sup_{\alpha < \kappa} \alpha^\lambda)^{\cof(\kappa)}$. 
\end{lem}


\begin{proof}
Fix a cofinal map $h \colon \cof(\kappa) \to \kappa$. 
To each $f \colon \lambda \to \kappa$, and each $\beta < \cof(\kappa)$
we associate a partial function $f_\beta \colon \lambda \to h(\beta)$. 
Namely, let $f_\beta= f \cap (\lambda \times h(\beta))$. The map 
$f \to (f_\beta)_{\beta < \cof (\kappa)}$ is clearly a one-to-one
map from $\kappa^\lambda$ to 
$(\sup_{\alpha < \kappa} \alpha^\lambda)^{\cof(\kappa)}$. 
\end{proof}


The next lemma gives somes information about the continuum function
at singular cardinals. 


\begin{lem}
Let $\kappa$ be a singular cardinal and suppose the continuum function 
below $\kappa$ is eventually constant, that is, there is a 
$\gamma < \kappa$ such that $2^{< \kappa} = 2^\gamma$. 
Then $2^\kappa=2^\gamma$. 
\end{lem}


\begin{proof}
An argument similar to lemma~\ref{cl1} shows that for any 
$\kappa$ we have $2^\kappa \leq (2^{< \kappa})^{\cof(\kappa)}$, and 
hence easily $2^\kappa = (2^{< \kappa})^{\cof(\kappa)}$. 
Thus, $2^\kappa= (2^{< \kappa})^{\cof(\kappa)}=
(2^\gamma)^{\cof(\kappa)}= (2^\delta)^{\cof(\kappa)}=
2^\delta=2^\gamma$, where $\gamma < \delta < \kappa$ and 
$\delta \geq \cof(\kappa)$. 
\end{proof}



We thus have the following theorem, which shows that the
continuum function can be computed entirely from the gimel function. 


\begin{thm}
For any cardinal $\kappa$:
\begin{enumerate}
\item
If $\kappa$ is a successor cardinal, then $2^\kappa=\gimel(\kappa)$.
\item
If $\kappa$ is a limit cardinal and the continuum below $\kappa$
is eventually constant, then $2^\kappa= 2^{< \kappa} \cdot \gimel(\kappa)$.
\item
If $\kappa$ is a limit cardinal and the continuum below $\kappa$
is not eventually constant, then $2^\kappa= \gimel(2^{<\kappa})$.
\end{enumerate}
\end{thm}



\begin{proof}
The first part is clear as successor cardinals are regular. 
Suppose that $\kappa$ is a limit cardinal, and the continuum function is
eventually constant below $\kappa$, say $2^{< \kappa}=2^\gamma$. 
If $\kappa$ is singular, then $2^\kappa=2^\gamma$ by the previous
lemma. If $\kappa$ is regular, then $2^\kappa=\kappa^\kappa=
\kappa^{\cof(\kappa)}=\gimel(\kappa)$. In the singular case, note 
that $2^\gamma =2^{< \kappa} \geq \kappa$. Thus, $\gimel(\kappa)=
\kappa^{\cof(\kappa)} \leq (2^\gamma)^{\cof(\kappa)}
=(2^\delta)^{\cof(\kappa)}=2^\delta=2^\gamma$ (where $\cof(\kappa)< \delta
<\kappa$). Thus, $2^{< \kappa} \cdot \gimel(\kappa)=2^{< \kappa}$. 
If $\kappa$ is regular, then $2^{< \kappa} \leq 2^\kappa= \kappa^\kappa=
\gimel(\kappa)$. So, $2^{< \kappa} \cdot \gimel(\kappa)=\gimel(\kappa)$. 
In either case, $2^\kappa= 2^{< \kappa} \cdot \gimel(\kappa)$. 
Finally, suppose $\kappa$ is a limit cardinal and the continuum 
function below $\kappa$ is not eventually constant. 
Then $\cof(2^{< \kappa})=\cof(\kappa)$. Then 
$2^\kappa=(2^{< \kappa})^{\cof(\kappa)} =\gimel(2^{< \kappa})$. 
\end{proof}



Note that if $\kappa$ is a strong limit cardinal (i.e., $2^{< \kappa}
=\kappa$) then $2^\kappa=\gimel(\kappa)$, so the continuum function
and gimel function coincide in the main case of interest. 

What can be said about the value of $2^\kappa$ or $\gimel(\kappa)$ 
in general? We shall see that if $\kappa$ is regular, then nothing more 
can be said that $2^\kappa> \kappa$ and $\cof(2^\kappa)> \kappa$ 
(and of course if $\kappa_1 < \kappa_2$ then $2^{\kappa_1} \leq 2^{\kappa_2}$
). So, for $\kappa$ regular, $2^\kappa=\gimel(\kappa)$ is basically 
arbitrary subject to Cantor's and K\"onig's theorems. 

If $\kappa$ is a singular limit cardinal, the situation is much
more difficult. Here there are restrictions on $2^\kappa$. 
For now, let's just observe one more fact about the gimel function. 
Note that if there is a $\lambda < \kappa$ such that $\lambda^{\cof(\kappa)}
 \geq \kappa$, then $\gimel(\kappa)=\lambda^{\cof(\kappa)}$, and so is
computed by exponentiation on smaller cardinals. 

\begin{exer} 
Suppose $\kappa$ is a singular limit cardinal. Suppose there is a 
$\lambda < \kappa$ such that $\lambda^{\cof(\kappa)} \geq \kappa$, and
let $\lambda$ be the least such. Show that $\cof(\lambda) \leq \cof(\kappa)$.
\end{exer}



More generally, if there is a $\lambda < \kappa$ with 
$\cof(\lambda) \geq \cof(\kappa)$ and $\gimel(\lambda)\geq \kappa$, then 
$\gimel(\kappa)=\kappa^{\cof(\kappa)} \leq \lambda^{\cof(\lambda)
\cdot \cof(\kappa)}=\lambda^{\cof(\lambda)}=\gimel(\lambda)$. 

Finally, suppose $\kappa$ is a singular limit cardinal and there is
no $\lambda < \kappa$ such that $\lambda^{\cof(\kappa)} \geq 
\kappa$. We claim that $\cof(\gimel(\kappa))\geq$ the the least $\alpha$
such that $\lambda^\alpha \geq \kappa$ for some $\lambda < \kappa$. 
For suppose $\lambda^\alpha< \kappa$ for all $\lambda< \kappa$, we show that
$\cof(\gimel(\kappa))> \alpha$. Then $\gimel(\kappa)^\alpha=
\kappa^{\cof(\kappa) \cdot \alpha}$. We may assume $\alpha \geq \cof(\kappa)$
as we know that $\cof(\gimel(\kappa))\geq \cof(\kappa)$. Thus, 
$\gimel(\kappa)^\alpha=\kappa^\alpha= (\sup_{\lambda< \kappa} \lambda^\alpha)
^{\cof(\kappa)}= \kappa^{\cof(\kappa)}=\gimel(\kappa)$. Thus, 
$\cof(\gimel(\kappa))> \alpha$ by K\"onig. 

We have thus shown:

\begin{lem}
Suppose $\kappa$ is a singular strong limit cardinal. 
Then $\cof(\gimel(\kappa))> \kappa$. 
\end{lem} 

















\end{document}
