# Thread: Equivalence relations on the integers

1. ## Equivalence relations on the integers

Hi,
I'm trying to solve
"If R is a relation on Z so that aRb if b=a+3 then how many equivalence relations, S on Z contain R?"
I had originally thought none, but then found that if S is a=b (mod 3) then this is an equivalence containing R.
So now I don't know where to go next. Is this the only relation? So how do I show that? Can someone point me in the right direction?
Thanks!

2. If aSb is a=b (mod 3), then S is indeed the least equivalence relation containing R. Obviously, it has three equivalence classes. Note that for two equivalence relations S' and S'', S' is a subset of S'' iff every equivalence class of S' is a subset of some equivalence class of S''. So, to get an equivalence relation containing S, we can join either two of the the tree or all three classes.

3. Ah, ok I hadn't thought to combine classes like that. Thanks.
I'm still not completely sure how we know that these (5) relations are the only ones?

4. First, S is the least equivalence relation containing R, i.e., every equivalence relation containing R also contains S. Second, the claim I wrote above is a biconditional; in particular, if S' is an equivalence relation containing S, then its equivalence classes are unions of the equivalence classes of S.