\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