Example 24: Equivalence relations containing (1, 2): counting

Basics you need

Solution

1. The smallest candidate $R_1$

   Every relation we are counting contains $(1,2)$ and $(2,1)$ (given) and, being reflexive, $(1,1), (2,2), (3,3)$⁠. So it contains

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

   Check that $R_1$ is itself an equivalence relation:

   • Reflexive: all three loops are present.
   • Symmetric: loops are their own mirrors, and the only other pairs, $(1,2)$ and $(2,1)$⁠, are mirrors of each other.
   • Transitive: the only chains of two non-loop pairs are $(1,2),(2,1)$⁠, giving $(1,1)$⁠, and $(2,1),(1,2)$⁠, giving $(2,2)$⁠. Both are in $R_1$⁠. Chains through a loop give back a pair already present.

   So $R_1$ is an equivalence relation, and it is contained in every relation we want.

   Starting from what is forced splits the problem in two: everything in $R_1$ is compulsory, and the only question left is which of the remaining pairs may be added. We check $R_1$ itself carefully, because if it failed one of the properties it would not count.
   Definition 4: an equivalence relation is reflexive, symmetric and transitive. For transitivity on a finite relation, only chains of two non-loop pairs can produce something new.

2. The four leftover pairs come in two mirror pairs

   $A\times A$ has 9 pairs and $R_1$ has 5, so 4 remain:

   $$(2,3),\ (3,2),\ (1,3),\ (3,1).$$

   Group them with their mirrors:

   $$P = \{(2,3), (3,2)\}, \qquad Q = \{(1,3), (3,1)\}.$$

   If an equivalence relation contains $(2,3)$ it must contain $(3,2)$⁠, and the other way round; likewise for $Q$⁠. So any equivalence relation we want is one of

   $$R_1, \qquad R_1\cup P, \qquad R_1\cup Q, \qquad R_1\cup P\cup Q.$$
   There are $2^4 = 16$ ways to choose which of the 4 leftover pairs to add. Symmetry immediately throws out the 12 choices that include one pair of $P$ or $Q$ without its mirror (for instance, adding $(2,3)$ alone leaves $(2,3)$ without $(3,2)$⁠). Only the 4 choices that respect mirror pairs remain.
   Symmetric means every pair's mirror is also present (Basic 3). So pairs join a symmetric relation two at a time.

3. Adding only one mirror pair breaks transitivity

   $R_1\cup P$ contains $(1,2)$ and $(2,3)$⁠. Transitivity would need $(1,3)$⁠, but $(1,3)\in Q$⁠, which was not added:

   $$(1,2),\ (2,3) \in R_1\cup P \quad\text{but}\quad (1,3)\notin R_1\cup P.$$

   $R_1\cup Q$ contains $(2,1)$ and $(1,3)$⁠. Transitivity would need $(2,3)$⁠, but $(2,3)\in P$⁠, which was not added:

   $$(2,1),\ (1,3) \in R_1\cup Q \quad\text{but}\quad (2,3)\notin R_1\cup Q.$$

   So neither $R_1\cup P$ nor $R_1\cup Q$ is an equivalence relation.

   This is the textbook's "for transitivity we are forced to add $(1,3)$ and $(3,1)$". Relating 3 to 2 while 2 is already related to 1 forces 3 to be related to 1, and the same with the roles of 1 and 2 swapped. Each mirror pair drags in the other.
   One chain with a missing shortcut disproves transitivity (Basic 5).

4. Adding both gives the universal relation, which works

   $R_1\cup P\cup Q$ contains all 9 pairs, so it is the universal relation $A\times A$⁠. It is reflexive (all loops present), symmetric (every mirror is present, since every pair is) and transitive (every shortcut $(a,c)$ is present, since every pair is). So the universal relation is an equivalence relation containing $(1,2)$ and $(2,1)$.

   The universal relation always has all three properties, because each property only ever asks for some pair to be present, and every pair is. So the "add everything" option always works.
   The universal relation $A\times A$ (Definition 2) is an equivalence relation on any set $A$⁠. Equivalence classes partition the set (Basic 4).

5. Count

   Of the four candidates in Step 2, exactly two are equivalence relations:

   $$\begin{gathered} R_1 = \{(1,1),(2,2),(3,3),(1,2),(2,1)\} \\ \text{and}\quad A\times A. \end{gathered}$$

   Hence the number of equivalence relations in $\{1,2,3\}$ containing $(1,2)$ and $(2,1)$ is two.

   Every relation we want contains $R_1$ (Step 1), every enlargement either breaks symmetry (Step 2), breaks transitivity (Step 3), or is the universal relation (Step 4). Nothing was left unchecked, so the count is exactly two. The picture gives the same answer: 3 can go with $\{1,2\}$ or on its own, two choices.

Every fact used, and where it comes from