Results 1 to 7 of 7
Like Tree2Thanks
  • 1 Post By Deveno
  • 1 Post By Deveno

Math Help - Equivalence relation

  1. #1
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    Equivalence relation

    Show that the relation V defined on Z (set of integers) defined by the setting xVy if absolute value(x^2-y^2) is less than or equal to 2 is an equivalence relation.

    Any help would be greatly appreciated
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    759

    Re: Equivalence relation

    is xVx always true? that is, is it true that |x2 - x2| < 2?

    what does it mean for xVy to imply yVx? (hint: note that |x2 - y2| = |-(x2 - y2)| = |y2 - x2|).

    transitivity will be the hardest thing to prove. think about the smallest possible difference of the squares of two (unequal) integers. which unequal integers can possibly be related by V?

    (for example, do we have 2V3? 1V2? -3V4?)
    Thanks from sakuraxkisu
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    Re: Equivalence relation

    Hi Deveno,

    I proved that it was reflexive and symmetric, but it was the transitivity proof that I was struggling with. Would it be possible if you could help me with that? Thank you
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    759

    Re: Equivalence relation

    suppose that xVy and yVz.

    then |x2-y2| < 2, and |y2-z2| < 2.

    since these are non-negative integers, they could only be 0, or 1, that is: |x2-y2| ≤ 1, |y2-z2| ≤ 1.

    now |x2-z2| = |x2-y2+y2-z2| ≤ |x2-y2| + |y2-z2|

    ≤ 1 + 1 = 2.

    so we know that |x2-z2| ≤ 2. can it ever equal 2?

    suppose it could. then we have:

    x ≠ z, so x = z + k, for some (positive or negative) integer k.

    there are two cases:

    a)|x| > |z|, so that |x2-z2| = x2-z2
    b)|x| < |z|, so that |x2-z2| = z2-x2.

    let's look at (a):

    then (z+k)2 - z2 = 2, so

    z2 + 2kz + k2 - z2 = 2, that is:

    2kz + k2 = 2.

    k divides the LHS, so k divides the RHS, that is k = -1,-2,1, or 2.

    if k = -1:

    -2z + 1 = 2, the LHS is odd, the RHS is even.

    if k = 1:

    2z + 1 = 2, same problem. so k must be -2 or 2.

    if k = -2:

    -4z + 4 = 2, so -2z + 2 = 1, the LHS is even, the RHS is odd.

    if k = 2:

    4z + 4 = 2, so 2z + 2 = 1, the LHS is again even, and the RHS is odd.

    so none of our 4 possibilities actually work, so (a) is impossible.

    i leave it to you to show (b) is impossible.

    this shows that |x2 - z2| cannot be 2, and therefore must be less than 2. so xVz, and we are done.
    Thanks from sakuraxkisu
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Equivalence relation

    Quote Originally Posted by Deveno View Post
    suppose that xVy and yVz.

    then |x2-y2| < 2, and |y2-z2| < 2.
    The inequalities should be non-strict.

    I suggest proving first that xVy iff x=\pm y or x\pm 1 = y = 0 or y\pm 1 = x = 0.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,677
    Thanks
    1618
    Awards
    1

    Re: Equivalence relation

    Quote Originally Posted by emakarov View Post
    The inequalities should be non-strict.
    I suggest proving first that xVy iff x=\pm y or x\pm 1 = y = 0 or y\pm 1 = x = 0.
    Yes I had noticed that also. This is really interesting equivalence relation. It hard for to believe that I had never seen it anywhere.

    Define T = \left\{ {( - 1, - 1),( - 1,0),( - 1,1),(0,0),(1,0),(1,1)} \right\} and T_1=T\cup T^{-1}.

    If n\in\mathbb{Z}^+\setminus\{1\} define T_n=\{(-n,-n),~(-n,n),~(n,-n),~(n,n)\}.

    Is it true that V = \bigcup\limits_k^\infty  {T_k }~?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    759

    Re: Equivalence relation

    Quote Originally Posted by emakarov View Post
    The inequalities should be non-strict.




    I suggest proving first that xVy iff x=\pm y or x\pm 1 = y = 0 or y\pm 1 = x = 0.

    oh dear. that really does put a wrinkle in things, doesn't it? must learn how to read one of these days.

    in that case, the argument has to be made FIRST, that the equivalence relation is actually the same as the one obtaining by "removing" the "or equals part" (same argument, really).

    the difference of two integer squares is never 2.

    Quote Originally Posted by Plato View Post
    Yes I had noticed that also. This is really interesting equivalence relation. It hard for to believe that I had never seen it anywhere.

    Define T = \left\{ {( - 1, - 1),( - 1,0),( - 1,1),(0,0),(1,0),(1,1)} \right\} and T_1=T\cup T^{-1}.

    If n\in\mathbb{Z}^+\setminus\{1\} define T_n=\{(-n,-n),~(-n,n),~(n,-n),~(n,n)\}.

    Is it true that V = \bigcup\limits_k^\infty  {T_k }~?
    i thought about looking at [0] = [1], first. but i thought it better to provide a direct proof of transitivity, using the definition of transitive, than a "back-door" approach of showing we have a partition on Z.
    Last edited by Deveno; November 22nd 2012 at 06:28 PM.
    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. ~ how is this an equivalence relation?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 29th 2009, 10:17 AM
  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