\documentclass[11pt,twoside]{article}	
\usepackage{latex-macros/course}
\usepackage{textcomp} % to get \textcent

\newcommand{\iden}[1]{\text{id}_{#1}}

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\renewcommand{\reading}
{\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln3.pdf}
{Week 3 Notes},
Rosen \S6.1, 6.3--6.6 (ignore Warshall's algorithm and lattices).}



%\hidesolutions
%\showsolutions

\begin{document}
\problemset{3}

Note: This problem set contains a number of questions that will
require you to write proofs.  The goal is not only to have correct
proofs, but also to make sure they are clear, orderly, and
well-presented.

%\begin{problem}
%Rosen, Ex 6.1.26 a,b.
%
%\solution{ a) There are two relations on a set with only one element,
%and both of these are transitive.
%
%b) Consider the two-element set $\{0, 1\}$.  There are sixteen
%relations on $\{0,1\}$, and it is easiest to count the non-transitive
%ones.  For any non-transitive relation $R$ there must exist elements
%$a$, $b$, and $c$ in $\{0, 1\}$ such that $R$ contains $(a, b)$ and
%$(b, c)$, but not $(a, c)$.  This implies that $a \neq b$ and $b \neq
%c$. Hence we conclude that any non-transitive relation contains both $(0,
%1)$ and $(1,0)$, but does not contain one of $(0, 0)$, $(1, 1)$.
%There are three such relations, namely
%\begin{itemize}
%  \item $\{(0,1),(1,0)\}$  
%  \item $\{(0,1),(1,0),(1,1)\}$  
%  \item $\{(0,1),(1,0),(0,0)\}$  
%\end{itemize}
%This shows that the number of transitive relations is $16-3$, or thirteen.
%}
%\end{problem}

\begin{problem}
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} \Leftrightarrow 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{
The proofs of the defining properties of an equivalence relation follow.

\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 equivalence classes under $\sim$ 
are there on the set $\{0,1,\ldots, n\} \times \{0,1,\ldots, n\}$. 
Explain.
\solution{
Using the observation from part a), we only need to count the number
of possible differenes.  This is $2n+1$ since the difference can be
any value in $\{-n,\ldots, n\}$.}
\end{problemparts}
\end{problem}

%\begin{problem}
%Rosen, \S6, Supplementary Exercise 10.
%
%\solution{
%Note that any equivalence relation is automatically reflexive; it is also circular,
%since if $a R b$ and $b R c$ hold for an equivalence relation $R$, then $c R b$ and
%$b R a$ hold by symmetry, and hence $c R a$ holds by transitivity.  This proves the
%only if part of the claim.
%
%To prove the converse, let $R$ be a reflexive circular relation.  We first prove
%symmetry.  Given any $a$, $b$ such that $a R b$, we note that $a R a$ holds by
%reflexivity, and then circularity applied to $a R a$ and $a R b$ shows that $b R a$
% holds.Hence $R$ is symmetric.If $a$, $b$, $c$ are elements such that $a R b$ 
% and $b R c$ hold, circularity implies $c R a$ and symmetry then shows $a R c$, so 
% transitivity follows.Since reflexivity was given, we have shown that $R$ is an 
% equivalence relation. 
%}
%\end{problem}

\begin{problem}

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
relation.

\begin{problemparts}

\problempart For the case when $n = 3$, draw the DAG for the relation
  $(\power(A),\subseteq)$ and label two maximal chains and two maximal
  antichains. Give an example of a topological sort of this relation.

  \solution{See Figure~\ref{figure1}. $\{\}, \{1\}, \{2\}, \{3\},
  \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}$ is a topological sort of this
  relation.

  \begin{figure}[ht]
  \begin{center}
  \unitlength=0.5pt
  \input{figures/ps3-1.pic}
  \end{center}
  \caption{DAG for Problem 4c.}
  \label{figure1}
  \end{figure}
  $(\power(A),\subseteq)$.
  }  

\problempart 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.}
  
  \problempart Prove that for any integer~$k$ such that $0 < k < n$, the
  set $\{B | B \subseteq A\ \textrm{and}\ |B| = k\}$ is an antichain in
  $(\power(A),\subseteq)$.
  
  \solution{Let $A_k = \{B | B \subseteq A\ \textrm{and}\ |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}
\end{problem}

\begin{problem}
 Let $R$ be the lexicographic (dictionary) 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{
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 $n \leqslant l$ and hence $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 (because $r=t$ and
$\gamma\restriction r = \beta\restriction r$).
\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. This implies that $R$ is total.
}

\problempart Prove that neither $R$ nor $R^{-1}$ is a well-ordering,
for alphabets with more than one element.  Recall that a well-ordering
on a set $S$ is a total ordering on $S$ such that every non-empty
subset of $S$ has a smallest element.

\solution{ 
Given any alphabet $A$ with at least two elements, consider
two distinct elements $a$, $b$ of $A$.  Without loss of generality, we
may assume that $a\preceq b$. Then $R$ is not a well ordering since
the set $\{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.  
}
\end{problemparts}
\end{problem}

\begin{problem}
Let $R$ be a symmetric relation on a set $A$.  Show that $R^n$ is
symmetric for each positive integer $n$.  Deduce that the reflexive
transitive closure, $R^*$, is symmetric.\footnote{Reminder:
\[
R^* \eqdef \bigcup_{k=0}^{\infty} R^k,
\]
where $R^0$ is defined to be the identity relation, $\iden{A}$, on $A$.}



\hint Use induction.

\solution{ We prove the first claim by induction.  

Base case ($n =
1$): Clearly, $R^1$ is symmetric.  

Induction step: Assuming $R^n$ is symmetric, we are to prove that
$R^{n+1}$ is.  Consider any two elements $a$, $b$ in $A$ such that $a
R^{n+1} b$ holds.  Since $R^{n+1} = R \circ R^n$, we conclude that
there must exist $c$ such that $a R^n c$ and $c R b$ both hold.  Since
$R^n$ is symmetric, $c R^n a$ holds; since $R$ is symmetric, $b R c$
holds.  Since $R^{n+1} = R^n \circ R$, the above implies that $b
R^{n+1} a$.  Hence, $R^{n+1}$ is symmetric, as required.

To prove the second claim, observe that $R^* \eqdef
\bigcup_{k=0}^{\infty} R^k$.  Now, suppose $(a, b) \in R^*$.  Then for
some natural number $n$, $(a, b) \in R^n$.  We observe that $R^n$ is
symmetric, since if $n>0$ this follows from the first part of the
problem, and in the case $n=0$, the identity relation is clearly
symmetric.  Hence, $(b, a) \in R^n$, and so, $(b, a) \in R^*$, proving
the claim.

}
\end{problem}

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

\begin{problemparts}

\problempart Show that $R_f$ is an equivalence relation.

\solution{We first prove $R_f$ is transitive. Suppose $a_1 R_f
a_2$ and $a_2 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)$ (because equality is transitive, a basic
fact we can assume w/o proof).  That is, $a_1 R_f a_3$.

To show that $R_f$ is reflexive, note that for any $a \in A$, $f(a) =
f(a)$, so $a R_f a$.  Symmetry also follows, since if, for some $a, b
\in A$, $a R_f b$, then $f(a) = f(b)$, hence also $f(b) = f(a)$, and
we conclude that $b R_f a$ holds.  
}

\problempart Show that for \emph{every} equivalence relation $E$ on $A$,
there exists a set $B$ and a function $f:A\to B$ such that $E = R_f$.

\solution{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 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 $R_f = E$ as required.}

\end{problemparts}
\end{problem}

\end{document}                            
