# Equivalence Relations

• Sep 30th 2009, 12:11 PM
elninio
Equivalence Relations
Let T be the set of all ordered pairs (x,y) of positive integers. For (m1,m2) in T and (n1,n2) in T define (m1,m2) ~ (n1,n2). Show that ~ is an equivalence relation.

EDIT: [CONTAINS MISSING RELATION, LATER STATED in post 5]
• Sep 30th 2009, 12:27 PM
Jose27
Quote:

Originally Posted by elninio
Let T be the set of all ordered pairs (x,y) of positive integers. For (m1,m2) in T and (n1,n2) in T define (m1,m2) ~ (n1,n2). Show that ~ is an equivalence relation.

Are you sure you're not missing the definition of the relation, otherwise it's clearly an equivalence relation since everybody is related to everybody.
• Sep 30th 2009, 04:16 PM
elninio
I still dont fully understand how to show that ~ is an equivalence relation.

I have another related question:

On $\displaystyle R^2$, define $\displaystyle (a_1,a_2) ~ (b_1,b_2)$ if $\displaystyle a_1^2 + a_2^2 = B_1^2 + b_2^2$. Check that this defines an equivalence relation. What are the equivalence classes?
• Sep 30th 2009, 04:23 PM
pomp
Quote:

Originally Posted by elninio
I still dont fully understand how to show that ~ is an equivalence relation.

I have another related question:

On $\displaystyle R^2$, define $\displaystyle (a_1,a_2) ~ (b_1,b_2)$ if $\displaystyle a_1^2 + a_2^2 = B_1^2 + b_2^2$. Check that this defines an equivalence relation. What are the equivalence classes?

In your first post you didn't say what the relation actually was.

Two elements of a set are related if they satisfy some conditions of a given relation. So in your second example, you did actually give a relation ~ defined as:

Two elements, $\displaystyle (a_1,a_2)$ and $\displaystyle (b_1, b_2)$ in $\displaystyle \mathbb{R}^2$ are related if and only if

$\displaystyle a_1^2 + a_2^2 = b_1^2 + b_2^2$ .

So to check that it is indeed an equivalence relation there are three criteria it needs to fulfil. Do you know what these are?

If so, on which of the three did you get stuck? If you show some working it will be easier for us to help you out.
• Sep 30th 2009, 04:28 PM
elninio
Ohhhhh BOY! I'm very sorry. The question should read:

Let T be the set of all ordered pairs (x,y) of positive integers. For (m1,m2) in T and (n1,n2) in T define (m1,m2) ~ (n1,n2) if m1 + n2 = m2 + n1. Show that ~ is an equivalence relation.
• Sep 30th 2009, 04:33 PM
elninio
And the three criteria are:
1) for all a element of S, (a,a) is an element of R
2) for all a,b elements of S, if (a,b) is an element of R then (b,a) is an element of R
3) for all a,b,c elements in S, if (a,b) are elements in R and (b,c) are elements in R, then (a,c) are elements in R.

And from my understand of the definition, if (a,b) are elements in R then it is denoted a~b.
• Sep 30th 2009, 04:37 PM
pomp
Quote:

Originally Posted by elninio
Ohhhhh BOY! I'm very sorry. The question should read:

Let T be the set of all ordered pairs (x,y) of positive integers. For (m1,m2) in T and (n1,n2) in T define (m1,m2) ~ (n1,n2) if m_1 + n_2 = m_2 + n_1. Show that ~ is an equivalence relation.

That's more like it!

Now, to verify that a given relation is an equivalence relation you need to show that it satisfies the 3 following criteria: (as well as the trivial criteria that it is indeed a binary operation)

1) Reflexivity : a ~ a for all a in our set
2) Symmetry: if a~b then b~a for all a and b in our set
3) Transitivity: if a~b and b~c then a~c for all a,b,c in our set

I'll will start you off by showing you how to approach 2) and you should be able to do the rest yourself. So..

Claim: If a~b then b~a for all a,b in our set
Proof:

Take any a and b in our set, say $\displaystyle a=(x_1,x_2) \quad b=(y_1,y_2)$ where all the x and y's are integers.

Now, by definition a~b implies that $\displaystyle x_1 + y_2 = x_2 + y_1$

As the x's and y's are just integers it doesn't matter which order we add them, so we can just rearrange to get:

$\displaystyle y_2 + x_1 = y_1 + x_2$ and if we just change the right and left hand side we get:

$\displaystyle y_1 + x_2 = y_2 + x_1$ and if we just look back at our definition of the relation, we can see that this is implies that b~a and our proof is complete.

Good luck with the rest
• Sep 30th 2009, 04:40 PM
elninio
Great explaination! But i'm confused as to how I introduce "c" and what it would be equivalent to.
• Sep 30th 2009, 04:42 PM
pomp
Quote:

Originally Posted by elninio
Great explaination! But i'm confused as to how I introduce "c" and what it would be equivalent to.

c is just any third element from our set. Our set is the set of pairs of integers (usually denoted $\displaystyle \mathbb{Z}^2$ )

So c is of the form $\displaystyle (z_1,z_2)$ where the z's are just any old integers.
• Sep 30th 2009, 05:02 PM
elninio
Here's my write-up for the first and third conditions (less some minor formalities). The first just doesnt seem right to me. Or maybe its just too simple.

i) a~a for all a in our set.

Lets say a=(x1,x2), where x's are integers.

a~a implies x1+x2=x2+x1 which can be re-arranged x2+x1=x1=x2 which implies a~a which proves the first condition.

iii) if a~b and b~c then a~c for all a,b,c in the set.

a=(x1,x2) b=(y1,y2) c=(z1,z2)

a~b=> y1+x2=y2+x1, which can be rearranged y1-y2=x1-x2
b~c=> z1+y2=z2+y1 which can be rearranged y1-y2=z1-z2

Since a~c=>z1+x2=z2+x1 can be rearranged as z1-z2=x1-x2, substituting we get:
y1-y2=y1-y2, which proves the third condition.
• Sep 30th 2009, 05:06 PM
elninio
Would the proof to my second question be any different than squaring each side when going through conditions?

And how are equivalence classes found?
• Sep 30th 2009, 05:20 PM
pomp
All looks good to me! (there was a typo somewhere but that was definitely unintentional)

Yeh, it looks as though the argument would be exactly the same, on first glance I can't see any pitfalls. I think it's forum protocol to start new threads for new questions but it's practically identical anyway.

Say we have an equivalence relation ~ on some set. Then if we take an element of that set say a, the equivalence class of a is the set of al other members in our set that satisfy the equivalence relation with a.

More formally, suppose our set is called A. Then if we denote the equivalence class of an element, a of A, with respect to an equivalence relation ~ acting on A as: $\displaystyle \quad [a]_\sim$ we have that:

$\displaystyle [a]_\sim$ = { all b in A such that b ~ a}

So, lets consider the second question you posed.

Take an arbitrary element a from the set, then $\displaystyle a = (x_1,x_2)$ where the x's are some real numbers.

The equivalence class of a with respect to ~ is therefore any elements in our set that satisfy the equivalence relation with a.

So suppose b is some other arbitrary element of our set, $\displaystyle b = (y_1,y_2)$ Then b is in a's equivalence class if and only if a~b.

So formally we say $\displaystyle b \in [a]_\sim$ if and only if $\displaystyle y_1^2 + y_2^2 = x_1^2 + x_2^2$

As an example. Suppose a was (3,4). Then the equivalence class of a would consist of all pairs of real numbers, such that the sum of the squares of the pairs equals 3^2 + 4^2 = 25. So the pair (0,5) would be in there as 0^2 + 5^2 = 25, so would the pair (-3, -4) etc.

Hope this cleared some things up, sorry if it was at all confusing.
• Oct 1st 2009, 02:47 PM
elninio
So how do I prove that condition 2 is satisfied for my second question?

Squaring both sides would give $\displaystyle x_1^2+2x_1y_2+y_2^2=x_2^2+2x_2y_1+y_1^2$
• Oct 1st 2009, 02:58 PM
pomp
Quote:

Originally Posted by elninio
So how do I prove that condition 2 is satisfied for my second question?

Squaring both sides would give $\displaystyle x_1^2+2x_1y_2+y_2^2=x_2^2+2x_2y_1+y_1^2$

In your second question, I thought the relation was:

$\displaystyle (x_1,x_2)$ ~ $\displaystyle (y_1,y_2)$ if and only if $\displaystyle x_1^2+x_2^2 = y_1^2+y_2^2$

Then to see if ~ satisfies the second criteria all you need to do is show that if

$\displaystyle x_1^2+x_2^2 = y_1^2+y_2^2$, Then $\displaystyle y_1^2+y_2^2 = x_1^2+x_2^2$

I don't see why you arrived at what you did.
• Oct 1st 2009, 03:03 PM
elninio
Ahh great, it appears I had confused myself. Thank you for clearing it up.