Question

The number of non-empty equivalence relations on the set \(\{1,2,3\}\) is :

• A. 6
• B. 7
• C. 5
• D. 4

Hint:

To count the number of equivalence relations, find all the possible partitions of the set.

Answer 1

The Correct Option is C

To determine the number of non-empty equivalence relations on the set \(\{1,2,3\}\), we need to find the number of partitions of this set. An equivalence relation corresponds to a partition of the set, and we enumerate the possible partitions of the set \(\{1,2,3\}\) as follows:

• Partition with one subset (trivial partition): \(\{\{1,2,3\}\}\)
• Partitions with two subsets:
  • \(\{\{1\},\{2,3\}\}\)
  • \(\{\{2\},\{1,3\}\}\)
  • \(\{\{3\},\{1,2\}\}\)
• Partition with three subsets: \(\{\{1\},\{2\},\{3\}\}\)

Counting these partitions, we find there are 5 distinct ways to partition the set \(\{1,2,3\}\). Hence, the number of non-empty equivalence relations on the set \(\{1,2,3\}\) is 5.

Answer 2

Recall: equivalence relations on a set are in one-to-one correspondence with partitions of that set (each equivalence class is a block of the partition).

1. So we need the number of partitions of a $3$-element set. This is the Bell number $B_3$.
2. List all partitions of $ \{1,2,3\} $ explicitly:
   • $\{\{1,2,3\}\}$ — one block (all elements equivalent).
   • $\{\{1\},\{2,3\}\}$.
   • $\{\{2\},\{1,3\}\}$.
   • $\{\{3\},\{1,2\}\}$.
   • $\{\{1\},\{2\},\{3\}\}$ — three singleton blocks (only identity pairs).
3. Each partition gives exactly one equivalence relation. Hence there are $5$ partitions, so $5$ equivalence relations.
4. (If useful, the corresponding relations written as sets of ordered pairs are:)
   • For $\{\{1,2,3\}\}$: $\{(i,j): i,j\in\{1,2,3\}\}$ (all $9$ pairs).
   • For $\{\{1\},\{2,3\}\}$: $\{(1,1),(2,2),(3,3),(2,3),(3,2)\}$.
   • For $\{\{2\},\{1,3\}\}$: $\{(1,1),(2,2),(3,3),(1,3),(3,1)\}$.
   • For $\{\{3\},\{1,2\}\}$: $\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$.
   • For $\{\{1\},\{2\},\{3\}\}$: $\{(1,1),(2,2),(3,3)\}$ (identity relation).

Answer

The number of equivalence relations on $\{1,2,3\}$ is $5$. (Option 3)