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
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.
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?Quote:
Originally Posted by TheRekz
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
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.Quote:
Originally Posted by TheRekz
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
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)$
