Number of Equivalence relations of $\{1,2,3\}$

Let $M$ be the set $\{1,2,3\}$. How many Equivalence relations $R \subset M \times M$ exists?

My idea is to count the disjoint partitions of M:

$K_1= \{\{1\},\{2\},\{3\}\}\Leftrightarrow\{(1,1),(2,2),(3,3)\}$

$K_2= \{\{1,2\},\{3\}\} \Leftrightarrow\{(1,1),(1,2),(2,1),(2,2),(3,3)\} $

$K_3= \{\{1,3\},\{2\}\}\Leftrightarrow\{(1,1),(1,3),(3,1),(2,2),(3,3)\}$

$K_4= \{\{1\},\{2,3\}\}\Leftrightarrow\{(1,1),(2,3),(3,2),(2,2),(3,3)\}$

$K_5=\{1,2,3\}\Leftrightarrow K_5=M^2$

So the answer would be $5$. Is this correct? Reflexivity and Symmetry are obvious, but how can i check the right side for Transitivity?

Solution 1:

There are good comments already above; I'm just spelling them out:

If $X = \bigsqcup_i X_i$ is partition of set $X$ into disjoint $X_i$'s, then we can declare equivalence relationon $X$ by $x\sim y$ if $x,y\in X_i$ for some $i$. Symmetry and reflexivity is obvious, and as you asked Transitivity really means asking: If $x,y\in X_i$, and $y,z\in X_j$, then are $x,z\in X_k$ for some $k$? Well, $X_i$'s were disjoint, so $y\in X_i$ and $y\in X_j$ means $X_i = X_j$, hence $x,z\in X_i$. So yes.

So any partition of a set gives a equivalence relation.

On the other hand, any equivalence relation gives a partition of a set where each disjoint sets are just equivalence classes (i.e. collect together elements that are equivalent to each other). This needs slightly more careful checking, but is very believable.

So, in conclusion, giving a equivalence relation is actually just the same thing as giving a partition of a set, as you accurately noticed already.