Results 1 to 6 of 6

Math Help - Equivalence Relations Proof

  1. #1
    Newbie
    Joined
    Oct 2009
    From
    Philidelphia/Pittsburgh PA
    Posts
    16

    Equivalence Relations Proof

    For homework I am supposed to prove a proposition that says: Assume we are given an equivalence relation on set A.
    For a1 and a2 in A either [a1] = [a2] or [a1] intersect [a2] = the empty set.
    where [a1] means the equivalence class of a1 in A and the or is inclusive.
    i tried breaking it up into cases one case where [a1] = [a2] and the other where if [a1] did not = [a2] the [a1] intersect [a2] must = the empty set. But apparently that wasn't correct.

    Can anyone help??? I'd really appreciate it.
    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 nataliemarie View Post
    For homework I am supposed to prove a proposition that says: Assume we are given an equivalence relation on set A.
    For a1 and a2 in A either [a1] = [a2] or [a1] intersect [a2] = the empty set.
    where [a1] means the equivalence class of a1 in A and the or is inclusive.
    i tried breaking it up into cases one case where [a1] = [a2] and the other where if [a1] did not = [a2] the [a1] intersect [a2] must = the empty set. But apparently that wasn't correct.

    Can anyone help??? I'd really appreciate it.
    Problem: Let E be a set and \sim an equivalence relation on E. If \ell\in E let \bar{\ell}=\left\{\ell'\in E:\ell\sim\ell'\right\}. Prove that either \bar{\ell}\cap\bar{\ell'} is empty or \bar{\ell}=\bar{\ell'}

    Proof: Let \bar{\ell}\cap\bar{\ell'}\ne\varnothing. Then there exists some k\in E such that k\in\bar{\ell},\bar{\ell'}. By definition though this means that \ell\sim k and \ell'\sim k. Since \sim is an equivalence relation we see that \ell'\sim k\implies k\sim \ell'. Furthermore, we know that \sim is transitive and that \ell\sim k,k\sim \ell'. Therefore \ell\sim \ell'. Now let x\in\bar{\ell}, then \ell \sim x. Once again though, we see that \ell \sim x and \ell\sim\ell'\implies \ell'\sim\ell implies \ell'\sim x. Therefore x\in\bar{\ell'} and \bar{\ell}\subset\bar{\ell'}. The same logic reveals that x\in\bar{\ell'}\implies x\in\bar{\ell}, so that \bar{\ell'}\subset\bar{\ell}. Consequently, \bar{\ell}=\bar{\ell'}. The conclusion follows.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    From
    Philidelphia/Pittsburgh PA
    Posts
    16
    I understand that, but shouldn't I also prove that the intersection is the empty set?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by nataliemarie View Post
    I understand that, but shouldn't I also prove that the intersection is the empty set?
    Why would you?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2009
    From
    Philidelphia/Pittsburgh PA
    Posts
    16
    Because for an or statement the basic proof is too show that if the first half is true, and if the first half isnt true then the second half must be true for the proposition to hold.

    so if a1 doesnt equal a2 then their intersection is the empty set. why do i not have to prove that part?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by nataliemarie View Post
    Because for an or statement the basic proof is too show that if the first half is true, and if the first half isnt true then the second half must be true for the proposition to hold.

    so if a1 doesnt equal a2 then their intersection is the empty set. why do i not have to prove that part?
    I think it follows from the original part. But if you feel that it is neccessary, practice never hurt! Try it yourself and report back if you have any issues.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 19th 2011, 02:09 PM
  2. Replies: 10
    Last Post: January 14th 2010, 01:28 PM
  3. equivalence relations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 3rd 2008, 04:15 AM
  4. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 13th 2008, 04:06 AM
  5. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: December 2nd 2007, 02:59 PM

Search Tags


/mathhelpforum @mathhelpforum