Results 1 to 4 of 4

Math Help - Equivalence relations on the integers

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    16

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    781
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2010
    Posts
    16
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    781
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  2. equivalence relations!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 29th 2010, 07:56 AM
  3. Help with Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 26th 2010, 10:59 AM
  4. Replies: 10
    Last Post: January 14th 2010, 12:28 PM
  5. Equivalence relations
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: October 14th 2009, 12:39 PM

Search Tags


/mathhelpforum @mathhelpforum