1. ## 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

2. ## 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?)

3. ## 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

4. ## 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.

5. ## Re: Equivalence relation

Originally Posted by Deveno
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$.

6. ## Re: Equivalence relation

Originally Posted by emakarov
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 }~?$

7. ## Re: Equivalence relation

Originally Posted by emakarov
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.

Originally Posted by Plato
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.