\documentclass[11pt,twoside]{article}	
\usepackage{latex-macros/course}

\renewcommand{\reading}{Course Notes 3. Optional: Rosen \S7.1-\S7.4 through Example 7, \S7.5, \S7.6 omitting subsection on Lattices.}

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

%\hidesolutions
%\showsolutions

\begin{document}
\problemset{2}

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

\begin{problem}

%\begin{problemparts}

%\problempart

List all the different binary relations on the set $\set{0,1}$.

\solution{There are altogether 16 binary relations.

\( \begin{array}{ll}
1. &  \emptyset\\
2. &  \{(0,0)\}\\
3. &  \{(0,1)\}\\
4. &  \{(1,0)\}\\
5. &  \{(1,1)\}\\
6. &  \{(0,0),(0,1)\}\\
7. &  \{(0,0),(1,0)\}\\
8. &  \{(0,0),(1,1)\}\\
9. &  \{(0,1),(1,0)\}\\
10. &  \{(0,1),(1,1)\}\\
11. &  \{(1,0),(1,1)\}\\
12. &  \{(0,0),(0,1),(1,0)\}\\
13. &  \{(0,0),(0,1),(1,1)\}\\
14. &  \{(0,0),(1,0),(1,1)\}\\
15. &  \{(0,1),(1,0),(1,1)\}\\
16. &  \{(0,0),(0,1),(1,0),(1,1)\}
\end{array} \)
}

\iffalse

\problempart Which of the relations in part (a) are
reflexive? symmetric? antisymmetric? transitive?

\solution{
We list the relations by number as given in the solution above:\\
\begin{itemize}
\item reflexive: $8, 13, 14, 16$\\
\item symmetric: $1, 2, 5, 8, 9, 12, 15, 16$\\
\item antisymmetric: $1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14$\\
\item transitive: $1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 16$\\
\end{itemize}

\end{problemparts}\fi

\end{problem}


\begin{problem}
Let $R$ be the relation on the set $A=\{2,3,4,5,6,7,8\}$ such that
\[
a\,R\, b \ \ \text{iff} \ \ [a\mbox{ is prime} \land (a\divides b)]
\]
(where $a\divides b$ means that $a$ divides $b$).

\begin{problemparts}

\problempart
List the ordered pairs, write the matrix, and draw the directed graph representing $R$.
\solution{
(2,2) (2,4) (2,6) (2,8) (3,3) (3,6) (5,5) (7,7)

\[
M_R = 
\left( \begin{array}{ccccccc}
        1 & 0 & 1 & 0 & 1 & 0 & 1\\
        0 & 1 & 0 & 0 & 1 & 0 & 0\\
        0 & 0 & 0 & 0 & 0 & 0 & 0\\
        0 & 0 & 0 & 1 & 0 & 0 & 0\\
        0 & 0 & 0 & 0 & 0 & 0 & 0\\
        0 & 0 & 0 & 0 & 0 & 1 & 0\\
        0 & 0 & 0 & 0 & 0 & 0 & 0
       \end{array}
\right)
\]

\begin{figure}[h]
\centerline{\includegraphics[height=2.5in]{figures/digraph-ps2f03.pdf}}
\end{figure}

}

\problempart Which of the following properties does $R$ have: reflexive,
symmetric, antisymmetric, transitive?  Explain.

\solution{$R$ is not reflexive or symmetric.  It is antisymmetric and transitive.}

\end{problemparts}

\end{problem}


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

\begin{problem}
Let $A$ be the set of binary strings with length $k$.  For any two strings
$x, y\in A$, the \emph{Hamming distance}, $H(x,y)$, between $x$ and $y$ is
the number of bit positions where $x$ and $y$ are different.  For example,
\[
H(0000,0100)= 1, \qquad H(0110,1101)= 3.
\]
Let $R$ be the ``Hamming distance $\le 1$'' relation.  That is,
\[
x\, R\, y \quad\text{ iff }\quad  H(x,y) \le 1.
\]
Explain why the graph of $R^*$ is $A \cross A$.

\solution{We prove this by induction on the Hamming distance, $n$, between
binary strings.

Define
\[
P(n) \eqdef \quad \forall x,y\in A\ [H(x,y) = n] \implies xR^*y.
\]

{\em Base case} $n=0$: Suppose $H(x,y)=0$.  Then $x=y$.  Since $R^*$ is by
definition reflexive, we have $xR^*x$ and hence $xR^*y$.  This proves
$P(0)$.

{\em Inductive step}: Suppose $P(n)$ is true for some $n\ge 0$.  Consider
a pair of strings $x, y$ with $H(x,y) = n+1$.  Let $i$ be the leftmost bit
position where $x$ and $y$ differ (by the Least Number Principle).  Let
$z$ be a string which is identical to $x$ except in the $i^{th}$ bit.  So
$H(x,z) = 1$.  Therefore, $(x,z)\in R$, and so $(x,z)\in R^*$ by
definition of $R^*$.

Also, $z$ and $y$ are different exactly at the bit positions where $x$ and
$y$ are different, except for the $i^{th}$ bit, where the bits of $z$ and
$y$ are the same.  Therefore, $H(z,y) =n$.  By the induction hypothesis,
$(z,y)\in R^*$.  So $(x,z),(z,y) \in R^*$, and since $R^*$ is transitive,
$(x,y)\in R^*$ as well.  This proves $P(n+1)$.

Therefore by induction, $P(n)$ is true for all $n$.  It follows that any
pair $(x,y)\in A\times A$ is in $R^*$.  In other words, $A\times
A\subseteq R^*$.  Finally, since $R^*\subseteq A\times A$ by definition of
$R^*$, we conclude $R^* = A \times A$.}
 
%\end{problemparts}

\end{problem}

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

\begin{problem}
Consider the natural numbers partially ordered by divisibility.

\begin{problemparts}

\problempart Show that this partial order has a unique minimal element.

\solution{1 is minimal as there is no other natural number that divides 1.
It is unique because all other numbers are divisible by 1 and therefore
are not minimal.}

\problempart Show that this partial order has a unique maximal element.

\solution{0 is maximal: all natural numbers divide zero.  It is the only
maximal element, because for every positive natural number, $n$, we have
that $n$ is strictly ``smaller'' than $2n$ under divisibility.}


\ppart Prove that this partial order has an infinite chain.

\solution{1 2 4 8 16 \dots is a chain with infinite length.}

\ppart Prove that this partial order has an infinite antichain. \hint The
primes.

\solution{The set of prime numbers is infinite.  Since no prime divides
another, any two primes are incomparable.  So the set of prime numbers is
an antichain.}

\iffalse

\problempart Prove that the length of the longest chain is $\lfloor\log_2 n\rfloor+1$.

\solution{The sequence
$1\preceq_R2\preceq_R4\preceq_R\ldots\preceq_R2^{\lfloor\log_2 n\rfloor}$
is a chain with length $\lfloor\log_2 n\rfloor+1$.  Suppose there is a
longer chain $a_0\preceq_R a_1\preceq_R a_2\preceq_R \ldots\preceq_R
a_m$. Since this chain is longer, $m\geq\lfloor\log_2 n\rfloor+1$. For
$i\in\{1, 2, 3, \ldots, m\}$, let $a_i=p_ia_{i-1}$, where $p_i$ is an
integer greater than 1. Then $a_m=p_1p_2\ldots p_ma_0$. Since each
$p_i\geq2$ and $a_0\geq1$, we have

\begin{eqnarray*}
a_m&=&p_1p_2\ldots p_ma_0\\
&\geq&2^{m}a_0\\
&\geq&2^{m}\\
&\geq&2^{\lfloor\log_2 n\rfloor+1}\\
&>&2^{\log_2 n}\\
&=&n,
\end{eqnarray*}

which is a contradiction since $a_m\leq n $ as $a_m\in A$.
}

\problempart Use Dilworth's Theorem and part (b) to derive a lower bound on
the largest anitchain. Construct an anitchain which is as large as the lower
bound. 

\solution{Part (b) implies there is no chain with length
$\geq\lfloor\log_2 n\rfloor+2$. Therefore, by Dilworth's Theorem, the size
of the largest antichain is at least $\frac{n}{\lfloor\log_2
n\rfloor+2}$. The set $\{\lfloor\frac{n}{2}\rfloor+1,
\lfloor\frac{n}{2}\rfloor+2,\ldots,n\}$ is an antichain with size
$\lceil\frac{n}{2}\rceil$, which is no less than the lower bound.}

\fi

\end{problemparts}

\end{problem}


\begin{problem}

Let $R_1$ and $R_2$ be two equivalence relations on a set, $A$.  Which of
the following relations must also be equivalence relations?  Prove it.

\begin{problemparts}
\problempart

$R_1 \intersect R_2$

\solution{
Let $R \eqdef R_1 \intersect R_2$.  We give two proofs that $R$ is an
equivalence relation using different characterizations of equivalence
relations.

\begin{proof}
We first prove that $R$ is an equivalence relations by showing that $R$ is
reflexive, symmetric, and transitive.

\emph{Reflexive:} $R_i$ is reflexive because it is an equivalence
relation, for $i=1,2$.  So $(a,a) \in R_i$ for $i=1,2$ and all $a \in A$.
So, $(a,a) \in (R_1 \intersect R_2) = R$ for all $a \in A$, that is, $R$
is reflexive.

\emph{Transitive:} Suppose $(a,b), (b,c) \in R$.  Since $R = R_1
\intersect R_2$, we have $(a,b), (b,c) \in R_i$ for $i=1,2$.  But $R_i$ is
an equivalence relation, and so is transitive.  Therefore, $(a,c) \in
R_i$, and so $(a,c) \in R_1\intersect R_2 = R$.  This shows that $R$ is
transitive.

\emph{Symmetric:} The proof that $R$ is symmetric follows the same format.

\end{proof}

\begin{proof}
Since $R_i$ is an equivalence relation for $i=1,2$, there is by
definition a total function, $f_i$, with domain, $A$, such that
\[
aR_i b \quad\text{ iff }\quad f_i(a) = f_i(b).
\]
Define the function, $f$, with domain, $A$, by
\[
f(a) \eqdef (f_1(a),f_2(a)).
\]
Clearly $f$ is total, since $f_i$ is total for $i=1,2$.  Now we have,
\begin{align*}
aRb \quad &  \text{ iff }\quad a(R_1 \intersect R_2)b & \text{def.\ of $R$}\\
    &  \text{ iff }\quad aR_ib\text{ for }i=1,2 & \text{def.\ of $\intersect$}\\
    &  \text{ iff }\quad f_i(a)=f_i(b) \text{ for }i=1,2 & \text{def.\ of $f_i$}\\
    &  \text{ iff }\quad (f_1(a),f_2(a)) = (f_1(b),f_2(b)) & \text{def.\ of $=$ pairs}\\
    &  \text{ iff }\quad f(a) = f(b) & \text{def.\ of $f$}.
\end{align*}
That is
\[
aRb \quad \text{ iff }\quad f(a) = f(b),
\]
which proves that $R$ is the equivalence relation $\equiv_f$.
\end{proof}
}

\problempart
$R_1 \cup R_2$ 

\solution{We give a counterexample showing that $R_1 \cup R_2$ may not be
an equivalence relation.  Let $R_1$ and $R_2$ be the relations on
$\set{1, 2, 3}$ where
\begin{align*}
R_1 \eqdef & \set{(1,1) (2,2) (3,3) (1,2) (2,1)},\\
R_2 \eqdef & \set{(1,1) (2,2) (3,3) (2,3) (3,2)}.
\end{align*}
It's easy to check that $R_1$ and $R_2$ are both equivalence relations.
But $R_1\cup R_2$ is not transitive, because $(1,2),(2,3) \in R_1\cup R_2$
and $(1,3) \notin R_1\cup R_2$.  Therefore $R_1\cup R_2$ is not an
equivalence relation.}

\end{problemparts}

\end{problem}



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

% \begin{problem}
% Show that the transitive closure of the symmetric closure of the
% reflexive closure of a relation $R$ is the smallest equivalence
% relation that contains $R$.

% \solution{
% Let $A$ be the set that $R$ is a relation on.  Let $S$ be the
% transitive closure of the symmetric closure of the reflexive closure
% of a relation $R$.  We need to prove that $S$ is an equivalence
% relation, and then we need to prove that any equivalence relation that
% contains $R$ also contains $S$ and is therefore bigger than $S$.

% To prove $S$ is an equivalence relation, we need to prove it is
% reflexive, symmetric, and transitive.  

% Reflexivity is easy.  Note
% that we got $S$ by performing 3 ``closure'' operations on $R$, each of
% which adds (but does not remove) some pairs to the relation.  The
% first, reflexive closure added all pairs $(a,a)$ for $a \in A$, and
% neither of the symmetric or transitive closure operations remove these
% pairs.  So $S$ has them all, and is reflexive.  

% Now let $T$ be the symmetric closure of the reflexive closure.
% Clearly $T$ is reflexive and symmetric, and $S$ is the transitive
% closure of $T$.  We use this to prove $S$ is symmetric.  Suppose
% $(a,b) \in S$.  Then by the definition of transitive closure of $T$,
% there's a path $(a=x_0,x_1,x_2,\ldots,x_n,b=x_{n+1})$ such that each
% $(x_i,x_{i+1}) \in T$.  It follows from the symmetry of $T$ that each
% $(x_{i+1},x_i) \in T$, which implies (since $S$ is a transitive
% closure) that $(x_{n+1},x_0)=(b,a) \in S$.  So $S$ is symmetric.

% Transitivity is also easy---since $S$ is a transitive closure, it is
% transitive. 

% Now we have to prove that any equivalence relation containing $R$ also
% contains $S$.  Suppose we have an equivalence relation $P \supseteq
% R$.  It follows that the reflexive closure of $P$ contains the
% reflexive closure of $R$.  but since $P$ is reflexive, its reflexive
% closure is $P$---that is, $P$ contains the reflexive closure of $R$.
% It follows that the symmetric closure of $P$ contains the symmetric
% closure of the reflexive closure of $R$, namely $T$.  But again, since
% $P$ is an equivalence relation, its symmetric closure is $P$, meaning
% $P \supseteq T$.  For similar reasons, $P \supseteq S$, as claimed.
% }

% \end{problem}



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

% \begin{problem}
% Prove that for any relations $Q,R$ and $S$
% \[ Q\circ (R^c \circ S)^c \subseteq ((Q\circ R)^c\circ S)^c, \]

% where $R^c$ is the complement of relation $R$.

% \solution{We want to prove that for any $(a,d)$, if 
% $(a,d)\in Q\circ (R^c\circ S)^c$ then 
% $(a,d)\in ((Q\circ R)^c\circ S)^c$.
% Assume for contradiction this is not true, 
% i.e., for some $(a,d)$ we have
% $(a,d)\in Q\circ (R^c\circ S)^c$ and
% $(a,d)\in ((Q\circ R)^c\circ S)$.
% From the definition of composition we know there exist
% $b$ and $c$ such that 
% $(a,b)\in (R^c\circ S)^c$, $(b,d)\in Q$,
% $(a,c)\in S$ and  $(c,d)\in (Q\circ R)^c$.

% We claim that $(c,b)\in R$. The proof is again 
% for contradiction: assume $(c,b)\in R$ is false.
% We have $(c,b)\in R^c$ and we know that $(a,c)\in S$.
% From the definition of composition we get 
% $(a,b)\in R^c\circ S$, which contradicts 
% $(a,b)\in (R^c\circ S)^c$.

% So, $(c,b)\in R$ and since we know that 
% $(b,d)\in Q$, we also have $(c,d)\in Q\circ R$.
% This is a contradiction because 
% $(c,d)\in (Q\circ R)^c$.
% }
% \end{problem}


\end{document}                            
