Return to Homework 3, Glossary, Theorems

### Problem 8

Prove that the relation $\simeq$ of being isomorphic is an equivalence relation on any set of binary structures. You may simply quote the results you were asked to prove in the preceding two exercises at the appropriate places in your proof.

**Solution**

Let $\langle S, * \rangle$, $\langle S', *' \rangle$, and $\langle S'', *'' \rangle$ be binary structures

*Reflexive:* Let $X:S \rightarrow S$ be an identity mapping. So $X$ maps $S$ *one-to-one* and *onto* for $a,b \in S$, $X(a*b) = a * b = X(a) * X(b)$ so $X$ is an isomorphism of $S$ with $S$, $S \simeq S$

*Symmetric:* If $S \simeq S'$ and $\phi : S \rightarrow S'$ is an isomorphism, then by Hw3 Problem 6, $\phi^{-1}: S' \rightarrow S$ is an isomorphism

*Transitive:* Suppose $S \simeq S'$ and $S' \simeq S''$ and that $\phi:S \rightarrow S'$ and $\phi: S' \rightarrow S''$ is an isomorphism. By HW3 Problem 7, $\psi \circ \phi : S \rightarrow S'$ is an isomorphism so $S \simeq S''$

Therefore, $\simeq$ is an equivalence relation