Counting equivalence classe - proof theorem

601 Views Asked by At

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.

1

There are 1 best solutions below

3
On

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