Q2: Which pair to remove from to make it an equivalence relation
A relation R in is defined as . Which element(s) of relation R be removed to make R an equivalence relation?
R is reflexive, as .
Why?
An equivalence relation must be reflexive, symmetric and transitive, so we test each property in turn.
Reflexive on S means for every in . All three such pairs are in R.
R is not symmetric, as but .
Why?
Symmetric means: whenever , also .
The only pair with two different entries is , and its reverse is missing. That one pair is the problem, so it is the element to remove.
After removing , , which is reflexive, symmetric and transitive.
Why?
Every pair left has the form . Its reverse is itself, so R is symmetric. Joining with gives again, so R is transitive.
Watch out: removing a pair such as instead would break reflexivity, and R would still not be symmetric. So is the only element to remove.
Answer: the element is to be removed.
Chapter 1, Relations and Functions: Equivalence relations.
Question type: A relation given as a list of pairs
How to spot it: click to see
Type 1. A relation given as a list of pairs: check each property
Spot it: is written out pair by pair, on a small set like .
Here: is listed in full on . Reflexive passes, but has no reverse , so symmetry fails: remove .
Tell us if something on this page is wrong or unclear. Send feedback on this question →
Relations and Functions in past papers: question 16 of 18 · see them all