Read: Continue with 7.2.
Turn in: 7.42, 7.43, and the additional problem below
Additional Problem: Prove that the relation $\cong_5$ defined in Problem 7.22 is a equivalence relation.
- On 7.42, when proving $a \sim b \implies \operatorname{rel}(a) = \operatorname{rel}(b)$, you will assume that $a \sim b$, and then start by proving that $\operatorname{rel}(b) \subseteq \operatorname{rel}(a)$, which should make use of transitivity. Then, to prove $\operatorname{rel}(a) \subseteq \operatorname{rel}(b)$, you can start by using symmetry to see that $b \sim a$ is true.
- On 7.43(b), you want to prove an “or” statement. A typical way to prove “$P$ or $Q$” is as follows: if $Q$ is true, then the statement “$P$ or $Q$” is automatically true, so we may assume that $Q$ is false and then use that to show that $P$ is true. Thus, you may assume that $\operatorname{rel}(a)\cap \operatorname{rel}(b) \neq \emptyset$ and use that to prove that $\operatorname{rel}(a)=\operatorname{rel}(b)$. Now, if $\operatorname{rel}(a)\cap \operatorname{rel}(b) \neq \emptyset$, then there exists some $c\in A$ such that $c \in \operatorname{rel}(a)$ and $c \in \operatorname{rel}(b)$. What does that tell you? (7.42 is helpful.)