CRN 12107: 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 \[(m,n)\in R \Leftrightarrow m^2+n^2 \mbox{ is even.}\]
- Show that $R$ is an equivalence relation.
- Find all distinct equivalence classes of this relation.
Problem 28. Let $R$ and $S$ be two equivalence relations on a non-empty set $X$. Prove or disprove:
- $R\cap S$ is an equivalence relation.
- $R\cup S$ is an equivalence relation.
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.
Problem 30. Consider the following relation $R$ defined on a Boolean Algebra ${\cal A}$: \[(P,Q)\in R \Leftrightarrow P\sqcup Q=Q\] Prove or disprove: $R$ is (a) reflexive, (b) transitive, (c) symmetric, (d) anti-symmetric.
