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]

Printable View

- Sep 30th 2009, 01:11 PMelninioEquivalence 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, 01:27 PMJose27
- Sep 30th 2009, 05:16 PMelninio
I still dont fully understand how to show that ~ is an equivalence relation.

I have another related question:

On , define if . Check that this defines an equivalence relation. What are the equivalence classes? - Sep 30th 2009, 05:23 PMpomp
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, and in are related if and only if

.

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, 05:28 PMelninio
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, 05:33 PMelninio
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, 05:37 PMpomp
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 where all the x and y's are integers.

Now, by definition a~b implies that

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:

and if we just change the right and left hand side we get:

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, 05:40 PMelninio
Great explaination! But i'm confused as to how I introduce "c" and what it would be equivalent to.

- Sep 30th 2009, 05:42 PMpomp
- Sep 30th 2009, 06:02 PMelninio
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, 06:06 PMelninio
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, 06:20 PMpomp
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: we have that:

= { 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 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, Then b is in a's equivalence class if and only if a~b.

So formally we say if and only if

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, 03:47 PMelninio
So how do I prove that condition 2 is satisfied for my second question?

Squaring both sides would give - Oct 1st 2009, 03:58 PMpomp
- Oct 1st 2009, 04:03 PMelninio
Ahh great, it appears I had confused myself. Thank you for clearing it up.