Results 1 to 15 of 15

Math Help - Equivalence Relations

  1. #1
    Member elninio's Avatar
    Joined
    Sep 2009
    Posts
    92
    Awards
    1

    Equivalence Relations

    Let T be the set of all ordered pairs (x,y) of positive integers. For (m1,m2) in T and (n1,n2) in T define (m1,m2) ~ (n1,n2). Show that ~ is an equivalence relation.

    EDIT: [CONTAINS MISSING RELATION, LATER STATED in post 5]
    Last edited by elninio; September 30th 2009 at 05:34 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    From
    México
    Posts
    721
    Quote Originally Posted by elninio View Post
    Let T be the set of all ordered pairs (x,y) of positive integers. For (m1,m2) in T and (n1,n2) in T define (m1,m2) ~ (n1,n2). Show that ~ is an equivalence relation.
    Are you sure you're not missing the definition of the relation, otherwise it's clearly an equivalence relation since everybody is related to everybody.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member elninio's Avatar
    Joined
    Sep 2009
    Posts
    92
    Awards
    1
    I still dont fully understand how to show that ~ is an equivalence relation.

    I have another related question:

    On R^2, define (a_1,a_2) ~ (b_1,b_2) if a_1^2 + a_2^2 = B_1^2 + b_2^2. Check that this defines an equivalence relation. What are the equivalence classes?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by elninio View Post
    I still dont fully understand how to show that ~ is an equivalence relation.

    I have another related question:

    On R^2, define (a_1,a_2) ~ (b_1,b_2) if a_1^2 + a_2^2 = B_1^2 + b_2^2. Check that this defines an equivalence relation. What are the equivalence classes?
    In your first post you didn't say what the relation actually was.

    Two elements of a set are related if they satisfy some conditions of a given relation. So in your second example, you did actually give a relation ~ defined as:

    Two elements, (a_1,a_2) and (b_1, b_2) in \mathbb{R}^2 are related if and only if

    a_1^2 + a_2^2 = b_1^2 + b_2^2 .

    So to check that it is indeed an equivalence relation there are three criteria it needs to fulfil. Do you know what these are?

    If so, on which of the three did you get stuck? If you show some working it will be easier for us to help you out.
    Last edited by pomp; September 30th 2009 at 05:24 PM. Reason: typooo
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member elninio's Avatar
    Joined
    Sep 2009
    Posts
    92
    Awards
    1
    Ohhhhh BOY! I'm very sorry. The question should read:

    Let T be the set of all ordered pairs (x,y) of positive integers. For (m1,m2) in T and (n1,n2) in T define (m1,m2) ~ (n1,n2) if m1 + n2 = m2 + n1. Show that ~ is an equivalence relation.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member elninio's Avatar
    Joined
    Sep 2009
    Posts
    92
    Awards
    1
    And the three criteria are:
    1) for all a element of S, (a,a) is an element of R
    2) for all a,b elements of S, if (a,b) is an element of R then (b,a) is an element of R
    3) for all a,b,c elements in S, if (a,b) are elements in R and (b,c) are elements in R, then (a,c) are elements in R.

    And from my understand of the definition, if (a,b) are elements in R then it is denoted a~b.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by elninio View Post
    Ohhhhh BOY! I'm very sorry. The question should read:

    Let T be the set of all ordered pairs (x,y) of positive integers. For (m1,m2) in T and (n1,n2) in T define (m1,m2) ~ (n1,n2) if m_1 + n_2 = m_2 + n_1. Show that ~ is an equivalence relation.
    That's more like it!

    Now, to verify that a given relation is an equivalence relation you need to show that it satisfies the 3 following criteria: (as well as the trivial criteria that it is indeed a binary operation)

    1) Reflexivity : a ~ a for all a in our set
    2) Symmetry: if a~b then b~a for all a and b in our set
    3) Transitivity: if a~b and b~c then a~c for all a,b,c in our set

    I'll will start you off by showing you how to approach 2) and you should be able to do the rest yourself. So..

    Claim: If a~b then b~a for all a,b in our set
    Proof:

    Take any a and b in our set, say a=(x_1,x_2) \quad b=(y_1,y_2) where all the x and y's are integers.

    Now, by definition a~b implies that x_1 + y_2 = x_2 + y_1

    As the x's and y's are just integers it doesn't matter which order we add them, so we can just rearrange to get:

    y_2 + x_1 = y_1 + x_2 and if we just change the right and left hand side we get:

    y_1 + x_2 = y_2 + x_1 and if we just look back at our definition of the relation, we can see that this is implies that b~a and our proof is complete.


    Good luck with the rest
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member elninio's Avatar
    Joined
    Sep 2009
    Posts
    92
    Awards
    1
    Great explaination! But i'm confused as to how I introduce "c" and what it would be equivalent to.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by elninio View Post
    Great explaination! But i'm confused as to how I introduce "c" and what it would be equivalent to.
    c is just any third element from our set. Our set is the set of pairs of integers (usually denoted \mathbb{Z}^2 )

    So c is of the form (z_1,z_2) where the z's are just any old integers.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member elninio's Avatar
    Joined
    Sep 2009
    Posts
    92
    Awards
    1
    Here's my write-up for the first and third conditions (less some minor formalities). The first just doesnt seem right to me. Or maybe its just too simple.

    i) a~a for all a in our set.

    Lets say a=(x1,x2), where x's are integers.

    a~a implies x1+x2=x2+x1 which can be re-arranged x2+x1=x1=x2 which implies a~a which proves the first condition.

    iii) if a~b and b~c then a~c for all a,b,c in the set.

    a=(x1,x2) b=(y1,y2) c=(z1,z2)

    a~b=> y1+x2=y2+x1, which can be rearranged y1-y2=x1-x2
    b~c=> z1+y2=z2+y1 which can be rearranged y1-y2=z1-z2

    Since a~c=>z1+x2=z2+x1 can be rearranged as z1-z2=x1-x2, substituting we get:
    y1-y2=y1-y2, which proves the third condition.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member elninio's Avatar
    Joined
    Sep 2009
    Posts
    92
    Awards
    1
    Would the proof to my second question be any different than squaring each side when going through conditions?

    And how are equivalence classes found?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    All looks good to me! (there was a typo somewhere but that was definitely unintentional)

    Yeh, it looks as though the argument would be exactly the same, on first glance I can't see any pitfalls. I think it's forum protocol to start new threads for new questions but it's practically identical anyway.

    Say we have an equivalence relation ~ on some set. Then if we take an element of that set say a, the equivalence class of a is the set of al other members in our set that satisfy the equivalence relation with a.

    More formally, suppose our set is called A. Then if we denote the equivalence class of an element, a of A, with respect to an equivalence relation ~ acting on A as:  \quad [a]_\sim we have that:

    [a]_\sim = { all b in A such that b ~ a}

    So, lets consider the second question you posed.

    Take an arbitrary element a from the set, then a = (x_1,x_2) where the x's are some real numbers.

    The equivalence class of a with respect to ~ is therefore any elements in our set that satisfy the equivalence relation with a.

    So suppose b is some other arbitrary element of our set, b = (y_1,y_2) Then b is in a's equivalence class if and only if a~b.

    So formally we say b \in [a]_\sim if and only if y_1^2 + y_2^2 = x_1^2 + x_2^2

    As an example. Suppose a was (3,4). Then the equivalence class of a would consist of all pairs of real numbers, such that the sum of the squares of the pairs equals 3^2 + 4^2 = 25. So the pair (0,5) would be in there as 0^2 + 5^2 = 25, so would the pair (-3, -4) etc.

    Hope this cleared some things up, sorry if it was at all confusing.
    Last edited by pomp; September 30th 2009 at 06:27 PM. Reason: latex errors
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member elninio's Avatar
    Joined
    Sep 2009
    Posts
    92
    Awards
    1
    So how do I prove that condition 2 is satisfied for my second question?

    Squaring both sides would give x_1^2+2x_1y_2+y_2^2=x_2^2+2x_2y_1+y_1^2
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by elninio View Post
    So how do I prove that condition 2 is satisfied for my second question?

    Squaring both sides would give x_1^2+2x_1y_2+y_2^2=x_2^2+2x_2y_1+y_1^2
    In your second question, I thought the relation was:

    (x_1,x_2) ~ (y_1,y_2) if and only if x_1^2+x_2^2 = y_1^2+y_2^2

    Then to see if ~ satisfies the second criteria all you need to do is show that if

    x_1^2+x_2^2 = y_1^2+y_2^2, Then y_1^2+y_2^2  = x_1^2+x_2^2

    I don't see why you arrived at what you did.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member elninio's Avatar
    Joined
    Sep 2009
    Posts
    92
    Awards
    1
    Ahh great, it appears I had confused myself. Thank you for clearing it up.
    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. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: April 29th 2010, 05:30 PM
  3. Replies: 10
    Last Post: January 14th 2010, 01:28 PM
  4. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: April 30th 2009, 11:41 PM
  5. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 16th 2008, 02:08 PM

Search Tags


/mathhelpforum @mathhelpforum