\documentclass[%
version=last,%
a4paper,%
12pt,%
%headings=small,%
%draft=false,%
draft=true,%
pagesize]%
{scrartcl}

\usepackage{amsmath,amsthm,amssymb,mathrsfs,hfoldsty,paralist,multicol,verbatim}

\newtheorem{problem}{Problem}

\theoremstyle{definition}
\newtheorem*{solution}{Solution}

\theoremstyle{remark}
\newtheorem*{instructions}{Instructions}
\newtheorem*{rem}{Remark}

\renewcommand{\theenumi}{\alph{enumi}}
\renewcommand{\labelenumi}{\theenumi)}

\newcommand{\included}{\subseteq}
\newcommand{\pincluded}{\subset}
\newcommand{\on}{\mathbf{ON}}
\usepackage{upgreek}
\newcommand{\vnn}{\upomega}
\newcommand{\pow}[1]{\mathscr P(#1)}
\renewcommand{\leq}{\leqslant}
\newcommand{\R}{\mathbb R}
\newcommand{\mapset}[2]{{}^{#1}#2}
\newcommand{\rwf}{\mathrm{\mathbf R}}
\newcommand{\card}[1]{\operatorname{card}(#1)}
\newcommand{\rank}[1]{\operatorname{rank}(#1)}
\renewcommand{\setminus}{\smallsetminus}
\begin{document}
\begin{comment}

\setcounter{page}{0}
\thispagestyle{empty}
\mbox{}
\newpage

\end{comment}
\title{Third Examination \emph{solutions}}
\author{Math 320, David Pierce}
\date{May 25, 2011}
\maketitle
\thispagestyle{empty}

\begin{instructions}
Write solutions on separate sheets; you may
keep \emph{this} sheet. 
%Show all useful steps in performing the computations of Problem~\ref{p1}.  
In Problem~\ref{p3}, do not assume the Axiom of
Choice.  Problem~\ref{p1} is worth 
15 points; the other three problems are worh 5 points each. 
\end{instructions}


\begin{problem}\label{p1}
For each of the following sets, write its cardinality as $\aleph_{\alpha}$ or
$\beth_{\alpha}$ for some ordinal $\alpha$.
All operations involving numbers $\aleph_{\alpha}$ or $\beth_{\alpha}$
are cardinal operations; all operations involving $\vnn$ are ordinal
operations.  
\begin{multicols}2
\begin{enumerate}
\item
$\vnn$
\item
$\vnn^{\vnn}$
\item
$\sup\{\vnn,\vnn^{\vnn},\vnn^{\vnn^{\vnn}},\dots\}$
\item
the set of countable ordinals
\item
$\R$
\item
$\mapset{\vnn}{\R}$
\item
the set of uncountable subsets of $\R$
\item
$\aleph_{\vnn^{\vnn}}+\aleph_{\vnn}$
\item
$\aleph_{\vnn}+\aleph_{\vnn^{\vnn}}$
\item
$\aleph_{\vnn^{\vnn}}\cdot\aleph_{\vnn}$
\item
$\aleph_0{}^{\aleph_0{}}$
\item
$\sup\{\aleph_0,\aleph_0{}^{\aleph_0},\aleph_0{}^{\aleph_0{}^{\aleph_0}},\dots\}$ 
\item
$\aleph_{\vnn^2\cdot3+\vnn}{}^{\aleph_{\vnn^{\vnn}}}$
\item
$\beth_{\vnn+1}{}^{\beth_{\vnn}}$
\item 
$\pow{\beth_{\vnn}}$
\end{enumerate}
\end{multicols}
\end{problem}

\begin{solution}
\mbox{}
%\begin{multicols}2
\begin{enumerate}
\item
$\vnn=\aleph_0$ [it is already a cardinal, so the cardinality of
  $\vnn$ is itself, which is $\aleph_0$]
\item
$\vnn^{\vnn}$ has cardinality  $\aleph_0$ [remember that $\vnn^{\vnn}$
  is the \emph{ordinal} power; see \S5.4 of the notes] 
\item
$\sup\{\vnn,\vnn^{\vnn},\vnn^{\vnn^{\vnn}},\dots\}
  =\bigcup\{\vnn,\vnn^{\vnn},\vnn^{\vnn^{\vnn}},\dots\}$, the union of
  a nonempty countable set of 
  countably infinite sets [by part (b)], so its cardinality is $\aleph_0$ [this
    is a special case of Theorem 123 of the notes]   
\item
the set of countable ordinals is exactly the first uncountable
ordinal, which is therefore itself a cardinal, namely $\aleph_1$  
\item
$\R$ has cardinality  $\beth_1$ [since
  $\R\approx\pow{\vnn}\approx\mapset{\vnn}2\approx 2^{\aleph_0}$ (the
  cardinal power), which is $\beth_1$ by definition] 
\item
$\card{\mapset{\vnn}{\R}}
  =(2^{\aleph_0})^{\aleph_0}=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}=\beth_1$  
\item
The set of uncountable subsets of $\R$ has cardinality  $\beth_2$.
[Denote the set of uncountable subsets of $\R$ by $a$.  Then
  $\pow{\R}\setminus a$ is the set $b$ of countable subsets of $\R$.
  Since $b\preccurlyeq\mapset{\vnn}{\R}$, we have $\card b\leq\beth_1$
  by part (f).  Hence 
\begin{align*}
\beth_2=\card{\pow{\R}}=\card{a\cup b}
&\leq\card a+\card b\\
&\leq\card a+\beth_1=\max(\card a,\beth_1).
\end{align*}
Since $\beth_1<\beth_2$, we must have $\beth_2\leq\card a$.  But also 
\begin{equation*}
\card a\leq\card{\pow{\R}}=\beth_2.
\end{equation*}
Therefore $\card a=\beth_2$.  Similarly, whenever $c\pincluded d$ and
$\card c<\card d$, but $d$ is infinite, then $\card{d\setminus
  c}=\card d$.] 
\item
$\aleph_{\vnn^{\vnn}}+\aleph_{\vnn}=\aleph_{\vnn^{\vnn}}$ [the greater
  of the two alephs] 
\item
$\aleph_{\vnn}+\aleph_{\vnn^{\vnn}}=\aleph_{\vnn^{\vnn}}$ [as in part
  (i)] 
\item
$\aleph_{\vnn^{\vnn}}\cdot\aleph_{\vnn}=\aleph_{\vnn^{\vnn}}$ [as in
  parts (i) and (j)] 
\item
$\aleph_0{}^{\aleph_0{}}=2^{\aleph_0}=\beth_1$ [since
  $2^{\aleph_0}\leq\aleph_0{}^{\aleph_0}\leq(2^{\aleph_0})^{\aleph_0}=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}$;
  see Exercise 30] 
\item
$\sup\{\aleph_0,\aleph_0{}^{\aleph_0},\aleph_0{}^{\aleph_0{}^{\aleph_0}},\dots\}
=\sup\{\aleph_0,2^{\aleph_0},2^{2^{\aleph_0}},\dots\}$ [as in (k)], and
\begin{equation*}
\sup\{\aleph_0,2^{\aleph_0},2^{2^{\aleph_0}},\dots\}
=\sup\{\beth_0,\beth_1,\beth_2,\dots\}=\beth_{\vnn}
\end{equation*}
[by definition of the beths; compare Exercise 35] 
\item
$\aleph_{\vnn^2\cdot3+\vnn}{}^{\aleph_{\vnn^{\vnn}}}
  =2^{\aleph_{\vnn^{\vnn}}}$ [as in (k), since 
$2\leq\vnn^2\cdot3+\vnn\leq\vnn^{\vnn}$; the cardinal
    $2^{\aleph_{\vnn^{\vnn}}}$ is $\aleph_{\alpha}$ for some unknown
    $\alpha$, but I do not know whether it is $\beth_{\beta}$ for any
    $\beta$; see Exercise 34; note that the given cardinal must be
    understood as $\kappa^{\lambda}$, where
    $\kappa=\aleph_{\vnn^2\cdot3+\vnn}$ and
    $\lambda=\aleph_{\vnn^{\vnn}}$]  
\item
$\beth_{\vnn+1}{}^{\beth_{\vnn}}
  =(2^{\beth_{\vnn}})^{\beth_{\vnn}}
  =2^{\beth_{\vnn}\cdot\beth_{\vnn}}=2^{\beth_{\vnn}}=\beth_{\vnn+1}$  
\item 
$\card{\pow{\beth_{\vnn}}}=2^{\beth_{\vnn}}=\beth_{\vnn+1}$
\end{enumerate}
%\end{multicols}
\end{solution}

\begin{rem}
Five of the exercises involved the beths (the numbers $\beth_{\alpha}$).
\end{rem}

\begin{problem}
\mbox{}
\begin{enumerate}
\item
Write the definitions of the cardinal product $\kappa\cdot\lambda$ and
the cardinal power $\kappa^{\lambda}$. 
\item
Show that $(\kappa^{\lambda})^{\mu}=\kappa^{\lambda\cdot\mu}$.
\end{enumerate}
\end{problem}

\begin{solution}
\mbox{}
  \begin{enumerate}
  \item 
 $\kappa\cdot\lambda=\card{\kappa\times\lambda}$ and
$\kappa^{\lambda}=\card{\mapset{\lambda}{\kappa}}$. 
\item{}
[\emph{Short version:}]
There is a bijection from $\mapset{\mu}{(\mapset{\lambda}{\kappa})}$ to
$\mapset{\lambda\times\mu}{\kappa}$, namely the function that converts
a function $f$ on $\mu$ (where $f(\alpha)$ is a function $x\mapsto
f(\alpha)(x)$ from
$\lambda$ to $\kappa$ for all $\alpha$ in $\mu$) to the function
\begin{equation*}
  (x,y)\mapsto f(y)(x).
\end{equation*}
[\emph{Long version:}]
We show there is a bijection $\Phi$ from
$\mapset{\mu}{(\mapset{\lambda}{\kappa})}$ to
$\mapset{\lambda\times\mu}{\kappa}$.  An element of
$\mapset{\mu}{(\mapset{\lambda}{\kappa})}$ is a function $f$ from
$\mu$ to $\mapset{\lambda}{\kappa}$.  In particular, if
$\alpha\in\mu$, then $f(\alpha)$ is a function from $\lambda$ to
$\kappa$. We can denote this function by  
\begin{equation*}
x\mapsto f(\alpha)(x).
\end{equation*}
We can convert $f$ into a function $\Phi(f)$ from $\lambda\times\mu$
into $\kappa$ by defining 
\begin{equation*}
\Phi(f)(x,y)=f(y)(x).
\end{equation*}
Then $\Phi$ is the desired bijection.  Indeed, we can define a
function $\Psi$ from $\mapset{\lambda\times\mu}{\kappa}$ to
$\mapset{\mu}{(\mapset{\lambda}{\kappa})}$ so that, if
$g\in\mapset{\lambda\times\mu}{\kappa}$, and $\alpha\in\mu$, then
$\Psi(g)(\alpha)$ is the function  
\begin{equation*}
x\mapsto g(x,\alpha)
\end{equation*}
from $\lambda$ to $\kappa$.
Then $\Psi$ is the inverse of $\Phi$, since
\begin{equation*}
	\Phi(\Psi(g))(x,y)=\Psi(g)(y)(x)=g(x,y),
\end{equation*}
so $\Phi(\Psi(g))=g$, and
\begin{equation*}
	\Psi(\Phi(f))(y)(x)=\Phi(f)(x,y)=f(y)(x),
\end{equation*}
so $\Psi(\Phi(f))=f$.
  \end{enumerate}
\end{solution}

\begin{rem}
Part (b) was part of Exercise 25.
\end{rem}
  
\begin{problem}\label{p3}
Let $a$ be some nonempty set.
\begin{enumerate}
\item
What is a \emph{choice-function} for $a$?
\item
Define a set $b$ such that
every subset of $b$ that is linearly ordered by $\pincluded$ has an
upper bound in $b$, and every maximal element of $b$ (with respect to
$\pincluded$) is a
choice-function for $a$.  
\end{enumerate}
\end{problem}

\begin{solution}
\mbox{}
  \begin{enumerate}
  \item 
A choice-function for $a$ is a function from $\pow a\setminus\{0\}$
(or $\pow a$) to $a$ such that 
\begin{equation*}
  f(x)\in x
\end{equation*}
for all nonempty subsets $x$ of $a$.
\item
Let $b$ be the set of functions $f$ such that the domain of $f$ is a
subset of $\pow a\setminus\{0\}$ and $f(x)\in x$ whenever $x$ is a
nonempty subset 
of $a$.  In particular, if the domain of $f$ is all of $\pow
a\setminus\{0\}$, then $f$ is a choice-function for $a$.  Suppose
$g\in b$, but the domain of $g$ is a proper subset of $\pow
a\setminus\{0\}$.  Then some element $c$ of $\pow a\setminus\{0\}$ is
not in the domain of $g$.  Then $c$ has an element $d$, and therefore
$g\cup\{(c,d)\}$ is an element of $b$ that is greater (with respect to
$\pincluded$) than $g$; so $g$ is not maximal.  Thus a maximal element
of $b$ must have domain $\pow a\setminus\{0\}$ and therefore be a
choice-function for $a$. 
  \end{enumerate}
\end{solution}

\begin{rem}
Part (b) was part of Exercise 24.
\end{rem}

\begin{problem}
Recall the definition
\begin{align*}
\rwf(0)&=0,&\rwf(\alpha+1)&=\rwf(\alpha),&
\rwf(\beta)&=\bigcup\{\rwf(x)\colon x\in\beta\}, 
\end{align*}
where $\beta$ is a limit.
Show that, for every subset $a$ of $\bigcup\rwf[\on]$, there is 
\begin{enumerate}
\item
$\alpha$ such that $a\included\rwf(\alpha)$,
\item
$\beta$ such that $a\in\rwf(\beta)$.
\end{enumerate}
\end{problem}

\begin{solution}
The definition of $\rwf$ is given incorrectly in the statement of the problem.  [This was my mistake.  The correct definition had been given in the exercises, just before Exercise 28.]  Under the given incorrect definition, $\rwf(\alpha)=0$ for all $\alpha$, so that $\bigcup\rwf[\on]=0$.  The only subset of this is $0$, and this is a subset of each $\rwf(\alpha)$, but it is not an element of any $\rwf(\alpha)$, since they are all empty.  [This would have been an acceptable answer.]

Under the correct definition, $\rwf(\alpha+1)=\pow{\rwf(\alpha)}$.  Then the problem can be solved as follows.
  \begin{enumerate}
  \item 
Note that $\bigcup\rwf[\on]=\bigcup\{\rwf(\alpha)\colon\alpha\in\on\}$.
If $b$ is a member of this, let $f(b)$ be the least ordinal $\alpha$ such that $b\in\rwf(\alpha)$.  Let $\gamma=\sup\{f(x)\colon x\in a\}$.
Then 
\begin{equation*}
a\included\bigcup\{\rwf(\delta)\colon\delta\leq\gamma\}
\included\bigcup\{\rwf(\delta)\colon\delta<\gamma+\vnn\}
=\rwf(\gamma+\vnn)
\end{equation*}
(since $\gamma+\vnn$ is a limit).  So we can let $\alpha=\gamma+\vnn$.
\item
If $\alpha$ is as in (a), then $a\in\pow{\rwf(\alpha)}$, which is $\rwf(\alpha+1)$; so we can let $\beta=\alpha+1$.
  \end{enumerate}
\end{solution}

\begin{rem}
In part (a), the ordinal $f(b)$ must be a successor, which is $\rank
b+1$ by definition of the rank function. 
\end{rem}

\vfill

\noindent\textbf{Scores.}
\hfill
\renewcommand{\arraystretch}{1.2}
\begin{tabular}[t]{|r|*8{c|}}\hline
 & EA&PC&AF&M\.I&O\c S&NT&\"OT\\\hline
1&  4& 5& 5&   1&    5&11&   5\\
2&  1& 2& 3&   1&    3& 5&   4\\
3&---& 2& 1& ---&    1& 4&   2\\
4&---& 1& 2& ---&    0& 3&   0\\\hline
 & 5&10&11&   2&    9&23&  11\\\hline
 \end{tabular}
% \hfill\mbox{}
\end{document}