\documentstyle[12pt,fullpage,doublespace]{article}


\setstretch{1.00}
\newcommand\os[1] {$\mit{#1}$}
%\newcommand\os[1]{#1}
 
\pagestyle{empty}

\begin{document}

\begin{center}
\large 
%\vspace*{-1.5cm}
Harvey Mudd College\\
Computer Science \os{80}\\
Logic for Computer Science\\
Spring Semester \os{2001}\\[16pt]

Assignment \#1 -- Mathematical Preliminaries\\
\large
Due { \os{11}:\os{00}am}, Wednesday January \os{31}, \os{2001}
\end{center}

\vspace{0.25in}

\begin{enumerate}
\item
Using the directed graph representation used in class, provide examples
of relations on a set of four objects that are:

\begin{enumerate}
\item transitive, not reflexive, not symmetric
\item transitive, symmetric, not reflexive
\item symmetric, reflexive, not transitive
\item anti-transitive, anti-symmetric, anti-reflexive
\end{enumerate}

\item Define a {\em non-trivial chain} in a binary relation $R$ as a sequence 
$(a_1,\ldots,a_n)$ for some $n\geq 2$ such that the $a_i$ are distinct, and 
$(a_i,a_{i+1})\in R$ for $i\in [n-1]$. A chain is a {\em non-trivial cycle} 
if $(a_n,a_1)$ is also an element of $R$.

Prove that a relation is a partial order iff it is reflexive and transitive and has 
no non-trivial cycles.

\item Given two binary relations, $R$ between $A$ and $B$, and $S$ between $B$ and $C$,
their {\em composition}, denoted by $R\circ S$, is a relation between $A$ and $C$ 
defined by the set of ordered pairs $\{(a,c)| \mbox{there is a } b\in B \mbox{ such
that } (a,b)\in R \mbox{ and } (b,c)\in S\}$.

\begin{enumerate}
\item Let $R = \{(a,b),(a,c),(c,d),(a,a),(b,a)\}$. What is the value of $R\circ R$?
\item Prove that, given any relation $R$ on a set $A$, $R$ is transitive iff $R\circ R$
is a subset of $R$.
\end{enumerate}

\item Given a poset $(A,\leq)$, define the {\em lexicographic ordering}, $\ll$, on
$A\times A$, induced by $\leq$, as follows: 
\begin{quote}
For all $x,y,x',y'\in A$, $(x,y) \ll (x',y')$ iff either:
\begin{itemize}
\item $x = x'$ and $y = y'$, or
\item $x < x'$, or
\item $x = x'$ and $y < y'$
\end{itemize}
\end{quote}
Prove that if the poset $(A,\leq)$ is well-founded, then $(A\times A,\ll)$ is also
well-founded. (You may assume [though you might want to confirm for yourself] that if
$\leq$ is a partial order, then $\ll$ is indeed a partial order).

\pagebreak

\item Ackerman's function on ${\cal N} \times {\cal N}$ is defined recursively in ML as:
\begin{verbatim}
    fun A(x,y) = if x = 0
                   then y+1
                   else if y = 0
                          then A(x-1,1)
                          else A(x-1, A(x,y-1));
\end{verbatim}
Assuming that such a recursive definition actually defines a partial function (this is
non-trivial but is established in {\em recursive function theory}), prove by induction
over the lexicographic ordering of  ${\cal N} \times {\cal N}$ that Ackerman's function
is in fact a total function on pairs of natural numbers. That is, that for any
pair of inputs there is a defined output.
\end{enumerate}

\end{document}
