Example 23: Reflexive, transitive, not symmetric: counting

Basics you need

Solution

1. Pairs forced by "reflexive" and by the question

   The question requires $(1,2)\in R$ and $(2,3)\in R$⁠. Reflexive requires $(a,a)\in R$ for each $a\in A$⁠, so

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

   So far five pairs are forced.

   We are counting relations with several properties at once. The cleanest way is to first collect everything those properties force, because those pairs are in every relation we count and need no further thought.
   Reflexive means every element is related to itself (Definition 3, Basic 2). On $\{1,2,3\}$ that is exactly the three "loops" $(1,1), (2,2), (3,3)$⁠.

2. Transitivity forces $(1,3)$

   Since $(1,2)\in R$ and $(2,3)\in R$⁠, transitivity (with $a=1, b=2, c=3$⁠) demands

   $$(1,2)\in R \ \text{and}\ (2,3)\in R \ \Longrightarrow\ (1,3)\in R.$$

   So every relation we are counting contains the six pairs

   $$R_1 = \{(1,1), (2,2), (3,3), (1,2), (2,3), (1,3)\}.$$
   Without $(1,3)$ the relation would have a chain $1\to2\to3$ with no direct link $1\to3$⁠, which is exactly what transitivity forbids. So $(1,3)$ is not a choice: it is compulsory.
   Transitive: $(a,b), (b,c)\in R \Rightarrow (a,c)\in R$ (Definition 3). One missing "shortcut" is enough to break it (Basic 3).

3. $R_1$ itself is reflexive, transitive and not symmetric

   Reflexive: it contains $(1,1), (2,2), (3,3)$⁠.

   Transitive: the non-loop pairs are $(1,2), (2,3), (1,3)$⁠. The only chain of two of them with matching middle element is $(1,2), (2,3)$⁠, and its shortcut $(1,3)$ is in $R_1$⁠. (The pair $(1,3)$ cannot start a chain, because no non-loop pair begins with 3, and nothing non-loop ends in 1.) Chains through a loop, such as $(1,2),(2,2)$⁠, give back $(1,2)$⁠, already present. So $R_1$ is transitive.

   Not symmetric: $(1,2)\in R_1$ but $(2,1)\notin R_1$⁠.

   So $R_1$ is one of the required relations, and it is the smallest one: every required relation contains it.

   We must check $R_1$ really has all the properties, not just assume it. "Smallest" matters for the counting: since every required relation contains $R_1$⁠, each one is $R_1$ together with some extra pairs, and that is what makes a complete search possible in the next step.
   For transitivity, only chains of two non-loop pairs can produce a new pair (Basic 5). A single counterexample is enough to show "not symmetric" (Basic 3).

4. Only three optional pairs are left, so only 8 candidates

   $A\times A$ has 9 pairs and $R_1$ uses 6. The three left over are

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

   Every required relation is $R_1$ plus some subset of these three pairs. A set of 3 pairs has $2^3 = 8$ subsets, so there are exactly 8 candidates to test.

   Reducing the problem to 8 concrete candidates is what turns "show the number is three" into something we can check completely. Without Steps 1 and 2 we would face $2^9 = 512$ relations on $\{1,2,3\}$⁠.
   A set of $k$ objects has $2^k$ subsets (Basic 4).

5. Test all 8 candidates

   Reflexivity and the two given pairs hold automatically, because every candidate contains $R_1$⁠. So for each candidate we only test transitivity and symmetry. When transitivity fails, the table names a chain whose shortcut is missing.

   Pairs added to $R_1$	Transitive?	Symmetric?	Counts?
   none ($R_1$⁠)	yes (Step 3)	no: $(2,1)$ missing	yes
   $(2,1)$	yes	no: $(2,3)$ in, $(3,2)$ missing	yes ($R_2$⁠)
   $(3,2)$	yes	no: $(1,2)$ in, $(2,1)$ missing	yes ($R_3$⁠)
   $(3,1)$	no: $(3,1),(1,2)$ but $(3,2)$ missing	no	no
   $(2,1), (3,2)$	no: $(3,2),(2,1)$ but $(3,1)$ missing	no	no
   $(2,1), (3,1)$	no: $(3,1),(1,2)$ but $(3,2)$ missing	no	no
   $(3,2), (3,1)$	no: $(2,3),(3,1)$ but $(2,1)$ missing	no	no
   all three	yes (universal relation)	yes	no

   Why the two "yes" rows for transitivity really are transitive:

   • $R_2 = R_1\cup\{(2,1)\}$⁠. The new chains are $(1,2),(2,1)\to(1,1)$⁠, $(2,1),(1,2)\to(2,2)$ and $(2,1),(1,3)\to(2,3)$⁠. All three shortcuts are present, and no other chain uses $(2,1)$ (no non-loop pair other than $(1,2)$ ends in 2). So $R_2$ is transitive.
   • $R_3 = R_1\cup\{(3,2)\}$⁠. The new chains are $(2,3),(3,2)\to(2,2)$⁠, $(3,2),(2,3)\to(3,3)$ and $(1,3),(3,2)\to(1,2)$⁠. All present, so $R_3$ is transitive.
   This table is the textbook's argument written out in full. It says that adding $(3,1)$⁠, or adding both $(2,1)$ and $(3,2)$⁠, forces the remaining pairs in "to maintain transitivity". Indeed, $(3,1)$ forces both $(3,2)$ (via $(3,1),(1,2)$⁠) and $(2,1)$ (via $(2,3),(3,1)$⁠), and the pair $(2,1),(3,2)$ forces $(3,1)$⁠. Once all three are in, we have the universal relation $A\times A$⁠, which is symmetric, so it is not wanted. Every one of the 8 cases is accounted for.
   To disprove transitivity, give one chain with its shortcut missing (Basic 3). To prove it on a finite relation, check every chain of non-loop pairs (Basic 5). The universal relation $A\times A$ (Definition 2, Section 1.2) contains every pair, so it is reflexive, symmetric and transitive.

6. Count the survivors

   Exactly three candidates pass every test:

   $$\begin{aligned} R_1 &= \{(1,1),(2,2),(3,3),(1,2),(2,3),(1,3)\},\\ R_2 &= R_1 \cup \{(2,1)\},\\ R_3 &= R_1 \cup \{(3,2)\}. \end{aligned}$$

   Hence the number of relations containing $(1,2)$ and $(2,3)$ that are reflexive and transitive but not symmetric is three.

   Steps 1 and 2 showed that every relation we want contains $R_1$⁠, and Step 5 tested every way of enlarging $R_1$⁠. So no relation can have been missed, and none counted twice: the 8 candidates are 8 different sets.

Every fact used, and where it comes from