Equivalence Relations

**elninio** · September 30th 2009, 12:11 PM

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]

**Jose27** · September 30th 2009, 12:27 PM

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.

**elninio** · September 30th 2009, 04:16 PM

I still dont fully understand how to show that ~ is an equivalence relation.

I have another related question:

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

**pomp** · September 30th 2009, 04:23 PM

Originally Posted by elninio

I still dont fully understand how to show that ~ is an equivalence relation.

I have another related question:

On $R^2$ , define $(a_1,a_2) ~ (b_1,b_2)$ if $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, $(a_1,a_2)$ and $(b_1, b_2)$ in $\mathbb{R}^2$ are related if and only if

$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.

**elninio** · September 30th 2009, 04:28 PM

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.

**elninio** · September 30th 2009, 04:33 PM

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.

**pomp** · September 30th 2009, 04:37 PM

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

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

$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

**elninio** · September 30th 2009, 04:40 PM

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

**pomp** · September 30th 2009, 04:42 PM

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 $\mathbb{Z}^2$ )

So c is of the form $(z_1,z_2)$ where the z's are just any old integers.

**elninio** · September 30th 2009, 05:02 PM

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.

**elninio** · September 30th 2009, 05:06 PM

Would the proof to my second question be any different than squaring each side when going through conditions?

And how are equivalence classes found?

**pomp** · September 30th 2009, 05:20 PM

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: $\quad [a]_\sim$ we have that:

$[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 $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, $b = (y_1,y_2)$ Then b is in a's equivalence class if and only if a~b.

So formally we say $b \in [a]_\sim$ if and only if $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.

**elninio** · October 1st 2009, 02:47 PM

So how do I prove that condition 2 is satisfied for my second question?

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

**pomp** · October 1st 2009, 02:58 PM

Originally Posted by elninio

So how do I prove that condition 2 is satisfied for my second question?

Squaring both sides would give $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:

$(x_1,x_2)$ ~ $(y_1,y_2)$ if and only if $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

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

I don't see why you arrived at what you did.

**elninio** · October 1st 2009, 03:03 PM

Ahh great, it appears I had confused myself. Thank you for clearing it up.

Thread: Equivalence Relations

LinkBack

Thread Tools

Display