\documentclass[%
version=last,%
a5paper,%
10pt,%
%twoside,%
headings=small,%
%DIV=18,%
DIV=12,%
pagesize]%
{scrartcl}

\usepackage{amsmath,amsthm,amssymb,hfoldsty,paralist,typearea}
\newtheorem{problem}{Problem}
\theoremstyle{definition}
\newtheorem*{solution}{Solution}
\theoremstyle{remark}
\newtheorem*{remark}{Remark}

\newcommand{\on}{\mathbf{ON}}
\newcommand{\Exists}[1]{\exists{#1}\;}
\newcommand{\Forall}[1]{\forall{#1}\;}
\newcommand{\liff}{\Leftrightarrow}
\newcommand{\included}{\subseteq}
\newcommand{\pincluded}{\subset}
\usepackage{upgreek}
\newcommand{\vnn}{\upomega}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\theenumi}{\alph{enumi}}
\renewcommand{\labelenumi}{\theenumi)}
\renewcommand{\theenumii}{\roman{enumii}}
\renewcommand{\labelenumii}{\theenumii)}
\begin{document}
\title{Exam 1 solutions}
\author{Math 320, David Pierce}
\date{April 7, 2011}
\maketitle
\mbox{}[Instructions given with exam:]
\begin{it}
\begin{compactitem}
\item
This examination assumes the axioms of Equality, Null Set, Adjunction,
Separation, Replacement, Union, and Infinity.
\item
Proofs are not required, unless they are explicitly asked for.
\item
In proofs, you may use any theorem
that we know, unless you are being asked to prove that theorem.  
\item
All problems have equal weight.
\end{compactitem}
\end{it}
\begin{problem}
Let $a$ and $b$ be sets.
\begin{asparaenum}
\item
 Write down a formula that defines the class denoted by $a\times b$.
 If you use any symbols other than $a$, $b$, $\in$, $=$, and logical
 symbols, you should define them. 
\item
Prove that $a\times b$ is a set.  
\end{asparaenum}
\end{problem}

\begin{solution}
\mbox{}
\begin{asparaenum}
\item
Such a formula is
\begin{equation*}
\Exists x\Exists y(z=(x,y)\land x\in a\land y\in b), 
\end{equation*}
where:
\begin{itemize}
\item 
$z=(x,y)$ stands for $z=\{\{x\},\{x,y\}\}$, 
\item
$z=\{u,v\}$ stands for $\Forall x(x\in z\liff x=u\lor x=v)$, 
\item
$x=\{u\}$ stands for $\Forall y(y\in x\liff y=u)$.
\end{itemize}
\item
By the Null Set and Adjunction axioms, ordered pairs are sets.
Therefore, for each $c$ in $a$,
there is a well-defined function
\begin{equation*}
y\mapsto(c,y)
\end{equation*}
on $b$.
The image of $b$ under this function is the class $\{c\}\times b$;
this class is a set, by the Replacement Axiom.
Therefore there is a well-defined function 
\begin{equation*}
x\mapsto\{x\}\times b
\end{equation*}
on
$a$.  The image of $a$ under this function is the class 
\begin{equation*}
\{\{x\}\times b\colon x\in a\}; 
\end{equation*}
this is a set, again by Replacement.
By the Union 
Axiom, the class
\begin{equation*}
  \bigcup\{\{x\}\times b\colon x\in a\}
\end{equation*}
is a set; but this class is just $a\times b$.
\end{asparaenum}
\end{solution}

\begin{remark}
  This problem was Exercise 18; it is also Theorem 74 of the notes.
  For example, if $a=3=\{0,1,2\}$, then 
  \begin{equation*}
    a\times b=(\{0\}\times b)\cup(\{1\}\times b)\cup(\{2\}\times b)
=\bigcup\{\{k\}\times b\colon k\in 3\}.
  \end{equation*}
\end{remark}

\begin{problem}
Write down:
\begin{asparaenum}
\item
A transitive set that is not an ordinal.
\item
A set that is well-ordered by membership, but is not an ordinal.
\end{asparaenum}
\end{problem}

\begin{solution}
\mbox{}
\begin{asparaenum}
\item
$\{0,\{0\},\{\{0\}\}\}$.
\item
$\{\{0\}\}$.
\end{asparaenum}
\end{solution}

\begin{remark}
There are many possible answers; those given are probably the simplest.
  One can approach this problem as follows:
  \begin{asparaenum}
  \item 
Start with a set $a$ that is not an ordinal, then find the smallest
set $b$ that contains $a$ and is transitive.
The simplest set that is not an ordinal is $\{1\}$, that is,
$\{\{0\}\}$; let this be $a$.  Then $a\in b$, so we must also have
$a\included b$, which means $1\in b$.  So $\{a,1\}\included b$.  But
since $1\in b$, we must have $1\included b$, that is, $0\in b$.  So
$\{a,1,0\}\included b$.  We are done: the set $\{a,1,0\}$, is now
transitive, but it is not an ordinal, since $a$ is not an ordinal.  
\item
Every set of ordinals is well-ordered by membership.  So take a set of
ordinals that is not an ordinal.  A set of \emph{one} ordinal is
enough, as long as that ordinal is not $0$.
  \end{asparaenum}
\end{remark}

\begin{problem}
Either prove or give a counterexample:
\begin{asparaenum}
\item
Every set of ordinals has a supremum.
\item
Every class of ordinals has a supremum.
\end{asparaenum}
\end{problem}

\begin{solution}
\mbox{}
\begin{asparaenum}
\item
Let $a$ be a set of ordinals.  Then its supremum is $\bigcup a$: we
prove this as follows. 

First, $\bigcup a$ is an ordinal.  For, each ordinal is a set of
ordinals, so $\bigcup a$ is a set of ordinals, and therefore it is
well-ordered by membership.  Moreover, if $\alpha\in\bigcup a$, then
$\alpha\in\beta$ for some $\beta$ in $a$, so $\alpha\pincluded\beta$,
but also $\beta\included\bigcup a$, so $\alpha\pincluded\bigcup a$.
Thus $\bigcup a$ is also transitive.  Therefore it is an ordinal. 

Now, if $\alpha\in a$, then $\alpha\included\bigcup a$.  Thus $\bigcup
a$ is an upper bound of $a$.  If $\beta$ is an upper bound, then for
all $\alpha$ in $a$, we have $\alpha\included\beta$; but this shows
$\bigcup a\subseteq\beta$.  Thus $\bigcup a$ is the least upper bound
of $a$. 
\item
The class $\on$ itself has no supremum, since it is closed under
$x\mapsto x'$, and $x\in x'$. 
\end{asparaenum}
\end{solution}

\begin{remark}
  The offered solution uses implicitly the theorem that, on $\on$, the
  relations $\in$ and $\pincluded$ are the same (and are the relation
  by which $\on$ is well-ordered).  Part (a) is really Theorem 69 of
  the notes.
\end{remark}

\begin{problem}
\mbox{}
\begin{asparaenum}
\item
Find a set of successor ordinals whose supremum is a limit ordinal. 
\item
Prove that there is no set of limit ordinals whose union is a successor
ordinal. 
\end{asparaenum}
\end{problem}

\begin{solution}
\mbox{}
\begin{asparaenum}
\item
$\vnn=\sup\{n+1\colon n\in\vnn\}$.
\item
Say $a$ is a set of limit ordinals, and let $\beta=\sup(a)$.  If
$\beta\in a$, it is a limit.  Say $\beta\notin a$.  Then for all
$\alpha$, if $\alpha<\beta$, then $\alpha<\gamma<\beta$ for some
$\gamma$ in $a$, and then $\alpha'\leq\gamma<\beta$.  Thus $\beta$ is
still a limit, or $0$. 
\end{asparaenum}
\end{solution}

\begin{problem}
Prove or disprove:
\begin{asparaenum}
\item
$k+n=n+k$ for all natural numbers $k$ and $n$.
\item
$\alpha+\beta=\beta+\alpha$ for all ordinals $\alpha$ and $\beta$.
\end{asparaenum}
\end{problem}

\begin{solution}
\mbox{}
\begin{asparaenum}
\item
The statement is true.  To prove it,
we shall use the definition of addition on $\vnn$:
\begin{align*}
  k+0&=k,&k+n'&=(k+n)'.
\end{align*}
We first show $0+k$ by induction: 
\begin{asparaenum}
\item 
$0+0=0$ by definition of $+$.
\item
If
$0+k=k$, then 
\begin{align*}
0+k'
&=(0+k)'&&\text{[by definition of $+$]}\\
&=k'&&\text{[by inductive hypothesis]}. 
\end{align*}
\end{asparaenum}
Next, we show $n'+k=(n+k)'$ by induction:  
\begin{asparaenum}
\item 
$n'+0=n'=(n+0)'$.
\item
If
$n'+k=(n+k)'$, then 
\begin{align*}
n'+k'
&=(n'+k)'&&\text{[by definition of $+$]}\\
&=(n+k)''&&\text{[by inductive hypothesis]}\\
&=(n+k')'&&\text{[by definition of $+$].} 
\end{align*}
\end{asparaenum}
Now we can prove the original claim by induction:  
\begin{asparaenum}
\item
$n+0=n=0+n$.
\item
If
$n+k=k+n$, then 
\begin{align*}
n+k'=(n+k)'&&\\
=(k+n)'&&\text{[by inductive hypothesis]}\\
=k'+n.&&
\end{align*}
\end{asparaenum}
\item
The statement is false:
\begin{align*}
1+\vnn
&=\sup\{1+n\colon n\in\vnn\}\\
&=\sup\{n+1\colon n\in\vnn]\}\\
&=\vnn\\
&\neq\vnn+1.
\end{align*}
\end{asparaenum}
\end{solution}

\begin{remark}
  In part (a), it was not strictly required to prove the preliminary
  lemmas, since it is permitted to assume Lemma 7 of the notes.  What
  is to be proved in part (a) is Theorem 31 of the notes; and doing 
  this was Exercise 8.
\end{remark}

\end{document}