4
$\begingroup$

Suppose I have an equivalence relation $\sim$ on $S=\{e,f,g,h,i\}$ such that $e \sim f, f \sim g$ and $e \nsim i$. I’m trying to find the number of such relations that can be defined on $S$. I know that $\{e,f,g\}$ will always be an equivalence class and that $\{i\}$ will also always be an equivalence class. The questions therefore is equivalent to asking how many different equivalence classes can $h$ belong to and the answer is obviously $3$ since it can belong to its own equivalence class $\{h\}$, $\{i\}$ or $\{e,f,g\}$. However I’m not sure if it’s possible that $h$ does not belong to any equivalence class, i.e. the set of equivalence classes for the relations would be $\{\{e,f,g\},\{i\}\}$. I think the answer is no because the set of equivalence classes has to partition $S$ but I’m not 100% sure.

$\endgroup$
8
$\begingroup$

An equivalence relation most certainly has to completely partition the set. It follows from the reflexivity requirement: at the very least, each element must be equivalent to itself, therefore constituting an equivalence class of its own.

$\endgroup$
7
$\begingroup$

There is a bijection between the set of equivalence relations on a set, and the partitions of that set. This allows us to switch between these notions fluidly.


That is, we know that $e,f,g$ are in the same equivalence class, which is one that is different from $i$. So, it is a question of where you place $h$, as you mentioned. The answer to your last part , is that it has to be part of its own equivalence class, since it is related to itself, and therefore must appear in one of the classes. Alternately, a partition covers every element, so must cover $h$. This gives us just the three possibilities, of $1.[e,f,g,h],[i]$ , $2 . [e,f,g],[h],[i]$, and $3. [e,f,g],[h,i]$.

$\endgroup$

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.