CMSC 250 Fall 2004 -- Homework 14 Answer

Due Wed., Dec. 8 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. 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$
2. 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.
   

3. 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.
4. 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$
5. 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$.
6. Definitions
   1. path = Traversal of a graph that does not allow repeated edges, but does allow repeated verticies. It does not need to start an stop at the same point, but it can.
   2. simple circuit = Traversal of a graph that starts and stops at the same point. It does not allow repeated edges at all, and allows only the first/last vertext to be repeated.
   3. circuit = Traversal of a graph that starts and stops at the same point. It does not allow repeated edges at all, but it does allow repeated verticies.
   4. Euler Circuit = A circuit (so you must apply the definition above - starts and stops at the same point, does not repeat an edge, but can repeat a vertex) and add that every edge and every vertext must be visited. In other words it is a circuit that contains every edge and every vertex (starts and stops at the same point, every vertex at least once, every edge exactly once).
   5. Hamiltonian Circuit = A simple circuit (so you must apply the definition above - starts and stops at the same point, does not repeat and edge and can only repeat the first/last vertex) and add that it contains every vertex. In other words it is a simple circuit that contains every vertex (starts and stops at the same point, uses every vertex exactly once and does not repeat any edge).

Web Accessibility