I have the assignment:

Provide a direct proof of this statement: Let A and B be two arbitrary sets such that B ⊆ A, and let R be an equivalence relation on A. Consider the relation S = {(a, b) ∈ R | a, b ∈ B} on the set B. Then S is an equivalence relation on B (that is, reflexive, symmetric and transitive).

Obviously i have to show that S is reflexive, symmetric and transitive. But how would this be done?

Any tips would be greatly appreciated

  • 1
    $\begingroup$ Check the three defining properties in turn : (i) Refl : is $aSa$ ? Obviously $a \in B$ implies $a \in A$. But if $(a,a) \in R$ then $(a,a) \in R \text { and } a \in B$. Thus, by def, $(a,a) \in S$. And so on... $\endgroup$ – Mauro ALLEGRANZA Sep 27 '19 at 11:48
  • $\begingroup$ Can you prove e.g. that $(a,a)\in S$ for every $a\in B$? That already proves reflexivity. It is just a matter of definitions. Also for symmetry and transitivity. $\endgroup$ – drhab Sep 27 '19 at 11:50
  • $\begingroup$ Thanks. @Mauro, how does a being in B imply that (a,a) is in S? Can we assume that? $\endgroup$ – ole Sep 27 '19 at 14:02

We have a relation $R\subset A\times A$ of pairs of elements of $A$. $S$ however, is exactly those pairs in $R$ that have both elements in $B\subset A$.

Since $R$ is reflexive, for any $a\in A$ we have $(a,a)\in R$. In particular for any $b\in B\subset A$ we have $(b,b)\in R$. But this is a pair with both elements in $B$, so $(b,b)\in S$ for any $b\in B$. Therefore $S$ is reflexive.

Since $R$ is symmetric, if $(a,a')\in R$ for some $a,a'\in A$, then also $(a',a)\in R$. Now, if $(b,b')\in S\subset R$, then also $(b',b)\in R$ as $R$ is symmetric, but again $(b',b)$ is a pair with both elements in $B$, so $(b',b)\in S$, meaning that $S$ is symmetric.

For transitive, let $b,b',b''\in B\subset A$ and $(b,b')\in S$ and $(b',b'')\in S$. Then $(b,b')$ and $(b',b'')$ are both elements of $R$, since $S\subset R$. Therefore $(b,b'')\in R$, because $R$ is transitive. But this is a pair with both elements in $B$, so $(b,b'')\in S$. This shows that $S$ is transitive.

  • $\begingroup$ Great explanation, thanks! $\endgroup$ – ole Sep 27 '19 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.