Miscellaneous · Q6 (MCQ): Reflexive and symmetric but not transitive: how many?

Basics you need

Solution

1. The pairs every such relation must contain

   Let $R$ be any relation with all the required properties.

   • Given: $(1,2) \in R$ and $(1,3) \in R$⁠.
   • Reflexive: $(1,1), (2,2), (3,3) \in R$⁠.
   • Symmetric, applied to the given pairs: $(2,1) \in R$ and $(3,1) \in R$⁠.

   So every qualifying $R$ contains the 7 pairs

   $$\begin{aligned} R_1 = \{&(1,1), (2,2), (3,3),\\ &(1,2), (2,1), (1,3), (3,1)\}. \end{aligned}$$
   Starting from the forced pairs shrinks the search from 512 relations to a handful. Each of the 7 pairs is forced by one stated condition, so no qualifying relation can leave any of them out.
   Reflexive and symmetric are both "must contain" conditions: they add pairs. Transitive is also a "must contain" condition, which is why "not transitive" is the condition that limits how much we may add. Basics: reflexive, symmetric, transitive

2. Only two pairs are left, and symmetry pairs them

   $A \times A$ has 9 pairs and $R_1$ has 7, so the undecided pairs are $(2,3)$ and $(3,2)$⁠. There are $2 \times 2 = 4$ ways to decide them:

   Add to $R_1$	Symmetric?
   nothing	yes (checked in Step 3)
   $(2,3)$ only	no: $(2,3)$ in, $(3,2)$ out
   $(3,2)$ only	no: $(3,2)$ in, $(2,3)$ out
   both	yes: this is all of $A \times A$

   So exactly two relations are reflexive, symmetric and contain $(1,2)$ and $(1,3)$⁠: $R_1$ and $R_2 = A \times A$⁠.

   Any qualifying relation equals $R_1$ plus some choice of the free pairs, and the four rows above are all the possible choices, with no overlap. Symmetry removes the two middle rows, because each contains a pair without its reverse.
   With 2 free pairs, each in or out, there are $2^2 = 4$ choices (multiplication principle). Basics: counting choices

3. Candidate $R_1$⁠: reflexive, symmetric, not transitive

   Reflexive: $(1,1), (2,2), (3,3) \in R_1$⁠. Symmetric: the non-loop pairs come in reverse pairs, $(1,2)$ with $(2,1)$ and $(1,3)$ with $(3,1)$⁠, and each loop $(a,a)$ is its own reverse. Not transitive:

   $$\begin{aligned} &(2,1) \in R_1 \ \text{and}\ (1,3) \in R_1,\\ &\text{but}\ (2,3) \notin R_1. \end{aligned}$$

   So $R_1$ has every required property, and it counts.

   For "not transitive" one failing chain is enough (Basic 3). The chain goes through 1, because 1 is the only element joined to both 2 and 3. A second failing chain, $(3,1), (1,2)$ with $(3,2) \notin R_1$⁠, also exists, but one is all we need.
   Transitive fails when some $(a,b), (b,c)$ are in $R$ but $(a,c)$ is not (Definition 3(iii)).

4. Candidate $R_2 = A \times A$⁠: transitive, so rejected

   $R_2$ contains every pair of $A \times A$⁠. So whenever $(a,b)$ and $(b,c)$ are in $R_2$⁠, the pair $(a,c)$ is in $R_2$ as well, because every pair is. Hence $R_2$ is transitive, and it does not meet the requirement "not transitive".

   The universal relation is transitive (indeed an equivalence relation), so it must be excluded. Missing this is the main way to get the wrong answer (B).
   The universal relation $A \times A$ (Definition 2) is reflexive, symmetric and transitive.

5. Count: every possibility exactly once

   Every relation that meets the conditions must contain $R_1$ (Step 1), so it is one of the four relations in the table of Step 2. Two of those are not symmetric, and $A \times A$ is transitive. Only $R_1$ remains, and Step 3 showed it qualifies. The four rows are different relations, so nothing is counted twice. Hence the number of such relations is 1.

   An exact count needs two halves: no qualifying relation is missed (Step 1 shows every one has the form $R_1$ plus free pairs, and Step 2 lists all such forms) and nothing is counted wrongly (each candidate was checked against every condition). This is the same method the textbook uses in Example 23.

6. Check every option

   Option	Verdict	Why
   (A) 1	correct	Only $R_1$ is reflexive, symmetric, contains $(1,2),(1,3)$ and is not transitive.
   (B) 2	wrong	Counts both reflexive symmetric candidates, $R_1$ and $A \times A$⁠, forgetting that $A \times A$ is transitive.
   (C) 3	wrong	Would need a third candidate, but after the 7 forced pairs only the 4 fillings of Step 2 exist, and 3 of them fail a condition.
   (D) 4	wrong	Counts all 4 fillings of $(2,3),(3,2)$⁠, ignoring both symmetry and the "not transitive" condition.

   An MCQ answer is safest when every wrong option is explained. The count 1 came from a complete list, so any other number is impossible, and each wrong option matches a specific skipped condition.

Every fact used, and where it comes from