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$
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.