Results 1 to 5 of 5

Math Help - Equivalence Relation Proof

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    86

    Equivalence Relation Proof

    I would really appreciate some help with the following problem:

    Prove that each of the following relations defined on Z x Z is an equivalence relation. Determine the equivalence classes for each relation.

    (x,y) ~ (v,w) if x^2 + y^2 = v^2 + w^2

    (x,y) ~ (v,w) if y - x^2 = w - v^2

    (x,y) ~ (v,w) if xy = vw

    (x,y) ~ (v,w) if x + 2y = v + 2w

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433
    Well, you need to show reflexivity, symmetry, and transitivity (usually the only hard one) for each. Have you tried that, and if so, where are you getting stuck?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2010
    Posts
    86
    Well I figured out how to prove that they are equivalence relations, but what are the respective equivalence classes? Here's what I have so far:

    (x,y) ~ (v,w) if x^2 + y^2 = v^2 + w^2
    Reflexitivity
    (x,y)~(x,y) because x^2 + y^2 = x^2 + y^2
    Symmetry
    (x,y)~(v,w) iff x^2 + y^2 = v^2 + w^2 iff v^2 + w^2 = x^2 + y^2 iff (v,w)~(x,y)
    Transitivity
    Suppose (x,y)~(v,w) and (v,w)~(s,t). Then x^2 + y^2 = v^2 + w^2 and v^2 + w^2 = s^2 + t^2. So x^2 + y^2 = s^2 + t^2 and (x,y)~(s,t)

    (x,y) ~ (v,w) if y - x^2 = w - v^2
    Reflexitivity
    (x,y)~(x,y) because y - x^2 = y - x^2
    Symmetry
    (x,y)~(v,w) iff y - x^2 = w - v^2 iff w - v^2 = y - x^2 iff (v,w)~(x,y)
    Transitivity
    Suppose (x,y)~(v,w) and (v,w)~(s,t). Then y - x^2 = w - v^2 and w - v^2 = t - s^2. So y - x^2 = t - s^2 and (x,y)~(s,t)

    (x,y) ~ (v,w) if xy = vw
    Reflexivity
    (x,y)~(x,y) because xy=xy
    Symmetry
    (x,y) ~ (v,w) iff xy = vw iff vw=xy iff (v,w)~(x,y)
    Transitivity
    Suppose (x,y)~(v,w) and (v,w)~(s,t). Then xy=vw and vw=st. So xy=st and (x,y)~(s,t).

    (x,y) ~ (v,w) if x + 2y = v + 2w
    Reflexitivity
    (x,y)~(x,y) because x + 2y = x + 2y
    Symmetry
    (x,y)~(v,w) iff x + 2y = v + 2w iff v + 2w = x + 2y iff (v,w)~(x,y)
    Transitivity
    Suppose (x,y)~(v,w) and (v,w)~(s,t). Then x + 2y = v + 2w and v + 2w = s + 2t. So x + 2y = s + 2t and (x,y)~(s,t)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,397
    Thanks
    760
    it appears as if you don't quite understand reflexivity and symmetry. ~ is reflexive iff A~A, symmetry means A~B --> B~A (in most of your examples, you have these transposed).

    in general, if (x,y) ~ (u,v) iff f(x,y) = f(u,v), then because equality is symmetric, f(u,v) = f(x,y), so (u,v) ~ (x,y), so ~ is symmetric.

    as far as determining the equivalence classes go, let's look at the first one. what is the equivalence class of (0,0)? clearly, for (x,y) to be equivalent to (0,0) we have to have:

    x^2 + y^2 = 0 --> x = y = 0. so the equivalence class of (0,0) is {(0,0)}. what is the equivalence class of (0,1)? then x^2 + y^2 = 1, which means that either x = 0, or y = 0,

    and if x = 0, then y = 1, or -1. similarly if y = 0, then x =1 or -1. so the equivalence class of (0,1) = {(-1,0), (0,-1), (1,0), (0,1)}.

    in general, the equivalence class of (x,y) is {(m,n) in ZxZ : m^2+n^2 = x^2 + y^2}, and there is one equivalence class for each integer expressible as the sum of two squares.
    Last edited by Deveno; March 25th 2011 at 05:15 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    You can prove them all at once using this simple fact : if you have a set A and a function f: A \to B, then the relation defined by x \sim y \Leftrightarrow f(x)=f(y) is an equivalence relation on A. (It is the equivalence relation induced on A by f).

    Just pick f: \mathbb{Z}\times \mathbb{Z} \to \mathbb{Z} accordingly, for example as f(a,b)=a^2+b^2.

    (In fact, every equivalence relation on a set is induced by a function on that set, namely, the projection on the equivalence classes.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. equivalence relation proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 3rd 2011, 05:18 AM
  2. Equivalence relation proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 17th 2011, 04:30 PM
  3. Formal proof of equivalence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 31st 2010, 06:25 AM
  4. Equivalence Relation Proof
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: August 5th 2009, 12:19 PM
  5. equivalence relation proof
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: July 3rd 2006, 01:46 PM

Search Tags


/mathhelpforum @mathhelpforum