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

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

\newtheorem{problem}{Problem}

\theoremstyle{definition}
\newtheorem*{sol}{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}
\renewcommand{\leq}{\leqslant}


\begin{document}
\title{Second Examination \emph{solutions}}
\author{Math 320, David Pierce}
\date{May 6, 2011}
\maketitle
\thispagestyle{empty}
\begin{comment}

\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 the proofs requested in the other three
problems, you may assume any theorems that would normally be used in
those proofs, under the restrictions given.  Problem~\ref{p1} is worth
15 points; the others are 5 each. 
\end{instructions}

\end{comment}

\begin{problem}\label{p1}
Write the following ordinals in Cantor normal form (that is, in base
$\vnn$).  All exponents should themselves be in normal form.
(\emph{Exception:}  The exponent $1$ and the coefficient $1$ need not
be written.  In strict normal form, $\vnn$ should be written as
$\vnn^{\vnn^0}$ or even
$\vnn^{\vnn^0\cdot1}\cdot1$; but this is not required.)
\end{problem}

\begin{sol}\mbox{} 
\begin{multicols}2
\begin{enumerate}
\item
$\vnn+2$ [already in normal form]
\item
$2+\vnn=\vnn$
\item
$\vnn^2+\vnn$ [already in normal form]
\item
$\vnn+\vnn^2=\vnn^2$
\item
$(\vnn+2)\cdot2=\vnn\cdot2+2$
\item
$2\cdot(\vnn+2)=2\cdot\vnn+2\cdot2=\vnn+4$
\item
$(\vnn+2)\cdot\vnn=\vnn\cdot\vnn=\vnn^2$
\item
$(\vnn+2)\cdot(\vnn+2)=(\vnn+2)\cdot\vnn+(\vnn+2)\cdot2=\vnn^2+\vnn\cdot2+2$ [by (g) and (e)]
\item
$(\vnn+2)^2=\vnn^2+\vnn\cdot2+2$ [by (h)]
\item
$2^{\vnn+2}=2^{\vnn}\cdot2^2=\vnn\cdot4$
\item
$(\vnn+2)^{\vnn}=\vnn^{\vnn}$
\item
$(\vnn+2)^{\vnn+2}=(\vnn+2)^{\vnn}\cdot(\vnn+2)^2=\vnn^{\vnn}\cdot(\vnn^2+\vnn\cdot2+2) =\vnn^{\vnn+2}+\vnn^{\vnn+1}\cdot2+\vnn^{\vnn}\cdot2$ [by (k) and (i)]
\item
$(\vnn^{\vnn^{\vnn}})^{\vnn^{\vnn^{\vnn}}}=\vnn^{\vnn^{\vnn}\cdot\vnn^{\vnn^{\vnn}}} =\vnn^{\vnn^{\vnn+\vnn^{\vnn}}} =\vnn^{\vnn^{\vnn^{\vnn}}}$
\item
$(\vnn^{\vnn^{\vnn^{\vnn}}})^{\vnn^{\vnn^{\vnn}}} =\vnn^{\vnn^{\vnn^{\vnn}}\cdot\vnn^{\vnn^{\vnn}}} =\vnn^{\vnn^{\vnn^{\vnn}+\vnn^{\vnn}}} =\vnn^{\vnn^{\vnn^{\vnn}\cdot2}}$
\item
$2^{\vnn^{2}}=(2^{\vnn})^{\vnn}=\vnn^{\vnn}$
\end{enumerate}
\end{multicols}
\end{sol}

\begin{rem}
It is essential to distinguish between $2+\vnn$ (which is $\vnn$) and  $\vnn+2$ (which is not).  One cannot do anything with ordinals without having internalized this distinction (made it a part of oneself).

Some people misremembered various rules of arithmetic, or forgot the special conditions under which they apply.  I don't try to memorize them, myself; I figure out what they must be, and I play with them, so that I develop a feeling for \emph{why} they should be true.
\end{rem}

\clearpage

\begin{problem}
\mbox{}
\begin{enumerate}
\item
State the recursive definition of ordinal addition.
\item
Prove from this definition that $0+\alpha=\alpha$ for all $\alpha$.
\end{enumerate}
\end{problem}

\begin{sol}
\mbox{}
\begin{enumerate}
\item
$\begin{aligned}[t]
\alpha+0&=\alpha\\
\alpha+\beta'&=(\alpha+\beta)'\\
\alpha+\gamma&=\sup\{\alpha+x\colon x<\gamma\}\text{ if $\gamma$ is a limit}
\end{aligned}$
\item
$0+0=0$.

If $0+\alpha=\alpha$, then $0+\alpha'=(0+\alpha)'=\alpha'$.

If $\beta$ is a limit, and $0+\alpha=\alpha$ whenever $\alpha<\beta$, then
\begin{equation*}
0+\beta=\sup_{\alpha<\beta}(0+\alpha) =\sup_{\alpha<\beta}\alpha=\beta.
\end{equation*}
\end{enumerate}
\end{sol}

\begin{problem}
Prove that
\begin{equation*}
\alpha\cdot(\beta+\gamma)=\alpha\cdot\beta+\alpha\cdot\gamma
\end{equation*}
for all ordinals.  Use only the \emph{recursive} definitions of $+$ and $\cdot$.  You may use the normality of the functions $x\mapsto\alpha+x$ and $x\mapsto\beta\cdot x$ where $\beta>0$, and you may use the theorem that makes normality useful (as the instructions above suggest).
\end{problem}

\begin{sol}
We use induction on $\gamma$.
\begin{enumerate}[i)]
\item
$\alpha\cdot(\beta+0)=\alpha\cdot\beta=\alpha\cdot\beta+0=\alpha\cdot\beta+\alpha\cdot0$.
\item
If $\alpha\cdot(\beta+\gamma)=\alpha\cdot\beta+\alpha\cdot\gamma$, then
\begin{align*}
\alpha\cdot(\beta+\gamma')
&=\alpha\cdot(\beta+\gamma)'\\
&=\alpha\cdot(\beta+\gamma)+\alpha\\
&=(\alpha\cdot\beta+\alpha\cdot\gamma)+\alpha\\
&=\alpha\cdot\beta+(\alpha\cdot\gamma+\alpha)\\
&=\alpha\cdot\beta+\alpha\cdot\gamma'.
\end{align*}
\item
If $\delta$ is a limit, and $\alpha\cdot(\beta+\gamma)=\alpha\cdot\beta+\alpha\cdot\gamma$ whenever $\gamma<\delta$, then
\begin{align*}
\alpha\cdot(\beta+\delta)
=\alpha\cdot\sup_{\gamma<\delta}(\beta+\gamma)
&=\sup_{\gamma<\delta}(\alpha\cdot(\beta+\gamma))\\
&=\sup_{\gamma<\delta}(\alpha\cdot\beta+\alpha\cdot\gamma)\\
&=\alpha\cdot\beta+\sup_{\gamma<\delta}(\alpha\cdot\gamma)=\alpha\cdot\beta+\alpha\cdot\delta
\end{align*}
\end{enumerate}
\end{sol}

\begin{rem}
The induction must be on $\gamma$; nothing else works.  With ordinals, all of the action that we know about from definitions happens on the \emph{right.}
\end{rem}

\clearpage

\begin{problem}
Assuming $\alpha>1$, prove that the function $x\mapsto\alpha^x$ on $\on$ is normal.
\end{problem}

\begin{sol}
By definition, if $\beta$ is a limit, then $\alpha^{\beta}=\sup\{\alpha^x\colon x<\beta\}$.  Therefore it remains to show
\begin{equation*}
\beta<\gamma\Rightarrow\alpha^{\beta}<\alpha^{\gamma}.
\end{equation*}
We prove this for all $\beta$, by induction on $\gamma$.
\begin{enumerate}[i)]
\item
The claim is vacuously true when $\gamma=0$ [since it is never true that $\beta<0$].  
\item
Suppose the claim is true when $\gamma=\delta$.  If $\beta<\delta'$, then $\beta\leq\delta$, so
\begin{equation*}
\alpha^{\beta}\leq\alpha^{\delta}<\alpha^{\delta}\cdot\alpha=\alpha^{\delta'}.
\end{equation*}
\item
Suppose $\delta$ is a limit, and the claim holds when $\gamma<\delta$.  If now $\beta<\delta$, then $\beta<\beta'<\delta$, so
\begin{equation*}
\alpha^{\beta}<\alpha^{\beta'}\leq\sup_{\gamma<\delta}\alpha^{\gamma}=\alpha^{\delta}.
\end{equation*}
\end{enumerate}
\end{sol}

Scores:
\begin{center}
\renewcommand{\arraystretch}{1.2}
\begin{tabular}[t]{|r|*9{c|}}\hline
 &EA&PC&AF&M\.I&MM&O\c S&NT&\"OT\\\hline
1&10&13& 8&   2& 7&   13&13&   9\\
2& 2& 5& 5&   2& 0&    5& 5&   4\\
3& 0& 5& 5&   0& 0&    0& 5&   0\\
4& 2& 0& 2&   0& 0&    4& 2&   2\\\hline
 &14&23&20&   4& 7&   22&25&  15\\\hline
 \end{tabular}
 \end{center}
\end{document}