# Equivalence relation

1. May 12, 2008

### thenoob

1. The problem statement, all variables and given/known data
We define a relation ~ for N^2 by:

(n, m) ~(k, l) <=> n + l = m + k

Show that ~ is a equivalence relation

2. Relevant equations

A relation R on a set A is equivalent if R is:
reflexive if x R x for all x that is an element of A
symmetric if x R y implies y R x, for all x,y that is an element of A
transitive if x R y and y R z imply x R z, for all x,y,z that is an element of A

3. The attempt at a solution
I have to prove this by showing that the relation is reflexive, symmetric and transitive. The symmetric part i understand, the fact that we can turn the relation around and it will be the same: n + l = m + k vs m + k = n + l.

But how do I prove the refexive and transitive part? I am really confused by the ~ and do not quite understand why it appears both as the name of the relation and as an element of the relation itself.

2. May 12, 2008

### dx

To prove reflexivity, you must check whether (x,y) ~ (x,y), i.e. whether any element a of $$N^2$$ satisfies a ~ a . By using the definition of ~ that you gave, can you check that (x,y) ~ (x,y)?

For transitivity, you must check whether (a,b) ~ (c,d) and (e,f) ~ (g,h) implies (a,b) ~ (g,h). Again, its just a matter of using the definition of ~.

Last edited: May 12, 2008
3. May 12, 2008

### thenoob

You mean by writing (x, y) ~ (x, y) <=> x + y = x + y ?

I think my problem is that I get really confused by the ~ and what it means.

4. May 12, 2008

### dx

~ is a relation, just like < or >. Just like you can check whether a < b, you can check whether (a,b) ~ (c,d) using the definition of ~ that you gave.

5. May 12, 2008

### tiny-tim

Welcome to PF!

Hi thenoob! Welcome to PF!

Maybe this will help … (and maybe it won't! )

An equivalence relation separates N^2 into mutually exclusive sets.

Anything in one set ~ anything else in that set, but ~ nothing in any other set.

Everything is in exactly one set.

So how would you describe the set (the equivalence class) that (1,0) is in (if necessary, pick a few examples, and find a pattern)?