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

Printable View

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

- Jul 7th 2007, 07:43 AMJhevon
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 AMTheRekz
I am confused on how to proof an ordered pair is reflexive or not

- Jul 7th 2007, 09:34 AMJhevon
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 $\displaystyle R$ be a relation on the set $\displaystyle \mathbb { N } \times \mathbb { N }$, such that $\displaystyle (a,b)R(c,d) \Longleftrightarrow ad = bc$.

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

....now continue - Jul 7th 2007, 09:48 AMred_dog
1) Reflexivity:

$\displaystyle (a,b)R(a,b)\Leftrightarrow ab=ab$, which is true.

2) Simmetry:

$\displaystyle (a,b)R(c,d)\Rightarrow ad=bc\Rightarrow cb=da\Rightarrow (c,d)R(a,b)$

3) Tranzitivity:

$\displaystyle (a,b)R(c,d)\Rightarrow ad=bc\Rightarrow \frac{a}{b}=\frac{c}{d}$ (1)

$\displaystyle (c,d)R(e,f)\Rightarrow cf=de\Rightarrow \frac{c}{d}=\frac{e}{f}$ (2)

From (1) and (2) $\displaystyle \frac{a}{b}=\frac{e}{f}\Rightarrow af=be\Rightarrow (a,b)R(e,f)$