# Prove transitivity of relation.

Let $\sim$ be a relation where $x \sim y \Leftrightarrow x = y \lor (x \in I \land y \in I)$. Show $\sim$ is a congruence relation on $S$ where $S= \{a,b, c, d, e\}$ and $I = \{a, d\}$. One of the requirements to prove a congruence is to show that $\sim$ is transitive i.e. $x \sim y \land y \sim z \implies x \sim z$. However, I am unsure how to show this. I can show that $\sim$ is reflexive and symmetric but and unable to show transitivity. Any hints are appreciated.

Suppose $x \sim y$ and $y \sim z$. Then by definition one of the following four cases must occur.

1. $x = y$ and $y = z$ in which case $x = z \implies x \sim z$
2. $(x \in I \land y \in I)$ and $(y \in I \land z \in I)$ in which case $(x \in I \land z \in I) \implies x \sim z$
3. $x = y$ and $(y \in I \land z \in I)$ in which case it is clear that $(y = x \in I \land z \in I) \implies x \sim z$
4. $(x \in I \land y \in I)$ and $y = z$ in which case as above $(x \in I \land y = z \in I) \implies x \sim z$

It follows that $x \sim y$ and $y \sim z \implies x \sim z$ and hence the relation is transitive. Since you have mentioned that you have no issue with proving the relation is reflexive and symmetric I will omit their proof.

• Thanks for the hints! They helped! – OckhamsRazor Mar 16 '14 at 4:12
• By the way, the last point to prove a congruence is to show $(a \sim b \land c \sim d) \implies a \cdot c \sim b \cdot d$. Is this similar to showing transitivity? – OckhamsRazor Mar 16 '14 at 4:42
• @OckhamsRazor: Similar but not identical. Can you tell me what $a . b$ means? – Ishfaaq Mar 16 '14 at 13:27