Results 1 to 9 of 9

Math Help - Equivalence Relation

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

    Equivalence Relation

    Let R be an equivalence relation on P(X) by ARB if A\cup Y=B \cup Y, where X=\{1,2,3,4\}, and Y=\{3,4\}.
    What is the equivalence class of \{1,2\}?

    I know there is only one element of the power set X for the answer such that

    A \cup \{3,4\} = \{1,2\} \cup \{3,4\}=\{1,2,3,4\}

    For A, the possibilities are

    \{1,2\}
    \{1,2,3\}
    \{1,2,3,4\}

    Question: Since the intersection of any two equivalence classes is an empty set, does it mean that we get to pick only one of three possibilities listed above?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by novice View Post

    Question: Since the intersection of any two equivalence classes is an empty set, does it mean that we get to pick only one of three possibilities listed above?
    Empty or the entire set. So, yes.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2006
    Posts
    71
    Quote Originally Posted by novice View Post
    Let R be an equivalence relation on P(X) by ARB if A\cup Y=B \cup Y, where X=\{1,2,3,4\}, and Y=\{3,4\}.
    What is the equivalence class of \{1,2\}?

    I know there is only one element of the power set X for the answer such that

    A \cup \{3,4\} = \{1,2\} \cup \{3,4\}=\{1,2,3,4\}

    For A, the possibilities are

    \{1,2\}
    \{1,2,3\}
    \{1,2,3,4\}

    Question: Since the intersection of any two equivalence classes is an empty set, does it mean that we get to pick only one of three possibilities listed above?
    No.
    The equivalence class in question is: {{1,2}, {1,2,3}, {1,2,4}, {1,2,3,4}}.
    And this set is a member of the partition of P(X) induced by R.
    I think it's important to understand that it's the partition that's a collection of pairwise disjoint sets.

    It's a good exercise; stretch it a bit. What's the rank of R?
    Last edited by PiperAlpha167; April 22nd 2010 at 03:02 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Drexel28 View Post
    Empty or the entire set. So, yes.
    By definition, every element of X belongs to exactly one equivalence class, so it must not be empty.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by PiperAlpha167 View Post
    No.
    The equivalence class in question is: {{1,2}, {1,2,3}, {1,2,4}, {1,2,3,4}}.
    And this set is a member of the partition of P(X) induced by R.<--Can't find this in my book.
    I think it's important to understand that it's the partition that's a collection of pairwise disjoint sets.

    It's a good exercise; stretch it a bit. What's the rank of R?
    The set of the distinct equivalence classes is a partition of the set X=\{1,2,3,4\}.

    Since a set of equivalence classes is a collection of pairwise disjoint, nonempty subset of X whose union is X. None of \{1,2\}, \{1,2,3\},\{1,2,4\}, \{1,2,3,4\} are pairwise disjoint subsets of X.

    I have a hunch that we are to pick only one of those while these are the possible partitions of X:

    \{\{1,2\},\{3,4\}\}
    \{\{1,2,3\},\{4\}\}<--doubtful
    \{\{1,2,4\},\{3\}\}<--doubtful
    or
     <br />
\{\{1,2,3,4\}\}<br />
<--this too is doubtful

    I have strong doubt of for those three since they are not pairwise disjoint with Y. There is also another reason for doubt, since Y={3,4} is a fixed subset of X.

    I wonder if there is a book that gives clear illustration in this regard.
    Last edited by novice; April 22nd 2010 at 08:14 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2006
    Posts
    71
    Quote Originally Posted by novice View Post
    The set of the distinct equivalence classes is a partition of the set X=\{1,2,3,4\}.

    Since a set of equivalence classes is a collection of pairwise disjoint, nonempty subset of X whose union is X. None of \{1,2\}, \{1,2,3\},\{1,2,4\}, \{1,2,3,4\} are pairwise disjoint subsets of X.

    I have a hunch that we are to pick only one of those while these are the possible partitions of X:

    \{\{1,2\},\{3,4\}\}
    \{\{1,2,3\},\{4\}\}<--doubtful
    \{\{1,2,4\},\{3\}\}<--doubtful
    or
     <br />
\{\{1,2,3,4\}\}<br />
<--this too is doubtful

    I have strong doubt of for those three since they are not pairwise disjoint with Y. There is also another reason for doubt, since Y={3,4} is a fixed subset of X.

    I wonder if there is a book that gives clear illustration in this regard.
    R is an equivalence relation on P(X), not on X.

    The set of equivalence classes partition P(X), not X.

    Each equivalence class is a set of sets of numbers from X, not a set of numbers from X.

    The disjointness has to do with these sets of sets.

    You are focusing your attention in the wrong place. You are looking at detail inside of X.
    This exercise is a good test case for demonstrating an ability to abstract. Back out of X, and elevate yourself by looking into P(X) -- all 16 members.
    I asked you about the rank of R. When you've gained a better understanding of this material, you'll see that the rank is four.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by PiperAlpha167 View Post
    R is an equivalence relation on P(X), not on X.

    The set of equivalence classes partition P(X), not X.

    Each equivalence class is a set of sets of numbers from X, not a set of numbers from X.

    The disjointness has to do with these sets of sets.

    You are focusing your attention in the wrong place. You are looking at detail inside of X.
    This exercise is a good test case for demonstrating an ability to abstract. Back out of X, and elevate yourself by looking into P(X) -- all 16 members.
    I asked you about the rank of R. When you've gained a better understanding of this material, you'll see that the rank is four.
    You are absolutely right. I got distracted by what I read in the book.
    Now as to the rank of R, the material in my book made no mention of the subject of rank. For this, I need more reading beyond what my book can offer. It's a good thing for me to look into, for the answer to question.

    Thanks for you time and a very valuable lesson. I'll catch up you later with the rank of R if I could get a hold of the definition. I got 4 equivalence classes. Is that what you mean by rank?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Oct 2006
    Posts
    71
    Quote Originally Posted by novice View Post
    You are absolutely right. I got distracted by what I read in the book.
    Now as to the rank of R, the material in my book made no mention of the subject of rank. For this, I need more reading beyond what my book can offer. It's a good thing for me to look into, for the answer to question.

    Thanks for you time and a very valuable lesson. I'll catch up you later with the rank of R if I could get a hold of the definition. I got 4 equivalence classes. Is that what you mean by rank?
    Yes.
    The rank (or index) of an equivalence relation R on a set S is the number of equivalence classes that make up the partition
    of A induced by R (essentially, the cardinality of the partition). If the partition is infinite, the rank is said to be infinite.
    But, apparently these terms have become archaic. Not too much on the Internet -- "amazingly", not even at Wiki.
    (I see I've unwittingly dated myself.)
    Anyway, I suggest disregarding them.
    Good luck in your studies.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by PiperAlpha167 View Post
    Yes.
    The rank (or index) of an equivalence relation R on a set S is the number of equivalence classes that make up the partition
    of A induced by R (essentially, the cardinality of the partition). If the partition is infinite, the rank is said to be infinite.
    But, apparently these terms have become archaic. Not too much on the Internet -- "amazingly", not even at Wiki.
    (I see I've unwittingly dated myself.)
    Anyway, I suggest disregarding them.
    Good luck in your studies.
    It's not too hard to relate too since it mimics the index of a group which of course induces the partition of cosets.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: April 7th 2011, 12:46 AM
  2. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 07:36 PM
  3. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 30th 2009, 10:03 AM
  4. equivalence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 12th 2009, 06:33 PM
  5. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 04:39 AM

Search Tags


/mathhelpforum @mathhelpforum