\documentclass[12pt]{article}   
\usepackage{latex-macros/course}% !! Use the macros

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip
                                % query 

\renewcommand{\reading}{Week 4 Notes.}

\begin{document}
\problemset{3}                  % !! Start the problem set with its number


\begin{problem}  %part(a) from F03, PS2

\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} \)
}


\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}

\end{problem}

% S02 PS3, S01 ps4
% source Problem Repository
% last used, Karger spring 00
% added some parts, RAD

\begin{problem} 
We partially order the $\power(\set{1,2,\dots,n})$ by the subset relation, $\subseteq)$.

\begin{problemparts}
 \problempart Describe a maximum length chain in $\power(\set{1,2,\dots,n})$.
  
  \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  Describe a maximum length antichain.

  \solution{

%Old version:
%\begin{quote}

%  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)$.

%\end{quote}

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

    If $n$ is even, let $n = 2k$. If $n$ is odd, let $n = 2k+1$. 
    The maximum length antichain is the set of all subsets containing exactly $k$ elements or
    the set of all subsets containing exactly $n-k$ elements. A proof for this part is not required. 


}

  \problempart Describe a topological sort of $\power(\set{1,2,\dots,n})$,
  with a brief justification that your sort is correct.

  \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}
Note that not all chains and antichains are labelled.  A chain is any group that is connected in some manner with arrows.  Antichains are groups of elements where no two members are connected.}  

\end{problemparts}
\end{problem}

\iffalse

\begin{problem}
Remember that a partial function, $g$, is an injection iff
\[
g(a_1) = g(a_2) \qimplies a_1 = a_2
\]
for all $a_1,a_2$ in the domain of definition of $g$.

Prove that a relation, $R$, on a set, $A$, is a \emph{weak} partial order
providing there is an \emph{injection}, $g$, from $A$ to a collection of
sets such that
\begin{equation}\label{wk-eqn}
a_1\,R\, a_2 \qiff g(a_1) \subseteq g(a_2)
\end{equation}
for all $a_1, a_2 \in A$.

Also, give an example showing that this result would not hold if the
condition that $g$ is an injection was dropped.

(From Week 4 Notes, Problem 2(b-c).) %weak po iff \subseteq
\end{problem}
\fi


\begin{problem}\label{monotone-comp}
\bparts

\ppart\label{sb} Let $R,R'$ be binary relations from $B$ to $C$, and $S',S$ be a
relations from $A$ to $B$.  Prove that if $R \subseteq R'$ and $S
\subseteq S'$, then
\[
R \composition S \subseteq  R' \composition  S'.
\]

\solution{
 We prove this by showing $(a,b) \in R \composition S \implies (a,b) \in R' \composition S'$ for arbitrary $a,b$.
 Given $(a,b) \in R \composition S$, by definition of composition, $\exists c [aSc \And cRb]$. Because $R \subseteq R'$ and $S
 \subseteq S'$, we know $a{S'}c \And c{R'}b$. By definition of composition, $a(R' \composition S')b$, thus 
 $(a,b) \in R' \composition S'$.
}

\ppart Prove that if $R$ is symmetric, then so is $R^*$. \hint
Part~(\ref{sb}) is useful here.

\solution{
  To show $R^*$ is symmetric, we show if an arbitrary element $(a,b) \in R^*$, then $(b,a) \in R^*$.
  Given $(a,b) \in R^*$, because $R^* = R^0 \union R^1 \union R^2 \union \ldots$,
  we know for some natural number $i$, $(a,b) \in R^i$. We show $(b,a) \in R^i$ by showing $R^i$ is symmetric
  for arbitrary $i$.

  \begin{claim}
  If $R^1$ is symmetric, then $R^i$ is symmetric for all natural numbers $i$.
  \end{claim}
  
  \begin{proof}
  We prove this by induction on $i$. Let $P(n)$ be ``$R^n$ is symmetric.'' For the base case, we know $P(0)$ and $P(1)$ are true.
  To show $P(n) \implies P(n+1)$, take an arbitrary element, $(a,b) \in R^{n+1}$. Given $R^{n+1} = R^n \composition R^1$,
  we know there exists some $c$ such that $a(R^1)c$ and and $c(R^n)b$. Because $R^1$ and $R^n$ are symmetric, we know 
  $c(R^1)a$ and and $b(R^n)c$. Thus, $\exists c [b(R^n)c \And c(R^1)a]$. By definition of composition, $b(R^{n+1})a$, thus
  $(b,a) \in R^{n+1}$. Therefore, $R^{n+1}$ is symmetric. This concludes our inductive proof.
  \end{proof}

}


\eparts

\end{problem}


%F03, PS2

\begin{problem}

Let $R$ and $S$ be relations on a set, $A$ and consider
\begin{itemize}

\item $R^{-1}$

\solution{

  $R^{-1}$ is transitive. Take arbitrary $a,b,c$ such  that $(a, b), (b,c) \in R^{-1}$. It holds that $(b,a), (c,b) \in R$.
  Because $R$ is transitive, $(c,a) \in R$. By definition of inverse, $(a,c) \in R^{-1}$. Therefore, $R^{-1}$ is transitive. 

}

\item $R \intersect S$

\solution{
Let $R' \eqdef R \intersect S$. $R'$ is transitive.

Suppose $(a,b), (b,c) \in R \intersect S$. Thus, we have $(a,b), (b,c) \in R \And (a,b), (b,c) \in S$.
Because $R$ and $S$ are transitive, we have $(a,c) \in R \And (a,c) \in S$.
Therefore, we have $(a,c) \in R \intersect S$. This satisfies the definition of transitivity.


%Alternative 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 \intersect S)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}
}

\item $R \union S$ 

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

}

\item $R \composition S$
\solution{
  We give a counterexample showing that $R \composition S$ is not transitive.
  Let $R$ and $S$ be relations on the set $\set{1,2,3,4,5}$ where
  \begin{align*}
    S \eqdef & \set{(1,4) (2,5)},\\
    R \eqdef & \set{(4,2) (5,3)}.
  \end{align*}
 
  We see $R$ and $S$ are transitive. Also, $(1,2),(2,3) \in R \composition S$, but $(1,3) \notin R \composition S$. Therefore
  $R \composition S$ is not transitive.

}

\end{itemize}

Suppose $R$ and $S$ are transitive.  Indicate which of the relations above
will \emph{not} be transitive, and give counterexamples for demonstrating this.

\end{problem}


%S01 tut4

% from repository: S00 PS3.2(b)

\begin{problem}
% topic: relations, building posets out of transitive closure of a reflexive, 
%        antisymmetric relation
% source: Velleman 4.5.12
\begin{falsethm}

Suppose $R$ is a reflexive, antisymmetric relation on $A$.  Then $R^*$ is
a partial order on $A$.

\end{falsethm}

\begin{falseproof}

$R$ is already reflexive and antisymmetric.  To form the relation $R^*$ we
add more ordered pairs to make it transitive as well.  Thus, $R^*$ is
reflexive, antisymmetric, and transitive, so it is a partial order.

\end{falseproof}

Identify precisely where the error is in this proof.

\solution{

\textbf{The theorem does not hold.}
Suppose we have the relation 

\begin{eqnarray*}
R = \{(a, a), (b, b), (c, c), (a, b), (b, c), (c, a)\}.  
\end{eqnarray*}

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{problem}


\begin{problem}
Prove that if $R$ is a relation on a finite set, $A$, then
\[
R^* = (R \union I_A)^{\card{A}}.
\]

(Week 4 Notes, Problem 6.)

\solution{

First, we show that $R^* \subseteq (R \union I_A)^{\card{A}}$.

Recall that $aR^*b$ implies that there is a path from $a$ to $b$
in the graph representation of $R$. Also, we know that that path
has length at most $\card{A}-1$ by Corollary 7.6 from the week
4 reading. Say the length of the path is $i$. Therefore, we know 
that there exists a path from $a$ to $b$ in the graph representation
of $(R \union I_A)$ of length $i$ because every path in $R$ is also
in $(R \union I_A)$. Since $I_A$ is also in graph $(R \union I_A)$,
we know that there is a path of length 1 from $b$ to $b$, therefore
there is a path of length $\card{A} - i$ from $b$ to $b$ (just
take the self loop over and over again). Therefore, there is a path
of length $\card{A}$ in graph $(R \union I_A)$ and we have shown 
$R^* \subseteq (R \union I_A)^{\card{A}}$.

Next we show that $(R \union I_A)^{\card{A}} \subseteq R^*$.
$a(R \union I_A)^{\card{A}}b)$ implies that there is a path from
$a$ to $b$ in the graph of $(R \union I_A)$ of length exactly 
$\card{A}$. Remove all of the self looping portions of the path,
i.e. the legs of the path that are from vertex $c$ to vertex $c$
for some $c$, and you are left with a path such that every leg
must have come from the graph of $R$ ($I_A$ only adds in self looping
edges). Therefore, we know there exists a path from $a$ to $b$ in
$R$ and that $aR^*b$, so we conclude that:  $(R \union I_A)^{\card{A}} \subseteq R^*$.

Therefore, $R^* = (R \union I_A)^{\card{A}}$.

ALTERNATIVE SOLUTION:
Note that this solution is fairly detailed and probably
overkill.
\begin{lemma}\label{lem:1} $A^n \subseteq (A \union B)^{n}$ for all $n$.
\end{lemma}
\begin{proof}
Proof is by induction. Let P(n) be the proposition that $A^n \subseteq (A \union B)^{n}$.

\textbf{Base Case(s):} P(0): $A^0=I_A=(A \union B)^0$.

P(1): $A \subseteq (A \union B)$ by definition of union.

\textbf{Inductive Step:} P(n+1): We know $A^n \subseteq (A \union B)^n$ by
the inductive hypothesis, and that $A \subseteq (A \union B)$ from the
base case. By problem 3a of this problem set, we know that: 
$$A^{n+1} = A^n \compose A \subseteq (A \union B)^n \compose (A \union B) = (A \union B)^{n+1}$$
Thus, by Induction we know that $A^n \subseteq (A \union B)^{n}$ for all $n$.
\end{proof}

Step 1: Show that $R^* \subseteq (R \union I_A)^{\card{A}}$.

From Corollary 7.6 of the Week 4 reading (page 22) we know that $$R^* = \lgunion_{k=0}^{\card{A}-1} R^k$$
Claim: $R^i \subseteq (R \union I_A)^{\card {A}}$ for all $0 \leq i \leq \card{A}$.
\begin{proof}
$R^i \subseteq (R \union I_A)^i$ by Lemma~\ref{lem:1}, and $I_A \subseteq (R \union I_A)^{\card{A} - i}$ also by
Lemma~\ref{lem:1}. Therefore, by problem 3a, 
$$R^i \compose I_A = R^i \subseteq (R \union I_A)^i \compose (R \union I_A)^{\card{A} -i} = (R \union I_A)^{\card{A}}$$
\end{proof}
Therefore, we conclude that $R^* \subseteq (R \union I_A)^{\card{A}}$ by the definition of union and subset.

Step 2: Show that $(R \union I_A)^{\card{A}} \subseteq R^*$.
\begin{lemma}\label{lem:2} $R^* = R^* \compose R^*$. 
\end{lemma}
\begin{proof}
Clearly, $R^* \subseteq (R^* \compose I_A) \subseteq (R^* \compose R^*)$. 
Now to show the other direction. $a(R^* \compose R^*)b$ implies
$\exists c (aR^*c \land cR^*b)$. By transitivity
of $R^*$ we conclude that $aR^*b$, and therefore that
$(R^* \compose R^*) \subseteq R^*$ and finally that $R^* = R^* \compose R^*$.
\end{proof}
We now continue our proof and proceed by induction.
Let P(n) be the proposition that $(R \union I_A)^n \subseteq R^*$

\textbf{Base Case:} P(1): $(R \union I_A) \subseteq R^*$ By definition.

\textbf{Inductive Step:} P(n+1): We know by inductive hypothesis 
that $(R \union I_A)^n \subseteq R^*$ and by the base case that 
$(R \union I_A) \subseteq R^*$. Therefore by problem 3a we know:
$(R \union I_A)^n \compose (R \union I_A) = (R \union I_A)^{n+1} \subseteq R^* \compose R^* = R^*$.
Thus, by induction, we see that $(R \union I_A)^{\card{A}} \subseteq R^*$.

Step 3: By Step 1 and Step 2, we conclude that $R^* = (R \union I_A)^{\card{A}}$.
}
\end{problem}

\iffalse

\begin{problem}
For any binary relation, $R$, on a set, $A$, The transitive closure of the
reflexive closure of the symmetric closure, $R^{\equiv}$ of $R$ is 
\[
R^{\equiv} \eqdef (R \union R^{-1} \union I_A)*.
\]

\bparts
\ppart Prove that $R \subseteq R^{\equiv}$.
\ppart Prove that $R^{\equiv}$ is an equivalence relation.
\ppart Prove if $S$ is an equivalence relation and $R \subseteq S$, then
$R^{\equiv}\subseteq S$.  That is, $R^{\equiv}$ is the smallest
equivalence relation containoing $R$.
\eparts
\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}
\fi

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

\begin{problemparts}

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

\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.}

\problempart\label{fl} Now restrict the domain to the natural numbers $\le n$. Prove
that the length of the longest chain is $\floor{\log_2 n}+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 Lemma and part~(\ref{fl}) to derive a lower
bound on the largest anitchain. Construct an antichain which is as large
as the lower bound.

% Conclude something about $\card{\set{\text{primes} \le n}}$?

\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.}


\end{problemparts}

\end{problem}

\iffalse

% topic: relations, compositions, reflexive, symmetric, transitive
% source: Velleman 4.3.9

%% \problemdata
%% {Velleman}
%% {relations}
%% {S00 ps3}

\begin{problem} 
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$?

\solution{
$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$.

$R \union S$: \textbf{Yes.} Their intersection contained $(a, a) \forall a \in
A$, so their union does too.

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

$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.
}

\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$?

\solution{
$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 = \naturals$, 
$R = \{(b, c), (c, b)\}$ 
, and 
$S = \{(a, b), (b, a)\}$
.  Then $R \composition S = \{(a, c)\}$, which is not symmetric.
}

\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$?

\solution{

$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. 
}

\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$?

\solution{

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

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

$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{problemparts}
\end{problem}
\fi

\end{document}












