Long ago we had a course called “Algebraic Structures”. It was a second year course on abstract algebra. For years it was taught using the then current edition of J. R. Durbin’s Modern Algebra (Wiley; now in its sixth edition). In the discussion of equivalence relations, Durbin suggests a priceless little problem: not difficult, priceless, because it develops powers of observation.
For those of you who do not know what an equivalence relation is, here is the definition (not a very rigorous one because it does not define a relation). Suppose we have a relation on a set . A relation is an equivalence relation if it is:
(a) Reflexive: for all , ;
(b) Symmetric: if for some , , then ;
(c) Transitive: if for some , and , then .
For example, let and define as follows: For , if and only if is divisible by 7 without remainder. So .
Here is Durbin’s question. Find the flaw in the “proof” of the following “Theorem”. [If this “proof” were correct, you would not need part (a) in the definition of an equivalence relation.]
“Theorem”. Any relation that is symmetric and transitive is an equivalence relation.
“Proof”. Let us call the relation . Since it is transitive and symmetric by assumption, all we need to prove is that it is reflexive. So let . By symmetry, we have then that But by transitivity, if and (taking in the definition of transitivity), then , i.e. the relation is reflexive, hence an equivalence relation.
So where is the flaw?