Example 1
Question: A relation R on A = \{1, 2, 3, 4\} is defined as \[R = \{(1,1),\ (2,2),\ (3,3),\ (2,3)\}.\] (i) Is R symmetric? Justify your answer. (ii) Find the smallest relation \(R_1\) such that \(R \cup R_1\) is an equivalence relation on A = \{1, 2, 3, 4\}.
Solution: Step 1 — Check Reflexivity of R. For R to be reflexive, we need \((a, a) \in R\) for every \(a \in A\). We have \((1,1), (2,2), (3,3) \in R\) but \((4,4) \notin R\). So R is NOT reflexive. Step 2 — Check Symmetry of R. R contains \((2, 3)\). For symmetry we need \((3, 2) \in R\), but \((3,2) \notin R\). Hence R is NOT symmetric. Step 3 — Find the smallest \(R_1\) so that \(R \cup R_1\) is an equivalence relation. We need to repair reflexivity, symmetry, and transitivity one step at a time. Repair reflexivity: Add \((4,4)\) because it is the only missing diagonal pair. Repair symmetry: \((2,3) \in R\), so add \((3,2)\). Check transitivity after the above additions: The pairs involving 2 and 3 are \((2,3)\) and \((3,2)\). Using \((2,3)\) and \((3,2)\) gives \((2,2)\) — already present. Using \((3,2)\) and \((2,3)\) gives \((3,3)\) — already present. No new pairs are required for transitivity. Therefore the smallest relation is \[R_1 = \{(4,4),\ (3,2)\}.\] Verification: \(R \cup R_1 = \{(1,1),(2,2),(3,3),(4,4),(2,3),(3,2)\}\). Reflexive: \((1,1),(2,2),(3,3),(4,4)\) — all present. ✓ Symmetric: \((2,3)\) and \((3,2)\) both present; all diagonal pairs are self-symmetric. ✓ Transitive: The only non-diagonal pairs are \((2,3)\) and \((3,2)\). Composing \((2,3)\) then \((3,2)\) gives \((2,2)\) ✓; composing \((3,2)\) then \((2,3)\) gives \((3,3)\) ✓. No violation. ✓ Hence \(R \cup R_1\) is an equivalence relation.
Answer: R is not symmetric because \((2,3) \in R\) but \((3,2) \notin R\). The smallest relation is \(R_1 = \{(4,4),\ (3,2)\}\).
Example 2
Question: A relation R on A = \{1, 2, 3\} is defined as \[R = \{(1,1),\ (2,2),\ (1,3),\ (3,1)\}.\] (i) Is R symmetric? Justify your answer. (ii) Find the smallest relation \(R_1\) such that \(R \cup R_1\) is an equivalence relation on A.
Solution: Step 1 — Check Reflexivity of R. For R to be reflexive, \((a,a)\) must belong to R for every \(a \in A = \{1,2,3\}\). We see \((1,1)\) and \((2,2)\) are in R, but \((3,3) \notin R\). Hence R is NOT reflexive. Step 2 — Check Symmetry of R. For symmetry, whenever \((a,b) \in R\) we need \((b,a) \in R\). The non-diagonal pairs are \((1,3)\) and \((3,1)\). Since both are present, the symmetry condition is satisfied for these pairs. The diagonal pairs are trivially symmetric. Hence R IS symmetric. Step 3 — Find the smallest \(R_1\) so that \(R \cup R_1\) is an equivalence relation. Repair reflexivity: \((3,3)\) is the only missing diagonal pair. Add \((3,3)\). Check transitivity after adding \((3,3)\): The current set becomes \(\{(1,1),(2,2),(3,3),(1,3),(3,1)\}\). Now check all compositions: Using \((1,3)\) and \((3,1)\): gives \((1,1)\) — already present. ✓ Using \((3,1)\) and \((1,3)\): gives \((3,3)\) — already present. ✓ Using \((1,3)\) and \((3,3)\): gives \((1,3)\) — already present. ✓ Using \((3,3)\) and \((3,1)\): gives \((3,1)\) — already present. ✓ No additional pairs are needed for transitivity. Therefore the smallest relation is \[R_1 = \{(3,3)\}.\] Verification: \(R \cup R_1 = \{(1,1),(2,2),(3,3),(1,3),(3,1)\}\). Reflexive: \((1,1),(2,2),(3,3)\) all present. ✓ Symmetric: \((1,3)\) and \((3,1)\) both present; diagonal pairs are self-symmetric. ✓ Transitive: Verified above — no violation. ✓ Hence \(R \cup R_1\) is an equivalence relation. Note: Under this equivalence relation, 1 and 3 are in the same equivalence class, while 2 is in its own class. The equivalence classes are \(\{1,3\}\) and \(\{2\}\).
Answer: R is symmetric because for every \((a,b) \in R\) we have \((b,a) \in R\). The smallest relation is \(R_1 = \{(3,3)\}\).