Question

The number of relations on the set A = {1, 2, 3}, containing at most 6 elements including (1, 2), which are reflexive and transitive but not symmetric, is ______

Answer 1

6

Answer 2

The relation $R$ on $A=\{1,2,3\}$ must be:

• Reflexive: It must contain $(1,1)$, $(2,2)$ and $(3,3)$.
• Mandatory element: It must contain $(1,2)$.
• All other elements may be chosen from
  $\{\, (1,3),\ (2,1),\ (2,3),\ (3,1),\ (3,2) \,\}$.

Thus, the “base” of $R$ already has 4 elements. Since $R$ has at most 6 elements, we can add 0, 1, or 2 extra pairs.

We denote:

• $a=(1,3), \; b=(2,1), \; c=(2,3), \; d=(3,1), \; e=(3,2).$

Now, we count selections ensuring $R$ is transitive and not symmetric.

1. When 0 extra pairs (k = 0):

   $$R = \{(1,1),(2,2),(3,3),(1,2)\}.$$
   • Transitivity: Holds (no problematic chain).
   • Not symmetric: $(1,2)$ is not “returned” by $(2,1)$.
     → Valid (1 relation).

2. When 1 extra pair (k = 1): Each candidate is $R = \text{base} \cup \{x\}$.

   • $x = a=(1,3)$: Transitive; not symmetric → Valid.
   • $x = b=(2,1)$: Though transitive, $(1,2)$ and $(2,1)$ make it symmetric → Invalid.
   • $x = c=(2,3)$: $(1,2)$ and $(2,3)$ force $(1,3)$ by transitivity, but $(1,3)$ is absent → Invalid.
   • $x = d=(3,1)$: $(3,1)$ with $(1,2)$ would require $(3,2)$ by transitivity, missing → Invalid.
   • $x = e=(3,2)$: Transitive; not symmetric → Valid.
     → Valid count: 2 relations.

3. When 2 extra pairs (k = 2): Choose 2 from $\{a, b, c, d, e\}$. Check each:

   • $\{a, c\} = \{(1,3), (2,3)\}$:
     $(1,2)$ and $(2,3)$ yield $(1,3)$ (present). No symmetric pair → Valid.
   • $\{a, e\} = \{(1,3), (3,2)\}$:
     $(1,3)$ and $(3,2)$ yield $(1,2)$ (present) → Valid.
   • $\{d, e\} = \{(3,1), (3,2)\}$:
     $(3,1)$ and $(1,2)$ yield $(3,2)$ (present) → Valid.
   • All other 2-element selections either force an extra pair by transitivity (which would make the relation exceed 6 elements) or introduce symmetry.
     → Valid count: 3 relations.

Total valid relations: $1+2+3 = 6$.