4
$\begingroup$

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 Answers 1

4

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)$?

  • 0
    Firstly thank you so much for your reply. How come D is not reflexive on A both 1 and 2 are in A ? The book defines a relation on a set A is a subset C of the Cartesian product A X A. So in other words C is a set of ordered pairs which is a subset of A X A, Hence it is safe to assume that it might be a proper subset. By That reasoning if a is a∈A_0 ⊂ A then (a,a)∈ (A_0, A_0) but C may not have (a,a), so reflexivity can not be shown then ?2012-01-31
  • 1
    @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$.2012-01-31
  • 0
    @Arturo, the book does not give an example of how to construct a relation by restriction, i tried googling for those words but did n't find any relevant example either.2012-01-31
  • 0
    @HenningMakholm Cheers bud i think i get it now.2012-01-31
  • 0
    @HenningMakholm Arturo seems busy could you please confirm if it safe to assume by definition of a relation C on a set A if it would have all the elements of A X A ?2012-01-31
  • 1
    @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$."2012-01-31
  • 1
    @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)2012-01-31
  • 1
    @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.2012-01-31
  • 1
    @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$.*2012-01-31
  • 0
    It holds because we assume C is an equivalent relation.2012-01-31
  • 0
    sorry i just saw your other comment. Thank you once again u are very kind and patient.2012-01-31
  • 1
    @Hardy: If I were grading your homework, I would not give you full credit for "because C is an equivalence relation." I would expect you to spell out exactly how the fact that $C$ is an equivalence relation **on $A$** (again: *context is important* because "reflexivity" is context-dependent) gives you the desired conclusions in each of the three properties. And as to your last question to Henning: no, it's not safe to assume that $C$ contains **all** the elements of $A\times A$; that is not warranted by the assumption that $C$ is an equivalence relation.2012-01-31
  • 0
    Thanks, just to let u know this book did not mention atleast not clearly to me about the context hence i learned that from u just then. Thanks2012-01-31
  • 0
    @Arturo Could u possibly recommend a book with lots of examples on set theory i am interested in reading about relations, recursive definitions, infinite sets, axiom of choice, well ordered sets, maximum principle, zorn's lemma etc.2012-01-31
  • 1
    @Hardy: "Proofs and Fundamentals" by Ethan Bloch, was reasonably good in its first edition; I know it's now in later editions, but I have not seen them. Halmos's "Naive Set Theory" is good but has very few examples. It can be complemented with Sigler's "Exercises in Set Theory", but unfortunately the latter is long out of print.2012-01-31
  • 0
    @Arturo Thank you very much i 'll try them.2012-01-31