0

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?

5xum
  • 123,496
  • 6
  • 128
  • 204
Lynnie
  • 475
  • 2
  • 6
  • 14
  • 1
    Are the equivalence classes finite? Suppose you partition the integers into even and odd? – almagest Sep 09 '14 at 07:52
  • 1
    Hint: Consider the trivial equivalence relation ($a \mbox{ equivalent to } b:=\Leftrightarrow a,b\in S$) on an arbitrary set $S$. –  Sep 09 '14 at 07:54

3 Answers3

2

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?

Andrea Mori
  • 26,969
1

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.

5xum
  • 123,496
  • 6
  • 128
  • 204
1

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

Peter Huxford
  • 2,561