# Thread: Binary relations and congruence

1. ## Binary relations and congruence

Prove that congruence n is an equivalence relation on the set (double barrel Z).
So I can show that it is symmetric because
a - b = nk
b - a = nk
(-1)(b - a) = (-1)nk
a - b = (-k)n
example
a = 1 b =2
1 - 2 = nk
(-1)(-1 = nk)
1 = (-k)n
2 - 1 = nk
1 = nk
it also seems to be reflexive because
if a = b
a - a = nk
if k was 0 that would be true
and if its reflexive and symmetric it would also be transitive
I am not sure if this work is accurate or if that final about it being reflexive and symmetric implies its transitive is correct. Any help would be greatly appreciated.

2. Originally Posted by Enkie
Prove that congruence n is an equivalence relation on the set (double barrel Z).
So I can show that it is symmetric because
a - b = nk
b - a = nk
(-1)(b - a) = (-1)nk
a - b = (-k)n
example
a = 1 b =2
1 - 2 = nk
(-1)(-1 = nk)
1 = (-k)n
2 - 1 = nk
1 = nk
it also seems to be reflexive because
if a = b
a - a = nk
if k was 0 that would be true
and if its reflexive and symmetric it would also be transitive
I am not sure if this work is accurate or if that final about it being reflexive and symmetric implies its transitive is correct. Any help would be greatly appreciated.
Firstly, you should say what the congruence is! I suspect it is $\displaystyle a \equiv b \text{ mod } n$, but I'm not entirely sure...if it is, your working for the first two parts look fine.

For the last bit, it is not true that reflexive and symmetric implies transitive. However, the working is along the same lines as the other two parts - you simply substitute in the definition.

I should perhaps point out that by definition, a congruence is an equivalence relation that "acts nicely" with the operation - if $\displaystyle (a, b) \in \rho$ (writing $\displaystyle (a, b) \in \rho$ for $\displaystyle a$ being related to $\displaystyle b$) then $\displaystyle (as, bs) \in \rho$ and $\displaystyle (sa, sb) \in \rho$.