• Support PF! Buy your school textbooks, materials and every day products Here!

Equivalence relation

  • Thread starter thenoob
  • Start date
  • #1
2
0

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.
 

Answers and Replies

  • #2
dx
Homework Helper
Gold Member
2,011
18
To prove reflexivity, you must check whether (x,y) ~ (x,y), i.e. whether any element a of [tex]N^2[/tex] 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:
  • #3
2
0
To prove reflexivity, you must check whether (x,y) ~ (x,y), i.e. whether any element a of [tex]N^2[/tex] 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.
 
  • #4
dx
Homework Helper
Gold Member
2,011
18
~ 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
tiny-tim
Science Advisor
Homework Helper
25,832
249
Welcome to PF!

Hi thenoob! Welcome to PF! :smile:

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

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)? :smile:
 

Related Threads for: Equivalence relation

Replies
2
Views
4K
Replies
4
Views
1K
  • Last Post
Replies
7
Views
588
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
14
Views
3K
  • Last Post
Replies
7
Views
375
Replies
4
Views
24K
Top