How do you find the number of equivalence classes in a equivalence relation?
Thanks,
Joan.
Printable View
How do you find the number of equivalence classes in a equivalence relation?
Thanks,
Joan.
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.