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