Show that the restriction of an equivalence relation is an equivalence relation.

Let $C$ be a relation on a set $A$. If $A_{0} \subset A$, define the restriction of $C$ to $A_{0}$ to be the relation $C \cap (A_{0} \times A_{0})$. Show that the restriction of an equivalence relation is an equivalence relation.

$\textit{Proof Attempt}$

Let's assume $C$ is an equivalence relation then it satisfies the 3 properties (reflexivity, Commutativity and transitivity). Now $(C \cap (A_{0} \times A_{0})) \subset C$ hence $(C \cap (A_{0} \times A_{0}))$ also satisfies the 3 properties (reflexivity, Commutativity and transitivity).

Since $C$ and $A_{0}$ are arbitrary we conclude the restriction of an equivalence relation is an equivalence relation.

-

1 Answer

Unfortunately, none of the properties of reflexivity, symmetry (the usual term for what you are calling "commutativity"), nor transitivity is inherited by subsets.

Moreover, note that while symmetry and transitivity are not contextual (they depend only on your set of pairs, that is, on your relation), reflexivity is contextual: you need to say what your underlying set is in order to discuss reflexivity: the exact same set of pairs may be reflexive when considered as a relation on a set $A$, but not when considered as a relation on a different set $B$, even if $C\subseteq (A\times A)\cap(B\times B)$.

That is, it is false that if $D\subseteq C$ and $C$ is reflexive (on something), then $D$ is reflexive (on something else). It is false that if $D\subseteq C$ and $C$ is symmetric, then $D$ is symmetric. And it is false that if $D\subseteq C$ and $C$ is transitive, then $D$ is transitive.

For instance, take $A=\{1,2,3\}$, $C=\{(1,1), (1,2), (2,1), (2,2), (3,3)\}$, $D=\{(1,1), (1,2),\}$. Then $C$ is reflexive, symmetric, and transitive, $D\subseteq C$, but $D$ is not reflexive (not on $A$ and not on $\{1,2\}$) and not symmetric. You can probably come up with examples where it is not transitive either.

Of course, I didn't construct $D$ by restriction; but the point is that nowhere did you use the fact that you were constructing your relation by restriction. You just asserted that $C\cap(A_0\times A_0)$ would have the desired properties by virtue of being contained in a relation that did, and that argument is invalid.

What you need to answer:

1. Reflexivity on $A_0$. Let $a\in A_0$; why must $(a,a)$ be in $C\cap (A_0\times A_0)$ (Hint: Must it be in each of the two sets you are intersecting?)

2. Symmetry. If $(a,b)\in C\cap(A_0\times A_0)$, why must $(b,a)$ also be in $C\cap (A_0\times A_0)$?

3. Transitivity. If $(a,b)\in C\cap (A_0\times A_0)$, and $(b,c)\in C\cap(A_0\times A_0)$, why must $(a,c)$ be in $C\cap(A_0\times A_0)$?

-
@Hardy: Arturo explicitly lists the elements of his $D$. It is just a matter of looking at that list to see that $(2,2)$ is not a member of the set, and therefore $D$ is by definition not reflexive on any set that contains $2$. –  Henning Makholm Jan 31 '12 at 21:12
@Hardy: What you are doing is constructing a relation by restriction (look at your title! "the restriction of an equivalence relation"). You have a relation defined on a set $A$, then you are taking a subset $A_0$; when you take $C\cap (A_0\times A_0)$, you are restricting (your attention) to those pairs that have both entries in the smaller (sub)set $A_0$; that's called "the restriction of $C$ to $A_0$." –  Arturo Magidin Jan 31 '12 at 21:33
@Hardy: "reflexive on A both 1 and 2 are in A" does not parse at all. The definition of "reflexive on A" is "for every $a\in A$, the pair $(a,a)$ is in the relation." The set $\{1,2\}$ contains both $1$ and $2$. But the pair $(2,2)$ is not in $D$, so $D$ cannot be reflexive on any set that contains the element 2. In order for $(a,a)$ to be in $C\cap(A_0\times A_0)$, you need two things: you need $(a,a)$ to be in $C$, and you need $(a,a)$ to be in $A_0\times A_0$. The first condition may or may not hold for a random $C$; why does it hold in the case you are considering? (cont) –  Arturo Magidin Jan 31 '12 at 21:38
@Hardy: (cont) The second condition, $(a,a)\in A_0\times A_0$, may or may not hold for a random $a\in A$. Why does it hold in the case you are considering? Those are the questions you need to ask and answer. –  Arturo Magidin Jan 31 '12 at 21:39
@Hardy: You know that $C$ is an equivalence relation on $A$. So you know that it is reflexive on $A$. That it is symmetric. And that it is transitive. The question is, why will $C\cap (A_0\times A_0)$ be reflexive *on $A_0$**; why will it be symmetric, and why will it be transitive. Naturally, you should use your hypotheses, including that $A_0\subseteq A$ and that $C$ is an equivalence relation *on $A$. –  Arturo Magidin Jan 31 '12 at 21:42