0
$\begingroup$

My Assignment Question:

If $R$ is an equivalence relation on a set $S$ and it has only finitely many equivalence classes altogether, then $S$ itself is a finite set.

From the theorem for Equivailence classes, i know that if $R$ is an equivalence class on set $S$ then the equivalence class of $X$ forms a partition of the set $X$.

Converse is $P=\{X_i\}_i$ is a partition of set $X$ then there is an equivalence relation on $X$ with equivalence class $X_i$ .

Does finitely equivalence class implies finite set?

$\endgroup$
  • 1
    $\begingroup$ Are the equivalence classes finite? Suppose you partition the integers into even and odd? $\endgroup$ – almagest Sep 9 '14 at 7:52
  • 1
    $\begingroup$ Hint: Consider the trivial equivalence relation ($a \mbox{ equivalent to } b:=\Leftrightarrow a,b\in S$) on an arbitrary set $S$. $\endgroup$ – mathmax Sep 9 '14 at 7:54
1
$\begingroup$

If R is an equivalence relation on a set S and it has only finitely many equivalence classes altogether, then S itself is a finite set.

This is a false statement. For example, taking $S=\mathbb R\setminus\{0\}$ and defining $R$ as $$xRy\iff \mathrm{sign}(xy)>0$$ means that there exist only two equivalence classes on $\mathbb R$, the set $(-\infty, 0)$ and $(0,\infty)$. $S$, however, is not a finite set.

$\endgroup$
2
$\begingroup$

You sure know that an equivalence relation on a set $S$ defines a partition of $S$.

So the situation now is that you have a partition. $$ S=S_1\cup S_2\cup\cdots\cup S_k. $$ Is this enough to deduce that $S$ is a finite set? How does the cardinality of $S$ relate to the cardinalities of the $S_i$?

HINT: Take any infinite set (of your choice) and try to partition into a finite number of parts. Can you succeed?

$\endgroup$
1
$\begingroup$

As a non trivial counterexample, consider the equivalence relation $\mathbb{Z}$, where $a\equiv b \iff 3\mid a-b$. It's easy to check that this is an equivalence relation on $\mathbb{Z}$, however there are three equivalence classes: $[0],[1],[2]$, corresponding to each of the possible remainders upon division by $3$.

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