\documentstyle[amstex]{article}
\input{macros-course}

\begin{document}

\pset{6}{March 11, 1997}{March 18, 1997}

This problem set has {\bf only 3} required problems, numbers 1--3.
{\bf All} others are {\bf optional.} If you do them, they will be
corrected (which will give you useful feedback for next time) but the
grade will not count. I suggest you use them to study for the quiz,
since they cover material that will be quizzed.



{\bf Reading:} Rosen, 1.5--1.6, 6.1--6.5.


\begin{problems}

\problem  

There is a ferry boat which leaves from Boston Harbor.
In order to board the boat, a person must go through several
steps:
\begin{itemize}
\item Go to the ticket counter
\item Purchase a ticket at the ticket counter
\item Go to the boat
\item Give the ticket to the conductor and get on
\end{itemize}
(Tickets purchased for a particular trip are not good for any other trips).
Give a state machine that models this scenario, in which each of the
above steps corresponds to one (separate) transition.

Suppose that initially there are only 60 tickets at the ticket counter.  Add
this fact to your state machine, and prove that there are never more
than 60 passengers on the boat.

\problem Consider an array/permutation $A[]$.  Show that it is
impossible to implement a two-element swap (eg, exchange elements 1
and 2 without changing any of the other elements' positions) via any
sequence of 3-element cyclic shifts (eg, $1 \rightarrow 2\rightarrow
3\rightarrow 1)$).  Hint: an inversion in a permutation is a pair of
elements $i$ and $j$ with $i<j$ but $A[i]>A[j]$.  Study the number of
inversions in the permutation as you perform swaps and shifts.


\problem 
Let $R_1$ and $R_2$ be two equivalence relations on a set $S$. Show that 
$R_1 \cap R_2$ is an equivalence relation on $S$.


\problemopt Let $A$, $B$, and $C$ be sets.  Prove that $A-(B \cap C)=
(A-B) \cup (A-C)$.

\problemopt
Prove that for any relations $Q,R$ and $S$
\[ Q\circ (R^c \circ S)^c \subseteq ((Q\circ R)^c\circ S)^c. \]

\problemopt  Let $X$ and $Y$ be sets, and $f: X \rightarrow Y$ be a
function.  Recall that for a set $X$, $f(X) = \{f(x) \mid x \in X\}$.
Prove or disprove the following.

\begin{problemparts}

\problempart For any subsets $A$ and $B$ of $X$, $f(A) \cup f(B) = f(A \cup B)$

\problempart For any subsets $A$ and $B$ of $Y$, $f^{-1}(A) \cap f^{-1}(B) = f^{-1}(A \cap B)$

\end{problemparts}

\problemopt Determine which of the relation following relations $R$ on
all people is reflexive, symmetric, antisymmetric, and/or transitive,
where $(a,b) \in R$ iff:
\begin{problemparts}
\problempart $a$ is taller than $b$
\problempart $a$ and $b$ were born on the same day of the week
\problempart $a$ and $b$ were born less than 24 hours apart
\problempart $a$ has a different first name from $b$
\problempart $a$ and $b$ have a common grandparent
\end{problemparts}

\problemopt 
Define a relation $R$ on $\naturals$ by, $(a,b) \in R$ if 
$\exists c \in \naturals$ such that $a^2 = b^2 + c^2$.

Decide whether $R$ is reflexive, symmetric, antisymmetric, or transitive.

\problemopt

Show that the transitive closure of the symmetric closure of the
reflexive closure of a relation $R$ is the smallest equivalence
relation that contains $R$.

\problemopt In the next problems, we are going to define the integers as
a equivalence classes of pairs of natural numbers.  For these
problems, use only natural numbers and the properties of addition.
Don't use negation or subtraction.  You may use the fact that addition
is associative, distributive, and commutative.  You will also
find it useful to use the following cancellation lemma: if $a+b=a+c$,
then $b=c$ (this can be proved by induction from the Peano-axiom
definition of plus, but you can take it as an axiom).

We define a relation $\equiv$ on $\naturals \times \naturals$ by $(a,
b) \equiv (c, d)$ iff $a + d = b + c$.  Prove that $\equiv$ is an
equivalence relation.  

\def\ints{{\Bbb Z}}

\problemopt Let $\ints$ be the set of equivalence classes of $\equiv$
(from the previous problem).  We define a relation $P$ from
$\ints\times\ints$ to $\ints$ by the following rule.  $(X,Y) \sim_P
Z$ iff $\exists a, b, c, d \in \naturals$ for which $(a, b) \in X$,
$(c, d) \in Y$, and $(a + c, b + d) \in Z$.  Note that $\sim_P$ is a
binary relation, but its first argument is an ordered pair.  

\begin{problemparts}
\problempart
Prove that $\sim_P$ is actually a function from $\ints \times \ints$
to $\ints$.

\problempart Since $P$ is a function, we will let $X+Y$ denote the
(unique) $Z$ for which $(X,Y)\sim_P Z$.  We now define subtraction via
a relation $M$ as follows.  $(X,Y) \sim_M Z$ if $X=Y+Z$.  Prove that
$M$ is a function.  Let $X-Y$ denote the $Z$ for which $M((X,Y),Z)$.

\end{problemparts}

\problemopt  We now prove some properties of our plus and minus
functions.  
\begin{problemparts}
\problempart  Prove that there is an element $\Theta$ in $\ints$ such that
$\forall X \in \ints \ \ \ X + W = W + X = X$. 
\problempart  Prove that for every element $X$ in $\ints$, there is an element $Y$ in
$\ints$ such that $X + Y = \Theta$. 
\problempart Prove that $X-X=\Theta$.
\problempart Give an injective function $f$ from $\naturals$ to
$\ints$ such that for any $x,y \in\naturals$, $f(x+y)=f(x)+f(y)$
(note that the right-hand side plus is operating on $\ints$).  This
function puts of ``copy'' of the natural numbers into the integers
we've defined.
\end{problemparts}


\end{problems}
\end{document}



% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
% LocalWords:  iff
