Thread: 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!

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?

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)

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.

You can prove them all at once using this simple fact : if you have a set and a function , then the relation defined by is an equivalence relation on . (It is the equivalence relation induced on by ).

Just pick accordingly, for example as .

(In fact, every equivalence relation on a set is induced by a function on that set, namely, the projection on the equivalence classes.)