How do you find the number of equivalence classes in a equivalence relation?

Thanks,

Joan.

Printable View

- Nov 8th 2010, 05:04 PMjuxiEquivalence Classes.
How do you find the number of equivalence classes in a equivalence relation?

Thanks,

Joan. - Nov 9th 2010, 07:17 AMemakarov
There is no general recipe. It depends on the relation and how it is presented.

If each equivalence class has n elements and the set on which the relation is given has m elements, then, obviously, the number of classes is m / n (since classes form a partition of the set). For another example, Myhill–Nerode theorem from the theory of formal languages states that a language L is regular (described by a regular expression or accepted by a finite automaton) iff the number of classes of the relation associated with L is finite. Thus, finding the number of classes helps determine if the language is regular, which may not be a trivial task.