Relation Isomorphism is Equivalence Relation

Theorem

Relation isomorphism is an equivalence relation.

Proof

Let $\struct {S_1, \RR_1}$, $\struct {S_2, \RR_2}$ and $\struct {S_3, \RR_3}$ be relational structures.

Let $S \cong T$ denote the relation that $S$ is (relation) isomorphic to $T$.

Checking in turn each of the criteria for equivalence:

Reflexive

The fact that relation isomorphism is reflexive follows immediately from Identity Mapping is Relation Isomorphism.

$\Box$

Symmetric

Suppose $S_1 \cong S_2$.

Let $\phi: S_1 \to S_2$ be a relation isomorphism from $S_1$ to $S_2$.

Then by Inverse of Relation Isomorphism is Relation Isomorphism, $\phi^{-1}: S_2 \to S_1$ is also a relation isomorphism.

So $S_2 \cong S_1$ and so relation isomorphism is symmetric.

$\Box$

Transitive

Suppose $S_1 \cong S_2$ and $S_2 \cong S_3$.

Let:

$\alpha: S_1 \to S_2$ be a relation isomorphism from $S_1$ to $S_2$

$\beta: S_2 \to S_3$ be a relation isomorphism from $S_2$ to $S_3$.

From Composite of Relation Isomorphisms is Relation Isomorphism, the composite mapping $\beta \circ \alpha$ is also a relation isomorphism.

That is, $S_1 \cong S_3$.

So relation isomorphism is transitive.

$\blacksquare$