Thread: Equivalence Relations question

Ok, here's my problem:

Let X={1,2,...,10}. Define a relation R on X*X by (a,b)R(c,d) if ad=bc.
A. Prove R an equivalence relation.
B. List the elements of [(5,4)].
C. How many distinct equivalence classes are there?

Ok, so here's what I've got so far:

Part A, Prove R is an equivalence relation. So I must prove that R is reflexive, symmetric and transitive.

Reflexive:
I need to show that ((a,b),(a,b)) is an element of R, for the set X. So I will check that ab=ba. Since c=a and d=b, then ab=ba, thus R is reflexive.

Symmetric:
I must show that (a,b),(c,d) is an element of R and (c,d),(a,b) is contained in R. If (a,b),(c,d) is an element of R, then ad=bc and cb=da since multiplication is commutative. Therefore (c,d),(a,b) is contained in R.

Transitive:
I must show that if (a,b),(c,d) is contained in R and (c,d),(e,f) is contained in R then (a,b),(e,f) is contained in R. Assume that (a,b),(c,d) is contained in R and (c,d),(e,f) is contained in R. Then ad=cb and cf=ed. This implies that a/b=c/d and that c/d=e/f so a/b=e/f thus, af=eb. So, (a,b),(e,f) is contained in R.

Part B:
List the elements of [(5,4)]:

I'm confused on this a bit, I am assuming they are asking what elements does the equivalence class [(5,4)] contain...
{(5,4),....

My thoughts here, if (a,b)=(5,4) and ad=bc, then 5d=4c, c=4/5d and d=5/4c, allowing that if c=5, d=4 and if c=10 then d=8.

so, {(5,4), (10,8)} would be my answer. Is this correct?

Ok and Part C...

This I'm lost on how to figure it up. So any help or pointers in the correct direction would be great!

Thanks in advance

Ashley

What you have done on parts a) & b) is correct.

Here is a hint for part c). Think fractions as in .

Thanks so much for the quick response, by thinking in terms of fractions like you said, I came up with 19 distinct equivalence classes for this relation.
1. (1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9 ,9),(10,10)
2. (1,2),(2,4),(3,6),(4,8),(5,10)
3. (1,3),(2,6),(3,9)
4. (1,4),(2,8)
5. (1,5),(2,10)
6. (2,1),(4,2),(6,3),(8,4),(10,5)
7. (2,3),(4,6),(6,9)
8. (2,5),(4,10)
9. (3,1),(6,2),(9,3)
10. (3,2),(6,4),(9,6)
11. (3,4),(6,8)
12. (3,5),(6,10)
13. (4,1),(8,2)
14. (4,3),(8,6)
15. (4,5),(8,10)
16. (5,1),(10,2)
17. (5,2),(10,4)
18. (5,3),(10,6)
19. (5,4),(10,8)

The problem I have with this though, is that I'm working with a couple of students also in my class (this was a test question the whole class missed, so we have to figure it out in groups and resubmit), and on this particular part, she said the answer was 5, but she's not sure why that was correct if it was.

It cannot be only five.
I did not carefully check your list.
But is seems to be correct.