\documentclass[11pt, twoside]{article}
\input{macros-course}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\renewcommand{\implies}{\longrightarrow}
\newcommand{\ignore}[1]{}
\showsolutionstrue
\begin{document}
\solset{3}{March 1, 2001}

%6782685711022254907  
\textbf{Be sure to indicate your TA's name clearly on the solutions
you turn in}.

\paragraph{Reading}
Velleman, \textit{How to Prove It}, Sections 4.1--4.3;
Rosen, \textit{Discrete Mathematics and Its Applications}, Sections
6.1--6.4.


\vspace{-.25in}

\paragraph{Policy on collaboration}
If you collaborated with someone on the problem sets, you should
mention their names on top of the problem set. If you did not
collaborate with anyone, you should explicitly say so. As a reminder,
the write-up of your solutions should be entirely your own.

\paragraph{Self-study}
Rosen, \emph{Discrete Mathematics and Its Applications}, Section 1.6.

The following exercises are \emph{optional;} do them if you think you
need the practice. The mini-quiz in tutorial on Friday will draw
(only) from these problems.
\begin{enumerate}
\item Exercises from Rosen (answers in the back of the book): Section
  1.6, exercises 1, 7, 10, 11, 13, 15, 17.
\end{enumerate}



\medskip
\begin{problems} 



% This problem is from Tina's Section:
%problem set 2, problem 7

\problem \label{ax+by:induct}
Suppose $a,b \in \naturals$ and $a>0$.  Prove by induction on $a$ that for
all $b\leq a$, there are $x,y \in \integers$ such that $ax+by= \gcd
(a,b)$.

\medskip
\solution{%
\textbf{Solution:}
\medskip
The proof is actually by strong induction.

{\bf Inductive Hypothesis:} 
\[P(a)::= \forall b\le a \exists x,y\in Z(\gcd(a,b)=a x +b y).
\]

\begin{proof}

{\bf Base Case:} $a=1$.  So $b=0$ or $b=1$.  In either case,
$\gcd(a,b)=a$, so letting $x=1$, $y=0$, proves $P(a)$.

{\bf Inductive Step:} We want to prove $P(a+1)$ assuming $P(n)$ holds for
all $n \leq a$.

If $b=0$ or $b=a+1$, then $P(a+1)$ holds as in the base case, so we may
assume $0<b\leq a$.  Since $b>0$, we can find the quotient, $q$, and
remainder, $r$, of $a+1$ divided by $b$, namely, $a+1 =qb + r$ for some
$q,r \in \integers, 0 \leq r < b \leq a$.

Now we know from the discussion in the text of Euclid's GCD algorithm that
$\gcd(b,r)=\gcd(a+1,b)$.  By induction hypothesis, $P(b)$, there are
integers $x',y'$ such that $gcd(b,r)=b x' + r y'$.  Therefore
\begin{eqnarray*}
\gcd(a+1,b) & = & \gcd(b,r)\\
     & = & b x' + r y'\\
& = & b x' + ((a+1)-q b) y'\\
& = & (a+1) y' + b (x' - q y').
\end{eqnarray*}
So letting $x=y'$ and $y = (x' - q y')$ proves $P(a+1)$.
\end{proof}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\problem 
% from spring00
% topic: Cartesian products, disjoint, direct proof
% source: Velleman 4.1.8

Prove that for any sets $A$, $B$, $C$, and $D$, if 
$A \times B$ and $C \times D$ 
are disjoint, then either $A$ and $C$ are disjoint or $B$ and $D$ are disjoint.

\solution{
We will prove the contrapositive.  In other words,
\newline 
prove: 
$[(A \intersect C) \neq \emptyset \land (B \intersect D) \neq \emptyset] 
\implies [(A \times B) \intersect (C \times D) \neq \emptyset]$
\newline
assume:
$[(A \intersect C) \neq \emptyset \land (B \intersect D) \neq \emptyset]$
\newline
$\therefore \exists a (a \in A \land a \in C) \land 
\exists b (b \in B \land b \in D)$.
\newline
then, $(a, b) \in A \times B$   by definition of Cartesian product, 
Velleman 158.
\newline
and, $(a, b) \in C \times D$   by definition of Cartesian product, 
Velleman 158.
\newline
$\therefore (a, b) \in [(A \times B) \intersect (C \times D)]$ so 
$[(A \times B) \intersect (C \times D) \neq \emptyset]$
\newline
$QED$
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
% Although I like this problem, I think that it is too hard. Maybe it
% is feasible if we remove the last part. /Lars
%
\newcommand{\F}{\mathcal{F}}
\newcommand{\G}{\mathcal{G}}
\renewcommand{\H}{\mathcal{H}}
\newcommand{\power}{\mathcal{P}}
\newcommand{\I}{\mathcal{I}}
\problem Suppose that $\Omega$~is a finite set. A collection $\F \subseteq
\power(\Omega)$ is called an \emph{algebra} if
\begin{enumerate}
\item $\Omega \in \F$,\label{algebra:non-empty}
\item $\omega \in \F \implies \overline{\omega} \in \F$,\label{algebra:complement}
\item $\omega_1 \in \F \land \omega_2 \in \F \implies \omega_1 \union
  \omega_2 \in \F$.\label{algebra:union}
\end{enumerate}
(The complement in item~\ref{algebra:complement} above is with respect
the universe~$\Omega$.)


For instance, if $\Omega = \{1,2,3\}$, the collection
$\{\{1,3\},\{2\}\}$ is \emph{not} an algebra, but the collection
$\{\emptyset,\{1,3\},\{2\},\{1,2,3\}\}$ is.

\solution{%
\begin{quote}\small
  A special type of algebras---so called $\sigma$-algebras---is the
  foundation of axiomatic probability theory. They are defined by
  basically the same axioms as above, but $\Omega$~does not have to be
  a finite set and the algebra has to be closed under the union of a
  countably infinite number of sets instead of the union of just two
  sets. The elements of~$\F$ are the possible \emph{events}, i.e., the
  information we can get about the outcome of the random experiment.
  Then a positive number $P(\omega)$ is assigned to every element
  of~$\F$ in such a way that $P(\Omega) = 1$ and $P(\omega_1 \union
  \omega_2) = P(\omega_1) + P(\omega_2)$ for disjoint
  $\omega_1,\omega_2 \in \F$. This number is the \emph{probability} of
  the events in~$\F$. The triple $(\Omega, P, \F)$ is usually called a
  \emph{probability space}. For the example above, with $\Omega =
  \{1,2,3\}$ and the algebra $\F =
  \{\emptyset,\{1,3\},\{2\},\{1,2,3\}\}$, we could for instance set
  $P(\{1,3\}) = 2/3$ and $P(\{2\}) = 1/3$. That would model the
  situation ``choose a number in $\{1,2,3\}$ uniformly'' where the
  only information we can observe about the outcome is if the number
  is odd or not.
\end{quote}
}

\begin{problemparts}
  \problempart Prove that if $\F$~is an algebra, $\omega_1 \in \F
  \land \omega_2 \in \F \implies \omega_1 \intersect \omega_2 \in \F$.

  \solution{%
    \begin{proof}
      By property~\ref{algebra:complement}, $\overline{\omega_1} \in
      \F$ and $\overline{\omega_2} \in \F$.  By the
      property~\ref{algebra:union}, this implies that
      $\overline{\omega_1} \union \overline{\omega_2} \in \F$. By
      property~\ref{algebra:complement}, this inplies that
      $\overline{\overline{\omega_1} \union \overline{\omega_2}} \in
      \F$. By DeMorgan, this implies that $\omega_1 \intersect
      \omega_2 \in F$.
    \end{proof}
    }

  \problempart Prove that if $\F_1 \subseteq \power(\Omega)$ and $\F_2
  \subseteq \power(\Omega)$ are algebras, then $\F_1 \intersect \F_2$ is
  also an algebra.

  \solution{%
    \begin{proof}
      Let $\F_1$ and~$\F_2$ be algebras. We now show that $\F_1
      \intersect \F_2$ satisfies the definition of an algebra.
      
      Since $\F_1$ is an algebra $\Omega \in \F_1$; since $\F_2$ is an
      algebra $\Omega \in \F_2$. Thus $\Omega \in \F_1 \intersect
      \F_2$ by the definition of intersection.
      
      Suppose that $\omega \in \F_1 \intersect \F_2$. Then $\omega \in
      \F_1 \land \omega \in \F_2$. If $\omega \in F_1$, then
      $\overline{\omega} \in \F_1$ since $\F_1$~is an algebra. If
      $\omega \in F_2$, then $\overline{\omega} \in \F_2$ since
      $\F_2$~is an algebra. Thus $\overline{\omega} \in \F_1
      \intersect \F_2$.
      
      Suppose that $\omega_1 \in \F_1 \intersect \F_2$ and that
      $\omega_2 \in \F_1 \intersect \F_2$. This implies that both
      $\omega_1$ and~$\omega_2$ are in~$\F_1$; and that both
      $\omega_1$ and~$\omega_2$ are in~$\F_2$.  Since both $\omega_1$
      and~$\omega_2$ are in~$\F_1$ and $\F_1$ is an algebra, $\omega_1
      \union \omega_2$ is also in~$\F_1$.  Since both $\omega_1$
      and~$\omega_2$ are in~$\F_2$ and $\F_2$ is an algebra, $\omega_1
      \union \omega_2$ is also in~$\F_2$. Thus $\omega_1 \union
      \omega_2$ is both in $\F_1$ and in~$\F_2$, which is the same
      thing as saying that $\omega_1 \union \omega_2 \in \F_1
      \intersect \F_2$.
    \end{proof}
    }
  
  \problempart Prove that if $\F_i \subseteq \power(\Omega)$ are algebras
  for $i = 1,\ldots,n$, then $\bigcap_{i=1}^n \F_i$ is also an
  algebra.
  
  \solution{%
    \begin{proof}
      We prove the claim by induction on~$n$. The base case ($n=1$) is
      clear. We now assume that $\bigcap_{i=1}^n \F_i$ is an
      algebra and rewrite
      \begin{displaymath}
        \bigcap_{i=1}^{n+1} \F_i = 
        \biggl(\bigcap_{i=1}^n \F_i\biggr) \intersect \F_{n+1}
      \end{displaymath}
      Thus, $\bigcap_{i=1}^{n+1} \F_i$ is---by the assumption---the
      intersection of two algebras. Since we proved above that the
      intersection of two algebras is also an algebra, we have thus
      proven that $\bigcap_{i=1}^{n+1} \F_i$ is an algebra.
    \end{proof}
    }
  
% \ignore'd by Lars 2/20
\ignore{
  \problempart Consider a collection $\G \subseteq \power(\Omega)$ that
  might not be an algebra. Consider the set
  \begin{displaymath}
    \I = \{\F_i \suchthat
    \mbox{$\G \subseteq \F_i$ and $\F_i$ is an algebra}\bigr\}
  \end{displaymath}
  of all algebras containing~$\G$. Note, that since $\power(\Omega)$ is
  itself an algebra, $\power(\Omega) \in \I$, and thus $\I$~is non-empty.
  By the result you proved above, $\F = \bigcap \I$ is an algebra.
  Moreover, $\G \subseteq \F$ since $\G \subseteq \F_i$ for all $\F_i
  \in \I$. Prove that $\F$~is the smallest algebra containing~$\G$. In
  other words, prove that there cannot exist any $\H \subseteq
  \power(\Omega)$ such that $\H$~is an algebra and $\G \subseteq \H \subset
  \F$.

  \solution{%
    \begin{proof}
      Suppose that there exists an $\H \subseteq \power(\Omega)$ such that
      $\H$~is an algebra and $\G \subseteq \H \subset \F$. Since $\H$
      is an algebra that contains~$\G$, $\H \in \I$. Thus, by the
      definition of~$\F$, $\F \subseteq \H$, which is a contradicion.
    \end{proof}
    }
  
  \problempart Consider an algebra $\F \subseteq \Omega$. The members
  of~$\F$ form a partial order with respect to the subset operation,
  i.e., $(\F,\subseteq)$ is a partial order. Since $\Omega \in \F$ by
  the definition of an algebra, we also have $\F \ni \bar{\Omega} =
  \emptyset$, which implies that the partial order $(\F,\subseteq)$
  has one unique minimal element, $\emptyset$. Now consider the set
  \begin{displaymath}
    \G = \bigl\{\omega \in \F \bigm| (\forall \omega' \in \F)
    (\omega' \subset \omega \implies \omega' = \emptyset\bigr\},
  \end{displaymath}
  i.e., the family of sets in~$\F$ that are immediately
  above~$\emptyset$ in the partial order. Prove that the elements
  of~$\G$ form a partition of~$\Omega$.

  \solution{%
    \begin{proof}
      We first prove that there are no two sets in~$\G$ that
      intersect. Suppose that there are two such sets~$G_1$ and~$G_2$
      such that $G_1 \neq G_2$ and $G_1 \intersect G_2 \neq
      \emptyset$. Since $\F$~is an algebra, $G_1 \intersect G_2 \in
      \F$. Moreover, either $G_1 \intersect G_2 \subset G_1$ or $G_1
      \intersect G_2 \subset G_2$ since $G_1 \neq \G_2$. This
      contradicts the fact that both $G_1$ and~$G_2$ are members
      of~$\G$.
      
      Fix some $a \in \Omega$. We now show that $a$~occurs in exactly
      one member of~$\G$. Assume the contrary, i.e., that $a$~does not
      occur in any member of~$\G$---we now by the above reasoning that
      no sets in~$\G$ intersect, so this is the only remaining
      possibility. Since $\Omega \in \F$, there exists at least one
      set in~$\F$ containing~$a$. Let $\omega$~be the smallest such
      set---by well-ordering, such an~$\omega$ always exists. By our
      assumption, $\omega \notin \G$. Consider the case $|\omega| =
      1$. Then the only proper subset of~$\omega$ is~$\emptyset$,
      which implies that $\omega \in \G$---a contradiction.
      
      Now assume that $|\omega| > 1$. Since $\omega \notin \G$, there
      must exist some~$\omega' \in \F$ satisfying $\emptyset \subset
      \omega' \subset \omega$. Moreover, since $\omega$~is the
      smallest set in~$\F$ that contains~$a$, $a \notin \omega'$. But
      since $\omega,\omega' \in \F$, the set $\omega - \omega'$, which
      contains~$a$, is also in~$\F$ and has a size smaller
      than~$|\omega|$. This is a contradiction.
    \end{proof}
    }
}
\end{problemparts}  



%%%%%%%%%%%%%%%% Fall00 Problem Set 3%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

The set $SSS$ of ``super-symmetric strings'' is defined as follows:
\begin{enumerate}
\item
The length one strings consisting of individual letters of the
alphabet, $a$, $b$, $c$, $d$, $\ldots$, $z$, are in $SSS$. 
\item
If $\alpha$ and $\alpha'$ are two strings in $SSS$ then the string
$\alpha \alpha' \alpha$ is in $SSS$.
\item
$SSS$ contains nothing else.
\end{enumerate}
\bparts
\ppart
Which of the following are super-symmetric strings?\\
i.  a\\     
ii.  aaaba\\   
iii.  abcbacabcba\\
iv. $\lambda$, the empty string\\
v. abaabcbaaba\\

\solution{
\medskip
\textbf{Solutions:}\\
i. Yes.  This is stated in part 1 of the definition.\\
ii. No.  This string is not of the form $\alpha \alpha' \alpha$.\\
iii. Yes.  Formally, consider $\alpha'=aca$, $\alpha=bcb$.  Then we have
a string of the form $a \alpha \alpha' \alpha a$, which is in $SSS$
by parts 1 and 2 of the definition.\\
iv.  No.  By part 3 of the definition\\
v. Yes. Similar reasoning to part iii shows that the string $bcb$ is in the 
middle of the super-symmetric\\ 
string, with the string $a$ wrapped around it, and with the string
$aba$ wrapped around that.

}

\ppart
Prove by structural induction that in any super-symmetric string $\alpha$, 
exactly one letter appears an odd number of times.\\

%%%
%Fix this either to be more complete, or to use Structural Induction.
%Find out what structural induction is, too.
%%%

\solution{
\medskip
\textbf{Solution:}\\
\textbf{Proof:} Define $P(e)$: String $e$ has exactly one letter which appears an odd number of times.
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall e \in SSS \ P(e)$.\\
1. (Base) $P(a)$\>\>\>\>The string $a$ has exactly one letter which appears an odd number of times.\\
2. (Base) $P(b)$\>\>\>\>Same for the string $b$\\
$\vdots$\\
26. (Base) $P(z)$\>\>\>\> Still has exactly one letter which appears once.\\
27. (Inductive Step) $\forall e, e' \in SSS \ P(e)\wedge P(e') \longrightarrow P(ee'e)$ \\
\>1. Fix $e,e' \in SSS$.\\
\>2. Assume $P(e) \wedge P(e')$.  That is, each of $e$ and $e'$ has exactly one letter which\\
\>\>appears and odd number of times.\\
\>3. By the inductive hypothesis, both $e$ and $e'$ have exactly one letter which appears an odd\\
\>\> number of times.  When we form the string $ee'e$, the letters in $e$ all get repeated, \\
\>\> and thus they all appear an even number of times.  By the IH, there is one letter in $e'$\\
\>\> which appears an odd number of times in $e'$.  Now, even if this letter is also present in\\
\>\>$e$, it will still appear an odd number of times in $ee'e$ (since
the sum of an odd number \\
\>\>and an even number is odd).  Therefore, we
have shown $P(ee'e)$.\\ 
\>4. QED.\\
\end{tabbing}
}

\eparts        





% Fall 98 Pset 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Let $R$ be a binary relation on the set $\{ a, b, c, d, e \}$
defined as follows:

\begin{eqnarray*}
R & =  \{ & (a, a), (a, b), (a, d), (b, a), (b, b), (b, c), (b, d), \\
  & \mbox{} & (c, b), (c, c), (c, d), (d, b), (d, c), (d, d), (e, e) \quad \}
\end{eqnarray*}

Answer yes or no to each of the following questions; if you answer no,
then defend your answer.

\begin{problemparts}
\problempart Is $R$ reflexive?

\solution{
Yes.
}

\problempart Is $R$ symmetric?

\solution{
No. $R$ contains $(a, d)$, but
not $(d, a)$.
}

\problempart Is $R$ transitive?

\solution{
No. $R$ contains $(d, b)$ and $(b, a)$, but not $(d, a)$.  }

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

% Source: Velleman Sec 4.2, Exercise 3 parts a,b and c.\\
\problem Suppose $A=\{1,2,3\}, B=\{4,5,6\}, R=\{(1,4), (1,5), (2,5),
(3,6)\}$, and $S=\{(4,5), (4,6), (5,4), (6,6)\}.$ Note that $R$ is a
relation from $A$ to $B$ and
$S$ is a relation from $B$ to $B$.  Find the following relations:\\
\medskip
a. $S\circ R$\\
b. $S\circ S$\\
c. $S^{-1}\circ R$

\solution{
Suppose $A=\{1,2,3\}, B=\{4,5,6\}, R=\{(1,4), (1,5), (2,5), (3,6)\}$, and 
$S=\{(4,5), (4,6), (5,4), (6,6)\}.$  Note that $R$ is a relation from $A$ to $B$ and
$S$ is a relation from $B$ to $B$.  Find the following relations:\\

\medskip
\textbf{Solutions:}\\
a. $S\circ R = \{(1,5), (1,6), (1,4), (2,4), (3,6)\}$\\
b. $S\circ S = \{(4,4), (4,6), (5,5), (5,6), (6,6)\}$\\
c. $S^{-1}\circ R = \{(1,5), (1,4), (2,4), (3,4), (3,6)\}$\\
%%%
%d.
%%% 
}



\problem Read the recursive definition of strings over an alphabet
$\Sigma$ in Rosen 3.3, example 10.  Define the {\em reversal} of a
  string $w$, written $w^R$, as follows:
\begin{itemize}
\item $\lambda^R = \lambda$
\item if $w=vx$ where $v \in \Sigma^*$ and $x \in \Sigma$, then $w^R \
=  xv^R$
\end{itemize}
Prove that for any $s,t \in \Sigma^*$, $(st)^R = t^Rs^R$

\solution{
We use structural induction. Specifically, the induction is on $t$ in
the assertion.
For the base case, we must show $\forall s\in\Sigma^*$,
$(s\lambda )^R=\lambda^Rs^R$---but this is clear since the left side
is $s^R$ and the right side is $s^R$ (because $\lambda$ is the empty
string).

Now we must show that if for an arbitrary $t\in\Sigma^*$, we have that $\forall s\in\Sigma^*$,
$(st)^R=t^Rs^R$, then $\forall s\in\Sigma^*,x\in\Sigma$,
$(s(tx))^R=(tx)^Rs^R$. We have $(s(tx))^R=(st(x))^R=x(st)^R$, the last
equality by the second property of reversal. But $x(st)^R=xt^Rs^R$ by
the structural inductive assumption and $xt^Rs^R=(tx)^Rs^R$ again by
the second property.

{\bf Alternative solution:}
\begin{proof}
\newline
by \textbf{strong induction} on the length, $n$, of $vw$.
\newline
\begin{tabbing}
XXti\=XXti\=XXti\=XXXXXXXXXXXXXX\=    \kill
\textbf{Base:} vw is of length 0.  Here, $vw = \lambda$ which means $v = w = \lambda$, so $(vw)^R = (\lambda)^R = \lambda = \lambda \lambda = w^Rv^R$.\\
\textbf{Inductive step: Assume:} $P(n): \forall i \in \naturals \; (0 \leq i \leq n) Q(i)$ holds (Inductive Hypothesis).\\
\> That is, $Q(i): ``(vw)^R = w^Rv^R \; for \; an \; arbitrary \; string \; vw \; of \; length \; i''$ \\
We now \textbf{prove} $P(n+1)$ holds.\\
Let $vw$ be an arbitrary string of length $n+1$.\\
\> \textbf{Case 1:} $w$ is of length exactly 0\\
\> \> then $(vw)^R = (v)^R = \lambda v^R = \lambda^R v^R = w^Rv^R$.\\
\> \textbf{Case 2:} $w$ is of length exactly 1\\
\> \> then $v \in \Sigma^*$ and $w \in \Sigma$ ($w$ is a single symbol)\\
\> \> $(vw)^R = wv^R$ by the definition of \emph{reversal}\\
\> \> then $w = w^R$ as $w^R = (\lambda w)^R = w \lambda^R = w$ by definition of \emph{reversal} for a single symbol\\
\> \> so $(vw)^R = w^Rv^R$\\
\> \textbf{Case 3:} $w$ is of length $> 1$ and $\leq n$\\
\> \> then $v \in \Sigma^*$ and has length $\geq 1$\\
\> \> $x \in \Sigma^*$ and $y \in \Sigma$ for some $x$, $y$, s.t. $w = xy$\\
\> \> thus, $vw = vxy$ for some $y \in \Sigma$\\
\> \> let $t = vx$  then, $t \in \Sigma^*$ and is of length $n$ by the definition of \emph{length}\\
\> \> then, $vw = ty$ so that $(vw)^R = (ty)^R = yt^R$ by the definition of \emph{reversal}\\
\> \> we know that $t^R = (vx)^R = x^Rv^R$ by the Inductive Hypothesis at n.\\
\> \> so, $(vw)^R = yx^Rv^R = y^Rx^Rv^R$ by substitution and $y = y^R$ for a single symbol.\\
\> \> we have that $y^Rx^R = (xy)^R = w^R$ by the Inductive Hypothesis at some $i \leq n$\\
\> \> thus, $(vw)^R = w^Rv^R$.\\
\> \textbf{Case 4:} $w$ is of length $n+1$\\
\> \> we have in this case that $v = \lambda$\\
\> \> thus, $(vw)^R = (\lambda w)^R = (w)^R = w^R\lambda = w^R\lambda^R = w^Rv^R$\\
$QED$\\
\end{tabbing}
\end{proof}
}


\problem 

\def\T{\cal N}
We define the family $\T$ of number search trees as follows:
\begin{enumerate}
\item
  Any single number $x$ is in $\T$.
\item If $T$ is in $\T$, and $x$ is a number greater than any number
  in $T$, then the structure formed by pointing an arrow
  labelled ``left'' from $x$ to $T$ is also in $\T$.
\item If $T$ is in $\T$, and $x$ is a number smaller than any number
  in $T$, then the structure formed by pointing an arrow
  labelled ``right'' from $x$ to $T$ is also in $\T$.
\item If $T$ and $T'$ are in $\T$, and a number $x$ is larger than
  ever number in $T$ but smaller than every number in $T'$, then the
  structure formed by attaching an arrow labelled ``left'' from $x$
  to $T$ and an arrow labelled ``right'' from $x$ to $T'$ is also in
  $\T$.
\end{enumerate}
In all cases above, the number $x$ is called the \emph{root} of the
tree that is formed.  Since the descriptions above are wordy, you may
wish to introduce some notation, like makeleft$(T,x)$ to denote the
thing built up according to the first recursive rule.  Likewise,
makeright$(x,T)$, makeboth$(T,x,T')$.

Now consider the following recursive algorithm for checking whether a
certain number is present in a tree $T$.
\begin{tabbing}
else\=else\=else\=else\=\kill

Algorithm Member$(q,T)$\\
\\
\>Let $x$ be the root of tree $T$\\
\> {\bf if} $x=q$ {\bf then}\\
\> \> {\bf return} YES\\
\> {\bf else} \\
\> \> {\bf if} $q<x$ {\bf and} $x$ has a ``left'' arrow to tree $T'$ {\bf
  then}\\
\> \> \> {\bf return} Member$(q,T')$\\
\> \> {\bf else if} $q>x$ {\bf and} $x$ has a ``right'' arrow to tree $T'$ {\bf
  then}\\
\> \> \> {\bf return} Member$(q,T')$\\
\> \> {\bf else}\\
\> \> \> {\bf return} NO\\
\end{tabbing}
Prove that a call to member$(q,T)$ returns YES if and only if $q$ is a
number in the number search tree $T$.

\newcommand{\membern}{\hbox{member}}
\newcommand{\makeleft}{\hbox{makeleft}}
\newcommand{\makeright}{\hbox{makeright}}
\newcommand{\makeboth}{\hbox{makeboth}}

\solution{ We use structural induction. We use $x<T$ to mean
  $x<\mbox{all numbers in }T$, and define $x>T$ similarly. We get four
  cases, one for each production rule.
\begin{enumerate}
\item
For a single-node tree $T$ with root $x$, if $q\in T$, $q=x$ and 
$\hbox{member}(q,T)$ returns YES. If $q\notin T$, since there are no arrows
from $x$, the final else is taken and $\hbox{member}(q,T)$ returns NO.
\item
Fix $T$, and assume $\forall q$, $\hbox{member}(q,T)$ returns YES iff $q\in T$.
We need to show that $\forall q,\forall x>T$,
$\membern(q,\makeleft(T,x))$ returns YES iff $q\in\makeleft(T,x)$.
If $q\in\makeleft(T,x)$, $q=x$ or $q\in T$. If $q=x$,
$\membern(q,\makeleft(T,x))$ immediately returns YES. If $q\in T$, $q<x$
and since $x$ has a left arrow to $T$, $\membern(q,T)$ is returned,
which is YES by inductive assumption. If $q\notin\makeleft(T,x)$, then
$q\ne x$ and $q\notin T$, so either the final else is taken and NO
returned or $\membern(q,T)$ is returned, returning NO by inductive
assumption.
\item
Similar to 2.
\item
Fix $T$, $T'$ and assume $\forall q$, $\membern(q,T)$ returns YES iff
$q\in T$ and $\membern(q,T')$ returns YES iff $q\in T'$. We need to
show that $\forall q$, $\forall x\suchthat x>T\wedge x<T'$,
$\membern(q,\makeboth(T,x,T'))$ returns YES iff
$q\in\makeboth(T,x,T')$. If $q\in\makeboth(T,x,T')$, there are 3
cases. Case 1: $q=x$, so member returns YES. Case 2: $q\in T$, so
$q<x$, $x$ has a left arrow to $T$, and $\membern(q,T)$ is returned,
which is YES by inductive assumption. Case 3: $q\in T'$, by similar reasoning
YES is returned. If $q\notin\makeboth(T,x,T')$, then $q\ne x$,
$q\notin T$, and $q\notin T'$, so
either NO is returned immediately or $\membern(q,T)$ or $\membern(q,T')$
is returned, which are NO by inductive assumption.
\end{enumerate}
}


\end{problems}

\end{document}                            
