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 :)

Printable View

- November 22nd 2012, 07:26 AMsakuraxkisuEquivalence 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 :) - November 22nd 2012, 07:48 AMDevenoRe: Equivalence relation
is xVx always true? that is, is it true that |x

^{2}- x^{2}| < 2?

what does it mean for xVy to imply yVx? (hint: note that |x^{2}- y^{2}| = |-(x^{2}- y^{2})| = |y^{2}- x^{2}|).

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?) - November 22nd 2012, 10:16 AMsakuraxkisuRe: 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 - November 22nd 2012, 11:58 AMDevenoRe: Equivalence relation
suppose that xVy and yVz.

then |x^{2}-y^{2}| < 2, and |y^{2}-z^{2}| < 2.

since these are non-negative integers, they could only be 0, or 1, that is: |x^{2}-y^{2}| ≤ 1, |y^{2}-z^{2}| ≤ 1.

now |x^{2}-z^{2}| = |x^{2}-y^{2}+y^{2}-z^{2}| ≤ |x^{2}-y^{2}| + |y^{2}-z^{2}|

≤ 1 + 1 = 2.

so we know that |x^{2}-z^{2}| ≤ 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 |x^{2}-z^{2}| = x^{2}-z^{2}

b)|x| < |z|, so that |x^{2}-z^{2}| = z^{2}-x^{2}.

let's look at (a):

then (z+k)^{2}- z^{2}= 2, so

z^{2}+ 2kz + k^{2}- z^{2}= 2, that is:

2kz + k^{2}= 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 |x^{2}- z^{2}| cannot be 2, and therefore must be less than 2. so xVz, and we are done. - November 22nd 2012, 01:35 PMemakarovRe: Equivalence relation
- November 22nd 2012, 02:25 PMPlatoRe: Equivalence relation
- November 22nd 2012, 07:24 PMDevenoRe: Equivalence relation

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.

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.