Results 1 to 12 of 12

Math Help - Equivalence relations

  1. #1
    Junior Member
    Joined
    Oct 2011
    Posts
    47

    Equivalence relations

    How many equivalence relations are there on the set {1,2,3}?

    I got just [1] = {1,2,3}

    because (1,1) (2,2) (3,3) (1,2) (2,1) (1,3) (3,1) (2,3) (3,2).
    [1] = {1,2.3}
    [2] = {1,3}
    [3] = {3,2}

    is this correct?
    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Equivalence relations

    I am not sure what your answer is. The question "how many" requires a number as an answer. You write, "I got just [1] = {1,2,3}." Usually, [x] denotes the equivalence class of x, i.e., the set of elements that are equivalent to x. So, [x] is a set, not a number. It could be that you mean "I got just one" equivalence relation, but then what is it?

    Also, if R = {(1,1), (2,2), (3,3), (1,2), (2,1), (1,3), (3,1), (2,3), (3,2)}, then [1] is indeed {1, 2, 3}, but [2] = [3] = {1, 2, 3} as well with respect to R.

    Each equivalence relation generates its own partition of {1, 2, 3}, so one way to find the answer is to count the number of partitions.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2011
    Posts
    47

    Re: Equivalence relations

    I am not sure if we need to add [2] and [3] since they are both have {1,2,3} the same as [1].
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Equivalence relations

    In any case, so far you have found just one equivalence relation, which is the total relation on {1, 2, 3}. There are several others. Again, my advice is to enumerate all possible partitions.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1581
    Awards
    1

    Re: Equivalence relations

    Quote Originally Posted by mathproblems View Post
    How many equivalence relations are there on the set {1,2,3}?
    There is a one-to-one correspondence between the number of partitions of a set and the number of equivalence relations on that set.
    That number is known as the Bell Number of the set.
    Bell numbers are sums of Stirling numbers of the second kind.
    For example on a set of ten the Bell number is 115975.
    So there are that many equivalence relations for a set of ten.

    In this case the number is small. It is less that 10.
    All you have to do is list all possible partitions of \{1,2,3\} and count them.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2011
    Posts
    47

    Re: Equivalence relations

    [1]=[2]=[3]= {1,2,3}
    3 correct?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1581
    Awards
    1

    Re: Equivalence relations

    Quote Originally Posted by mathproblems View Post
    [1]=[2]=[3]= {1,2,3}
    3 correct?
    No. That as nothing to do with any of this.
    Do you know what a partition of that set is?
    If so, show us four of them.
    If you don't know, then you are not ready to do this question.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Equivalence relations

    Yes, as I said in post #2,
    Quote Originally Posted by emakarov View Post
    If R = {(1,1), (2,2), (3,3), (1,2), (2,1), (1,3), (3,1), (2,3), (3,2)}, then [1] is indeed {1, 2, 3}, but [2] = [3] = {1, 2, 3} as well with respect to R.
    Also, as I said in post #4,
    Quote Originally Posted by emakarov View Post
    In any case, so far you have found just one equivalence relation, which is the total relation on {1, 2, 3}. There are several others. Again, my advice is to enumerate all possible partitions.
    Imagine that there are three regions on the map and that there are 1, 2, or 3 kings are fighting with each other for these regions. How can they split them between themselves? Start with 3 kings, then consider 2 kings, and finally just 1. Each splitting would be a partition.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Oct 2011
    Posts
    47

    Re: Equivalence relations

    Quote Originally Posted by Plato View Post
    No. That as nothing to do with any of this.
    Do you know what a partition of that set is?
    If so, show us four of them.
    If you don't know, then you are not ready to do this question.
    no I guess I dont know, so I cannot really show four of them. Would you please?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Oct 2011
    Posts
    47

    Re: Equivalence relations

    Quote Originally Posted by Plato View Post
    No. That as nothing to do with any of this.
    Do you know what a partition of that set is?
    If so, show us four of them.
    If you don't know, then you are not ready to do this question.
    { {1}, {2}, {3} }, or 1/2/3.
    { {1, 2}, {3} }, or 12/3.
    { {1, 3}, {2} }, or 13/2.
    { {1}, {2, 3} }, or 1/23.
    { {1, 2, 3} }, or 123
    is this correct?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1581
    Awards
    1

    Re: Equivalence relations

    Quote Originally Posted by mathproblems View Post
    { {1}, {2}, {3} }, or 1/2/3.
    { {1, 2}, {3} }, or 12/3.
    { {1, 3}, {2} }, or 13/2.
    { {1}, {2, 3} }, or 1/23.
    { {1, 2, 3} }, or 123
    is this correct?
    BINGO By George you have it.
    So the answer is 5.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Oct 2011
    Posts
    47

    Re: Equivalence relations

    thank you!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Equivalence relations X x X
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: October 16th 2011, 10:53 AM
  2. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  3. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 8th 2010, 10:55 AM
  4. Replies: 10
    Last Post: January 14th 2010, 12:28 PM
  5. equivalence relations
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: January 12th 2010, 07:17 PM

Search Tags


/mathhelpforum @mathhelpforum