Results 1 to 2 of 2

Math Help - Equivalence classes

  1. #1
    Junior Member
    Joined
    Oct 2010
    Posts
    27

    Equivalence classes

    \Rightarrow "Let R be an equivalence relation on A. For any x, y \in A either

    \left[ x \right]_{R} = \left[ y \right]_{R}

    or

    \left[ x \right]_{R} \cap \left[ y \right]_{R} = \emptyset "

    My professor gave the following proof to the preceding lemma in his notes, but he starts it by saying "It is enough to assume" then footnoting this and writing "no it isn't". So how do I need to add to this to make it a complete proof?

    It is enough to assume (footnoted here)
    \left[ x \right]_{R} \cap \left[ y \right]_{R} \neq  \emptyset
    and deduce that
    \left[ x \right]_{R} = \left[ y \right]_{R}

    First, fix w \in \left[ x \right]_{R}. For any z \in \left[ x \right]_{R},

    z \in \left[ x \right]_{R} means xRz
    xRw (similarly)
    wRx (symmetry)
    Therefore wRz (transitivity), i.e.,
    z \in \left[ w \right]_{R}

    That is, for every z \in \left[ x \right]_{R}, z \in \left[ w \right]_{R}.

    In other words,

    w \in \left[ x \right]_{R} \Rightarrow \left[ x \right]_{R} \subseteq \left[ w \right]_{R}

    In particular, w \in \left[ x \right]_{R}\Rightarrow x \in \left[ w \right]_{R}
    and also x \in \left[ w \right]_{R} \Rightarrow \left[ x \right]_{R} \subseteq \left[ w \right]_{R}

    Therefore w \in \left[ x \right]_{R} \Rightarrow \left[ x \right]_{R} = \left[ w \right]_{R}

    So, if \left[ x \right]_{R} \cap \left[ y \right]_{R} \neq  \emptyset choose some w \in \left[ x \right]_{R} \cap \left[ y \right]_{R}

    Then \left[ x \right]_{R} = \left[ w \right]_{R} and \left[ y \right]_{R} = \left[ w \right]_{R}, so

    \left[ x \right]_{R} = \left[ y \right]_{R}
    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 Conn View Post
    \Rightarrow "Let R be an equivalence relation on A. For any x, y \in A either

    \left[ x \right]_{R} = \left[ y \right]_{R}

    or

    \left[ x \right]_{R} \cap \left[ y \right]_{R} = \emptyset "

    My professor gave the following proof to the preceding lemma in his notes, but he starts it by saying "It is enough to assume" then footnoting this and writing "no it isn't". So how do I need to add to this to make it a complete proof?

    It is enough to assume (footnoted here)
    \left[ x \right]_{R} \cap \left[ y \right]_{R} \neq  \emptyset
    and deduce that
    \left[ x \right]_{R} = \left[ y \right]_{R}

    First, fix w \in \left[ x \right]_{R}. For any z \in \left[ x \right]_{R},

    z \in \left[ x \right]_{R} means xRz
    xRw (similarly)
    wRx (symmetry)
    Therefore wRz (transitivity), i.e.,
    z \in \left[ w \right]_{R}

    That is, for every z \in \left[ x \right]_{R}, z \in \left[ w \right]_{R}.

    In other words,

    w \in \left[ x \right]_{R} \Rightarrow \left[ x \right]_{R} \subseteq \left[ w \right]_{R}

    In particular, w \in \left[ x \right]_{R}\Rightarrow x \in \left[ w \right]_{R}
    and also x \in \left[ w \right]_{R} \Rightarrow \left[ x \right]_{R} \subseteq \left[ w \right]_{R}

    Therefore w \in \left[ x \right]_{R} \Rightarrow \left[ x \right]_{R} = \left[ w \right]_{R}

    So, if \left[ x \right]_{R} \cap \left[ y \right]_{R} \neq  \emptyset choose some w \in \left[ x \right]_{R} \cap \left[ y \right]_{R}

    Then \left[ x \right]_{R} = \left[ w \right]_{R} and \left[ y \right]_{R} = \left[ w \right]_{R}, so

    \left[ x \right]_{R} = \left[ y \right]_{R}
    It is complete. What you want to show is that given two equivalence classes [x],[y] they're equal or disjoint? You've showed that their not disjoint implies their equal and so either they are equal, or they're not equal in which case they must be disjoint (otherwise they'd be equal!).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. equivalence classes of P(N)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 13th 2010, 08:26 AM
  2. Replies: 10
    Last Post: January 14th 2010, 12:28 PM
  3. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 06:36 PM
  4. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 03:39 AM
  5. Equivalence classes
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 30th 2008, 11:04 PM

Search Tags


/mathhelpforum @mathhelpforum