Thread: 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!

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.

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?

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.