Question

The number of equivalence relations on the set $\{1,2,3,4\}$ is

• A. 15
• B. 16
• C. 24
• D. 4

Answer 1

The correct option is A 15

Corresponding to every partition of the set $\{1,2,3,4\}$, there exists a unique equivalence relation. So we count every type of unordered partitions of the set of 4 elements into one block, two block, three block and four block partitions, as shown below:
$4$
$\stackrel{\downarrow }{4}=\frac{4!}{4!}=1$
=$\frac{4!}{3!}+\frac{4!}{2!2!2!}=4+3=7$
$=\frac{4!}{2!2!}=6$

$=\frac{4!}{4!}=1$

Total $=1+7+6+1=15$
So the number of equivalence relations on the set $\{1,2,3,4\}$ is 15.