Let $\mathcal{R}$ be relation on $A$ and $A_0 \subseteq A$. The $\mathbf{restriction}$ of $\mathcal{R}$ to $A_0$ is defined to be the relation $\mathcal{R} \cap (A_0 \times A_0) $.

$\mathbf{Homework \; Problem:}$ Please prove that that the restriction of equivalence relation is also an equivalence relation.


Let $\mathcal{R}$ be equivalence relation on set $A$. Pick any point $x \in A_0$. We have to show that $(x,x) \in \mathcal{R} \cap (A_0 \times A_0) $. But, we are given that $x \in A$ as well, so $(x,x) \in \mathcal{R}$. Since $x \in A_0$, then $(x,x) \in A_0 \times A_0$. therefore, $(x,x) \in \mathcal{R} \cap ( A_0 \times A_0) $.

Next, suppose $(x,y) \in \mathcal{R} \cap (A_0 \times A_0) $ and since $ \mathcal{R} \cap (A_0 \times A_0) \subseteq \mathcal{R} $, then $(x,y) \in \mathcal{R}$. so $(y,x) \in \mathcal{R}$. Also, we know $(x,y) \in A_0 \times A_0$. So by definition of product of a set with itself, then $(y,x)$ must be in $A_0 \times A_0$ as well. Therefore $(y,x) \in \mathcal{R} \cap ( A_0 \times A_0 )$. So we have symmetry.

Finally, say $(x,y)$ and $(y,z) $ are in $\mathcal{R} \cap (A_0 \times A_0) $. First, we obtain $(x,z) \in \mathcal{R}$ by transitivity of $\mathcal{R}$. since $x,y,z \in A_0$, then $ (x,z)$ must be in $A_0 \times A_0$ and so $(x,z) \in \mathcal{R} \cap (A_0 \times A_0)$ and so we get transitivity.

Is this a sufficient argument? Thanks.

  • 4
    $\begingroup$ Excellent. I cannot find any possibilities to improve it. $\endgroup$ – drhab May 27 '16 at 7:28
  • 1
    $\begingroup$ If the main purpose of your post is getting feedback on your proof, you should probably use (proof-verification) tag. See the tag-info for more details. $\endgroup$ – Martin Sleziak May 27 '16 at 8:22

Your Answer

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