## 1.3 Exercise 3

"Here is a "proof" that every relation $C$ that is both symmetric and transitive is also reflexive: "Since $C$ is symmetric, $aCb$ implies $bCa$.  Since $C$ is transitive, $aCb$ and $bCa$ together imply $aCa$, as desired.''  Find the flaw in this argument."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 28.)

--------

SOLUTION

Rephrasing, the argument suggests that every relation that is symmetric and transitive is reflexive, and hence is an equivalence relation.  The problem is that reflexivity must be true for all elements in the base set $A$.  Here's a counter-example that disproves the statement.

Suppose $A = \{1, 2, 3, 4, 5\}$, and let's assume we know the relation $C$ consists of the elements $\{(2, 3), (4, 5)\}$.  By following the argument, $C$ includes elements $\{(3, 2), (5, 4)\}$ by symmetry, and $\{(2, 2), (3, 3), (4, 4), (5, 5)\}$ by transitivity.  But the reflexive property of equivalence relations would require that $\{(1, 1)\}$ be in the relation, which, as we've seen, is not obtainable by symmetry and transitivity alone.  Despite being symmetric and transitive, $C$ is not, in this case, "totally" reflexive, and therefore it is not an equivalence relation.

Categories: