The Stirling numbers $S(m,n)$ of second kind gives the number of ways a set with n elements can be partitioned into n disjoint nonempty sets.
I understand this, but in some books it is defined that,
they count the number of different equivalence relations with precisely $n$ equivalence classes that can be defined on an $m$ element set
Considering the example:
The set $\{1,2,3\}$ can be partitioned into 2 subsets in the following ways $$ \{\{1,2\},\{3\}\}, \{\{1,3\},\{2\}\}, \{\{1\},\{2,3\}\} $$
why do we call these disjoint subsets as equivalence classes, what is the equivalence relation here ?
(The Fundamental Theorem of Equivalence Relations may be of interest.)
The relation is the pairs of elements $(x, y)$ such that x and y appear in the same block of the partition. Why does this work?
Let $P$ be a partition of a set $X$. Here's a sketch of why the relation $$\sim ~=~\{(x, y) \hspace{1pt}| \hspace{1pt} \text{$x$ and $y$ are in the same block of $P$} \}$$ $$\text{ (that is,} \text{ there is some } P_i \in P \text{ such that } x \in P_i \text{ and } y\in P_i )$$
is an equivalence relation.
From the definition of a partition, we know that for each $x \in X$, there is exactly one $P_i \in P$ such that $x \in P_i$.
First, let $x \in X$ be an element of the block $P_i \in P$. Since $x \in P_i$ and $x \in P_i$, $x\sim x$, and $\sim$ is reflexive.
Now, let $x \in X$ be an element of the block $P_i \in P$. If $x \sim y$ for some $y \in X$, then $y \in P_i$. Since $y \in P_i$ and $x\in P_i$, we have $y \sim x$, and $\sim$ is symmetric.
Last, we want to show if $x\sim y$ and $y \sim z$ for all $x, y, z \in X$, then $x \sim z$. Fix such an $x, y, z$. Let $x \in P_i$. Then $y \in P_i$, since $x \sim y$. Since $y \in P_i$, $y$ is only in the block $P_i$, and so for $y \sim z$ to be true, we must have $z \in P_i$. So $z \in P_i$. But since $x \in P_i$ and $z\in P_i$, we have $x\sim z$. Now forgetting we've fixed $x, y, z$, we've shown that $\sim$ is transitive.
Since we've shown $\sim$ is reflexive, symmetric, and transitive, it is an equivalence relation on $X$.
It can also be shown that the equivalence classes of an equivalence relation form a partition, and that the mapping sending each partition $P$ to the equivalence relation defined above is the mutual inverse of the mapping that maps an equivalence relation to the partition formed by its equivalence classes. The existence of these bijections means that if the sets of equivalence relations on a set $X$ and partitions of $X$ are finite, then the size of one is the size of the other.