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

\renewcommand{\reading}{ \href{
http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln3.pdf}
{Week 3 Notes}, Rosen \S 6.1, 6.3-6 (ignore Warshall's algorithm and
lattices).}
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

%\hidesolutions		
%\showsolutions

\begin{document}
\problemset{3}		


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

% Point distribution, 10 points each
% 1 (2,3,5) 2 (5,5) 3 (2 2 3 3) 4 (3 4 3) 5 (3 3 4) 6 (3 3 4)

\textit{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 have clear, orderly, and well presented proofs.

% source: problem Repository
% source: Velleman \S 4.6, Exercise 5.
% topics: equivalence relation, simple

\begin{problem} 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.  Note: triangles $A$ and $B$ are
similar if all three angles of $A$ are equal to the angles of $B$.

%% (NOTE: Maybe replace with Rosen 6.5.32)

\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 angles.
$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 angles 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 angles, and
triangles $t$ and $r$ also have three pairs of equal-degree angles.
$s$ and $r$ must share these three pairs of equal-degree angles
since triangles only have three angles. $\qed$.
}
\end{problem}

% source: Problem repository,
% topics: relational properties
% last used: ?

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

\textbf{Claim 1:} Every symmetric, weakly transitive relation is transitive.

\textbf{Claim 2:} Every reflexive, symmetric, weakly transitive relation
is an equivalence relation.

One of the claims above is true, and one is false. Which is which? Prove it.

\solution{

Claim 1 is false. 

Here is a simple counterexample. Let $A = \{1,2,3,4\}$ $R = \{(1,2) (1,4)
(2,1) (2,3) (3,2) (3,4) (4,1) (4,3)\}$. $R$ is weakly transitive but not transitive ---
$(1,2)$ and $(2,3)$ are in $R$ but $(1,3)$ is not in $R$.

Claim 2 is true.

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

% source: problem Repository, 
% RAD but editted to add new last part (rosen 6.1.36)
% source: spring00 ps3, Velleman 4.3.9 
% topic: relations, compositions, properties

\begin{problem} Suppose $R$ and $S$ are binary relations on a set $A$, and
that both $R$ and $S$ are symmetric. Must each of the following new
relations be symmetric? For each part, justify your answer with a
brief argument if the new relation is symmetric and a counterexample
if it is not.

\begin{problemparts}
\problempart $R^{-1}$

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

\problempart $R \intersect S$

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

% \problempart $R \union S$ 

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

\problempart $R \composition S$

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

\problempart $R \composition R$

\solution{\textbf{Yes.} $R^2$ is symmetric.  For every ordered pair
$(a,b)$ that is a member of $R$, $(b,a)$ must also be in $R$.  Then in
the composition, $R^2$, $(a,a)$ is certainly symmetric.  What about
the case where $(a,b)$ is in $R$, and so is $(b,c)$?  $(a,c)$ will be
in $R^2$, but so will $(c,a)$ since $(c,b)$ and $(b,a)$ are both in
$R$ because of symmetry. In fact, $R^n$ is symmetric if $R$ is
symmetric.}

% \problempart $R^n$, where $n$ is a positive integer greater than
% 0. ??? TOO HARD/LONG ??
% \solution{It is symmetric, add proof - use induction?rosen 6.1.36,
% solution should be in instructor's manual}

\end{problemparts}
\end{problem}

% source Problem Repository
% last used, Karger spring 00
% added some parts, RAD

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

  \problempart Draw a DAG for the relation $(\power(A),\subseteq)$ if
  $A = \{1,2,3\}$ and indicate which are the chains and
  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{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.}  


%   \problempart Prove that, if $A$ is finite then every non-empty
%   subset of $P(S)$ has a \textit{minimal element} (as defined in Rosen
%   ?, or include definition).

%   \solution{FIX, let $T$ be a non-empty subset of $\power(A)$, then we
%   can order the elements of $T$ by cardinality. Size of a set is a
%   natural number which and any of the sets with the smallest size will
%   be the set with then can order the elements }

\end{problemparts}
\end{problem}

% source Vellemen 4.4.6
% not used before

\begin{problem} Let $B$ be the set of integers greater than 1, and let $R$ be
the divisibility relation on the set $B$ (which means that $aRb$ iff
$ak=b$ for some natural number $k$).

\begin{problemparts}
\problempart Does the poset $(B,R)$ have any minimal elements? If so
what are they?

\solution{Yes, all prime numbers are minimal elements of the poset $(B,R)$ since no numbers divide them. Prime numbers divide all other numbers in their chains and can thus be considered the ``head'' of the chain.  }

\problempart Does poset $(B,R)$ have a smallest element? If so, what
is it?  

\solution{There is no unique minimal element or ``smallest'' element.  Intuitively, since there are separate chains each with its own minimal element (``head''), there is no ``smallest'' element. For example, consider the numbers 2 and 3.  2 divides all multiples of 2 and 3 divides all multiples of 3, thus 2 and 3 are the heads of their respective chains.  But 2 and 3 are incomparable, so there is no least element. }

\problempart Does poset $(B,R)$ have a maximal element?  \solution{No,
for any $n$, we can create a larger number, namely $2n$, so the poset
$(B,R)$ does not have a maximal element.  Note that a maximal element here is a number which is divisible by all the numbers in the chain (and can thus be considered as the ``tail'' of the chain).  Since we can always make a larger number in the chain, no such maximal element exists.  

}

\problempart Let $C$ be the natural numbers (includes zero). What are
the maximal and minimal element of the poset $(C,R)$.  

\solution{Now $C$ is the natural numbers, which include 0 and 1.  Thus for $C$, the minimal element is 1 since 1 divides all natural numbers.  The maximal element is 0 since no numbers divide 0.}

\end{problemparts}
\end{problem}

% source: Rosen 6.supplementary.14 (Erdos number)

\begin{problem} (Rosen \S 6, Supplementary Exercise 14) Let $R$ be the
relation on the set of all mathematicians that contains the ordered
pair (a,b) if and only if $a$ and $b$ have written a paper together

\begin{problemparts}
\problempart Describe the relation $R^2$.

\solution{Two mathematicians are related under $R^2$ if and only if
each has written a joint paper with some mathematician $c$.}

\problempart Describe the relation $R^*$.

\solution{Two mathematicians are related under $R^*$ if there is a
finite sequence of mathematicians $a=c_0, c_1, c_2,..., c_{m-1},
c_m=b$, with $m \geq 1$, such that for each $i$ from 1 to $m$,
mathematician $c_i$ has written a joint paper with mathematician
$c_{i-1}$.}

\problempart The \textit{Erd\H{o}s number} of a mathematician is 1 if
this mathematician wrote a paper with the prolific Hungarian
mathematician Paul Erd\H{o}s, it is 2 if this mathematician did not
write a joint paper with Erd\H{o}s but wrote a joint paper with
someone who wrote a joint paper with Erd\H{o}s, and so on (except that
the Erd\H{o}s number of Erd\H{o}s himself is 0). Give a definition of
the Erd\H{o}s number in terms of paths in $R$.

\solution{The Erd\H{o}s number of $a$ is the length of a shortest path
in $R$ from $a$ to Erd\H{o}s, if such a path exists.  (Some
mathematicians have no Erd\H{o}s number).}

\end{problemparts}
\end{problem}

\end{document}                            
