Prove $R$ is an equivalence relation.

Question

I think I'm on the right track.

Set $S = N \times N$, and for any two members $(a,b),(c,d)$ of $S$, define $(a,b) \simeq (c,d)$ provided that $ad = bc$. Prove that $\simeq$ is an equivalence relation on $S$ and list four members of $[(6,8)]$.

I've come up with some examples:

$$(1,1) \simeq (1,1)$$ $$(1,1) \simeq (2,2)$$ $$(1,1) \simeq (3,3)$$

From these we observe symmetry, transitivity, and reflexivity. I believe I am meant to simply prove that these properties hold for the relation. I think I was a bit confused because the relation is made of tuples rather than naturals.

Answer 1

It looks to me like you need help with understanding how exactly you are supposed to show this versus just looking at examples.

First, you need to ask yourself about reflexivity. You need to look at an arbitrary element $(a,b)$ in $N \times N$ and show that under this relation $\sim$, $(a,b) \sim (a,b)$. Ok, well, how do we show this? Hmm, what would have to be true for $(a,b) \sim (a,b)$ to hold? By definition of $\sim$, we would need $ab = ba$. But of course this is true, since $a$ and $b$ are numbers. Multiplication is commutative for all real numbers, so $ab = ba$. So that means $(a,b) \sim (a,b)$ is true, too.

Now you need to show that the relation is symmetric. That means you need to show if $(a,b) \sim (c,d)$, then $(c,d) \sim (a,b)$. Ok, we are assuming $(a,b) \sim (c,d)$. What does that mean? It means $ad = bc$. We need to show $(c,d) \sim (a,b)$. But that means, by definition of $\sim$, that we need to show $cb = da$. But we know $cb = bc$, and $ad = da$ since multiplication of real numbers is commutative. And by assumption we have $ad = bc$, so this implies that we have $cb = da$, which is what we wanted. So $(c,d) \sim (a,b)$.

Finally, we need $\sim$ to be transitive. That means if we assume $(a,b) \sim (c,d)$ and $(c,d) \sim (e,f)$, then we want to show $(a,b) \sim (e,f)$.

What do we need for $(a,b) \sim (e,f)$ to be true? We need $af = be$. To show this is a little bit tricky, but not hard at all. We just use our assumptions. We know $(a,b) \sim (c,d)$ implies $ad = bc$. We also know $(c,d) \sim (e,f)$ implies $cf = de$. We want $af = be$. Hmm... If we multiply the corresponding sides of the equation $ad = bc$ with the equation $cf = de$, we get $adcf = bcde$. That's almost what we want! We have $af$ on one side and $be$ on the other. But there is a $dc$ and a $cd$ in the way... But wait, $dc = cd$ since multiplication is commutative! And we can divide both sides by this number to get $af = be$, which is what we wanted. So, $(a,b) \sim (e,f)$, as desired.

Answer 2

I'm not sure what you mean by "From these we observe...". These are simply examples, and don't really prove anything :)

You have to show that

• The relation is reflexive: for any $(a,b)\in S$ that $(a,b)\sim (a,b)$;
• The relation is symmetric: for any $(a,b), (c,d)\in S$ that if $(a,b)\sim (c,d)$ then $(c,d)\sim (a,b)$;
• The relation is transitive: for any $(a,b), (c,d), (e,f)\in S$ that if $(a,b)\sim (c,d)$ and $(c,d)\sim (e,f)$ that $(a,b)\sim (e,f)$.

The only one of these that might present any difficulty is the third. Just write down the definitions of what all these mean and try not to be confused by the fact that the elements of $S$ are themselves sets.

Answer 3

Reflexivity: For any two numbers $a$ and $b$, it holds that $ab = ba$, so $(a,b) \simeq (a,b)$.

Symmetry: Suppose $(a,b) \simeq (c,d)$. Then $ad = bc$ which also means that $cb = da$, so $(c,d) \simeq (a,b)$.

Transitivity: Suppose $(a,b) \simeq (c,d)$ and $(c,d) \simeq (e,f)$. Then $ad = bc$ and $cf = de$. This means that $d = \frac{bc}{a}$, so $cf = \frac{bce}{a} \implies af = be$ so we can conclude $af = be$, so $(a,b) \simeq (e,f)$.

Answer 4

Note that the condition that $(a,b) \sim (c,d) \iff \dfrac{a}{b} = \dfrac{c}{d}$. From this all three properties of equivalence relation are true.