Results 1 to 7 of 7
Like Tree1Thanks
  • 1 Post By Plato

Thread: equivalence relation

  1. #1
    Newbie
    Joined
    Jan 2013
    From
    galway
    Posts
    18

    equivalence relation

    question



    An equivalence relation R defined on a set contains
    the pairs (1,1 ), (1,2 ), ( 2,3). Find R, given that R A x A.

    have to do this for a assignment but have no idea where to start I missed the class covering this. could anyone tell me the basic technique how to solve this so i know where to start at least!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,455
    Thanks
    1368

    Re: equivalence relation

    An equivalence relation on A is a subset of A x A with certain properties. The three pairs you show do not currently satisfy those properties.

    1. You need reflexivity: For all $\displaystyle a \in A,(a,a) \in R$.
    2. You need symmetry: If $\displaystyle (a,b) \in R$, then $\displaystyle (b,a) \in R$.
    3. You need transitivity: If $\displaystyle (a,b)\in R$ and $\displaystyle (b,c) \in R$ then $\displaystyle (a,c) \in R$.
    Last edited by SlipEternal; Oct 22nd 2013 at 11:44 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2013
    From
    galway
    Posts
    18

    Re: equivalence relation

    sorry wrote question wrong

    An equivalence relation R defined on a set A ={1,2,3,4}contains
    the pairs (1,1 ), (1,2 ), ( 2,3). Find R, given that R ≠ A x A.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,455
    Thanks
    1368

    Re: equivalence relation

    What I am saying is, add pairs until you satisfy those three properties.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2013
    From
    galway
    Posts
    18

    Re: equivalence relation

    im sorry i dont understand
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,455
    Thanks
    1368

    Re: equivalence relation

    Check: for any $\displaystyle a \in A$, do you have $\displaystyle (a,a) \in R$? No. So, add those pairs that you are missing. $\displaystyle (1,2) \in R$. Do you have $\displaystyle (2,1) \in R$? No. So add that pair. Etc.

    Edit: By add those pairs, I mean add the pairs to the list of pairs you know must be in $\displaystyle R$. You started with the three given pairs. Then, from those three, you use the properties to figure out which other pairs must also be in $\displaystyle R$. In the end, you should find 10 pairs in $\displaystyle R$. If another equivalence relation $\displaystyle R'$ has $\displaystyle R \subseteq R'$ and you know $\displaystyle R' \setminus R \neq \emptyset$, then it is easy to show that $\displaystyle R' = A \times A$. In other words, $\displaystyle R$ is the unique equivalence relation on $\displaystyle A$ with those three pairs.
    Last edited by SlipEternal; Oct 22nd 2013 at 12:59 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,796
    Thanks
    2827
    Awards
    1

    Re: equivalence relation

    Quote Originally Posted by ronanbrowne88 View Post
    question
    An equivalence relation R defined on a set contains
    the pairs (1,1 ), (1,2 ), ( 2,3). Find R, given that R A x A.
    have to do this for a assignment but have no idea where to start I missed the class covering this. could anyone tell me the basic technique how to solve this so i know where to start at least!
    Define $\displaystyle F=\{(1,1),(1,2),(2,3)\}$. The diagonal is $\displaystyle \Delta_A=\{(1,1),(2,2),(3,3),(4,4)\}$

    Define $\displaystyle G=F\cup\Delta_A$ and $\displaystyle H=(G\circ G)\cup G$

    Define $\displaystyle R=H\cup H^{-1}$.

    Show that $\displaystyle R$ is an equivalence relation.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relation on equivalence classes of other relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Jan 7th 2013, 02:15 PM
  2. Replies: 1
    Last Post: Apr 6th 2011, 11:46 PM
  3. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Jan 7th 2010, 06:36 PM
  4. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Sep 30th 2009, 09:03 AM
  5. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jan 7th 2009, 03:39 AM

Search Tags


/mathhelpforum @mathhelpforum