Key Concepts and Formulas

• Equivalence Relation: A relation $R$ on a set $S$ is an equivalence relation if it is reflexive, symmetric, and transitive.
• Partition of a Set: A partition of a set $S$ is a collection of non-empty, pairwise disjoint subsets of $S$ whose union is $S$.
• Correspondence: There is a one-to-one correspondence between the set of equivalence relations on a set $S$ and the set of partitions of $S$. The equivalence classes of an equivalence relation form a partition of the set, and conversely, any partition of a set defines an equivalence relation.
• Bell Numbers ($B_n$): The number of partitions of a set with $n$ elements. $B_n = \sum_{k=0}^n S(n,k)$, where $S(n,k)$ are Stirling numbers of the second kind. For non-empty sets, we sum from $k=1$.

Step-by-Step Solution

The problem asks for the number of non-empty equivalence relations on the set $S = \{1, 2, 3\}$. We know that the number of non-empty equivalence relations on a set is equal to the number of partitions of that set. Therefore, we need to find the number of ways to partition the set $\{1, 2, 3\}$ into non-empty, disjoint subsets whose union is $\{1, 2, 3\}$.

Step 1: Identify the set and its size. The given set is $S = \{1, 2, 3\}$. The size of the set is $n = 3$.

Step 2: Enumerate partitions based on the number of subsets (blocks). We will systematically list all possible partitions of $S$ by considering the number of blocks (non-empty subsets) in the partition.

• Case 1: Partition into 1 block. This means all elements are grouped into a single subset. The only partition is $\{\{1, 2, 3\}\}$. There is 1 such partition.

• Case 2: Partition into 2 blocks. We need to divide the set $\{1, 2, 3\}$ into two non-empty subsets. The only possible distribution of elements is one subset with 1 element and another subset with 2 elements. To form these partitions, we can choose 1 element to be in a singleton set, and the remaining 2 elements will form the other set. The number of ways to choose 1 element from 3 is $\binom{3}{1} = 3$. The possible partitions are:

  1. $\{\{1\}, \{2, 3\}\}$
  2. $\{\{2\}, \{1, 3\}\}$
  3. $\{\{3\}, \{1, 2\}\}$ There are 3 such partitions.

• Case 3: Partition into 3 blocks. This means each element forms its own singleton subset. The only partition is $\{\{1\}, \{2\}, \{3\}\}$. There is 1 such partition.

Step 3: Sum the number of partitions from each case. Total number of partitions = (Number of partitions with 1 block) + (Number of partitions with 2 blocks) + (Number of partitions with 3 blocks) Total number of partitions = $1 + 3 + 1 = 5$.

Step 4: Relate the number of partitions to the number of equivalence relations. Since there is a one-to-one correspondence between the partitions of a set and the equivalence relations on that set, the number of non-empty equivalence relations on $\{1, 2, 3\}$ is equal to the total number of partitions of $\{1, 2, 3\}$.

Therefore, there are 5 non-empty equivalence relations on the set $\{1, 2, 3\}$.

Common Mistakes & Tips

• Forgetting Reflexivity: Equivalence relations must always be reflexive, meaning $(a, a)$ is in the relation for every $a$. This ensures that all equivalence relations on a non-empty set are non-empty.
• Confusing Relations with Partitions: While related, it's important to remember that the question asks for the number of relations, which we find by counting partitions. Listing actual relations can be tedious and error-prone.
• Bell Numbers: For larger sets, the number of partitions grows rapidly. The number of partitions of a set of size $n$ is given by the $n$-th Bell number ($B_n$). For $n=3$, $B_3 = 5$.

Summary

The problem requires us to count the number of non-empty equivalence relations on the set $\{1, 2, 3\}$. This is equivalent to finding the number of distinct partitions of the set $\{1, 2, 3\}$. By systematically enumerating partitions based on the number of subsets (1, 2, or 3 blocks), we found there is 1 partition with 1 block, 3 partitions with 2 blocks, and 1 partition with 3 blocks. Summing these up gives a total of $1 + 3 + 1 = 5$ partitions, which corresponds to 5 non-empty equivalence relations.

The final answer is $\boxed{5}$, which corresponds to option (C).