a. Mr. X claims the following: 'If a relation R is transitive and symmetric then R is reflexive.' He offers the following proof: From xRy, by symmetry we get yRx. Combining xRy and yRx, by transitivity we get xRx. Therefore, R is reflexive. Is the proof correct? If not, point out the flaw and give a counterexample.
b. Give an example of a relation R which is both symmetric and transitive but not reflexive.
GATE 1999 · Discrete Mathematics · Relations · medium
Answer: The proof is incorrect because it assumes every element has at least one related partner. Counterexample: R = {(1,1),(1,2),(2,1),(2,2)} on {1,2,3} is symmetric and transitive but not reflexive since (3,3) is absent.
Identify the flaw: Mr. X starts with 'From xRy...' but never justifies that such y exists for every x. If element x is isolated (no y with xRy), the symmetry and transitivity steps never get triggered for x, so xRx is never derived.
Construct a counterexample: Let A = {1, 2, 3} and R = {(1,1),(1,2),(2,1),(2,2)}. Check: Symmetric — (1,2) in R and (2,1) in R; (1,1),(2,2) self-loops trivially symmetric. Transitive — (1,2) and (2,1) gives (1,1); (2,1) and (1,2) gives (2,2); all other compositions are in R. Not reflexive — (3,3) is NOT in R.