\documentclass[12pt]{article}
\input{macros-course}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
    \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother


%% Latex asks whether or not to include solutions
\askaboutsolutions
\begin{document}

%% Quiz 1
\ifshowsolutions
  \qsol{1}{September 28, 2001}{\stamp}
\else
  \quiz{1}{September 28, 2001}{\stamp}
\fi

\newcommand{\pts}[1]{\relax[#1 points]\enskip\ignorespaces}


\textbf{Your Name}:\ \mbox{}\hrulefill\mbox{}\par

\textbf{Circle the name of your Tutorial Instructor}:\\
\begin{center}
\begin{tabular}{l@{\hskip 3em}l@{\hskip 3em}l@{\hskip 3em}l}
Yu-Han & Christos & Nikos & Ashish \\
\ &&& \\
Thien-Loc & Jaime & Tina & Tong
\end{tabular}
\end{center}

%\noindent Write the hour at which your Thursday tutorial begins \brule{3em}.

\medskip

\begin{closeitemize}
\item This quiz is \textbf{closed book}.  There is an Appendix giving the
      definitions of some standard operations on relations.

\item There are four (4) problems totaling 100 points.  Problems are
      labeled with their point values.

\item Put your name on the top of {\bf every} page -- \emph{these
    pages may be separated for grading}.

\item Write your solutions in the space provided.  If you need more
  space, write on the back of the sheet containing the problem.
  Please keep your entire answer to a problem on that problem's page.

\item You may assume any of the results presented in class or in the
  lecture notes.

\item \remove{Show your work, as partial credit will be given.}
\textbf{Be neat and write legibly}.  You will be graded not only on the
correctness of your answer, but also on the clarity with which you express
it.

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\hrule
\smallskip
\centerline{\textbf{DO NOT WRITE BELOW THIS LINE}}
\smallskip
\hrule

\medskip

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
Problem & Points & Grade & Grader\\
& & & \\ \hline \hline
& & & \\
1 &  20 & & \\ & & & \\\hline & & &\\
2 &  30 & & \\ & & & \\\hline & & &\\
3 &  20 & & \\ & & & \\\hline & & &\\
4 &  30 & & \\ & & &\\
\hline
\hline
& & &\\
Total & 100 & & \\
& & &\\
\hline
\end{tabular}
\end{center}

\newpage

\begin{problems}

\problem\pts{20} For each of the following logical formulas with domain of
discourse the natural numbers, $\nats$, indicate whether it
is a possible formulation of
\begin{itemize}
\item[I:] the \textbf{I}nduction Axiom, 
\item[S:] the \textbf{S}trong Induction Axiom,
\item[L:] the \textbf{L}east Number Principle (also known as
  Well-ordering), or
\item[N:] \textbf{N}one of these.
\end{itemize}

For example, the ordinary Induction Axiom could be expressed by the
following formula, so it gets labelled ``I''.
\[
(P(0) \land [\forall k\; P(k) \implies P(k+1)]) \implies
\forall k\; P(k) \qquad\text{\underline{\quad  I \quad}}
\] 


\bparts

\ppart $P(0) \implies ([\forall k\; P(k) \implies P(k+1)] \implies
\forall k\; P(k))$ \hfill\brule{2em} \solnospace{\pts{2} I}

\ppart $(\exists n\; P(n)) \implies \exists n\; \forall k <
n\; \bar{P(k)}$ \hfill\brule{2em} \solnospace{\pts{4} N}

\ppart $(P(0) \land [\forall m\, (\forall k \le m\; P(k)) \implies P(m+1)])
\implies \forall n\; P(n)$ \hfill\brule{2em}  \solnospace{\pts{3} S}

\ppart $(P(b) \land [\forall k\ge b\; P(k) \implies P(k+1)])
\implies \forall k\ge b\; P(k)$ \hfill\brule{2em} \solnospace{\pts{4} I}

\ppart $(P(b) \land [\forall k \le b \; P(k) \implies P(k+1)])
\implies \forall k \le b\; P(k)$ \hfill\brule{2em} \solnospace{\pts{3} N}

\ppart $(\exists n\; P(n)) \implies (\exists n\; P(n) \land \forall k \le
n\; P(k) \implies k=n)$ \hfill\brule{2em} \solnospace{\pts{4} L}

\remove{\ppart $\forall n\; [P(n) \implies (\exists n\; P(n) \land \forall k <
n\; \bar{P(k)})]$ \hfill\brule{2em} \solnospace{L}}

\remove{\ppart $[\forall b\; P(b) \land \forall k\le b\; P(k) \implies P(k+1)]
\implies \forall k\; P(k)$ \hfill\brule{2em} \solnospace{N}}

\remove{\ppart $\forall b\; (\forall k < b\; P(k)) \implies P(b)]
\implies \forall k; P(k)$ \hfill\brule{2em}  \solnospace{S}}

\remove{\ppart $\forall n\; \bar{P(n)} \lor (\exists n\; P(n) \land
\forall k < n\; \bar{P(k)})$ \hfill\brule{2em} \solnospace{L}}

\eparts

\newpage
\problem\pts{30} The 6.042 mascot, Theory Pig, made a startling discovery while
playing with his prized collection of unit squares over the weekend.
Here is what happened.

First, Theory Pig put his favorite unit square down on the floor as in
Figure~\ref{fig:squares}~(a).  He noted that the length of the periphery
of the resulting shape was 4, an even number.  Next, he put a second unit
square down next to the first so that the two squares shared an edge as in
Figure~\ref{fig:squares}~(b).  He noticed that the length of the periphery
of the resulting shape was now 6, which is also an even number.  (The
periphery of each shape in the figure is indicated by a thicker line.)
Theory Pig continued to place squares so that each new square shared an
edge with at least one previously-placed square and no squares overlapped.
Eventually, he arrived at the shape in Figure~\ref{fig:squares}~(c).  He
realized that the length of the periphery of this shape was 36, which is
again an even number.

Our plucky porcine pal is perplexed by this peculiar pattern.  Use
induction on the number of squares to prove that the length of the
periphery is always even, no matter how many squares Theory Pig places or
how he arranges them.

\begin{figure}[htbp]
\centering
\includegraphics[width=4in]{figures/f98ps2}
\caption{Some shapes that Theory Pig created.} \label{fig:squares}
\end{figure}

%\emph{(TO HARD TO GRADE?)}

\solnospace{\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that the
periphery length is even after $n$ squares are placed.  In the base
case, $P(1)$ is true because the periphery of a single square has
length 4, which is even.

In the inductive step, assume that the periphery length is even after
$n$ squares are placed to prove that the periphery length is even
after $n+1$ squares are placed.  The $(n+1)$-st square could share 1,
2, 3, or 4 edges with previously-placed squares.

\begin{itemize}

\item If the new square shares 1 edge with a previously placed square,
then this one edge is removed from the periphery, but three edges of
the new square are added to the periphery.  Overall, the periphery
length increases by two and thus remains even.

\item If the new square shares 2 edges with previously placed squares,
then these two edges are removed from the periphery, but two edges of
the new square are added.  The periphery length is unchanged and thus
remains even.

\item If the new square shares 3 edges, then these three edges are removed
from the periphery, but one edge is added.  The periphery length
decreases by two and remains even.

\item If the new square shares 4 edges, then these four edges are removed
from the periphery and none are added.  The periphery length decreases
by four and remains even.

\end{itemize}

In all cases, the length of the periphery remains even.  Therefore,
for all $n \geq 1$, $P(n)$ implies $P(n+1)$ and the claim is proved by
induction.
\end{proof}
}

\newpage
\problem\pts{20} In this problem, let $R$ be a binary relation on a set,
$A$, and $S$ be a binary relation from $A$ to a set, $B$.  Indicate
whether each of the following statements is \textbf{True} or
\textbf{False}.  For the false ones, \textbf{\emph{describe a
counterexample}}.

\bparts

\ppart If $R= R^*$, then $R$ is an equivalence relation.
\solnospace{False. Counterexample: $A \eqdef \nats, R \eqdef \le$}

\vspace{0.7in}

\ppart If $R$ is symmetric, then so is $(R^{-1})^*$. \solnospace{True}

\vspace{0.7in}

\ppart If $R$ is the graph of a bijection $f:A \to A$, then $R^{-1}$ is
the graph of $f^{-1}$. \solnospace{True}

\vspace{0.7in}

\ppart If $A = B$, then $S \compose R = R \compose
S$. \solnospace{False.  Counterexample: $A = B \eqdef \set{1,2,3}, R \eqdef
\set{(1,2)}, S \eqdef \set{(2,3)},$ so $S \compose R = \set{(1,3)}, R
\compose S = \emptyset$}

\vspace{0.7in}

\ppart If $R = R^{-1}$ and $R$ is nonempty, then $R$ is
reflexive. \solnospace{False.  Counterexample: $xRy \eqdef\ x\neq y$ as
long as $\card{A} \ge 2$.}

\eparts

\newpage

\problem\pts{30} Ackermann's function, $A: \nats \cross \nats \to \nats$, satisfies
the following equations (simplified from Tutorial 2):
\begin{align}
A(m,n) &=  2n, &&\text{if $m=0$ or $n \le 1$},\label{Am0}\\ 
A(m,n) &=  A(m-1,A(m,n-1)), &&\text{if $m > 0$ and $n > 1$}.\label{AA}
\end{align}

These equations uniquely determine Ackermann's function.  That is,
\begin{lemma*}
If $B: \nats \cross \nats \to \nats$ also satisfies
the same equations as $A$, namely,
\begin{align}
B(m,n) &=  2n, &&\text{if $m=0$ or $n \le 1$},\label{Bm0}\\ 
B(m,n) &=  B(m-1,B(m,n-1)), &&\text{if $m > 0$ and $n > 1$},\label{BB}
\end{align}
then $A = B$.
\end{lemma*}

In this question, we ask you to fill in or justify various parts of a
proof of this Lemma.   The possible justifications are listed below.
You must choose your answers from this list.

\begin{itemize}
\item one or more of the equations (\emph{indicate exactly which ones}) numbered
(\ref{Am0}), (\ref{AA}), \dots (\ref{AB})
\item $P(0)$
\item $P(m)$
\item $P(m+1)$
\item $Q_m(0)$
\item $Q_m(n)$
\item $Q_0(n)$
\item $Q_m(n+1)$
\end{itemize}

\begin{proof}
We must prove that
\begin{equation}
\forall m \forall n\; A(m,n) = B(m,n). \label{a=b}
\end{equation}

The proof is by induction on $m$.  More precisely, the main induction
hypothesis, $P(m)$, is
\[
P(m) \eqdef\ \forall n\; A(m,n) = B(m,n).
\]

\textbf{Base case}: $m=0$.  It follows directly from equation(s)
\brule{4em} \solnospace{\pts{1} (\ref{Am0}), ~(\ref{Bm0})}

that $A(m,n) = B(m,n)$ for all $n$, confirming that \brule{4em}
\solnospace{\pts{2} $P(0)$}\\
is true.

\newpage

\textbf{Induction step}: Suppose $P(m)$ holds for some fixed $m \geq
0$.  We must prove that $P(m+1)$ also holds.

Namely, assuming $\forall n\; A(m,n)=B(m,n)$, we must prove
(\textbf{fill-in}):
\begin{equation}
\forall n\; \brule{2in} \text{\solnospace{\pts{3} $A(m+1,n)=B(m+1,n)$}} \label{m+1}
\end{equation}

We prove~(\ref{m+1}) by another induction, this time on $n$,
using the induction hypothesis,
\[
Q_m(n) \eqdef\ A(m+1, n) = B(m+1,n).
\]

%%\begin{quotation}
\addtolength{\leftskip}{0.5in}%

\textbf{Base case}: $n=0$.  $Q_m(0)$ follows immediately from equation(s)
\brule{4em}.  \solnospace{\pts{2} (\ref{Am0}), ~(\ref{Bm0})}

\textbf{Induction step}: Suppose $Q_m(n)$ holds for some $n \geq 0$.  We
must prove that $Q_m(n+1)$ also holds.

Let $k \eqdef A(m+1, n)$, so
\begin{equation}
A(m+1, n+1) = A(m,k)\label{Ak}
\end{equation}
by \brule{1in} \solnospace{\pts{3} (\ref{AA})}.

Then also
\begin{equation}
k = B(m+1, n),\label{kB}
\end{equation}
because \brule{1in} \solnospace{\pts{4} $Q_m(n)$}\\
holds, and so
\begin{equation}
B(m+1, n+1) = B(m,k)\label{Bk}
\end{equation}
by \brule{1in} \solnospace{\pts{2} (\ref{BB})}.

But
\begin{equation}
A(m,k) = B(m,k),\label{AB}
\end{equation}
since \brule{1in}\solnospace{\pts{5} $P(m)$}\\
holds.  Now combining equations \brule{5em}
\solnospace{\pts{5} (\ref{Ak}), (\ref{Bk}), and~(\ref{AB})},\\
we obtain
\[
A(m+1, n+1) = B(m+1,n+1).
\]
That is, $Q_m(n+1)$ holds.

This completes the proof by induction on $n$ that~(\ref{m+1}) holds.
%%\end{quotation}
\addtolength{\leftskip}{-0.5in}%

So we have also completed the proof by induction on $m$ that $\forall m\;
\brule{3em}$. \solnospace{\pts{3} $P(m)$}\\

That is, we have proved~(\ref{a=b}), as required.

\end{proof}

\end{problems}

\newpage

\section*{Appendix}
\subsection*{Relation operators}

\begin{eqnarray*}
S \compose R & \eqdef& \set{(a,b) \suchthat \exists c\; (a, c) \in R \land
(c, b) \in S}\\
R^{-1} & \eqdef  & \set{(b, a) \suchthat (a, b) \in R}\\
R^1 & \eqdef & R\\
R^{n+1} & \eqdef & R \compose R^n\\
R^* & \eqdef & \lgunion_{n=1}^{\infty} R^n
\end{eqnarray*}

\end{document}                            
