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

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

\newtheorem{problem}{Problem}

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

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

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

\newcommand{\lto}{\Rightarrow}
\newcommand{\card}[1]{\operatorname{card}(#1)}

\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{\Forall}[1]{\forall#1\;}
\newcommand{\Exists}[1]{\exists#1\;}
\newcommand{\liff}{\Leftrightarrow}

\renewcommand{\theequation}{\fnsymbol{equation}}
\begin{document}
\title{Fourth and Final Examination \emph{solutions}}
\author{Math 320, David Pierce}
\date{June 11 (Saturday), 2011, at 13:30 in M-04}
\maketitle
\thispagestyle{empty}

\begin{instructions}
Each of the five numbered problems is
worth 8 points. 
As usual, write solutions on separate sheets, keeping \emph{this}
sheet.  Then enjoy the holiday!  
\end{instructions}


\begin{problem}
Write down formulas defining the following\linebreak classes.  (Use only the
symbols $\in$, $\lnot$, $($, $\lto$, $)$, and $\exists$; variables; and
the constant $a$.) 
\begin{enumerate}
\item 
$\pow a$
\item
$\bigcup a$
\end{enumerate}
\end{problem}

\begin{solution}\mbox{}
  \begin{enumerate}
  \item 
$x\included a$, that is,
$\Forall y(y\in x\lto y\in a)$, that is,
    \begin{equation*}
\lnot\Exists y\lnot(y\in x\lto y\in a).
    \end{equation*}
\item
$\Exists y(y\in a\land x\in y)$.
  \end{enumerate}
\end{solution}

\begin{remark}
  The formulas \emph{defining} the classes are as given.  Then for
  example the class $\pow a$ itself is
  \begin{equation*}
  \{x\colon\lnot\Exists
  y\lnot(y\in x\lto y\in a)\}.
  \end{equation*}
\end{remark}

\begin{problem}
  Prove or disprove:
  \begin{enumerate}
  \item 
Every set is a class.
\item
Every class is a set.
  \end{enumerate}
\end{problem}

\begin{solution}
  \mbox{}
  \begin{enumerate}
  \item 
Every set $a$ is the class $\{x\colon x\in a\}$.
\item
Not every class is a set.  Indeed, the class $\{x\colon x\notin
x\}$ is not a set, for if it were the set $a$, then
\begin{equation*}
 \Forall x(x\in a\liff x\notin x),
\end{equation*}
and in particular
\begin{equation*}
  a\in a\liff a\notin a,
\end{equation*}
which is a contradiction.
  \end{enumerate}
\end{solution}

\begin{problem}
  Perform the following ordinal computations, giving the answers in
  Cantor normal form.
\end{problem}

  \begin{solution}
    \mbox{}
    \begin{enumerate}
    \item 
$3\cdot(\vnn+4)=3\cdot\vnn+3\cdot4=\vnn+12$
    \item 
$(\vnn+4)\cdot3=\vnn\cdot3+4$
\item
$(\vnn+5)^2=(\vnn+5)\cdot(\vnn+5)=(\vnn+5)\cdot\vnn+(\vnn+5)\cdot5
  =\vnn^2+\vnn\cdot5+5$  
\item
$9^{\vnn+2}=9^{\vnn}\cdot9^2=\vnn\cdot81$
\item
$(\vnn+5)^{\vnn+2}= (\vnn+5)^{\vnn}\cdot(\vnn+5)^2
  =\vnn^{\vnn}\cdot(\vnn^2+\vnn\cdot5+5)
  =\vnn^{\vnn+2}+\vnn^{\vnn+1}\cdot5+\vnn^{\vnn}\cdot5$  
\item
$(\vnn^{\vnn})^{\vnn^{\vnn}} =\vnn^{\vnn\cdot\vnn^{\vnn}}
  =\vnn^{\vnn^{1+\vnn}}=\vnn^{\vnn^{\vnn}}$ 
\item
$(\vnn^{\vnn^{\vnn}})^{\vnn^{\vnn}}
  =\vnn^{\vnn^{\vnn}\cdot\vnn^{\vnn}} =\vnn^{\vnn^{\vnn\cdot2}}$
\item
$6^{\vnn^{1330}} =(6^{\vnn})^{\vnn^{1329}}=\vnn^{\vnn^{1329}}$
    \end{enumerate}
%  \end{multicols}
  \end{solution}

\begin{problem}
  Prove, for all ordinals $\alpha$, $\beta$, and $\gamma$ such that $\alpha>1$,
  \begin{equation}\label{eqn:exp}
    \alpha^{\beta+\gamma}=\alpha^{\beta}\cdot\alpha^{\gamma}
  \end{equation}
Use the recursive definitions, and normality, of $x\mapsto\alpha^x$,
$x\mapsto\beta+x$, and $x\mapsto\delta\cdot x$ (where $\delta>0$).
You may use other known ordinal 
identities, besides~\eqref{eqn:exp} itself.
\end{problem}

  \begin{solution}
    We use induction on $\gamma$.
Since
\begin{equation*}
\alpha^{\beta+0}=\alpha^{\beta}
=\alpha^{\beta}\cdot1=\alpha^{\beta}\cdot\alpha^0,
\end{equation*}
the claim holds when $\gamma=0$. 
Suppose the claim holds when $\gamma=\delta$.  Then
\begin{equation*}
  \alpha^{\beta+\delta'}=\alpha^{(\beta+\delta)'}
=\alpha^{\beta+\delta}\cdot\alpha
=\alpha^{\beta}\cdot\alpha^{\delta}\cdot\alpha
=\alpha^{\beta}\cdot\alpha^{\delta'},
\end{equation*}
so the claim holds when $\gamma=\delta'$.

Suppose finally $\delta$ is a limit, and the claim holds when
$\gamma<\delta$.  Then
\begin{align*}
  \alpha^{\beta+\delta}
&=\alpha^{\sup_{\gamma<\delta}(\beta+\gamma)}& &\text{[by definition of
      $x\mapsto\beta+x$]}\\ 
&=\sup_{\gamma<\delta}\alpha^{\beta+\gamma}& &\text{[by normality of
      $x\mapsto\alpha^x$]}\\  
&=\sup_{\gamma<\delta}(\alpha^{\beta}\cdot\alpha^{\gamma})& &\text{[by
    inductive hypothesis]}\\ 
&=\alpha^{\beta}\cdot\sup_{\gamma<\delta}\alpha^{\gamma}& &\text{[by
    normality of $x\mapsto\alpha^{\beta}\cdot x$]}\\
&=\alpha^{\beta}\cdot\alpha^{\delta},& &\text{[by definition of
    $x\mapsto\alpha^x$]}
\end{align*}
so the claim holds when $\gamma=\delta$.
  \end{solution}

\begin{problem}
  Define the function $\alpha\mapsto V_{\alpha}$ on $\on$ by
  \begin{align*}
    V_0&=0,&
V_{\alpha+1}&=\pow{V_{\alpha}},&
V_{\beta}&=\bigcup_{\alpha<\beta}V_{\alpha},
  \end{align*}
where $\beta$ is a limit.  Find $\card{V_{\alpha}}$ in the following
cases.  Your answer should be a natural number, an aleph
$\aleph_{\beta}$, or a beth $\beth_{\gamma}$.
%\enlargethispage{1\baselineskip}
\begin{multicols}2
\begin{enumerate}
\item 
$\alpha\in\vnn$
\item
$\alpha=\vnn$
\item
$\alpha=\vnn+320$
\item
$\alpha=\vnn\cdot6$
\item
$\alpha=\vnn\cdot11+2011$
\item
$\alpha=\vnn^2$
\item
$\alpha=\aleph_1$
\item
$\alpha=\beth_1$
%\item[]Enjoy the holiday!
\end{enumerate}
\end{multicols}
\end{problem}

\begin{solution}
\mbox{}
  \begin{enumerate}
  \item
$\card{V_0}=0$, and $\card{V_{k+1}}=2^{\card{V_k}}$ if $k\in\vnn$.
\item
$\card{V_{\vnn}}=\sup_{k\in\vnn}\card{V_k}=\aleph_0$.
\item
$\card{V_{\vnn+1}}=2^{\card{V_{\vnn}}}=2^{\aleph_0}=2^{\beth_0}=\beth_1$,
  and in general
  \begin{equation*}
    \card{V_{\vnn+k}}=\beth_k
  \end{equation*}
if $k\in\vnn$; in particular, $\card{V_{320}}=\beth_{320}$. 
\item
$\card{V_{\vnn\cdot2}}=\sup_{k\in\vnn}\card{V_{\vnn+k}}=\sup_{k\in\vnn}\beth_k=\beth_{\vnn}$,
  and in general
  \begin{equation*}
    \card{V_{\vnn\cdot(n+1)}}=\beth_{\vnn\cdot n}
  \end{equation*}
if $n\in\vnn$;
in particular, $\card{V_{\vnn\cdot6}}=\beth_{\vnn\cdot5}$. 
\item
In general,
\begin{equation}\label{eqn}
\card{V_{\vnn+\alpha}}=\beth_{\alpha}
\end{equation}
for all ordinals $\alpha$; in particular,
$\card{V_{\vnn\cdot11+2011}}=\beth_{\vnn\cdot10+2011}$. 
\item
Since $\vnn^2=\vnn+\vnn^2$, we have
$\card{V_{\vnn^2}}=\beth_{\vnn^2}$. 
\item
$\card{V_{\aleph_1}}=\beth_{\aleph_1}$
\item
$\card{V_{\beth_1}}=\beth_{\beth_1}$
  \end{enumerate}
\end{solution}

\begin{remark}
  The rule~\eqref{eqn} can be proved by induction, but this was
  not required.  Note the resemblance to the rule for powers of
  natural numbers, which can be written as
  \begin{equation*}
n^{\vnn^{1+\alpha}}
=n^{\vnn\cdot\vnn^{\alpha}}=(n^{\vnn})^{\vnn^{\alpha}}=\vnn^{\vnn^{\alpha}}.  
  \end{equation*}
where $1<n<\vnn$.
\end{remark}

\section*{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&---& 3& 7& ---&    1& 7&   0\\
2&---& 3& 7&   0&    4& 7&   0\\
3&  8& 7& 7& ---&    6& 7&   6\\
4&  5& 8& 7& ---&    6& 8&   6\\
5&  0& 2& 4& ---&    2& 7&   0\\\hline
 & 13&23&32&   0&   19&36&  12\\\hline
 \end{tabular}


\end{document}
