If S is finite then the equivalence classes will not exceed the size of set S

Question

If S is a finite set and $\sim$ is an equivalence relation on it, then the total number of equivalence classes can never exceed $\vert S\vert$ and it can be any integer number $1\leq k\leq\vert S\vert$. Is this true?

Answer 1

This is true. One way to think about an equivalence relation is as a partition of a set. Think about dividing a set up into disjoint subsets. The largest number of partitions is achieved when you let $x\sim x\Leftrightarrow x=x$, so the number of classes can never exceed $|S|$. You can achieve $k$ classes by having $k-1$ singleton classes, and letting the remaining $|S|-k+1$ elements of $S$ be mutually equivalent.

Answer 2

The equivalence classes partition $S$ which means

$$S=\cup_iE_i$$ $$i\neq j\Rightarrow E_i\cap E_j=\phi$$

So if we assume each class is made of one element we see that the number of classes cannot exceed $|S|$

Now the second claim is slightly more subtle. Take any partition of $S$ in other words any set of disjoint subsets whose union is $S$ and define $x\sim y\iff \exists i, \quad x\in E_i\land y\in E_i$. We have $\sim$ is an equivalence whose equivalence classes are exactly $E_i$