Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So, for a course I'm following we got some practice exams to prepare for the finals. However, for some of these we do not have answers, nor can I find someone who is certain of his answer on the following question.

I was hoping someone here can give me some insight to the question(s) listed below.

I figured that when trying to solve (a) I would have to take an arbitrary equivalence class of R and proof that it is also in S. But I am unsure of how to actually formally proof this.

For question (b) I have absolutely no clue, as I originally thought it was false.


Let $R$ and $S$ be two equivalence relations on a finite set U satisfying $R \subseteq S$.

(a) Prove that every equivalence class of R is a subset of an equivalence class of S.

(b) Let $n_R$ be the number of equivalence classes of R and let $n_S$ be the numer of equivalence classes of S. Prove that $n_R \geq n_S$

share|improve this question
1  
I don't know what you've done so far, but it might be helpful to look at a small example: let $U=\{1,2,3,4\}$, $R=\{(1,2),(2,1)\}\cup\Delta$, $S=R\cup\{(3,4),(4,3)\}$, where $\Delta$ denotes the diagonal. What do the equivalence classes of $R$ look like and what do those of $S$ look like? Once you know these, it should be possible to prove (a). After you've done that, part (b) immediately follows from (a). Namely, if you take any equivalence class of $S$, it contains at least one equivalence class of $R$. –  HSN Jan 23 '13 at 13:46
    
Another hint: if $y \in [x]_R$, this means $(x,y) \in R$. so $(x,y) \in S$. –  David Wheeler Jan 23 '13 at 13:49
    
Okay, so I think the equivalence classes of R are: [[1]] = {1, 2} and [[2]] = {1, 2}. While the equivalence classes of S are: [[1]] = {1, 2}, [[2]] = {1, 2}, [[3]] = {4}, [[4]] = {3}. But I think I did something wrong, as $nr < ns$. Maybe I did not understand the definition of equivalence correctly. –  Ruddie Jan 23 '13 at 13:58
    
What you're forgetting here, is that all elements of $U$ need to be in some equivalence class. You're right that the equivalence classes of $1$ and $2$ are $\{1,2\}$ in both cases, but I'm afraid you're not quite right about the $3$ and $4$. Since $(3,4)\in S$, it follows that both $3$ and $4$ are in the equivalence class of $3$ in this case. Just figure out what $[3]_R$ and $[4]_R$ look like. –  HSN Jan 23 '13 at 14:58

1 Answer 1

up vote 2 down vote accepted

The basic thoughts you need are these:

(a) Take an arbitrary object $o$ in the domain of the relations.

By definition, if $o$ and $x$ belong to the same $R$ equivalence class, then $oRx$. By hypothesis, if $oRx$ the $oSx$. By definition, if $oSx$ then $o$ and $x$ belong to the same $S$-equivalence class.

Hence, putting things together, if $o$ and $x$ belong to the same $R$ equivalence class, then $o$ and $x$ also belong to the same $S$-equivalence class.

So the $R$-equivalance class containing $o$ must be a subset of the $S$-equivalance class containing $o$. But $o$ was arbitrary. So it follows immediately that every $R$-equivalence class is indeed a subset of some $S$-equivalence class.

(b) If $R \subseteq S$ then $S$ is no more discriminating than $R$, so $S$ partitions the universe no more finely than $R$. That evidently means there are at least as many $R$-equivalence classes as $S$-equivalence classes.

share|improve this answer
    
Woh, that was actually really easy. I think I was more thinking about how R was a Set, rather then an actually equivalence relation. Thanks! –  Ruddie Jan 23 '13 at 19:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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