# Prove equivalence relation

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

• 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... – Mauro ALLEGRANZA Sep 27 '19 at 11:48
• 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. – drhab Sep 27 '19 at 11:50
• Thanks. @Mauro, how does a being in B imply that (a,a) is in S? Can we assume that? – 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.