CMSC 250 Fall 2004 -- Homework 14

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

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.
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.
4. 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$$
      
      

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.

6. Define each of the following as it pertains to a graph
   1. Path
   2. Simple Circuit
   3. Circuit
   4. Euler Circuit
   5. Hamiltonian Circuit

Web Accessibility