equivalence relations

Printable View

Jul 7th 2007, 07:18 AM
TheRekz

equivalence relations

Let R be the relation on the set of ordered pairs of positive integers such that $((a,b), (c,d)) \in$ if and only if ad = bc. Show that R is an equivalence relations.
Jul 7th 2007, 07:43 AM
Jhevon

Quote:

Originally Posted by TheRekz

Let R be the relation on the set of ordered pairs of positive integers such that $((a,b), (c,d)) \in$ if and only if ad = bc. Show that R is an equivalence relations.

this is just a case of applying definitions. Do you know what it means for a relation to be an equivalence relation? reflexive? symmetric? transitive?

Hint: A relation is said to be an "equivalence relation" if it is reflexive, symmetric and transitive.

Proving each of those cases are true for this relation should not be very difficult

Hint 2: A somewhat similar problem was done here. There are also definitions for all the terms mentioned in that thread as well. Use it as a guide
Jul 7th 2007, 09:23 AM
TheRekz

I am confused on how to proof an ordered pair is reflexive or not
Jul 7th 2007, 09:34 AM
Jhevon

Quote:

Originally Posted by TheRekz

I am confused on how to proof an ordered pair is reflexive or not

The transitive part is actually the toughest to prove. but i'll give you the reflexive part just so you see how to work with it.

Proof (incomplete):

Let $R$ be a relation on the set $\mathbb { N } \times \mathbb { N }$ , such that $(a,b)R(c,d) \Longleftrightarrow ad = bc$ .

First, we show that $R$ is reflexive. Since $ab = ba$ we have $(a,b)R(a,b)$ . Thus $R$ is reflexive.

....now continue
Jul 7th 2007, 09:48 AM
red_dog

1) Reflexivity:
$(a,b)R(a,b)\Leftrightarrow ab=ab$ , which is true.
2) Simmetry:
$(a,b)R(c,d)\Rightarrow ad=bc\Rightarrow cb=da\Rightarrow (c,d)R(a,b)$
3) Tranzitivity:
$(a,b)R(c,d)\Rightarrow ad=bc\Rightarrow \frac{a}{b}=\frac{c}{d}$ (1)
$(c,d)R(e,f)\Rightarrow cf=de\Rightarrow \frac{c}{d}=\frac{e}{f}$ (2)
From (1) and (2) $\frac{a}{b}=\frac{e}{f}\Rightarrow af=be\Rightarrow (a,b)R(e,f)$