CMSC 250 Fall 2004 -- Homework 16 Answer

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. 1. $R_1$ is not antisymmetric

      

   2. $R_2$ is antisymmetric

      

2. 1. R $= \{(a,b), (d,e), (e,f), (g,e)\}$.

   2. The reflexive closure of R: $\{(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(g,g)\}\cup R.$

   3. The symmetric closure of R: $\{(b,a), (e,d), (f,e), (e,g)\}\cup R$.

   4. The transitive closure of R: $\{(d,f),(g,f) \}\cup R$.

3. 1. 0	1	0	0	0	0	0
      0	0	0	0	0	0	0
      0	0	0	0	0	0	0
      0	0	0	0	1	0	0
      0	0	0	0	0	1	0
      0	0	0	0	0	0	0
      0	0	0	0	1	0	0

   2. 1	1	0	0	0	0	0
      0	1	0	0	0	0	0
      0	0	1	0	0	0	0
      0	0	0	1	1	0	0
      0	0	0	0	1	1	0
      0	0	0	0	0	1	0
      0	0	0	0	1	0	1

   3. 0	1	0	0	0	0	0
      1	0	0	0	0	0	0
      0	0	0	0	0	0	0
      0	0	0	0	1	0	0
      0	0	0	1	0	1	1
      0	0	0	0	1	0	0
      0	0	0	0	1	0	0

   4. 0	1	0	0	0	0	0
      0	0	0	0	0	0	0
      0	0	0	0	0	0	0
      0	0	0	0	1	1	0
      0	0	0	0	0	1	0
      0	0	0	0	0	0	0
      0	0	0	0	1	1	0

4. 1. 

   2. 

   3. 

   4. 

5. The original relation $R$ is:

   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

   The reflexive closure of $R$ is:

   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	1

   The symmetric closure of $R$ is:

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

6. R $= \{(1,1),(2,2),(3,3),(4,4)\\ (1,2),(1,3),(1,4),(2,3),(2,4),\\ (3,4)\}$
   

   For $\leq$ to be antisymmetric means that for all real numbers $a_1$ and $a_2$ in A, If $a_1 \leq a_2$ and $a_2 \leq a_1$ then x = y. This follows immediately from the definition of $\leq$ which says that given any real numbers $a_1$ and $a_2$, exactly one of the following holds:

   $a_1 < a_2$ or $a_1 = a_2$ or $a_2 < a_1$.

7. Let A $= \{a,b\}$ and B$= \{b,c\}$. Since $A\not\subseteq B$ and $B\not\subseteq A$.

8. R is not a partial order relation because R is not anitsymmetric.

   Counter example: 1 R 3 ( because 1 + 3 is even) and 3 R 1 ( because 3 + 1 is also even) but $1 \neq 3$

9. C $= \{ \emptyset, \{1\},\{1,2\},\{1,2,3\},\{1,2,3,4\},\{1,2,3,4,5\},\{1,2,3,4,5,6\}\}$

10. The Hasse diagram looks like this:

    

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}$}$$
       
       
       
       Answer: $-1: \{-1\},\{-1,0\}$
       $0: \{0\},\{-1,1\},\{-1,0,1\}$
       $1: \{1\},\{0,1\}$
    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$}$$
       
       
       
       Answer: $0: 00$
       $1: 01,10$
       $2: 02,11,20$
       $3: 12,21$
       $4: 22$
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.

    ANSWER:
    This problem becomes one of looking at the slope of the line that determines the equivalence class as well as the quadrant of the caresian plane it exists in. Assuming that $p_1 = (x_1,y_1)$, the slope of the line that eminates from the origin through this point is $m = \frac{y_1}{x_1}$ (since the second point used to determine the slope is the origin. Using the slope/intersept form of the formula for a line we get the formula for the line is $y = \frac{y_1}{x_1}x$ since the intersept is also determined by the origin. The other portion is that the quadrant needs to be the same (this is the only way we can talk about 1/2 lines rather than full lines). The quadant is determined by the parity (positive/negative) of the x's being the same and the parity of the y's being the same. Therefore the relationship is that $p_1$ and $p_2$ are related where $p_1 = (x_a,y_a)$ and $p_2 = (x_b,y_b)$ if an only if $y_a = \frac(y_b)(x_b)x_a$. In order to see that this forms an equivalence relation we must be able to prove that it is reflexive, symmetric and transitive.

    Reflexive:
    When you let $(a,b)$ be arbitrary in the caresian plane.
    The formula $a = \frac{b}{a}b$ reduces to $a = a$ when you cancel the b's.
    Therefore it is reflexive as long as the point is not the origin.
    Also every point is in the same quadrant of the cartesian plane with itself so this property is also reflexive.
    

    Symmetric:
    Comparing the formulas:
    $y_a = \frac{y_b}{x_b}x_a$ and $y_b = \frac{y_a}{x_a}x_b$
    You see that they are algrbraically equivalent.
    This means that the relationship is symmetric.
    Also every two points if $p_1$ is in the same quadrant as $p_2$ then $p_2$ is in the same quadrant as $p_1$ so this property is also symmetric.
    

    Transitive: Let $p_1,p_2, p_3$ be arbitrary on the cartesian plane (but none are the origin).
    Let $p_1 = (x_1,y_1)$ and $p_2=(x_2,y_2)$ and $p_3 = (x_3,y_3)$.
    Assume that $p_1$ is related to $p_2$ and that $p_2$ is related to $p_3$.
    This means that $y_1 = \frac{y_2}{x_2}x_1$ and $y_2 = \frac{y_3}{x_3}x_2$ by the definition of the function.
    By substitution we get $y_1 = \frac{\frac{y_3}{x_3}x_2}{x_2}x_1$
    Cancelling the $x_2$ we get $y_1 = \frac{y_3}{x_3}x_1$
    Since this is the formula that shows that $p_1$ is related to $p_3$, we know that the formula is transitive.
    Also if $p_1$ is in the same quadrant as $p_2$ and $p_2$ is in the same quadrant as $p_3$ then $p_1$ is in the same quadrant as $p_3$ so this property is also transitive.
    

    Since it has the properties of being reflexive, symmetric and transitive, it is an equivalence relation.
    

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.
    Answer: Since $R$ is symmetric, $x\ R\ y$ implies $y\ R\ x$. Since $R$ is transitive, $x\ R\ y$ and $y\ R\ x$ implies $x\ R\ x$. Thus $R$ is reflexive and therefore is an equivalence relation.
14. Prove or disproof (i.e. give a counterexample) whether the following relations are partial order.
    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$}$$
       
       
       
       Answer: No, because it is not antisymmetric: e.g. $12\ R\ 18$ and $18\ R\ 12$ but $12\neq 18$
    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$$
       
       
       
       Answer: No, because it is not antisymmetric: e.g. $1^2 \le (-1)^2$ and $(-1)^2 \le 1^2$ but $1\neq -1$
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.
    Answer: Yes, since it is a partial order, and for any two elements $x,y \in A$, either $(x,y)$ or $(y,x)$ is in $A$. It is a partial order because it is reflexive, antisymmetric and transitive. In particular, the order is $c<b<a<d$.

Web Accessibility