\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 $\$ is defined by \[ \=\{\{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 $\$ 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 $\$ is a well-ordered set then there is a unique ordinal which is order-isomorphic to $\$, and that we can express ``$\a$ is an ordinal which is order-isomorphic to $\$'' 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 $\$ 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 $\$ 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 $\$ and $\$ be well-ordered sets. Then $\$ is an {\em end-extension\/} of $\$ 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 $\$ be a totally ordered set, and for each $i\in I$, let $\$ be a well ordered set. Suppose that if $i,j\in I$ with $i\pe j$ then $\$ is an end-extension of $\$. 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 $\$ is an end-extension of $\$ 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}