\documentclass[12pt]{article}
\usepackage{exam,amssymb}
%\documentstyle[12pt,exam96,ams]{article}
%\input{amssym}
\paper{MATHS 713}
\title{Logic and Set Theory}
\time{two}
\semester{first semester}
\year{1999}

\note{Answer \underline{THREE} questions.  All question carry equal
marks.  This note is not yet long enough, so I will make it longer.\\
I will also put in a paragraph break.}
\begin{document} 
\let\>=\rangle
\let\<=\langle
\let\pe=\preccurlyeq
\let\minus=\smallsetminus
\let\phi=\varphi
\let\w=\omega
\let\a=\alpha
\let\b=\beta
\def\Z{{\mathbb Z}}
\let\iff=\leftrightarrow
\let\Iff=\Leftrightarrow

Here is some text before the questions.
Here is some text before the questions.
Here is some text before the questions.
Here is some text before the questions.
Here is some text before the questions.
Here is some text before the questions.
Here is some text before the questions.
Here is some text before the questions.
Here is some text before the questions.

Here is some text before the questions.
Here is some text before the questions.
Here is some text before the questions.
Here is some text before the questions.
Here is some text before the questions.
Here is some text before the questions.
Here is some text before the questions.
Here is some text before the questions.
Here is some text before the questions.

\begin{questions}
\question Recall that the ordered pair $\<x,y\>$ is defined by
  \[
  \<x,y\>=\{\{x\},\{x,y\}\}.
  \]
  \begin{enumerate}
  \item Show that the axiom system ZFC, as described in the ATTACHMENT
    (page~\pageref{Axioms}), guarantees that if $x$ and $y$ are sets
    then $\<x,y\>$ is a set.
  \item Show that the axiom system ZFC guarantees that if $A$ and $B$
    are sets then $A\times B$ is a set.
  \item Show that we can express the statement ``$R$ is a well-order
    on $X$'' in LST.
  \item Let $X$ be a set.  Show that the axiom system ZFC guarantees
    that the collection of all ordinals $\a$ such that there is a 1--1
    function $f:\a\to X$ is a set.  [You may assume that if $\<Y,R\>$
    is a well-ordered set then there is a unique ordinal which is
    order-isomorphic to $\<Y,R\>$, and that we can express ``$\a$ is
    an ordinal which is order-isomorphic to $\<Y,R\>$'' in LST.]
  \end{enumerate}

\question
  \begin{enumerate}
  \item Recall that addition and multiplication on $\w$ are defined by
    \begin{eqnarray*}
      m+0&=&m\\
      m+n^+&=&(m+n)^+\\
      m\cdot0&=&0\\
      m\cdot n^+&=&m\cdot n+m
    \end{eqnarray*}
    Show from these definitions that addition and multiplication are
    associative and commutative, and that multiplication is
    distributive over addition.

  \item Addition of ordinal numbers is defined by
    \begin{eqnarray*}
      \a+0&=&\a\\
      \a+\b^+&=&(\a+\b)^+\\
      \a+\eta&=&\bigcup\{\,\a+\b\mid\beta\in\eta\,\}
      \qquad\mbox{when $\eta$ is a limit ordinal}
    \end{eqnarray*}
    Show that addition of ordinal numbers is \emph{not} commutative.
  \end{enumerate}


\question Assume that the natural numbers have been constructed with their
  familiar arithmetic and ordering properties.  Describe in detail how
  the integers can be constructed.  Explain how addition,
  multiplication and ordering of integers are defined, and show that
  they are well-defined.  Show that there exists a 1--1 function
  $\theta:\w\to\Z$ such that for all $m,n\in\w$,
  \begin{eqnarray*}
    \theta(m + n)&=&\theta(m) +_\Z \theta(n)\\
    \theta(m \cdot n) &= &\theta(m) \cdot_\Z \theta(n)\\
    m \le n&\Leftrightarrow& \theta(m) \le_\Z \theta(n)
  \end{eqnarray*}
  

  
\question Let $R$ be a relation on a set $A$.  Then $R$ is said to be {\em
    well-founded\/} if, for every non-empty $B\subseteq A$, there is
  some $R$-minimal element of $B$ (in other words, some $x\in B$ such
  that if $y\in B$ with $y\,R\,x$ then $y=x$).  The pair $\<A,R\,\>$
  is said to {\em support induction\/} if, for every formula $\phi(x)$
  of LST, if
  \[
  \forall x\in A\bigl(\forall y\in A((y\,R\,x\land y\ne
  x)\to\phi(y))\to\phi(x))
  \]
  then $\phi(x)$ holds for all $x\in A$.
  \begin{enumerate}
  \item Prove that $R$ is well-founded if and only if $\<A,R\,\>$
    supports induction.
  \item Assume that $R$ is well-founded.  For each $x\in A$, let
    \[
    \mbox{seg}(x)=\{\,y\in A\mid y\,R\,x\land y\ne x\,\}.
    \]
    Let $B$ be a set, and let
    \[
    Y=\bigcup\{\,{}^{{\rm seg}(x)}B\mid x\in A\,\}
    \]
    (in other words, $Y$ is the set of all functions whose domain is
    $\mbox{seg}(x)$ for some $x\in A$ and whose range is a subset of
    $B$).  Let $H:Y\to B$ be a function.  Prove that there is a unique
    function $F:A\to B$ such that for every $x\in A$,
    $F(x)=H(F\restriction \mbox{seg}(x))$.
  \end{enumerate}
  
\question Let $\<X,\le_X\>$ and $\<Y,\le_Y\>$ be well-ordered sets.  Then
  $\<Y,\le_Y\>$ is an {\em end-extension\/} of $\<X,\le_X\>$ if
  \begin{enumerate}
  \item[]\begin{enumerate}
    \item $X\subseteq Y$;
    \item for all $x,y\in X$, if $x\le_X y$ then $x\le_Y y$; and
    \item for all $x\in X$ and $y\in Y\minus X$, $x\le_Y y$.
    \end{enumerate}
  \end{enumerate}
  \begin{enumerate}
  \item Let $\<I,\pe\>$ be a totally ordered set, and for each $i\in
    I$, let $\<X_i,\le_i\>$ be a well ordered set.  Suppose that if
    $i,j\in I$ with $i\pe j$ then $\<X_j,\le_j\>$ is an end-extension
    of $\<X_i,\le_i\>$.  Put $X=\bigcup\{\,X_i\mid i\in I\,\}$ and
    define a relation $\le$ on $X$ by declaring that $x\le y$ if and
    only if $x\le_i y$ for some $i\in I$.  Show that $\le$ is a
    well-order on $X$, and that $\<X,\le\>$ is an end-extension of
    $\<X_i,\le_i\>$ for each $i\in I$.
  \item Assume Zorn's Lemma, but do not assume any other version of
    the Axiom of Choice.  Prove that every set can be well-ordered.
  \end{enumerate}

\end{questions}

\attachment
\label{Axioms}
\begin{center}
  \large\bf The Axiom System ZFC
\end{center}
\begin{list}{}{\setlength{\itemsep}{20pt}}
\item[\bf Extensionality:] For any sets $x$ and $y$, 
  \[
  x=y\qquad\Iff\qquad\forall z\,(z\in x\iff z\in y).
  \]

\item[\bf Pairing:] If $x$ and $y$ are sets then $\{x,y\}$ is a set.
  
\item[\bf Union:] If $x$ is a set then $\bigcup x=\{\,y\mid\exists
  z\,(y\in z\land z\in x)\,\}$ is a set.
  
\item[\bf Power Set:] If $x$ is a set then $\Bbb P x=\{\,y\mid
  y\subseteq x\,\}$ is a set.
  
\item[\bf Comprehension:] If $x$ is a set and $\phi(y)$ is a formula
  of LST then $\{\,y\in x\mid\phi(y)\,\}$ is a set.
  
\item[\bf Replacement:] If $x$ is a set and $\phi(z,y)$ is a formula
  of LST such that for each $z$ there is at most one $y$ satisfying
  $\phi(z,y)$, then $\{\,y\mid\exists z\in x(\phi(z,y))\,\}$ is a set.
  
\item[\bf Infinity:] There is a set $x$ such that $\varnothing\in x$
  and, for every $y\in x$, $y\cup\{y\}\in x$.
  
\item[\bf Foundation:] If $x$ is a non-empty set then there is some
  $y\in x$ with $y\cap x=\varnothing$.
  
\item[\bf Choice:] If $x$ is a set then there is a function $f:\Bbb
  Px\smallsetminus\{\varnothing\}\to x$ such that for all $y\in\Bbb
  Px\smallsetminus\{\varnothing\}$, $f(y)\in y$.

\end{list}

\end{document}

