# Equivalence Relation Proof

• Mar 16th 2011, 07:46 PM
jstarks44444
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!
• Mar 16th 2011, 08:06 PM
Tinyboss
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?
• Mar 17th 2011, 01:48 PM
jstarks44444
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)
• Mar 25th 2011, 05:01 AM
Deveno
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.
• Mar 25th 2011, 08:32 AM
Bruno J.
You can prove them all at once using this simple fact : if you have a set $\displaystyle A$ and a function $\displaystyle f: A \to B$, then the relation defined by $\displaystyle x \sim y \Leftrightarrow f(x)=f(y)$ is an equivalence relation on $\displaystyle A$. (It is the equivalence relation induced on $\displaystyle A$ by $\displaystyle f$).

Just pick $\displaystyle f: \mathbb{Z}\times \mathbb{Z} \to \mathbb{Z}$ accordingly, for example as $\displaystyle 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.)