I am reading "Introduction to Algorithms 3rd Edition" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.
I am reading section 16.4 "Matroids and greedy methods" now.
And the following proposition is used implicitly in a proof of Theorem 16.5 on p.438.
I know this proposition is intuitively obvious.
But I cannot prove it rigorously.
Please tell me a rigorous proof.
Let $A$ be a finite set.
Let $R$ be an equivalence relation on $A$.
Let $\{C_1, \cdots, C_m\}$ be the set of the equivalence classes of the equivalence relation $R$ on $A$.
Let $S$ be an equivalence relation on $A$.
Let $\{D_1, \cdots, D_n\}$ be the set of the equivalence classes of the equivalence relation $S$ on $A$.
Prove the follwoing proposition:
If $n < m$, then there exist $i \in \{1, \cdots, n\}, j, k \in \{1, \cdots, m\}$ such that $D_i \cap C_j \neq \emptyset$ and $D_i \cap C_k \neq \emptyset$ and $j \neq k$.
Suppose the statement is false. Then each $D_i$ intersects at most one $C_j$. But every element of $D_i$ is an element of $A$ - therefore an element of some $C_k$ - therefore an element of this particular $C_j$. That is, $D_i$ is a subset of $C_j$. Thus the union of all $n$ of the $D_i$ is a subset of the union of some $n$ or fewer of the $C_j$; and since $n<m$, this is a proper subset of $A$. We have shown that $A$ is a proper subset of $A$, and this is a contradiction.