23666: HW 6

Problem 26. Consider the following equivalence relation on the set $A=\{1,2,3,4,5,6\}$:

$$R=\{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(1,2),(1,4),(2,1),(2,4),(4,1),(4,2),(3,6),(6,3)\}.$$ Find the partition generated by $R$.

Problem 27. Let $R$ be a relation on $\mathbb{N}$ defined by

$$(p,q)\in R \Leftrightarrow p^2+q^2 \mbox{ is even.}$$

1. Show that $R$ is an equivalence relation.
2. Find all distinct equivalence classes of this relation.

Problem 28. Define a relation $R$ on $\mathbb{N}$ by: $xRy$ if $x$ and $y$ have the same prime divisors. (For example, $6R12$.)

1. Show that $R$ is an equivalence relation.
2. Find the partition generated by $R$.

Problem 29. A relation $R$ on a non-empty set $X$ is called reverse-transitive if

$$(a,b)\in R \wedge (b,c)\in R \Rightarrow (c,a)\in R \mbox{ for all }a,b,c \in X.$$ Show that a relation $R$ on a non-empty set $X$ is an equivalence relation if and only if it is reflexive and reverse-transitive.