\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}