2

THEOREM: (Counting equivalence classes)

Let $R$ be an equivalence relation on a finite set $A$.
If all the equivalence relation of a finite set $A$ have the same size, $m$, then the number of equivalence classes is $|A|/m$.

First comment, I think that the number of equivalence class is always $|A|$, because $\forall a \in A : a \in [a]$.
In general we suppose different equivalence classes on $A$ like the theorem. Is that correct?

proof

Let $R$ be an equivalence relation on a finite set A and all the equivalence classes of $R$ have the same size $m$. So, each equivalence class contains $m$ elements, $[a_1] = \{a_1, a_2, \dots,a_m\}$ and we know (every element is related to itself) $a_1 \in [a_1], a_2 \in [a_2], \dots, a_m \in [a_m]$. Because if $[a_i] \cap [a_j] \neq \emptyset, 1 \leq i < j \leq m$, then $[a_i] = [a_j]$. We have $m$ same equivalence classes.

Now, I am not sure how continue...

It can be question like this. We have 100 beads, and 10 different colours. Each colours have 10 beads (e. g. blue has 10 beads, green has 10 bead, and so on). How many different (by colour) beads we have? Of course answer is 100/10 = 10.

How many different equivalence classes we have? - immediately, the answer is $|A|/m$.

Can you please check my proof? If it's ok, then please help me reformulate the end of the proof. Else say where is the problem. Thank you.

Kapur
  • 489

1 Answers1

1

Your argument First comment, I think that the number of equivalence class is always $|A|$, because $\forall a \in A : a \in [a]$. is not correct.

It is true that $a \in [a]$ for all $a \in A$. However, you can have (as soon a class has more than one element), $a\neq b$ and $[a] = [b]$. This will induce that the number of equivalence classes with be smaller than $\vert A \vert$.

Then regarding the theorem itself. The equivalence classes form a partition of $A$ (see Fundamental theorem of equivalence relations paragraph in Equivalence relation - Wikipedia). Therefore if all the equivalence classes have the same number of elements $m$, the number of equivalence classes is $\vert A \vert /m$.

mathcounterexamples.net
  • 70,018
  • Yes i agree that number of equivalence classes are not always $|A|$. How can this help with my proof? - After I say "We have $m$ same equivalence classes", then say - This induce that the numbef of equivalence classes with be smaller than $m$ factor, so we have $|A|/m$. But I need say, what is the $|A|$. Can I say this is maximum number of equivalence classes? – Kapur Aug 22 '18 at 20:31
  • @Kapur See my updated answer. – mathcounterexamples.net Aug 22 '18 at 20:34
  • So I can the theorem (in main post) rewrite in partition like this: Let $P$ be a partition on a finite set $A$. If all the parts of $P$ have the same size $m$, then the number of parts is $|A|/m$. And now is nothing to prove, beacuse answer is immediately $|A|/m$ parts. Therefore $|A|/m$ equivalence classes. Can be this another version of proof? – Kapur Aug 22 '18 at 21:25