\problemdata     
{S01-PS4-2}           
{relations, partial order, total order}              
{}              
{S01-PS4} 		
{S01 Karger}


\begin{problem}

\textbf{Partial Orders}

\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\  \mid \ $the word $x$ comes before the word $y$ alphabetically$\}$.\\
c. $A=\reals, R=\{(x,y) \in \reals \times \reals \ \mid \ |x|\leq |y|\}$.\\
d. $A=\reals, R=\{(x,y) \in \reals \times \reals \ \mid \ x \le y-3\}$.\\
e. The relation ``is a parent of'' on people.


\solution{
  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 not reflexive, and thus it is not a partial order on~$A$. \\
  e. The relation ``is a parent of'' is not reflexive, so it is not
     a partial order on people (a person is not a parent of himself).
     Note that this relation is not transitive or antisymmettic either.}

\end{problem}
