# Equivalence relation

thenoob

## Homework Statement

We define a relation ~ for N^2 by:

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

Show that ~ is a equivalence relation

## Homework 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

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

Homework Helper
Gold Member
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:
thenoob
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)?

You mean by writing (x, y) ~ (x, y) <=> 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 ~.

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

Homework Helper
Gold Member
~ 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.

Homework Helper
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)? 