Exercise 1.1 · Q15 (MCQ): Which properties does this relation on {1, 2, 3, 4} have?

Basics you need

Solution

1. Organise the relation

   Put a tick in row $a$⁠, column $b$ when $(a,b)\in R$⁠:

   $a \backslash b$	1	2	3	4
   1	✓	✓	✓
   2		✓
   3		✓	✓
   4				✓

   There are $7$ ticks, one for each pair in the list. The same information as an arrow diagram, with an arrow from $a$ to $b$ for each $(a,b)\in R$ with $a \ne b$⁠, and a loop at $a$ for each $(a,a)\in R$⁠:

   A list of seven pairs in a jumbled order is easy to misread. The table makes reflexivity visible (the diagonal) and symmetry visible (is the table the same after reflecting in the diagonal?), and the diagram makes chains visible as paths of two arrows.
   The diagonal entries of the table are the pairs $(a,a)$⁠. Reflecting a tick in the diagonal turns $(a,b)$ into $(b,a)$⁠.

2. Reflexive: check each of the 4 elements

   $a$	1	2	3	4
   $(a,a)\in R$⁠?	$(1,1)$ yes	$(2,2)$ yes	$(3,3)$ yes	$(4,4)$ yes

   All four pairs are in the list, so $R$ is reflexive.

   Reflexive means $(a,a)\in R$ for every element of the set $\{1,2,3,4\}$⁠, so all four must be checked. Forgetting 4 is a common slip: it is related only to itself, but that is exactly what reflexivity asks of it.
   For a finite set, reflexive means the whole diagonal of the table is ticked.

3. Symmetric: one missing reverse pair is enough to fail

   The pairs $(a,a)$ are their own reverses, so only the three pairs with $a \ne b$ need checking:

   Pair in $R$	Reverse	Reverse in $R$⁠?
   $(1,2)$	$(2,1)$	no
   $(1,3)$	$(3,1)$	no
   $(3,2)$	$(2,3)$	no

   For instance $(1,2)\in R$ but $(2,1)\notin R$⁠. So $R$ is not symmetric.

   Symmetry is a "whenever" statement, so a single pair whose reverse is missing destroys it; $(1,2)$ alone settles the matter. Here in fact every one of the three pairs fails, which the table records for completeness.
   One counterexample disproves a "for all" statement. Basics: proving and disproving

4. Transitive: check every chain, grouped by the middle element

   A chain is two pairs $(a,b), (b,c)$ in $R$ that share the middle element $b$⁠. To be sure none is missed, go through $b = 1, 2, 3, 4$ in turn: list the pairs of $R$ ending in $b$ and the pairs starting with $b$⁠, and combine every first pair with every second pair.

   Middle $b$	$(a,b)\in R$	$(b,c)\in R$	Chain	Needs $(a,c)$	In $R$⁠?
   1	$(1,1)$	$(1,1)$	$(1,1),(1,1)$	$(1,1)$	yes
   1	$(1,1)$	$(1,2)$	$(1,1),(1,2)$	$(1,2)$	yes
   1	$(1,1)$	$(1,3)$	$(1,1),(1,3)$	$(1,3)$	yes
   2	$(1,2)$	$(2,2)$	$(1,2),(2,2)$	$(1,2)$	yes
   2	$(2,2)$	$(2,2)$	$(2,2),(2,2)$	$(2,2)$	yes
   2	$(3,2)$	$(2,2)$	$(3,2),(2,2)$	$(3,2)$	yes
   3	$(1,3)$	$(3,2)$	$(1,3),(3,2)$	$(1,2)$	yes
   3	$(1,3)$	$(3,3)$	$(1,3),(3,3)$	$(1,3)$	yes
   3	$(3,3)$	$(3,2)$	$(3,3),(3,2)$	$(3,2)$	yes
   3	$(3,3)$	$(3,3)$	$(3,3),(3,3)$	$(3,3)$	yes
   4	$(4,4)$	$(4,4)$	$(4,4),(4,4)$	$(4,4)$	yes

   The counts per middle element are $1\times3 = 3$ (for $b=1$⁠), $3\times1 = 3$ (for $b=2$⁠), $2\times2 = 4$ (for $b=3$⁠) and $1\times1 = 1$ (for $b=4$⁠): $3+3+4+1 = 11$ chains in all. Every one of them passes, so $R$ is transitive.

   To prove transitivity we must show that no chain fails, so all chains must be listed; grouping by the middle element guarantees none is overlooked. Ten of the eleven chains use a loop $(b,b)$ or $(a,a)$⁠, and such a chain always passes automatically: $(a,b),(b,b)$ asks only for $(a,b)$⁠, which we started with. The only chain made of two genuine arrows is $(1,3),(3,2)$⁠, and it needs $(1,2)$⁠, which is in $R$⁠. That single pair $(1,2)$ is what keeps $R$ transitive.
   Transitivity: $(a,b)\in R$ and $(b,c)\in R$ $\Rightarrow (a,c)\in R$⁠, for all $a,b,c$⁠, including the cases where some of them are equal. Basics: reflexive, symmetric, transitive

5. Summarise

   $R$ is reflexive (Step 2), not symmetric (Step 3) and transitive (Step 4). Because it is not symmetric, it is not an equivalence relation.

   An option is correct only if every claim in it is true, so we need the exact status of all three properties before looking at the options.

6. Test every option

   Option	Claims	Verdict	Reason
   (A)	reflexive, symmetric, not transitive	wrong	Two false claims: $R$ is not symmetric ($(1,2)\in R$⁠, $(2,1)\notin R$⁠), and $R$ is transitive (all 11 chains pass).
   (B)	reflexive, transitive, not symmetric	correct	All three claims agree with Steps 2, 3 and 4.
   (C)	symmetric, transitive, not reflexive	wrong	Two false claims: $R$ is not symmetric, and $R$ is reflexive (all of $(1,1),(2,2),(3,3),(4,4)$ are in $R$⁠).
   (D)	equivalence relation	wrong	An equivalence relation must be symmetric, and $R$ is not.

   Checking every option, not only the one we chose, guards against a slip in the working: if two options seemed right, or none did, we would know to recheck. Here exactly one option matches.

Every fact used, and where it comes from