\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand{\solution}{%
  \paragraph{Solution}}

\begin{document}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% A new problem spring 2001. /Lars

\newcommand{\power}{\mathcal{P}}

\problem\textbf{Chains and antichains}

\noindent Let $A = \{1,2,\ldots,n\}$
and consider the partial order $(\power(A),\subseteq)$. (Remember that
$\power(A)$ is the set of all subsets of~$A$ and that $\subseteq$ is
the normal subset operator.)

\begin{problemparts}
  \ppart Prove that there exists a chain of length~$n+1$ in
  $(\power(A),\subseteq)$.
  
  \solution{Let $A_0 = \emptyset$ and $A_i = A_{i-1} \cup \{i\}$ for
    $0 < i \leq n$. Then $A_i \subset A_{i+1}$ and there are $n+1$
    different $A_i$'s.}

  
  \ppart Prove that for any integer~$k$ such that $0 < k < n$, the
  set $\{B \subseteq A : |B| = k\}$ is an antichain in
  $(\power(A),\subseteq)$.
  
  \solution{Let $A_k = \{B \subseteq A : |B| = k\}$ and consider
    $B_1,B_2 \in A_k$ such that $B_1 \neq B_2$. We prove the claim by
    contradiction, i.e., by assuming that $B_1$ and~$B_2$ are related.
    Thus, assume without loss of generality that $B_1 \subseteq B_2$.
    Since $B_1 \neq B_2$, this implies that $B_1 \subset B_2$, which
    implies that $|B_1| < |B_2|$, which contradicts the fact that
    $B_1,B_2 \in A_k$.  Thus $B_1$ and~$B_2$ are uncomparable, which
    implies that $A_k$~is an antichain.}
\end{problemparts}

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

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 3    *
%**************

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
problem {\bf (5 points)} 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}


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

\problem {\bf (10 points)} A relation $R$ on a set $A$ is {\em weakly
transitive} if for all $a, b, c, d \in A$, the relations $aRb$, $bRc$,
and $cRd$ imply the relation $aRd$.

Prove or disprove the following statements.

\begin{problemparts}

\problempart Every symmetric, weakly transitive relation is transitive.

\solution{
The claim is false.  The diagram below shows a counterexample.

\begin{figure}[h!]
\centerline{\resizebox{!}{1.0in}{\includegraphics{figs/f98ps3-relation-cx.eps}}}
\end{figure}
}

\problempart Every reflexive, symmetric, weakly transitive relation
is an equivalence relation.

\solution{
\begin{proof}
The relation $R$ is an equivalence relation if it is reflexive,
symmetric, and transitive.  The first two properties hold by
assumption; all that remains is to show that $R$ is a transitive
relation.  Suppose that the relations $aRb$ and $bRc$ hold.  Because
$R$ is reflexive, the relation $aRa$ also holds.  Because $R$ is
weakly transtive, the relations $aRa$, $aRb$, and $bRc$ imply the
relation $aRc$.  Therefore, $R$ is transitive.
\end{proof}
}

\end{problemparts}

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

\begin{problemparts}

\problempart List all the linear extensions of the poset represented by the
Hasse diagram below.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{figs/f98ps3-partial2.eps}}}
\end{figure}

\solution{
\[
\begin{array}{ccc}
a > b > c > e > d       & \quad \quad &         a > c > b > e > d \\
a > b > c > d > e       &       &               a > c > b > d > e \\
a > b > d > c > e
\end{array}
\]
}

\problempart  After considering the above examples, Theory Pig formulated
the following claim.

\bigskip

{\bf Claim.} The number of linear extensions of a partially ordered
set with $n$ elements always divides $n!$.

\bigskip

Either prove that his claim is correct for all posets or else draw
the Hasse diagram of a counterexample and list all linear extensions.

\bigskip

\solution{
The claim is false.  The 4-element poset depicted below has 5 linear
extensions.  This is a counterexample, because 5 does not divide 4!.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{figs/f98ps3-poset-cx.eps}}}
\end{figure}

\[
\begin{array}{ccc}
a > b > c > d   & \quad \quad &         a > b > d > c \\
b > a > c > d   &       &               b > a > d > c \\
b > d > a > c
\end{array}
\]
}

\end{problemparts}

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

%END   Kavita's problems

%BEGIN Joe's problems
\problem %source: spring00 ps3
Find the flaws in the following fallacious proofs of
putative theorems.  For each, if the theorem is false, give a
counterexample; if it is correct, give a correct proof.

%\begin{problemparts}

\problempart
% topic: false proof, Cartesian products, relations
% source: Velleman 4.1.5


\emph{Theorem?} For any sets $A$, $B$, $C$, and $D$, $(A \union C)
\times (B \union D) \subseteq (A \times B) \union (C \times D)$?

\begin{proof}
  Suppose $(x, y) \in (A \union C) \times (B \union D)$.  Then $x \in A \union 
  C$ and $y \in B \union D$, so either $x \in A$ or $x \in C$, and either 
  $y \in B$ or $y \in D$.  We consider these cases separately.

  \emph{Case 1}. $x \in A$ and $y \in B$.  Then $(x, y) \in A \times B$.
  \newline
  \emph{Case 2}. $x \in C$ and $y \in D$.  Then $(x, y) \in C \times D$.

  Thus, either $(x, y) \in A \times B$ or $(x, y) \in C \times D$, so 
  $(x, y) \in (A \times B) \union (C \times D)$.
\end{proof}

\omitsolution{%
\begin{solution}
\newline
\textbf{The theorem does not hold.}
The cases do not exhaust all of the
possibilities.
The correct way to write the proof would be to include first the possibilities
that $A$, $B$, $C$, and $D$ are null and then trying out all \emph{four} 
cases, $x \in A \land y \in B$, $x \in A \land y \in D$, $x \in C \land y \in 
B$, and $x \in C \land y \in D$.
\newline
Consider the case where $A = \emptyset$, $C = \{1\}$, $B = \{2\}$, and $D = 
\{4\}$.  Then, the LHS (left-hand-side) gives $\{(1, 2), (1, 4)\}$, while the
RHS gives $\{(1, 4)\}$.  The statement of the theorem clearly does not hold in
this case.

\end{solution}
}

\problempart
% topic: ???
% source: Velleman 4.3.10

\emph{Theorem?}  Suppose $R$ is a relation on $A$.  If $R$ is symmetric and 
transitive, then $R$ is reflexive.

\begin{proof}
Let $x$ be an arbitrary element of $A$.  Let $y$ be any element of $A$ such 
that $xRy$.  Since $R$ is symmetric, it follows that $yRx$.  Then by 
transitivity, since $xRy$ and $yRx$.  We conclude that $xRx$.  Since $x$ was
arbitrary, we have shown that $\forall x \in A (xRx)$, so $R$ is reflexive.
\end{proof}

\omitsolution{%
\begin{solution}
\newline
\textbf{The theorem does not hold.}
Suppose $A = \{a, b, c, d\}$ and we are given the relation 
$R = \{(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), 
(c, c)\}$.  Then R is symmetric [``$\forall x \in A \forall y \in A (xRy 
\implies yRx$''] and transitive [``$\forall x \in A \forall y \in A 
\forall z \in A ((xRy \land yRz) \implies xRz)$''].  However, it is not
reflexive, as it is not the case that ``$\forall x \in A (xRx)$'', as 
$(d, d) \notin R$.
\end{solution}
}


\problempart
% topic: relations, building posets out of transitive closure of a reflexive, 
%        antisymmetric relation
% source: Velleman 4.5.12

\emph{Theorem?}  Suppose $R$ is a reflexive, antisymmetric relation on $A$.  
Let $S$ be the transitive closure of $R$.  Then $S$ is a partial order on $A$.
\begin{proof}
$R$ is already reflexive and antisymmetric.  To form the relation $S$ we add 
more ordered pairs to make it transitive as well.  Thus, $S$ is reflexive, 
antisymmetric, and transitive, so it is a partial order.
\end{proof}

\omitsolution{%
\begin{solution}
\newline
\textbf{The theorem does not hold.}
Suppose we have the relation $R = \{(a, a), (b, b), (c, c), (a, b), 
(b, c), (c, a)\}$.  This relation is both reflexive and antisymmetric
on $A = \{a, b, c\}$.  However, taking its transitive closure would break
the antisymmetry.  For example, the transitive closure $T$ of $R$ includes 
$(a, c)$, since there is a walk from $a$ to $c$ in $R$.  Since $T$ also 
contains $(c, a)$, it is not antisymmetric.
\end{solution}
}

%\end{problemparts}

 
% topic: relations, transitive closures, symmetric relations
% source: Velleman 4.5.10

Suppose $R$ is a relation on $A$, and let $S$ be the transitive closure of $R$.
Prove that if $R$ is symmetric, then so is $S$.  (Hint:  Assume that $R$ is 
symmetric.  Prove that $R \subseteq S^{-1}$ and $S^{-1}$ is transitive.  What
can you conclude about $S$ and $S^{-1}$?)

\omitsolution{%
\begin{solution}
\begin{proof}
Assume that $R$ is symmetric.  We can prove that $R \subseteq S^{-1}$.  
Suppose arbitrary $(a, b) \in R$.  Then $(b, a) \in R$ as well.  So, both 
$(a, b)$ and $(b, a)$ are in $S$ as $R \subseteq S$ by definition of
closure.  Likewise, $(b, a)$ and $(a, b)$ are also in $S^{-1}$ by the 
defintion of inverse.  Thus, $R \subseteq S^{-1}$.
\newline
We must now prove that $S^{-1}$ is transitive.  Suppose we choose an 
arbitrary three elements $a \in A$, $b \in A$, and $c \in A$ such that
$((a, b) \in S^{-1} \; \land (b, c) \in S^{-1})$.  This means that 
$(b, a) \in S \; \land (c, b) \in S$ by definition of inverse.  But 
since $S$ is transitive this means $(c, a) \in S$.  Thus, by definition
of inverse $(a, c) \in S^{-1}$.  This is the necessary condition to 
satisfy transitivity.  Thus, $S^{-1}$ is transitive.
\newline
We know that the cardinality of $S$ and its inverse are both the same.  
Since $S$ was the transitive closure of $R$, it is the smallest set
such that $R \subseteq S$ and $S$ is transitive.  Since $S^{-1}$ has
the same cardinality as $S$, $R \subseteq S^{-1}$, and $S^{-1}$ 
is a transitive superset of (or equal to) $R$; $S^{-1}$ is also a
transitive closure of $R$.  But the transitive closure of $R$ is unique.
So, $S = S^{-1}$.
\newline
Therefore, since $S$ is the same set as its inverse, $S$ is symmetric.  
$QED$. 
\end{proof}
\end{solution}
}

\problem %source: spring00 ps3, Velleman 4.3.9 
% topic: relations, compositions, reflexive, symmetric, transitive

Suppose $R$ and $S$ are binary relations on a set $A$.  For each part, give 
either proofs or counterexamples to justify your answers.

%\begin{problemparts}

\problempart

Suppose $R$ and $S$ are reflexive. Must $R \intersect S$ be reflexive?  What
about $R \union S$?  What about $R^{-1}$?  What about $R \composition S$?

\omitsolution{%
\begin{solution}
\newline
$R \intersect S$: \textbf{Yes.} $\forall a \in R \; (a, a) \land \forall a \in
S \; (a, a)$.  Therefore, $R \intersect S$ contains $(a, a)$ for every 
$a \in A$.
\newline
$R \union S$: \textbf{Yes.} Their intersection contained $(a, a) \forall a \in
A$, so their union does too.
\newline
$R^{-1}$: \textbf{Yes.} For every $(a, a) \in R$, it holds that $(a, a) 
\in R^{-1}$ by the definition of inverse.  Thus, since $\forall a \in A 
(a, a) \in R$, it holds that $\forall a \in A (a, a) \in R^{-1}$, so the 
inverse is reflexive.
\newline
$R \composition S$: \textbf{Yes.} It holds that $\forall a \in A ((a, a) \in
S \land (a, a) \in R)$.  Thus, $\forall a \in A \; \exists b \in A \;
((a, b) \in S \land (b, a) \in R)$, so that $\forall a \in A \; ((a, a) \in 
R \composition S)$ by the definition of composition.
\end{solution}
}

\problempart Suppose $R$ and $S$ are symmetric.  Must $R \intersect S$
be symmetric?  What about $R \union S$?  What about $R^{-1}$?  What
about $R \composition S$?

\omitsolution{%
\begin{solution}
\newline
$R \intersect S$: \textbf{Yes.} If $(x, y) \in R \intersect S$, 
we must prove that $(y, x) \in R \intersect S$.  We have that $xRy$ 
(in which case 
$yRx$ as well) and $xSy$ (in which case $ySx$ as well).  Since $yRx \land
ySx$, we have $(y, x) \in R \intersect S$.
\newline
$R \union S$: \textbf{Yes.} Suppose $(x, y) \in R \union S$.  
Therefore, either $xRy$ (in which case $yRx$ and $\therefore (y, x) \in
R \union S$) or $xSy$
(in which case $ySx$ and $\therefore (y, x) \in R \union S$).  So by 
cases $(y, x) \in R \union S$.
\newline
$R^{-1}$: \textbf{Yes.} Suppose $(x, y) \in R^{-1}$.  By the 
definition of inverse, this 
means that $yRx$.  But since $R$ is symmetric, this means that $xRy$.  By the
definition of inverse again, this means that $(y, x) \in R^{-1}$.  
So $R^{-1}$ is symmetric.
\newline
$R \composition S$: \textbf{No.}  Suppose $A = \naturals$, 
$R = \{(b, c), (c, b)\}$ 
, and 
$S = \{(a, b), (b, a)\}$
.  Then $R \composition S = \{(a, c)\}$, which is not symmetric.
\end{solution}
}

\problempart Suppose $R$ and $S$ are transitive.  Must $R \intersect
S$ be transitive?  What about $R \union S$?  What about $R^{-1}$?
What about $R \composition S$?

\omitsolution{%
\begin{solution}
\newline
$R \intersect S$: \textbf{Yes.} Suppose there is 
a walk from $x$ to $y$ in $R \intersect S$.  We need to prove $(x,y) \in
R \intersect S$.  In order for there to
be a walk from $x$ to $y$ in $R \intersect S$, there must have been a walk 
from $x$ to $y$ 
in both of $R$ and $S$ (otherwise, those walks would not appear in their 
intersection as walks).  Thus, $xRy$ and $xSy$, so $(x, y) \in R 
\intersect S$ as needed.
\newline
$R \union S$: \textbf{No.} Suppose $R = \{(a, b), (b, c), (a, c)\}$ and 
$S = \{(b, c), (c, a), (b, a)\}$.  Then $U = R \union S = \{(a, b), (b, a), 
(b, c), (c, a), (a, c)\}$, so that $cUa$ and $aUb$ but $\neg (cUb)$.
\newline
$R^{-1}$: \textbf{Yes.} Suppose $(a, b) \in R^{-1} \land 
(b, c) \in R^{-1}$.  We must prove that $(a, c) \in R^{-1}$.  
We know from the definition of inverse that
$bRa \land cRb$.  Furthermore, since $R$ is transitive, we have that $cRa$.  
By the definition of inverse again we have that $(a, c) \in 
R^{-1}$, as needed.
\newline
$R \composition S$: \textbf{No.} Suppose $R = \{(b, a), (b, c), (c, a)\}$ and 
$S = \{(a, b), (a, c), (b, c)\}$.  Then $(b, a) \in R \composition S$ and 
$(a, c) \in R \composition S$ but $(b, c) \notin R \composition S$.  
Transitivity fails for the composition. 
\end{solution}
}

\problempart
% topic: equivalence relations, intersection, union, composition
% source: Velleman 4.6.9

Suppose $R$ and $S$ are equivalence relations.  Must $R \intersect S$ 
be an equivalence relation on $A$?  What about $R \union S$?  What about 
$R \composition S$?

\omitsolution{%
\begin{solution}
\newline
$R \intersect S$: \textbf{Yes.}  Here we are supposing $R$ and $S$ are 
reflexive, symmetric, and transitive.  Since we showed above that these 
properties hold over intersection, $R \intersect S$ is reflexive, symmetric,
transitive, and therefore an equivalence relation as well.
\newline
$R \union S$: \textbf{No.}  Suppose $R = \{(a, a), (b, b), (c, c), (a, b),
(b, a)\}$ and 
$S = \{(a, a), (b, b), (c, c), (b, c), (c, b)\}$.  Then $(c, b) \in R \union 
S$ and $(b, a) \in R \union S$ but $(c, a) \notin R \union S$.  Transitivity
fails and $R \union S$ is not an equivalence relation.
\newline
$R \composition S$: \textbf{No.}  Suppose $R$ and $S$ are as in the above 
counterexample.  Then $(a, b) \in R \composition S$ and $(b, c) \in R
\composition S$ but $(a, c) \notin R \composition S$.  Transitivity fails
and $R \composition S$ is not an equivalence relation.
\end{solution}
}

%\end{problemparts}



%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%

\problem %source: spring00 ps3, Velleman 4.4.4
% topic: relations, posets

Suppose $R$ is a partial order on $A$ and $S$ is a partial order on $B$.  
Define a relation $T$ on $A \times B$ as follows: $T = \{((a, b), (a', b')) \in
(A \times B) \times (A \times B) \mid aRa' \mbox{ and } bSb'\}$.  Show that $T$ is a partial
order on $A \times B$.  If both $R$ and $S$ are total orders, will $T$ also be 
a total order?

\omitsolution{%
\begin{solution}
\newline
To show $T$ is a poset on $A \times B$, we must show it is reflexive, 
symmetric, and transitive on $A \times B$.
\newline
\emph{Reflexive:} Choose an arbitrary element of $A \times B$, if one exists
(if none exists, there's nothing to prove and $T$ is reflexive).  Call this
element $(x, y)$.  To prove $T$ is reflexive, we must prove $((x, y)T(x, y))$.
Given we have $(x, y)$ chosen, we know $xRx$ and $ySy$ as both $R$ and $S$ 
are reflexive.  Thus, by the definition of $T$, $((x, y), (x, y)) \in T$ as
it is an element of $(A \times B) \times (A \times B)$ such that $xRx \land
ySy$.  Therefore, $T$ is reflexive.
\newline
\emph{Antisymmetric:} We must show that $\forall (a, b) \in (A \times B) \;
\forall (c, d) \in (A \times B) \; 
(((a, b)T(c, d) \land (c, d)T(a, b)) \implies (a, b) = (c, d))$.  Suppose 
we choose an arbitrary $a \in A$, $b \in B$, $c \in A$, and $d \in B$ such 
that the above premise holds.  If no such elements exist, $T$ is trivially
antisymmetric.  We have that $aRc \land cRa$ from the definition of $T$,
and thus $a = c$ as $R$ is antisymmetric.  Furthermore, $b = d$ by similar
rationale.  Thus, $(a, b) = (c, d)$, as needed.  $T$ is antisymmetric.
\newline
\emph{Transitive:} We must show that $\forall (a, b) \in (A \times B) \; 
\forall (c, d) \in (A \times B) \; \forall (e, f) \in (A \times B) \; 
(((a, b)T(c, d) \land (c, d)T(e, f)) \implies (a, b)T(e, f))$.  Let's 
arbitrarily choose a particular $a \in A$, $b \in B$, $c \in A$, $d \in B$, 
$e \in A$, and $f \in B$ such that the premise of the above implication holds. 
If there are no such elements, there is nothing to prove and $T$ is transitive.
We know that since $aRc$ and $cRe$ (by the definition of $T$), $aRe$ (by the
definition of $R$ being transitive).  Similarly, $bSf$ as $S$ is transitive.  
But since $aRe \land bSf$, $((a, b), (e, f)) \in T$ by the definition of $T$. 
Therefore, $T$ is transitive.
\newline
\textbf{No, $T$ is not a total order.}  Suppose you have $R = 
\{(a, a), (a, b), (b, b)\}$ (lexicographically less than or equal to) and 
$S = \{(1, 1), (1, 2), (2, 2)\}$ (numerically less than or equal to).  Then 
if we form $T$ as defined, there is no way to compare the points $(b, 1)$
and $(a, 2)$.
\newline
%\emph{A picture here would be nice!!!}
\end{solution}
}

\problem %source: spring00 pset3, after end of document
% topic: relations, compositions, domains, ranges
% source: Velleman 4.2.7

Suppose $R$ is a relation from $A$ to $B$ and $S$ and $T$ are relations from 
$B$ to $C$.  Must the following statements be true?  Justify your answers with
proofs or counterexamples.

%\begin{problemparts}

\problempart
If $S \subseteq T$ then $S \composition R \subseteq T \composition R$.

\omitsolution{%
\begin{solution}

\emph{not done yet}

\end{solution}
}

\problempart
$(S \intersect T) \composition R \subseteq (S \composition R) \intersect
(T \composition R)$.

\omitsolution{%
\begin{solution}

\emph{not done yet}

\end{solution}
}

\problempart
$(S \intersect T) \composition R = (S \composition R) \intersect
(T \composition R)$.

\omitsolution{%
\begin{solution}

\emph{not done yet}

\end{solution}
}

\problempart
$(S \union T) \composition R = (S \composition R) \union
(T \composition R)$.

\omitsolution{%
\begin{solution}

\emph{not done yet}

\end{solution}
}

%\end{problemparts}


%END   Joe's problems

%BEGIN Ray's problems

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  New problem for Spring 2000
%  not used yet
\problem \textbf{Ordering}


After graduating from MIT, you are hired by a startup company that
specializes in organizing frog races.  Your first assignment is to
plan the finals for a race near Johnstown, Pa.  The competition is run
in two stages.  First, some prelimnary races are run between small
groups of the frogs.  Then, the results of those races are used to
determine the frogs' starting positions for the final, deciding race.
All the preliminary races have been run with the following results:


\begin{center}
\begin{tabular}{l|c|c|c|c}
  & Race 1 & Race 2 & Race 3 & Race 4 \\ 
\hline
  1st & Lars & Ivan & David & Ray \\
  2nd & Ray & Josh & Lars & George \\
  3rd & Kavita & Tina & Ivan & Tina \\
  4th & Be & Be & Joe & Joe
\end{tabular}

\end{center}



You must line the 10 frogs up for the final race so that no frog is
after a frog it has beaten in one of the preliminary rounds.  Give one
possible ordering.

\solution{\medskip
\textbf{Solution:}

Two possible orderings are:

David, Lars, Ivan, Josh, Ray, George, Tina, Joe, Kavita, Be

and

David, Lars, Ray, Kavita, George, Ivan, Josh, Tina, Be, Joe

}


%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

\problem \textbf{Relations}
\bparts
\ppart Velleman \S 4.2, Exercise 3 parts a,b and c.\\
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.
%%% 
}
%%%
%\ppart Velleman \S 4.2, Exercise 7
%%%
\eparts

%%%
%\problem \textbf{Relations --- Ordering}
%Velleman \S 4.3, Exercise 9.
%%%
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \textbf{Relations --- Properties}
\bparts
\ppart Velleman \S 4.4, Exercise 1. %[[[Good finger exercise.]]]


\noindent In each case, say whether or not $R$ is a partial order on $A$.  If so, is it a total order?\\
a. $A=\{a,b,c\}, R=\{(a,a),(b,a),(b,b),(b,c),(c,c)\}.$\\
b. $A=\{$ the set of all words in English, $R = \{(x,y\}\in A \times
A\  \nand \ $the word $x$ comes before the word $y$ alphabetically$\}$.\\
c. $A=\reals, R=\{(x,y) \in \reals \times \reals \ \nand \ |x|\leq |y|\}$.\\
d. $A=\reals, R=\{(x,y) \in \reals \times \reals \ \nand \ |x| < |y|$
or $x=y\}$.\\
\medskip
\solution{
\textbf{Solutions:}\\
a. $R$ is reflexive, transitive, and antisymmetric.  Therefore, $R$ is a partial order on $A$.  However, it is not a total order on $A$ since neither the pair $(a,c)$ nor $(c,a)$ is in $R$.\\
b. $R$ is not reflexive (although it is transitive and antisymmetric), and thus it is not a partial order on $A$.\\
c. $R$ is reflexive and transitive. However, it is not antisymmetric. As a counterexample, \\
$|-3| \leq |3|, |3| \leq |-3|$, but $3 \neq -3$. \\
d. $R$ is reflexive, transitive, and antisymmetric.  Therefore, $R$ is a partial order on $A$. However, $R$ is not a total order on $A$. As a counterexample, if x = 5, y = -5, then none of the following holds: $x = y, |x| < |y|, |y| < |x|$.  
}


%%%
%\ppart Velleman \S 4.4, Exercise 5. %[[[Good]]]
%%%

\eparts   
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \textbf{Relations --- Equivalence relations}
\bparts
\ppart Velleman \S 4.6, Exercise 3. \\
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Which of the following relations are equivalence relations?  For those that are equivalence\\
relations, what are the equivalence classes?\\
\>a. $R=\{(x,y) \in W \times W \ \nand \ $ the words $x$ and $y$ start with the same letter$\}$,\\
\>\>where $W=$ the set of all words in teh English language.\\
\>b. $S=\{(x,y) \in W \times W \ \nand \ $ the words $x$ and $y$ have at least one letter in\\
\>\>common$\}$, where $W=$ the set of all words in teh English language.\\
\>c. $R=\{(x,y) \in \reals \times \reals \ \nand \ x-y \in \rationals\}$.\\
\>d. $R=\{(x,y) \in \reals \times \reals \ \nand \ \exists n \in \integers$ such that $(y=x\cdot 10^n)\}$.\\
\end{tabbing}
\solution{
\textbf{Solutions:}\\
\renewcommand{\labelenumi}{\alph{enumi}.}
\begin{enumerate}

\item 
$R$ is an equivalence relation since it is reflexive, symmetric, and transitive.  The equivalence class of $x$ with respect to $R$ is the set $[x]_R = $ the set of words $y$, such that $y$ has the same first letter as $x$.

\item
 $S$ is reflexive and symmetric, but it is not transitive.  Therefore, $S$ is not an equivalence relation.  For example, let $w_1$ be the word ``scream,'' let $w_2$ be the word ``and,'' and let $w_3$ be the word ``shout.''  Then $w_3 S w_1$, and $w_1 S w_2$, but it is \textbf{not} the case that $w_3 S w_2$.

\item
$R$ is reflexive since, for any $x\in R$, $x-x=0$.  $R$ is symmetric because if $(x-y)$ is rational, then $(y-x)=-(x-y)$ is rational as well.  Finally, $R$ is also transitive.  To see this, consider $(x,y)\in R$ and $(y,z)\in R$.  We would like to know if $(x,z)$ is also in $R$.  We start by noting that $(x-y)\in \rationals$ and $(y-z)\in \rationals$ by definition of our relation $R$.  Now, we can express $(x-z) = (x-y)+(y-z)$.  Since the sum of any two rational numbers is another rational number, and we have written $(x-z)$ as such, we have shown that $(x,z)\in \rationals$.  Therefore, $R$ is transitive.  Since $R$ is also reflexive and symmetric, $R$ is an equivalence relations on $\reals$.\\
The equivalence class for x is $[x]_R = \{y\ |\ y$ can be written in the form $x + r$, for some rational number $r\}$

\item
$R$ is reflexive, since we can set $n=0$.  $R$ is symmetric because if $y=x*10^k$, for some $k\in \integers$, then $x=y*10^{-k}$, so if $(x,y)\in R$, then $(y,x)\in R$.  We can show that $R$ is transitive as follows: consider pairs $(x,y)\in R$ and $(y,z)\in R$.  $y=x*10^n$ and $z=y*10^m$, for $m,n\in \integers$.   Then, substituting, we have that $z=y*10^{m+n}$.  Since $m+n$ is also $\in \integers$, $(x,z)$ is $\in R$.\\
The equivalence class for x is $[x]_R = \{ y\ |\ y  = x*10^n$, for some $n\in \integers\}$
\end{enumerate}
\renewcommand{\labelenumi}{\arabic{enumi}.}
%%someone should check this... it's getting late and this just seems silly to me
}

\ppart Velleman \S 4.6, Exercise 5. \\
Given $T$, the set of all triangles, and $S=\{(s,t)\in T\times T$ $|$ the triangles $s$ and $t$ are similar$\}$, prove that $S$ is an equivalence relation.\\
\medskip
\medskip
\solution{
\textbf{Solution:}\\
\textbf{Proof:} To prove this, we need to show that $S$ is reflexive, symmetric, and transitive.  Here we go:\\
First of all, two triangles $s$ and $t$ are said to be \textit{similar} if they have three pairs of equal-degree vertices.\\
$S$ is reflexive because every triangle is similar to itself.  That is, every triangle $s$ has three angles of equivalent size to its own three angles.\\
$S$ is symmetric because if $s$ is similar to $t$, then $s$ and $t$ have vertices of the same size, so $t$ is similar to $s$ as well.\\
Finally, $S$ is transitive because if triangle $s$ is similar to triangle $t$, and triangle $t$ is similar to triangle $r$ then triangles $s$ and $t$ have three pairs of equal-degree vertices, and triangles $t$ and $r$ also have three pairs of equal-degree vertices.  $s$ and $r$ must share these three pairs of equal-degree vertices since triangles only have three vertices. $\qed$.
}

%%%
%\ppart Velleman \S 4.6, Exercise 12. 
%%%
\eparts

%%%
%\problem \textbf{Relations --- Topological sorting}
%\bparts
%\ppart Find two total orders that are topological sorts of the divisibility
%relation for the set of natural numbers 1-8:\\
%(i) One with as many as you can pairs out of numerical order.\\
%(ii) One with the FEWEST POSSIBLE pairs out of numerical order.\\
%\eparts
%%%
%%%%%%%%%%%%%%  Fall 2000  Problem Set 4    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem
% Task scheduling or Dilworth
At last count, our 6.042 class contains 180 students.
Prove that the class must contain either:
(a) A set $S$ of 15 students such that, if they line up in size
places, they are also arranged in increasing order of age,
or
(b) a set $T$ of 13 students such that, if they line up in size
places, they are also arranged in decreasing order of age.




\solution{
\medskip
\textbf{Solution:}\\
For each student, we can assign a pair $(s,a)$ where $s$ represents the size (height) of the student and $a$ represents the age of the student. We then get a set $U$ of 180 such pairs. We can define the following binary relation $R$, denoted by $\preceq$, between two pairs $P_{1}$ and $P_{2}$: 
$P_{1}\preceq P_{2}$ iff $s_{1}\leq s_{2}$ and $a_{1}\leq a_{2}$. 

For example, if $P_{1}=(180, 20)$, $P_{2} = (180, 21)$, $P_{3}= (185, 19)$, we have $P_{1}\preceq P_{2}$ but $P_{3}$ and $P_{1}$ are incomparable.

It is easy to check that $R$ is reflexive, transitive and antisymmetric. Thus, it defines a partial order on the set $U$. By Dilworth's Theorem, since $U$ has 180 elements, it must either have a chain of size$>14$ or an antichain of size $\geq \frac{180}{14}$. 
\subparagraph{Case 1} $U$ has a chain of size $> 14$. Then it has a chain of size at least 15. This means that we can find 15 pairs which satisfy the relation $P_{1}\preceq P_{2}\preceq P_{3}\ldots \preceq P_{15}$. From the definition of our binary relation $(\preceq)$, this implies that $s_{1}\leq s_{2}\leq s_{3}\leq \ldots \leq s_{15}$ AND $a_{1} \leq a_{2} \leq a_{3}\leq\ldots\leq a_{15}$. Therefore, if we place the corresponding 15 students in the same order, they will be lined up in in increasing order of size AND in increasing order of age.

\subparagraph{Case 2} $U$ has an antichain of size $\geq\frac{180}{14}$, so, since antichains only come in integer lengths, it has an antichain of size at least 13. Therefore, we can find 13 pairs which are incomparable. We can line them up in order of increasing size (ignoring age), and  come up with an order $P_{1}\ldots  P_{13}$ so that $s_{i} \leq s_{i+1} (i= 1\ldots 12)$. Since for all $i$, $s_{i}\leq s_{i+1}$ and $P_{i}, P_{i+1}$ are incomparable, we can conclude that $a_{i}> a_{i+1}$ (because if not, $a_{i}\leq a_{i+1}$ so for that $i$, $s_{i}\leq s_{i+1},$ $a_{i}\leq a_{i+1}$, therefore $P_{i}\preceq P_{i+1}$, so $P_{i}$ and $P_{i+1}$ would NOT be incomparable.) If we take the students corresponding to $P_{1}\ldots  P_{13}$ and line them up in that order, they will be in increasing order of size (since $s_{i}\leq s_{i+1}$) and in decreasing order of age (since we established that $a_{i}>a_{i+1}$).



To eliminate some confusion: the sequence $\{2, 2, 3, 4\}$ is in increasing order, but not in strictly increasing order. 


  }

%[[[The idea here is supposed to be similar to the increasing sequence
%or decreasing sequence example that is suppressed in the lecture
%notes, under Dilworth's theorem material.  Order the students in the
%entire class by height.  Then use the argument about increasing or
%decreasing sequence.]]] 
             
%%%%%%%%%%%%%%%%%%%%%%%Fall 01 Tutorial 4 %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%this problem appeared in a problem set in fall 00
%very few people who didn't go to office hours got it right, even though
%it's not particularly difficult. Perhaps doing it in tutorial is a better idea


\problem \textbf{Dilworth}

At last count, our 6.042 class contains 180 students.
Prove that the class must contain either: \begin{enumerate} \setlength{\itemsep}{0pt} %\setlength{\itemsep}{0cm}
\item A set $S$ of 15 students such that, if they line up in size
places, they are also arranged in increasing order of age,
or
\item a set $T$ of 13 students such that, if they line up in size
places, they are also arranged in decreasing order of age.  \end{enumerate}
To eliminate some confusion: the sequence $\{2, 2, 3, 4\}$ is in increasing order, but not in strictly increasing order.



\solution{
\medskip
\textbf{Solution:}\\
For each student, we can assign a pair $(s,a)$ where $s$ represents the size (height) of the student and $a$ represents the age of the student. We then get a set $U$ of 180 such pairs. We can define the following binary relation $R$, denoted by $\preceq$, between two pairs $P_{1}$ and $P_{2}$: 
$P_{1}\preceq P_{2}$ iff $s_{1}\leq s_{2}$ and $a_{1}\leq a_{2}$. 

For example, if $P_{1}=(180, 20)$, $P_{2} = (180, 21)$, $P_{3}= (185, 19)$, we have $P_{1}\preceq P_{2}$ but $P_{3}$ and $P_{1}$ are incomparable.

It is easy to check that $R$ is reflexive, transitive and antisymmetric. Thus, it defines a partial order on the set $U$. By Dilworth's Theorem, since $U$ has 180 elements, it must either have a chain of size$>14$ or an antichain of size $\geq \frac{180}{14}$. 
\subparagraph{Case 1} $U$ has a chain of size $> 14$. Then it has a chain of size at least 15. This means that we can find 15 pairs which satisfy the relation $P_{1}\preceq P_{2}\preceq P_{3}\ldots \preceq P_{15}$. From the definition of our binary relation $(\preceq)$, this implies that $s_{1}\leq s_{2}\leq s_{3}\leq \ldots \leq s_{15}$ AND $a_{1} \leq a_{2} \leq a_{3}\leq\ldots\leq a_{15}$. Therefore, if we place the corresponding 15 students in the same order, they will be lined up in in increasing order of size AND in increasing order of age.

\subparagraph{Case 2} $U$ has an antichain of size $\geq\frac{180}{14}$, so, since antichains only come in integer lengths, it has an antichain of size at least 13. Therefore, we can find 13 pairs which are incomparable. We can line them up in order of increasing size (ignoring age), and  come up with an order $P_{1}\ldots  P_{13}$ so that $s_{i} \leq s_{i+1} (i= 1\ldots 12)$. Since for all $i$, $s_{i}\leq s_{i+1}$ and $P_{i}, P_{i+1}$ are incomparable, we can conclude that $a_{i}> a_{i+1}$ (because if not, $a_{i}\leq a_{i+1}$ so for that $i$, $s_{i}\leq s_{i+1},$ $a_{i}\leq a_{i+1}$, therefore $P_{i}\preceq P_{i+1}$, so $P_{i}$ and $P_{i+1}$ would NOT be incomparable.) If we take the students corresponding to $P_{1}\ldots  P_{13}$ and line them up in that order, they will be in increasing order of size (since $s_{i}\leq s_{i+1}$) and in decreasing order of age (since we established that $a_{i}>a_{i+1}$).



}


\end{problems}
\end{document}                                            
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%% Fall 01 Tutorial 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \textbf{Relations}


Consider the following putative theorem and the accompanying proof.
\begin{theorem*}
  For any sets $A$, $B$, $C$, and $D$, if $A \times B \subseteq C
  \times D$ then $A \subseteq C$ and $B \subseteq D$.
\end{theorem*}
\begin{proof}
  Suppose $A \times B \subseteq C \times D$.  Let $a$ be an arbitrary
  element of $A$, $b$ be an arbitrary element of $B$, and $(a, b) \in
  A \times B$.  Since $A \times B \subseteq C \times D$, it follows
  that $(a, b) \in C \times D$.  Therefore, $a \in C$ and $b \in D$.
  Since $a$ and $b$ were arbitrary elements of $A$ and $B$,
  respectively, this shows that $A \subseteq C$ and $B \subseteq D$.
\end{proof}
Is the proof correct?  If so, what proof strategies does it use?  If
not, can it be fi xed?  Is the theorem correct?

\solution{
\medskip
\textbf{Solution:}\\
    The problem lies in the statement \emph{``let $a$ be an arbitrary
      element of $A$''} (and without loss of generality, $b$ an
    arbitrary element in $B$).  Namely, if $A = \emptyset$, $B = \{1,
    2, 3\}$, $C = \{1, 2\}$, and $D = \{3, 4\}$, then $A \times B
    \subseteq C \times D$ ($\emptyset \subseteq E$ for any set $E$),
    but $B \not\subseteq D$.  This is an example of the proof failing
    at a boundary case.
  }

                     
%%%%%%%%%%%%%%%%%%%Fall 01 Tutorial 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\problem \textbf{Relations and Matrices} 

Let $A$ be the adjacency matrix for a digraph $G$ with $n$ vertices.  Note
that $A$ is a zero-one valued $n \times n$ matrix.  In this problem we use
the Boolean ``OR'' operation, $\vee$, instead of ``+'' when multiplying
zero-one valued matrices (this is called ``boolean'' matrix product).

%\begin{problemparts}

\problempart

For $k \in \naturals$, let $A^k$ be the $k$th {\em Boolean} power
of $A$.  Prove that ${A^k}_{ij} = 1$ iff there is a directed path of
length $k$ from the $i$th to the $j$th vertex of $G$.

%\omitsolution{%
  \solution{%
    Let $P(n)$ be the predicate that ${A^n}_{ij} = 1$ iff there is a
    directed path of length $n$ from the $i$th to the $j$th vertex
    of $G$.  We prove that $P(n)$ holds for all $n\geq 1$ by induction
    on $n$.

    {\bf Inductive Hypothesis:} $P(k): {A^k}_{ij} = 1$ iff there is a
    directed path of length $k$ from the $i$th to the $j$th vertex
    of $G$.
 

    {\bf Base Case:} $k = 1$.  By the definition of an adjacent matrix
    A, $A_{ij} = 1$ iff there is a directed edge (directed path of
    length $k = 1$) from the $i$th to the $j$th vertex of $G$.
 

    {\bf Inductive Step:} Assume $P(k)$ to prove $P(k+1)$.
 
\[{A^k}_{ij} = \bigvee_{l \in G} ({A^k}_{il} \wedge A_{lj})\]

Now we consider both directions for the iff.

Case 1:

There is a directed path of length $k+1$ from the $i$th to the $j$th
vertex of $G$.  This path looks like $i, i_1, i_2, \dots i_k, j$.
Then consider $l = i_k$.  ${A^k}_{il} = 1$ (inductive hypothesis).
${A}_{lj} = 1$ (there is an edge from $i_k$ to $j$), under the Case 1
assumption.  Therefore,

\[({A^k}_{il} \wedge A_{lj}) = 1\]
\[{A^{k+1}}_{ij} = 1\]

Case 2: ${A^{k+1}}_{ij} = 1$.

Then $\exists\; l \in G : ({A^k}_{il} \wedge A_{lj}) = 1$.  Thus there
is an edge from $l$ to $j$ and there is path of length $k$ from $i$ to
$l$(by the inductive hypothesis) which looks like $i, i_1, i_2, \dots
i_{k-1}, l$.  Thus, there is a path of length $k+1$ from $i$ to $j$
which hits $l$ on the $k$th step and then has the $k+1$st edge from
$l$ to $j$.  This path follows the vertices: $i, i_1, i_2, \dots
i_{k-1}, l, j$.

Q.E.D.
}


\problempart

Let $B = A \vee I$ where $I$ is the $n \times n$ identity matrix.
Prove that ${B^k}_{ij} = 1$ iff there is a directed path of length
$\leq k$ from the $i$th to the $j$th vertex of $G$.

%\omitsolution{%
  \solution{%
    From part a, it can be seen that ${B^k}_{ij} = 1$ iff there is a
    directed path of length $k$ from the $i$th to the $j$th vertex of
    $G'$, where $G'$ is the graph described by the adjacency matrix
    $B$.  Since $G'$ is just $G$ with self loops, a path exists
    between $i$ and $j$ in $G'$ iff a path exists between $i$ and $j$
    in $G$ (all vertices have paths of length $0$ to themselves).

    For any such path between $i$ and $j$ in $G'$, either it uses a
    self-loop edge or it does not.  If it does not, then the
    equivalent path in $G$ will have the same length.  If it does,
    then there is a shorter path in $G$ which can be obtained by not
    using the self loop.  So if there is a path of length $k$ between
    $i$ and $j$ in $G'$ then there is a path of length $\leq k$
    between $i$ and $j$ in $G$.

    If there is a path of length $\leq k$ between $i$ and $j$ in $G$,
    then it can be made to be of length $k$ by using self loops to
    lengthen the path.  Thus there is a path in $G'$ of length $k$ iff
    there is a path in $G$ of length $\leq k$.  Since ${B^k}_{ij} = 1$
    iff there is a path of length $k$ between $i$ and $j$ in $G'$ then
    ${B^k}_{ij} = 1$ iff there is a path of length $\leq k$ between
    $i$ and $j$ in $G$.%
    }%
  

\problempart 

Conclude that ${B^n}_{ij} = 1$ iff there is a directed path from the $i$th
to the $j$th vertex.

%\omitsolution{%
\solution{
If ${B^n}_{ij} = 1$ then there is a directed path from the $i$th to
the $j$th vertex.  If ${B^n}_{ij} = 0$ then there is no path of length
$<=n$ from the $i$th to the $j$th vertex.  There must also be no path of
length $>n$ from the $i$th to the $j$th vertex.  If there were, then the
path must cross through some vertices twice, since the length of the path is
$>n$.  For those vertices through which the path passes twice, eliminate
the loops so that the path uses no vertex more than once.  This means the
path must be of length $<=n$, which reaches a contradiction, since we know
that there are no paths from $i$ to $j$ of length $<=n$.  Therefore, if
${B^n}_{ij} = 0$ there is no path from $i$ to $j$ at all.\\
}
                        


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%                                  
        
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems


%BEGIN Tina's problems
%Fall 99
%%%%%%%%%%%%%%%

% problem set 4, problem 1
% equivalence classes
\begin{problems}

\problem \textbf{Equivalence Relations}
Let $(a,b) \sim (c,d)$ if $a+d = b+c$. We claim that $\sim$ is an
equivalence relation.

\begin{problemparts}

\problempart Partition the set $\{0,1,2\} \times \{0,1,2\}$ 
into the distinct equivalence classes under $\sim$.

\solution{
We can rewrite $(a,b) \sim (c,d)$ if $a+d = b+c$ as $(a,b) \sim (c,d)$ 
if $a-b = c -d$. This shows that with any equivalence class 
${\cal C}$ we can associate a {\em difference} $d$ such that 
$(a,b) \in {\cal C} \Rightarrow a - b = d$. This gives us an easy way to 
list the equivalence classes of $\{0,1,2\} \times \{0,1,2\}$.
\begin{itemize}
\item $d = -2$ :  $\{(0,2)\}$.
\item $d= -1$ : $\{(0,1),(1,2)\}$.
\item $d= 0$ : $\{(0,0),(1,1),(2,2)\}$.
\item $d= 1$ : $\{(1,0),(2,1)\}$.
\item $d= 2$ : $\{(2,0)\}$.
\end{itemize}
}

\problempart  Prove that $\sim$ is an equivalence 
relation on $\integers \times \integers$.

\solution{
\begin{itemize}
\item {\em Reflexivity} $(a,b) \sim (a,b)$ since $a + b = b + a$.
\item {\em Symmetry} $(a,b) \sim (c,d) \Rightarrow (c,d) \sim (a,b)$ 
since $a + d = b + c \Rightarrow c + b = d + a$.
\item {\em Transitivity} Assume $(a,b) \sim (c,d)$, i.e. $ a + d = b + c$. 
And, $(c,d) \sim (e,f)$, i.e. $c + f = d + e$. Adding we get 
$a + d + c + f = b + c + d + e$ or $a + f = b + e$, 
i.e. $(a,b) \sim (e,f)$. 
Hence $(a,b) \sim (c,d) \wedge (c,d) \sim (e,f) \Rightarrow (a,b) \sim (e,f)$.
\end{itemize}
Since $\sim$ is reflexive, symmetric and transitive it is an equivalence relation.
}

\problempart How many distinct equivalence classes under $\sim$ 
are there on the set $\{0,1,\ldots, n\} \times \{0,1,\ldots, n\}$. 
You do not need to prove your answer.

\solution{
$2n+1$ since the difference can be any value in $\{-n,\ldots, n\}$.}
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem set 4, problem 2
%posets

\problem \textbf{Posets}

Let $R$ be the lexicographic ordering of strings of symbols
from a totally ordered alphabet as defined in Rosen p. 417.

\begin{problemparts}

\problempart Prove that $R$ is a total order.

\solution{We first show that $R$ is a partial order.
Reflexivity is clear from the definition. To show antisymmetry,
suppose that $a_1\ldots a_m<b_1\ldots b_n$, and let $t=\min(m,n)$. This
means that either $a_1\ldots a_t = b_1\ldots b_t$ and $m<n$, so that
$b_1\ldots b_n \not <a_1\ldots a_m$, or else $a_1\ldots a_t<b_1\ldots b_t$,
so that $b_1\ldots b_t \not < a_1\ldots a_t$ and hence again 
$b_1\ldots b_n\not < a_1\ldots a_m$. Finally for transitivity, suppose that
$a_1\ldots a_m<b_1\ldots b_n<c_1\ldots c_p$
. Let $t=\min(m,n)$, $r=\min(n,p)$,
$s=\min(m,p)$, and $l=\min(m,n,p)$. Now if 
$a_1\ldots a_l<b_1\ldots b_l<c_1\ldots c_l$
then clearly $a_1\ldots a_m<c_1\ldots c_p$. Otherwise, without loss
of generality we may assume that $a_1\ldots a_l=b_1\ldots b_l$. If $l=t$
then $m<n$ and $m\le p$. Furthermore, either $b_1\ldots b_r<c_1\ldots c_r$
or $b_1\ldots b_r=c_1\ldots c_r$ and $n<p$. In the former case, if 
$r>l$, then since $p>m$ we have $a_1\ldots a_m<c_1\ldots c_p$, whereas if 
$r=l$ then $a_1\ldots a_l<c_1\ldots c_l$. In the latter case, 
$a_1\ldots a_s=c_1\ldots c_s$ and $m<p$, so again 
$a_1\ldots a_m<c_1\ldots c_p$. If $l<t$, then we must have 
$b_1\ldots b_l<c_1\ldots c_l$, whence $a_1\ldots a_l<c_1\ldots c_l$.
Finally, the fact that $R$ is a total order follows trivially from the 
definition of a lexicographic order and noticing
that the strings of symbols are taken from a totally ordered alphabet.
}

\problempart Prove that neither $R$ nor $R^{-1}$ is a well-ordering.

\solution{
Consider the alphabet $\{a,b\}$ with $a\preceq b$. Then $R$ is not
a well ordering since $\{b,ab,aab,aaab,aaaab,\ldots\}$ has no least element.
Moreover, $R^{-1}$ is not a well-ordering since $\{a,aa,aaa,aaaa,\ldots\}$
has no least element. 
%Consider the alphabet 
%$\{\ldots,a_{-2},a_{-1},a_0,a_1,a_2,\ldots\}$, 
%with the ordering 
%$\ldots\preceq a_{-1}\preceq a_0\preceq a_1\preceq\ldots$. 
%Then $R$ is not a well-ordering, since the set of strings, 
%$\{a_{-1},a_{-2},a_{-3},\ldots\}$ does not have a least element.
%Moreover, the set of strings $\{a_0,a_1,a_2,\ldots\}$ 
%does not have a least element under the ordering $R^{-1}$, and
%therefore $R^{-1}$ is not a well-ordering either.
}

\end{problemparts}

%END   Tina's problems


%BEGIN Christos Fall 01

%-----------------------------------------------------------------%
% source   : Fall 99 tutorial? (in problemRepository)
% topic    : equivalence classes
% outcomes : 1
% similar problem as Rosen 6.5.10

\problem
Define $(a,b) \sim (c,d)$ iff $a+d = b+c$.


\problempart  
Prove that $\sim$ is an equivalence relation on
$\integers\cross\integers$.  

\solnospace{
\begin{itemize}
\item 
{\em Reflexivity}. 
$(a,b) \sim (a,b)$ since $a + b = b + a$.
\item 
{\em Symmetry}.
$(a,b) \sim (c,d) \implies (c,d) \sim (a,b)$ 
since $a + d = b + c \implies c + b = d + a$.
\item 
{\em Transitivity}. 
Assume $(a,b) \sim (c,d)$, i.e., $ a + d = b + c$.
And, $(c,d) \sim (e,f)$, i.e., $c + f = d + e$. Adding we get 
$a + d + c + f = b + c + d + e$ or $a + f = b + e$, i.e., 
$(a,b) \sim (e,f)$.  Hence 
$(a,b)\sim(c,d)\wedge(c,d)\sim(e,f)\implies(a,b)\sim(e,f)$. 
\end{itemize}

Since $\sim$ is reflexive, symmetric, and transitive, it is an 
equivalence relation.
}


\problempart  
Partition the set $\set{0,1,2} \cross \set{0,1,2}$ into the
distinct equivalence classes under $\sim$.

\solnospace{
The trick is to rewrite $(a,b) \sim (c,d)$ iff $a+d = b+c$ as
$(a,b) \sim (c,d)$ iff $a-b = c -d$.  This shows that with any
equivalence class ${\cal C}$ we can associate a 
{\em difference~$d\in\ints$} such that 
$(a,b) \in {\cal C} \iff a - b = d$.  This gives us an easy way 
to list the equivalence classes of $\set{0,1,2} \cross \set{0,1,2}$.
\begin{itemize}
\item $d = -2$: $\{(0,2)\}$.
\item $d = -1$: $\{(0,1),(1,2)\}$.
\item $d = 0$:  $\{(0,0),(1,1),(2,2)\}$.
\item $d = 1$:  $\{(1,0),(2,1)\}$.
\item $d = 2$:  $\{(2,0)\}$.
\end{itemize}
}


\problempart 
How many distinct equivalence classes under $\sim$ are there on the
set $\set{0,1,\dots, n} \cross \set{0,1,\dots, n}$? You do not need to
prove your answer. 

\solnospace{
$2n+1$, since the difference can be any value in $\{-n,\ldots, n\}$.
}









%-----------------------------------------------------------------%
% Source   : Karger tutorial 3 Spring 01
% topic    : relation composition using matrices
% outcomes : 1
% editted the problem and solution to try and make it easier to
% understand (Rad)

% Lars Comment on original version (Spring '01):
% Maybe this problem was a bit too hard? I think that the problem of
% proving formally that the matrix representation of S o R is the
% product of M_R and M_S with \land instead of \times and \lor
% instead of + may be better. This makes the students understand
% what the composition is and it also introduces notation like
% \bigvee, which can be defined recursively, and we could make
% them prove something like "\bigvee_{x \in X} x = 1 \iff
% (\exists x \in X) [x = 1]" by induction.                     /Lars
%

\newcommand{\paritycomp}{\diamond} 

\problem 
Suppose that $A$, $B$ and~$C$ are finite sets and that $R$~is
a relation from $A$ to $B$ and $S$~is a relation from $B$ to $C$. 

The \emph{parity composition} of the relations $R$ and~$S$, denoted 
$S\paritycomp R$, is defined as follows:
\begin{align*}
  (a,c) \in S \paritycomp R & \iff \card{\set{b \in B \suchthat (a,b) \in
      R \land (b,c) \in S}} \text{is an odd number}.
\end{align*}
Let $M_R = [r_{ab}]$ be the matrix representing $R$.  \emph{Reminder}: this means
\begin{align*}
    r_{ab} & = \begin{cases}
      1 & \mbox{if $(a,b) \in R$,} \\
      0 & \mbox{otherwise,}
    \end{cases}
\end{align*}
for $a \in A, b \in B$.
Similarly, let $M_S = [s_{bc}]$ be the matrix representing $S$ and $M_{S
\paritycomp R} = [t_{ac}]$ be the matrix representing $M_{S \paritycomp
R}$.

Find a formula for $t_{ac}$ in terms of the $r$'s and $s$'s, and explain
why your formula is correct.

\solnospace{
\[
t_{ac} = \bigoplus_{b \in B} r_{ab} \cdot s_{bc},
\]
where $\bigoplus$ denotes mod 2 sum.

\begin{proof}
By the definition of parity composition,
\begin{displaymath}
      t_{ac} = \begin{cases}
        1 & \mbox{if there are an odd number of~$b \in B$ such that
          $(a,b) \in R$ and $(b,c) \in S$,} \\
        0 & \mbox{otherwise.}
      \end{cases}
\end{displaymath}
Using the matrix representation of $R$ and~$S$, respectively, we
can rewrite this as
\begin{displaymath}
      t_{ac} = \begin{cases}
        1 & \mbox{if there are an odd number of~$b \in B$ such that
          $r_{ab} \cdot s_{bc} = 1$,} \\
        0 & \mbox{otherwise.}
      \end{cases}
\end{displaymath}
Now, this is exactly the same thing as saying that
\begin{displaymath}
      t_{ac} = \bigoplus_{b \in B} r_{ab} \cdot s_{bc},    
\end{displaymath}
by the definition of~$\bigoplus$.
\end{proof}
}

%% Describes how to do count, eaiser than parity so should be before

% \problempart
% Consider the matrix $U_{R,S}=(u_{ac})$, whose $(a,c)$th entry is 
% \[
% u_{ac} \eqdef \card{\set{b\in B \suchthat (a,b)\in R \land (b,c)\in S$.
% \]
% Extending the ideas you have used for
% the first part of this problem, can you find a formula for~$u_{ac}$? 

% \solnospace{
% To calculate $u_{ac}$, we need to count the number of $b$'s in $B$ for
% which $(a,b)\in R$ and $(b,c)\in S$. Thinking as in the first part of
% the problem, we see that this is exactly the number of $b$'s in $B$
% for which $r_{ab}\wedge s_{bc}=1$. So, if we just sum up all
% $(r_{ab}\wedge s_{bc})$'s, we will get exactly this number (because,
% whenever a $(r_{ab}\wedge s_{bc})$ is not~1, it is~0). Hence, we can
% derive the formula of $u_{ac}$ from that of $t_{ac}$, by simply
% replacing the XOR operator with the summation operator:
% $$
% u_{ac} = \sum_{b\in B}  r_{ab}\wedge s_{bc} .
% $$
% Notice that this formula is identical to the one that we would get for
% $u_{ac}$ if $U_{R,S}$ were the ordinary matrix product of $M_R$ and
% $M_S$. Therefore, a more compact way to define $U_{R,S}$ is actually, 
% $$
% U_{R,S} = M_R \times M_S.
% $$
% }





%-----------------------------------------------------------------%
% source   : Velleman 4.6, Exercise 3.
% topic    : equivalence relations
% outcomes : 1
% last used Fall00 Problem Set 3 (in ProblemRepository)

\problem 

Which of the following relations are equivalence relations?  For those
that are equivalence relations, what are the equivalence classes? For
those that are not, give an example of how they fail.

\bparts
\ppart
$R \eqdef \set{(x,y) \in W \times W \suchthat \text{ the words $x$ and
$y$ start with the same letter} }$ where $W$ is the set of all words
in the 2001 edition of the Oxford English dictionary.

\solnospace{
$R$ is an equivalence relation since it is reflexive, symmetric, and
transitive.  The equivalence class of $x$ with respect to $R$ is the
set $[x]_R = $ the set of words $y$, such that $y$ has the same first
letter as $x$. There are 26 equivalence classes, one for each letter
of the English alphabet.
}

\ppart
$S \eqdef \set{(x,y) \in W \times W \suchthat \text{ the words $x$ and $y$
have at least one letter in common} }$.

\solnospace{
$S$ is reflexive and symmetric, but it is not transitive.  Therefore, $S$
is not an equivalence relation.  For example, let $w_1$ be the word
``scream,'' let $w_2$ be the word ``and,'' and let $w_3$ be the word
``shout.''  Then $w_3 S w_1$, and $w_1 S w_2$, but it is \textbf{not} the
case that $w_3 S w_2$.}

\ppart
$R \eqdef \set{(x,y) \in \reals \times \reals \suchthat x-y \in \rationals }$.

\solnospace{
$R$ is reflexive since, for any $x\in R$, $x-x=0$.  $R$ is symmetric
because if $(x-y)$ is rational, then $(y-x)=-(x-y)$ is rational as well.
Finally, $R$ is also transitive.  To see this, consider $(x,y)\in R$ and
$(y,z)\in R$.  We would like to know if $(x,z)$ is also in $R$.  We start
by noting that $(x-y)\in \rationals$ and $(y-z)\in \rationals$ by
definition of our relation $R$.  Now, we can express $(x-z) =
(x-y)+(y-z)$.  Since the sum of any two rational numbers is another
rational number, and we have written $(x-z)$ as such, we have shown that
$(x,z)\in \rationals$.  Therefore, $R$ is transitive.  Since $R$ is also
reflexive and symmetric, $R$ is an equivalence relations on $\reals$.

The equivalence class for x is
\[
[x]_R = \set{x + r \suchthat r \in \rationals}.
\]
}

\ppart
$R \eqdef \set{(x,y) \in \reals \times \reals \suchthat \exists n \in
\integers\; y=10^{n} x}$.

\solnospace{
$R$ is reflexive, since we can set $n=0$.  $R$ is symmetric because if
$y=10^k x$, for some $k\in \integers$, then $x=10^{-k}y$, so if
$(x,y)\in R$, then $(y,x)\in R$.  We can show that $R$ is transitive
as follows: consider pairs $(x,y)\in R$ and $(y,z)\in R$.  So $y=10^nx$
and $z=10^m y$, for $m,n\in \integers$.  Then, substituting, we have
that $z=10^{m}(10^{n} x) = 10^{m+n}x$.  Since $m+n \in \ints$, we conclude
that $(x,z) \in R$.

The equivalence class for x is 
\[
[x]_R = \set{10^{n}x \suchthat n\in \integers}.
\]
There is a distinct equivalence class for every real number in the
intervals $(-10,-1] \union \{0\} \union [1, 10)$.
}

\eparts







%-----------------------------------------------------------------%
% source     : Velleman \S 4.5 exercise 13
% topic      : relations
% outcomes   : 1
% Used first time, revised by ARM 9/11/01

\problem

The Bassethound Bus Company is trying to decide on \emph{one-way} bus
routes to run among the cities
\begin{quotation}\noindent
San Francisco, Chicago, Dallas, New York, and Washington D.C.
\end{quotation}
Bassethound wants to make sure that there is always some way to follow its
routes and get from any of the cities to any other.  We will represent
Bassethound's routes by a binary relation, $B$, on the set, $C$, of cities
above.

\bparts
\ppart Succinctly express the property that Bassethound wants $B$ to have
using relational and set operators on $B$ and $C$.

\solnospace{From every city $c \in C$ there should be a possible
series of bus routes to get to any other city $c' \in C$. This implies that
$\forall (c, c') \in C \cross C, (c,c') \in B^*$ (transitive closure
of B). In other words, $C \cross C \subseteq B^*$.

Note that, since we know that $B^* \subseteq C \cross C$, it
equivalent to require that $C \cross C = B^*$.}

\eparts

However, Bassethound wants to run as few bus routes as possible.  That is,
Bassethound wants the size, $\card{B}$, of $B$ to be as small as possible.

\bparts
\problempart What is the smallest possible value of $\card{B}$?
Explain.

\solnospace{5. We can connect the cities in a ring with one way edges
between them. So for example, $B$ could be the set $\set{(SF,C) ,
(C,D) , (D,NY), (NY,W) , (W, SF)}$.

5 is the minimum number of edges possible because for each city to be
accessible there must be at least one edge entering the city. Hence
$B$ can not have fewer than 5 edges.
}

\problempart
Is the smallest satisfactory $B$ unique?

\solnospace{No, since we could connect the cities in different orders.}

\ppart Unfortunately, Bassethound has a legacy problem.  They already have
a set of routes, $A$, that connect all the cities.  While they can cancel
routes easily, new routes are expensive, and they are reluctant to add
them.  Starting from $A$, can Bassethound arrive at a smallest size $B$
solely by cancelling routes?  Give a counterexample showing that it can't,
or explain how it can.

\solnospace{If $A$ has round trip direct from NY to each other city
(not unusual for these companies to have hubs), no route can be
cancelled and still maintain connectivity. But $A$ has 8 routes, not
the minimum number of 5. In general if a ring does not already exist
in the original $A$ digraph, there is no way to arrive at one.}

\eparts






%-----------------------------------------------------------------%
% Problem Repository, only used two parts (Rad)
% source: spring00 ps3, Velleman 4.3.9 
% topic: relations, compositions, reflexive, symmetric, transitive
% outcome: 1

\problem
Suppose $R$ and $S$ are binary relations on a set $A$.  For each part,
give either proofs or counterexamples to justify your answers.

\bparts

\problempart Suppose $R$ and $S$ are symmetric.  Must $R \intersect S$
be symmetric?  What about $R \union S$?  What about $R^{-1}$?  What
about $R \composition S$?

\solnospace{
$R \intersect S$: \textbf{Yes.} If $(x, y) \in R \intersect S$, we must
prove that $(y, x) \in R \intersect S$.  We have that $xRy$ (in which case
$yRx$ as well) and $xSy$ (in which case $ySx$ as well).  Since $yRx \land
ySx$, we have $(y, x) \in R \intersect S$.

$R \union S$: \textbf{Yes.} Suppose $(x, y) \in R \union S$.  Therefore,
either $xRy$ (in which case $yRx$ and $\therefore (y, x) \in R \union S$)
or $xSy$ (in which case $ySx$ and $\therefore (y, x) \in R \union S$).  So
by cases $(y, x) \in R \union S$.

$R^{-1}$: \textbf{Yes.} Suppose $(x, y) \in R^{-1}$.  By the definition of
inverse, this means that $yRx$.  But since $R$ is symmetric, this means
that $xRy$.  By the definition of inverse again, this means that $(y, x)
\in R^{-1}$.  So $R^{-1}$ is symmetric.

$R \composition S$: \textbf{No.}  Suppose $A = \{a,b,c\}$, $R = \{(b, c),
(c, b)\}$ , and $S = \{(a, b), (b, a)\}$ .  Then $R \composition S = \{(a,
c)\}$, which is not symmetric.

} %end solution

\problempart Suppose $R$ and $S$ are transitive.  Must $R \intersect
S$ be transitive?  What about $R \union S$?  What about $R^{-1}$?
What about $R \composition S$?

\solnospace{
$R \intersect S$: \textbf{Yes.} Suppose there is 
a walk from $x$ to $y$ in $R \intersect S$.  We need to prove $(x,y) \in
R \intersect S$.  In order for there to
be a walk from $x$ to $y$ in $R \intersect S$, there must have been a walk 
from $x$ to $y$ 
in both of $R$ and $S$ (otherwise, those walks would not appear in their 
intersection as walks).  Thus, $xRy$ and $xSy$, so $(x, y) \in R 
\intersect S$ as needed.

$R \union S$: \textbf{No.} Suppose $R = \{(a, b), (b, c), (a, c)\}$ and 
$S = \{(b, c), (c, a), (b, a)\}$.  Then $U = R \union S = \{(a, b), (b, a), 
(b, c), (c, a), (a, c)\}$, so that $cUa$ and $aUb$ but $\neg (cUb)$.

$R^{-1}$: \textbf{Yes.} Suppose $(a, b) \in R^{-1} \land 
(b, c) \in R^{-1}$.  We must prove that $(a, c) \in R^{-1}$.  
We know from the definition of inverse that
$bRa \land cRb$.  Furthermore, since $R$ is transitive, we have that $cRa$.  
By the definition of inverse again we have that $(a, c) \in 
R^{-1}$, as needed.

$R \composition S$: \textbf{No.} Suppose $R = \{(b, a), (b, c), (c, a)\}$ and 
$S = \{(a, b), (a, c), (b, c)\}$.  Then $(b, a) \in R \composition S$ and 
$(a, c) \in R \composition S$ but $(b, c) \notin R \composition S$.  
Transitivity fails for the composition. 

} % end{solution}
\eparts





%-----------------------------------------------------------------%
% From Problem Repository (Rad)
% topic: relations, transitive closures, symmetric relations
% source: Velleman 4.5.10
% outcome: 1

\problem Suppose $R$ is a relation on $A$, and let $S$ be the
transitive closure of $R$.  Prove that if $R$ is symmetric, then so is
$S$.  (Hint: Assume that $R$ is symmetric.  Prove that $R \subseteq
S^{-1}$ and $S^{-1}$ is transitive.  What can you conclude about $S$
and $S^{-1}$?)

\solnospace{
\begin{proof}
Assume that $R$ is symmetric.  We can prove that
$R \subseteq S^{-1}$.  Suppose arbitrary $(a, b) \in R$.  Because R is
symmetric, $(b, a) \in R$ as well.  $R \subseteq S$ by definition of
closure, therefore both $(a, b)$ and $(b, a)$ must be in $S$. However
by definition of inverse, $(b, a)$ and $(a, b)$ are also in $S^{-1}$.
Thus, $R \subseteq S^{-1}$.

We must now prove that $S^{-1}$ is transitive.  Suppose we choose an 
arbitrary three elements $a \in A$, $b \in A$, and $c \in A$ such that
$((a, b) \in S^{-1} \; \land (b, c) \in S^{-1})$.  This means that 
$(b, a) \in S \; \land (c, b) \in S$ by definition of inverse.  But 
since $S$ is transitive this means $(c, a) \in S$.  Thus, by definition
of inverse $(a, c) \in S^{-1}$.  This is the necessary condition to 
satisfy transitivity.  Thus, $S^{-1}$ is transitive.

Since $S$ was the transitive closure of $R$, it is the smallest set
such that $R \subseteq S$ and $S$ is transitive (definition of
transitive closure). Since $R \subseteq S^{-1}$ and $S^{-1}$ is a
transitive, $S^{-1}$ contains the transitive closure $S$ of $R$. So $S
\subseteq S^{-1}$. We also know that $|S| = |S^{-1}|$ by definition of
inverse, so in fact $S = S^{-1}$.  Therefore, since $S$ is the same
set as its inverse, $S$ is symmetric.
\end{proof}
} % end solution







%-----------------------------------------------------------------%
% topic: relations 
% outcome: 1

\problem For any function $f:A \to B$, define a binary relation,
$\relsub{R}{f}$, on $A$ by the condition:
\[
a_1 \relsub{R}{f} a_2 \iff f(a_1) = f(a_2).
\]

\bparts

\ppart Show that $\relsub{R}{f}$ is an equivalence relation.

\solnospace{We first prove $\relsub{R}{f}$ is transitive.
\begin{proof}
Suppose $a_1 \relsub{R}{f}
a_2$ and $a_2 \relsub{R}{f} a_3$.  So $f(a_1) = f(a_2)$ and $f(a_2) =
f(a_3)$.  So $f(a_1) = f(a_3)$ (becuase equality is transitive, a basic
fact we can assume w/o proof).  That is, $a_1 \relsub{R}{f} a_3$.
\end{proof}
The proofs that $\relsub{R}{f}$ is reflexive and symmetric are equally
easy, and we omit them.}

\ppart (*) Show that for \emph{every} equivalence relation, $E$, on $A$,
there is a $B$ and an $f:A\to B$ such that $E = \relsub{R}{f}$.

\solnospace{Let $B$ be the blocks of the partition of $A$ defined by $E$, that
is,
\[
B \eqdef \set{[a]_{E} \suchthat a \in A}.
\]
Define $f:A\to B$ by the rule
\[
f(a) \eqdef [a]_{E}.
\]
So
\begin{eqnarray*}
a_1 \relsub{R}{f} a_2 & \iff & f(a_1) = f(a_2)\\
& \iff & [a_1]_{E} = [a_2]_{E}\\
& \iff & a_1 \,E\, a_2,
\end{eqnarray*}
which means that $\relsub{R}{f} = E$ as required.}
\eparts






%----------------------------------
% source     : pRepository
% topic      : posets
% outcome    : 1


\problem Let $R$ be the lexicographic (dictionary) ordering of strings
of symbols from a totally ordered alphabet as defined in Rosen p. 417.

\problempart Prove that $R$ is a total order.

\solnospace{
If $\alpha$, $\beta$ are strings, let us denote by
$\alpha\sqsubseteq\beta$ the fact that $\alpha$ is a \emph{prefix} of
$\beta$, i.e., that $\alpha\gamma=\beta$, for some $\gamma$.  Let us
also denote by $\alpha\restriction n$ the prefix of $\alpha$ of length
$n$. 

Then, the lexicographic order $R$ is such that 
$$
\alpha R \beta 
\:\iff\:
\alpha\sqsubseteq\beta 
\;\vee \;
\alpha\restriction t \prec \beta\restriction t
$$
where $t$ is the length of the shortest string. That is, $\alpha$ comes
before $\beta$ iff either it is a prefix of $\beta$ or its $t$-prefix
comes \emph{strictly} before the $t$-prefix of $\beta$ (in the
ordering of strings of length $t$, which we know is total). 

We first show that $R$ is a partial order. Reflexivity is obvious, and
antisymmetry is deduced easily: Suppose $\alpha R\beta$ and $\beta
R\alpha$. If any of the strings has its $t$-prefix strictly before the
$t$-prefix of the other string, then the latter one can't be a prefix
of the former; and it certainly cannot have its $t$-prefix strictly
before the $t$-prefix of the former string. Hence, the only
possibility is that both $\alpha \sqsubseteq \beta$ and
$\beta\sqsubseteq\alpha$, which implies $\alpha=\beta$.  

For transitivity, let's assume that $\alpha R\beta$ and 
$\beta R\gamma$, where $\alpha$, $\beta$, $\gamma$ are of 
length $m$, $n$, $l$, respectively, and $t=\min(m,n)$, 
$s=\min(n,l)$,  $r=\min(m,n,l)$. Then: 
\begin{itemize}
\item
If $\beta\sqsubseteq\gamma$, then $r=t$ and:
\begin{itemize}
\item If $\alpha\sqsubseteq\beta$, then $\alpha$ is also a prefix of
$\gamma$.
\item
If $\alpha\restriction t\prec\beta\restriction t$, then 
$\alpha\restriction r\prec\gamma\restriction r$, too.
\end{itemize} 
\item
If $\beta\restriction s\prec\gamma\restriction s$, then:
\begin{itemize}
\item
If $\alpha\sqsubseteq\beta$, then we either have
$\alpha\sqsubseteq\gamma$, or $\alpha\restriction
r\prec\gamma\restriction r$. 
\item
If $\alpha\restriction t\prec\beta\restriction t$, then we can infer
that again $\alpha\restriction r\prec\gamma\restriction r$.
\end{itemize}
\end{itemize}
Therefore, in any case, we have $\alpha R\gamma$; so $R$ is indeed
transitive, which concludes the proof $R$ is a partial order.

To prove that $R$ is total, consider any two $\alpha$, $\beta$ and
note that their $t$-prefixes are comparable (by the fact $\preceq$ over
strings of length $t$ is total). Equality of the prefixes implies one
of the strings is a prefix of the other; and any strict order of the
prefixes implies a similar order for the strings. In any case, the
strings are comparable. Which implies $R$ is total.
}


% OLD PROOF FOR PROBLEM 1
%Let $S$ be the totally ordered alphabet, $\preceq_S$ the total order
%on it, and $\prec_S$ the corresponding ``less than'' relation,
%$$
%a \prec_S b  
%\:\iff\: 
%a\preceq_S \wedge a\neq b,
%$$
%again on $S$. 
%
%In Rosen, $R$ is defined to be the relation that, for every two
%strings $\alpha,\beta\in S^\ast$, 
%$$
%\alpha R \beta  \:\iff\:  
%\alpha=\beta \;\vee\; \alpha\prec\beta,
%$$
%where $\prec$ is the following relation on $S^\ast$ (Rosen, p.~418): if
%$\alpha=a_1a_2\dots a_m$, $\beta=b_1b_2\dots b_n$, and $t=\min(m,n)$,
%then   
%$$
%\alpha\prec\beta
%\iff
%(a_1,a_2,\dots,a_t) \prec_t (b_1,b_2,\dots,b_t)
%\\
%\vee \bigl[
%	(a_1,a_2,\dots,a_t) = (b_1,b_2,\dots,b_t)
%	\wedge
%	m<n
%\bigr],
%$$
%$\prec_t$ being the lexicographic ordering that $\preceq_S$ induces
%onto $S^t$. 
%
%\medskip
%Let us first try to prove that $R$ is a partial order. One can easily
%verify that it is sufficient to show that $\prec$ is both
%assymetric\footnote{A relation $R$ on a set $A$ is assymetric iff, for
%all $x,y\in A$, $xRy\implies y\mbox{$\not\!\!R$}x$. Note that
%\emph{a}symmetry and \emph{anti}symmetry are different properties, in
%general. (See also Rosen Exercises~6.1.10--12.)} and transitive. So,
%we try to prove these two things.
%
%For assymetry, suppose $\alpha\prec\beta$, for arbitrary $\alpha =
%(a_1,a_2,\dots,a_m)$, $\beta  = (b_1,b_2,\dots,b_n)$. Then, setting
%$t=\min(m,n)$, we have either $(a_1,a_2,\dots,a_t) \prec_t
%(b_1,b_2,\dots,b_t)$, or $(a_1,a_2,\dots,a_t) = (b_1,b_2,\dots,b_t)
%\wedge m<n$. In the first case, there is an $i\in\{1,2,\dots,t\}$ such
%that  
%$$
%a_1=b_1,\quad  
%a_2=b_2,\quad  
%\dots,\quad  
%a_{i-1}=b_{i-1},\quad  
%a_i\prec_S b_i.
%$$
%This implies that certainly 
%$(b_1,b_2,\dots,b_t) \not\!\prec_t (a_1,a_2,\dots,a_t)$ and also that
%$(b_1,b_2,\dots,b_t) \neq (a_1,a_2,\dots,a_t)$; so,
%$\beta\not\prec\alpha$. In the second case, $\alpha$ is a proper
%prefix of $\beta$, which again easily implies that
%$\beta\not\prec\alpha$. 
%
%For transitivity, assume $\alpha\prec\beta$ and $\beta\prec\gamma$,
%for any  
%$\alpha = (a_1,a_2,\dots,a_m)$, 
%$\beta  = (b_1,b_2,\dots,b_n)$, and
%$\gamma = (c_1,c_2,\dots,c_l)$. Then, setting 
%$t=\min(m,n)$ and $u=\min(n,l)$, we have 
%$$
%\text{either } 
%(a_1,a_2,\dots,a_t) \prec_t (b_1,b_2,\dots,b_t), 
%\text{ or }
%(a_1,a_2,\dots,a_t) = (b_1,b_2,\dots,b_t)\wedge m<n,
%$$
%and
%$$
%\text{either } 
%(b_1,b_2,\dots,b_u) \prec_u (c_1,c_2,\dots,c_u), 
%\text{ or }
%(b_1,b_2,\dots,b_u) = (c_1,c_2,\dots,c_u)\wedge n<l,
%$$
%and we are left with four cases to examine. We study the most
%interesting one (the rest can be treated in similar ways), i.e., the
%case where both $(a_1,a_2,\dots,a_t) \prec_t (b_1,b_2,\dots,b_t)$, and  
%$(b_1,b_2,\dots,b_u) \prec_u (c_1,c_2,\dots,c_u)$. Then we know there
%exist $i\in\{1,2,\dots,t\}$ and $j\in\{1,2,\dots,u\}$ such that 
%\begin{gather*}
%a_1=b_1,\quad 
%a_2=b_2,\quad  
%\dots,  \quad  
%a_{i-1}=b_{i-1},\quad  
%a_i\prec_S b_i,
%\\
%b_1=c_1,\quad  
%b_2=c_2,\quad  
%\dots,  \quad 
%b_{j-1}=c_{j-1},\quad  
%b_j\prec_S c_j.
%\end{gather*}
%Pick $k=\min(i,j)$. Then, we have 
%$$
%a_1=b_1=c_1,\quad  
%a_2=b_2=c_2,\quad  
%\dots,\quad  
%a_{k-1}=b_{k-1}=c_{k-1},\quad  
%a_k\preceq_S b_k \preceq_S c_k,
%$$
%where, in the last relation, at least one of the inequalities has to
%be strict ($\prec_S$, not $\preceq_S$), since $k$ has to equal at
%least one of $i,j$. Hence, what we really have is a
%$k\in\{1,2,\dots,\min(m,l)\}$ for which (also using the transitivity
%of $\prec_S$)
%$$
%a_1=c_1,\quad  
%a_2=c_2,\quad  
%\dots,\quad  
%a_{k-1}=c_{k-1},\quad  
%a_k\prec_S c_k;
%$$
%but this clearly implies that $\alpha\prec\gamma$.
%
%\medskip
%Finally, to prove that $R$ is total, consider two arbitrary strings
%$\alpha=(a_1,a_2,\dots,a_m)$, $\beta=(b_1,b_2,\dots,b_n)$, and again
%let $t=\min(m,n)$. If $\alpha=\beta$, then certainly $\alpha R\beta$,
%i.e., the strings are indeed comparable. If $\alpha$, $\beta$ are
%distinct, then there are two cases: either $a_i=b_i$ for all
%$i=1,2,\dots,t$, or there exists an $i\in\{1,2,\dots,t\}$ such that
%$a_i\neq b_i$. 
%
%In the first case it has to be $m\neq n$ (otherwise, we would have
%$\alpha=\beta$, which is false, by assumption); hence, either $m<n$,
%in which case $\alpha\prec\beta$, or $n<m$, in which case
%$\beta\prec\alpha$. (Notice our use of the fact that the natural
%ordering $\leq$ on the nonnegative integers is total.) So, $\alpha
%R\beta$ or $\beta R\alpha$, and the strings are comparable.
%
%In the second case, let $i_0$ be the least $i\in\{1,2,\dots,t\}$ for
%which $a_i\neq b_i$. Since the ordering $\preceq_S$ on $S$ is total,
%we know that either $a_{i_0}\prec_S b_{i_0}$ or $b_{i_0}\prec_S
%a_{i_0}$. Hence (also using the minimality of $i_0$), we have either
%$$
%a_1=b_1,\quad
%a_2=b_2,\quad
%\dots,  \quad
%a_{i_0-1}=b_{i_0-1},\quad  
%a_{i_0}\prec_S b_{i_0},
%$$
%in which case $\alpha\prec\beta$, or 
%$$
%b_1=a_1,\quad
%b_2=a_2,\quad
%\dots,  \quad
%b_{i_0-1}=a_{i_0-1},\quad  
%b_{i_0}\prec_S a_{i_0},
%$$
%in which case $\beta\prec\alpha$. So, again $\alpha R\beta$ or $\beta
%R\alpha$, and  the strings are comparable. 
%
%Therefore, in every case, $\alpha$ and $\beta$ are comparable; that
%is, $R$ is total.



\problempart Prove that neither $R$ nor $R^{-1}$ is a well-ordering,
for alphabets with more than one element.

\solnospace{Consider the alphabet $\{a,b\}$ with $a\preceq b$. Then $R$
is not a well ordering since\\ $\{b,ab,aab,aaab,aaaab,\ldots\}$ has no
least element.  Moreover, $R^{-1}$ is not a well-ordering since
$\{a,aa,aaa,aaaa,\ldots\}$ has no least element.

%Consider the alphabet 
%$\{\ldots,a_{-2},a_{-1},a_0,a_1,a_2,\ldots\}$, 
%with the ordering 
%$\ldots\preceq a_{-1}\preceq a_0\preceq a_1\preceq\ldots$. 
%Then $R$ is not a well-ordering, since the set of strings, 
%$\{a_{-1},a_{-2},a_{-3},\ldots\}$ does not have a least element.
%Moreover, the set of strings $\{a_0,a_1,a_2,\ldots\}$ 
%does not have a least element under the ordering $R^{-1}$, and
%therefore $R^{-1}$ is not a well-ordering either.
}



%END Christos Fall 01


\end{problems}

\end{document}


