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