CMSC 250 Fall 2004 -- Homework 16

Due Never at the beginning of your discussion section.

You must write the solutions to the problems single-sided on your own lined paper, with all sheets stapled together, and with all answers written in sequential order or you will lose points.

1. Let $R_1$ and $R_2$ be the relation on $\{0,1,2,3\}$ defined as follows. Draw the directed graphs for $R_1$ and $R_2$ and indicate which relations are antisymmetric.
   1. $R_1 = \{(0,1),(1,2),(1,3),(2,3),(3,1)\}$

   2. $R_2 = \{(0,0)(0,1),(3,2),(2,1),(3,0),(3,3)\}$

2. Let $A=\{a,b,c,d,e,f,g\}$. Let $R$ be a binary relation on $A$ with the following pairs related: $aRb$, $dRe$, $eRf$, $gRe$. Write the following sets using ordered pair notation.
   1. $R$

   2. The reflexive closure of $R$.

   3. The symmetric closure of $R$.

   4. The transitive closure of $R$.

3. Redo number 3 representing each relation as a matrix.

4. Redo number 3 representing each relation as a directed graph.

5. Let $R$ be a relation defined by

   1	0	0	0	1	0
   0	1	1	0	0	1
   1	1	1	0	0	1
   1	0	1	1	1	0
   0	0	0	0	1	1
   0	1	1	1	0	0

   Write the matrices representing the reflexive and symmetric closures of $R$. Is $R$ asymmetric? Is $R$ antisymmetric? Is $R$ reflexive? Is $R$ irreflexive? Give reasons for your answers.

6. Let $A=\{1,2,3,4\}$. Let $R$ be a binary relation defined on $A$ defined by: $a_{1}Ra_{2}$ if $a_{1} \leq a_{2}$. Write the the relation using ordered pair notation, and show that the relation is antisymmetric.

7. Using the subset inclusion partial order relation, give an example of two elements that are not comparable.

8. Define a relation R on the set of all integers as follows: $\forall x,y \in Z,$

   $xRy\leftrightarrow x+y$ is even.

   Is R a partial order relation? Prove or give counterexample.

9. Let $A=\{1,2,3,4,5,6\}$. Let $R$ be the partial order relation defined by inclusion of subsets of $A$. Write a chain $C$ of maximal length contained in $R$.

10. Let $R$ be a partial order relation on $A=\{a,b,c,d,e,f\}$ given by:

    $R=\{(a,a), (b,b), (c,c), (d,d), (e,e), (f,f), \\ (a,b), (a,c), (a,d), (a,e), (a,f), (b,c), (b,d), \\ (b,e), (b,f), (d,f), (e,f)\}$

    Draw the Hasse diagram for $R$.

11. In the following, the relation $R$ is an equivalent relation on the set $A$. Find the distinct equivalence classes of $R$.
    1. $X=\{-1,0,1\}$ and $A=P(X)$. $R$ is defined on $P(X)$ as follows: For all sets ${\sl s}$ and ${\sl t}$ in $P(X)$,
       
       $${\sl s}\ R\ {\sl t}\Leftrightarrow \mbox{the sum of the elements in ${\sl s}$\ equals the sum of the elements in ${\sl t}$}$$
       
       

    2. $A$ is the set of all strings of length 2 in 0's, 1's, and 2's. $R$ is defined on $A$ as follows: For all strings $s$ and $t$ in $A$,
       
       $$s\ R\ t \Leftrightarrow \mbox{the sum of the characters in $s$\ equals the sum of the characters in $t$}$$
       
       

12. Let $P$ be the set of all points in the Cartesian plane except the origin. $R$ is the relation defined as follows: For all $p_1$ and $p_2$ in $P$,
    
    $$p_1\ R\ p_2 \Leftrightarrow \mbox{$p_1$\ and $p_2$\ lie on the same half-line emanating from the origin.}$$
    
    
    Proof that the relation is and equivalence relation, and describe the distinct equivalence classes.
13. Let $R$ be a binary relation on a set $A$ and suppose $R$ is symmetric and transitive. Prove the following: If for every $x$ in $A$ there is a $y$ in $A$ such that $x\ R\ y$, then $R$ is an equivalence relation.
14. For each of the following either prove that it is a partial order relation or indicate why it is not a partial order relation.
    1. Define a relation $R$ on the set ${\bf Z}$ of all integers as follows: For all $m,n \in {\bf Z}$,
       
       $$m\ R\ n \Leftrightarrow \mbox{every prime factor of $m$\ is a prime factor of $n$}$$
       
       

    2. Define a relation $R$ on the set ${\bf R}$ of all real numbers as follows: For all $x,y \in {\bf R}$,
       
       $$x\ R\ y \Leftrightarrow x^2 \leq y^2$$
       
       

15. Let $A = \{a,b,c,d\}$, and let $R$ be the relation
    
    $$R = \{(a,a),(b,b),(c,c),(d,d),(c,b),(a,d),(b,a),(b,d),(c,d),(c,a)\}$$
    
    
    Is $R$ a total order on $A$? justify your answer.

Web Accessibility