سوال ۹۶ کنکور ارشد علوم کامپیوتر ۱۳۹۹

A relation is an equivalence relation iff it is reflexive, symmetric, and transitive. Test each option against these three properties.

Option 1 — $R \cap S$: equivalence relation. ✓

• Reflexive: Since $R$ and $S$ both contain the diagonal $\Delta = \{(a,a) : a \in A\}$, so does $R \cap S$.
• Symmetric: If $(x,y) \in R \cap S$, then $(x,y)$ lies in both $R$ and $S$; by symmetry of each, $(y,x)$ lies in both, so $(y,x) \in R \cap S$.
• Transitive: If $(x,y),(y,z) \in R \cap S$, then both pairs are in $R$ (giving $(x,z)\in R$) and both are in $S$ (giving $(x,z)\in S$), hence $(x,z) \in R \cap S$.

The intersection of equivalence relations is always an equivalence relation.

Option 2 — $R \cup S$: not always transitive. ✗

Take $A=\{1,2,3\}$ with $R = \Delta \cup \{(1,2),(2,1)\}, \qquad S = \Delta \cup \{(2,3),(3,2)\}.$ Then $(1,2),(2,3) \in R \cup S$ but $(1,3) \notin R \cup S$. Reflexivity and symmetry hold, yet transitivity fails, so the union need not be an equivalence relation.

Option 3 — $R^{-1} \cup S^{-1}$: identical to Option 2. ✗

An equivalence relation is symmetric, so $R^{-1} = R$ and $S^{-1} = S$. Therefore $R^{-1} \cup S^{-1} = R \cup S$, which by the counterexample above is not always transitive.

Option 4 — $R - S$: not reflexive. ✗

Both $R$ and $S$ contain the full diagonal $\Delta$, so $R - S$ contains no diagonal pair: $(a,a) \in R$ but $(a,a) \in S$ too, hence $(a,a) \notin R - S$. A reflexive relation must contain every $(a,a)$, so $R - S$ fails reflexivity (for $|A|\ge 1$ it is never an equivalence relation unless empty).

Conclusion: only the intersection is guaranteed — the answer is Option 1.

Exam trick: Closure under set operations splits cleanly: intersection preserves all three equivalence properties, but union and difference do not (union can break transitivity; difference always destroys reflexivity because both relations share the whole diagonal). Memorize "intersection good, union/difference bad."