Results 1 to 14 of 14

Math Help - Equivalence relation

  1. #1
    Member
    Joined
    Nov 2008
    Posts
    121

    Equivalence relation

    If I have a subset, how do I define an equivalence relation.
    I understand it has to satisfy three properties:transitive, symmetric and reflexive, but I'm not sure how to give an explicit definition of the equivalence relation, for example on I where
    I=\{(x,y) : 0 \le x\le 1 \ \& \ 0 \le y \le 1\}
    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 bigdoggy View Post
    If I have a subset, how do I define an equivalence relation.
    I understand it has to satisfy three properties:transitive, symmetric and reflexive, but I'm not sure how to give an explicit definition of the equivalence relation, for example on I where
    I=\{(x,y) : 0 \le x\le 1 \ \& \ 0 \le y \le 1\}
    How about the old fashioned partition way. Partition [0,1]\times[0,1] Into \left[0,\frac{1}{2}\right]\times\left[0,1\right]=X_1 and \left(\frac{1}{2},1\right]\times\left(0,1\right]. Define an equivalence relation \sim on I by (x,y)\sim (x_1,y_1)\text{ iff they belong to the same block}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2008
    Posts
    121
    Quote Originally Posted by Drexel28 View Post
    How about the old fashioned partition way. Partition [0,1]\times[0,1] Into \left[0,\frac{1}{2}\right]\times\left[0,1\right]=X_1 and \left(\frac{1}{2},1\right]\times\left(0,1\right]. Define an equivalence relation \sim on I by (x,y)\sim (x_1,y_1)\text{ iff they belong to the same block}
    Hi
    I've never seen that before...please could you elaborate?
    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 bigdoggy View Post
    Hi
    I've never seen that before...please could you elaborate?
    What exactly is troubling you? What the relation means...or why it is an equivalence relation?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2008
    Posts
    121
    Quote Originally Posted by Drexel28 View Post
    What exactly is troubling you? What the relation means...or why it is an equivalence relation?
    To be honest I'm new to this area..I've been looking at the problem for a while!
    I know how to verify if a relation is an equivalence relation...but I've not seen a problem which asks to 'give the explicit definition of the equivalence relation'...
    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 bigdoggy View Post
    To be honest I'm new to this area..I've been looking at the problem for a while!
    I know how to verify if a relation is an equivalence relation...but I've not seen a problem which asks to 'give the explicit definition of the equivalence relation'...
    Now I'm lost. I thought we were talking about the partition relation I gave you. Is there something else your asking now?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1584
    Awards
    1
    Quote Originally Posted by Drexel28 View Post
    What exactly is troubling you? What the relation means...or why it is an equivalence relation?
    I think that it needs to be pointed out that there are uncountably many equivalent relations on that set.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Nov 2008
    Posts
    121
    Quote Originally Posted by Drexel28 View Post
    Now I'm lost. I thought we were talking about the partition relation I gave you. Is there something else your asking now?
    Sorry...I was referring back to the stated problem.
    I guess I'm not sure what 'type' of solution or what it should look like....I understand I'm being extremely vague, but I'm lost on where to start
    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 Plato View Post
    I think that it needs to be pointed out that there are uncountably many equivalent relations on that set.
    Yes. Plato is right. And not just uncountably man differnt partition relations but relations of every kind and flavor.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Nov 2008
    Posts
    121
    Quote Originally Posted by Drexel28 View Post
    Yes. Plato is right. And not just uncountably man differnt partition relations but relations of every kind and flavor.
    that adds some clarity...I was, for some reason, expecting there to be one single unique equivalence relation....
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    For an even simpler one (still partition) what about paritioning this set into points whose coordinates are rational and those that are not?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1584
    Awards
    1
    Quote Originally Posted by Drexel28 View Post
    Yes. Plato is right. And not just uncountably man differnt partition relations but relations of every kind and flavor.
    My point of course is I do not think that the questioner understands that point.
    Nor do I think that he/she has any idea of the one-to-one correspondence between equivalence relations and partitions.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    If the OP can wait I'll post up the concept of partitions/ERs corresponence.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    As promised. First we need a little background, namely 'what is a partition?'

    Definition: Let \pi=\left\{E_{\alpha}:\text{ }\alpha\in\mathcal{I}\right\} be a collection of sets, with \mathcal{I} being some indexing set. Then \pi is a partition of a set E if

    1) E_{\alpha_1}\cap E_{\alpha_2}=\varnothing\quad\alpha_1\ne \alpha_2

    2) \bigcup_{\alpha\in\mathcal{I}}E_{\alpha}=E

    In simpler terms, a collection of sets (specifically subsets) of E is a partition if no two of them overlap and their union is the entire set. Think about it as taking the whole set and cutting it into pieces. We call the indvidual E_{\alpha}'s 'blocks' of the partition.

    Definition: Equivalence class- Let E be a set, and \sim and equivalence relation on E. Then the set \bar{a}=\left\{x:a\sim x\right\} is called the equivalence class of a.

    Theorem: A parition \pi of E induces an equivalence relation on E.

    Proof: This relation, which we'll call \stackrel{\pi}{\sim}, is defined by a\stackrel{\pi}{\sim}b\Longleftrightarrow \left(a\in E_{\alpha}\right)\wedge \left(b\in E_{\alpha}\right) for the same E_{\alpha}\in \pi. We prove that is satisfies the three conditions of an equivalence relation.

    1. Relfexive- Since a belongs to precisely one set it is clear that a\stackrel{\pi}{\sim}a

    2. Symmetric- Keeping in mind that each element belongs to exactly one element of \pi it is clear that if a\stackrel{\pi}{\sim}b\Longleftrightarrow \left(a\in E_{\alpha}\right)\wedge\left(b\in E_{\alpha}\right) that \left(b\in E_{\alpha}\right)\wedge\left(a\in E_{\alpha}\right)\Longleftrightarrow b\stackrel{\pi}{\sim}a

    3. Transitive- Suppose that a\stackrel{\pi}{\sim}b\Longleftrightarrow a,b\in E_{\alpha} and b\stackrel{\pi}{\sim}c\Longleftrightarrow b,c\in E_{\alpha}. And note that since [tex]b[\math] belongs to precisely one E_{\alpha} that a,c must belong the same E_{\alpha} or in other words a\stackrel{\pi}{\sim}c

    This proves that a partition \pi defines a relation on E.

    We next move onto our next concept.

    Theorem: An equivalence relation \sim on a set E induces a partition on E

    Proof: Define a parition \pi on E by \pi=\left\{\bar{a}:a\in E\right\}. Let us show that this is a parition.

    1) Suppose that \bar{a}\ne \bar{b}. WLOG Let x\in\bar{a} then a\sim x so that x\sim a which of course means that x\nsim a. This means that x\notin\bar{b}. Thus no element of \bar{a} is in \bar{b}. The exact same method shows that no element of \bar{b} is in \bar{a}. Thus \bar{a}\cap\bar{b}=\varnothing.

    2) Clearly \forall a\in E a\in\bar{a}. So clearly every element of E is in some equivalence class (namely it's own equivalence class). So \bigcup_{a\in E}\bar{a}=\bigcup_{x\in\pi}x=E.

    This shows that \pi is a partition of E



    This is all that is really needed. But just in case here is one last theorem.

    Theorem: If \bar{a}\cap\bar{b}\ne\varnothing then \bar{a}=\bar{b}

    Proof: If \bar{a}\cap\bar{b}\ne\varnothing hen there exists some c\in\bar{a},\bar{b} but by definition that means that a\sim c and b\sim c. But because \sim is an equivalence relation we can see that bu symmetry b\sim c\implies c\sim b. So a\sim c and c\sim b which by transitivity means that a\sim b. Now clearly then for any x\in \bar{a} we can see that x\sim a and a\sim b therefore x\sim b, so \bar{a}\subset\bar{b}. The same methodology shows that \bar{b}\subset\bar{a}. Thus we conclude that \bar{a}=\bar{b}

    This just about does it. It's late and I easily could have made a typo but I hope you get the point.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum