Subjects discrete mathematics

Equivalence Relation C74A88

Step-by-step solutions with LaTeX - clean, fast, and student-friendly.

Use the AI math solver

1. **Problem statement:** Show that the relation $R$ on $\mathbb{N} \times \mathbb{N}$ defined by $(a,b) R (c,d) \iff \frac{a}{c} = \frac{b}{d}$ is an equivalence relation. 2. **Recall the definition of an equivalence relation:** A relation is an equivalence relation if it is reflexive, symmetric, and transitive. 3. **Step 1: Reflexivity** We need to show $(a,b) R (a,b)$ for all $(a,b) \in \mathbb{N} \times \mathbb{N}$. Since $\frac{a}{a} = 1$ and $\frac{b}{b} = 1$, we have $$\frac{a}{a} = \frac{b}{b} = 1,$$ so $(a,b) R (a,b)$ holds. 4. **Step 2: Symmetry** Assume $(a,b) R (c,d)$, i.e., $$\frac{a}{c} = \frac{b}{d}.$$ Then by equality of fractions, $$\frac{c}{a} = \frac{d}{b},$$ so $(c,d) R (a,b)$. 5. **Step 3: Transitivity** Assume $(a,b) R (c,d)$ and $(c,d) R (e,f)$, i.e., $$\frac{a}{c} = \frac{b}{d} \quad \text{and} \quad \frac{c}{e} = \frac{d}{f}.$$ From the first, $$ad = bc,$$ and from the second, $$cf = de.$$ Multiply the first equation by $f$ and the second by $b$: $$adf = bcf,$$ $$bcf = bde.$$ By equality, $$adf = bde.$$ Cancel $d$ (nonzero since natural numbers): $$\cancel{d}af = b\cancel{d}e,$$ so $$af = be,$$ which implies $$\frac{a}{e} = \frac{b}{f},$$ thus $(a,b) R (e,f)$. 6. **Conclusion:** Since $R$ is reflexive, symmetric, and transitive, it is an equivalence relation. --- **Final answer:** $R$ defined by $(a,b) R (c,d) \iff \frac{a}{c} = \frac{b}{d}$ is an equivalence relation on $\mathbb{N} \times \mathbb{N}$.