Miscellaneous · Q7 (MCQ): Equivalence relations containing (1, 2): how many?

Basics you need

Solution

1. The pairs every such relation must contain

   Let $R$ be an equivalence relation on $A$ with $(1,2) \in R$⁠.

   • Reflexive: $(1,1), (2,2), (3,3) \in R$⁠.
   • Symmetric, applied to $(1,2)$⁠: $(2,1) \in R$⁠.

   So every such $R$ contains

   $$S_1 = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}.$$

   $S_1$ is itself an equivalence relation: it is reflexive, it is symmetric ($(1,2)$ and $(2,1)$ are both present), and it is transitive, because the only chains through two different elements are $(1,2),(2,1)$⁠, giving $(1,1) \in S_1$⁠, and $(2,1),(1,2)$⁠, giving $(2,2) \in S_1$⁠; chains using a loop $(a,a)$ just return a pair already in $S_1$⁠. So $S_1$ counts.

   The question says "containing $(1,2)$" only, but symmetry forces $(2,1)$ as well, so this question asks for the same count as the textbook's Example 24 ("containing $(1,2)$ and $(2,1)$"). Starting from the smallest possible relation is the textbook's method there.
   A chain $(a,a),(a,c)$ or $(a,c),(c,c)$ always gives back $(a,c)$⁠, which is already present, so loops never create new transitivity demands. Basics: reflexive, symmetric, transitive

2. The free pairs, and the four symmetric candidates

   Of the 9 pairs in $A \times A$⁠, the 5 in $S_1$ are forced, leaving 4 undecided: $(1,3), (3,1), (2,3), (3,2)$⁠. That gives $2^4 = 16$ ways to choose which to add. Symmetry requires $(1,3)$ and $(3,1)$ to be added together or not at all, and the same for $(2,3)$ and $(3,2)$⁠. So only 4 of the 16 choices are symmetric:

   $$\begin{aligned} &S_1, \qquad T_{13} = S_1 \cup \{(1,3),(3,1)\},\\ &T_{23} = S_1 \cup \{(2,3),(3,2)\}, \qquad A \times A. \end{aligned}$$
   Every equivalence relation containing $(1,2)$ is $S_1$ plus some of the 4 free pairs, and it must be symmetric, so it is one of these four. The four are different from each other, so no relation will be counted twice.
   With symmetry, the two pairs $(a,b), (b,a)$ act as one unit: 2 units, each in or out, gives $2 \times 2 = 4$ candidates.

3. Test the two middle candidates for transitivity

   $T_{13}$ contains $(2,1)$ and $(1,3)$⁠, so transitivity would need $(2,3)$⁠; but $(2,3) \notin T_{13}$⁠. So $T_{13}$ is not transitive.

   $T_{23}$ contains $(1,2)$ and $(2,3)$⁠, so transitivity would need $(1,3)$⁠; but $(1,3) \notin T_{23}$⁠. So $T_{23}$ is not transitive.

   $A \times A$ contains every pair, so it is transitive, and it is reflexive and symmetric too: $A \times A$ counts.

   This is the textbook's observation in Example 24: once 3 is linked to either 1 or 2, transitivity drags in the link to the other one, and symmetry then fills in the reverse, so the relation grows all the way to $A \times A$⁠. There is no way to link 3 to only one of them.
   Universal relation $A \times A$ (Definition 2) is an equivalence relation, since every pair it could need is present.

4. The same answer through equivalence classes

   Each equivalence relation on $\{1,2,3\}$ corresponds to a way of splitting $\{1,2,3\}$ into classes. There are exactly five splittings:

   Two of the five keep 1 and 2 together, matching the two relations found in Steps 1 to 3.

   This check uses a completely different route (classes instead of pairs), so agreement is strong evidence. It also explains the answer in one line: 1 and 2 share a class, and 3 either joins it or forms its own class.
   An equivalence relation divides the set into mutually disjoint classes whose union is the set, and conversely (Section 1.2, after Example 5). Lesson: equivalence relations

5. Count: every possibility exactly once

   Every equivalence relation containing $(1,2)$ is one of the four symmetric candidates of Step 2. Of these, $S_1$ and $A \times A$ are equivalence relations and $T_{13}$⁠, $T_{23}$ are not. So there are exactly 2.

   The list in Step 2 contains every possibility (nothing missed) and each candidate once (nothing doubled), and Steps 1 and 3 checked each candidate against all three properties.

6. Check every option

   Option	Verdict	Why
   (A) 1	wrong	Counts only the smallest relation $S_1$ and forgets the universal relation $A \times A$⁠, which also contains $(1,2)$⁠.
   (B) 2	correct	Exactly $S_1$ and $A \times A$⁠.
   (C) 3	wrong	Would require one of $T_{13}, T_{23}$ to be an equivalence relation, but both fail transitivity.
   (D) 4	wrong	Counts all four reflexive symmetric candidates, ignoring transitivity.

   The complete list makes every other number impossible, and each wrong option corresponds to a specific overlooked relation or skipped condition.

Every fact used, and where it comes from