Suppose $R$ is an equivalence relation on $A$ such that there are only finitely many distinct equivalence classes $A_1,A_2,\ldots,A_k$ w.r.t $R$. Show that $$A=\bigcup_{i=1}^k A_i$$

Since $A_i\subset A$ for each $i$, $$\bigcup_{i=1}^{k}A_i \subseteq A$$. For the other side, Let $a \in A$. Then $a \sim a$. Hence $a \in Cl(a)$. Since there are only finitely many equivalence classes, $Cl(a)=A_i$. Then $a \in \bigcup_{i=1}^{k} A_i$. And we are done.

Another one on the same lines: Show that $$R=\bigcup_{i=1}^{k}A_i\times A_i$$ For this: Let $(x,y) \in R$. Then $x \sim y$. Hence $x,y \in A_i$ for some $i$. Then $(x,y) \in A_i \times A_i \implies (x,y)\in \bigcup_{i=1}^{k}A_i \implies R \subseteq \bigcup _{i=1}^{k}A_i $.

For the other side let $(a,b) \in \bigcup _{i=1}^{k}A_i \times A_i$ which gives $(a,b) \in A_j \times A_j$ for some $j$ . Hence $a \in A_j$ and $b \in A_j$ and hence $a \sim b$. So $(a,b) \in R$. So $\bigcup _{i=1}^{k}A_i \times A_i \subseteq R$ .

Is this alright??

Thanks for the help!!

  • $\begingroup$ Normally one asserts in addition that the union is disjoint. You might want to double check if you need to do this. (To be clear: it might be that you are not asked to do this, but it also might be you overlooked some dot over the union symbol or something like that.) $\endgroup$ – quid Aug 5 '14 at 14:54
  • $\begingroup$ finiteness is not necessary as long as the family you are given is of distinct equivalences classes the result holds true. $\endgroup$ – Anurag A Aug 5 '14 at 14:54
  • $\begingroup$ @AnuragA the question mentions finite $\endgroup$ – tattwamasi amrutam Aug 5 '14 at 14:55
  • 1
    $\begingroup$ @quid. There is no dot over the union symbol $\endgroup$ – tattwamasi amrutam Aug 5 '14 at 14:56
  • 1
    $\begingroup$ @tattwamasiamrutam yes I know but I just wanted to point out the statement is true in general. All you need to make sure is that the family $\{A_i\}$ has all possible equivalence classes. $\endgroup$ – Anurag A Aug 5 '14 at 14:56

Since $a \in [a]$, we must have $A = \cup_{a \in A} [a]$. This is true whether or not the number of equivalence classes is finite or not.

If we let $A/{\sim} $ denote the equivalence classes, we have $A = \cup_{B \in A /{\sim}} B$.

If it happens that $A /{\sim} = \{ A_1,...,A_k \}$, you can write $A = \cup_{i=1}^k A_i$.

  • $\begingroup$ take a look now $\endgroup$ – tattwamasi amrutam Aug 5 '14 at 15:53
  • $\begingroup$ The addition looks good. In general, you should add a new question rather than piggy-backing on an existing one. $\endgroup$ – copper.hat Aug 5 '14 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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