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.

  • $\begingroup$ Thanks for the hints! They helped! $\endgroup$ – OckhamsRazor Mar 16 '14 at 4:12
  • $\begingroup$ 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? $\endgroup$ – OckhamsRazor Mar 16 '14 at 4:42
  • $\begingroup$ @OckhamsRazor: Similar but not identical. Can you tell me what $a . b$ means? $\endgroup$ – Ishfaaq Mar 16 '14 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.