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.)



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.

  1. No comments yet.
  1. No trackbacks yet.