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?

(MG)

### Like this:

Like Loading...

*Related*

Very nice problem!

Is this a counterexample?

Let’s consider all the people who voted in the last Scottish election. We say that one person is related to another if they both voted for Labour in the last election. It’s easy to see that this relationship is symmetric: if Andre and Brian are related then they both voted for Labour, so Brian and Andre are related…because they both voted Labour. It’s also transitive: If Andre and Brian are related…and Brian and Chris are related then Andre, Brian and Chris all voted for Labour, so Andre and Chris are related.

But is the relationship reflexive?…well it certainly is if we’re thinking about Andre, Brian and Chris (Andre is related to Andre because they/he voted Labour). But what about David…who is a staunch SNP supporter. David is not related to David because to be related he has to vote Labour…and after years of New Labour that’s never going to happen!

I think that’s fine, just so long as your set is the set (can’t think where you got those names from) rather than the set of all the people who voted in the last Scottish election. As you spotted, the key is that property (a) requires us to be able to find, for any , some such that , and we can’t necessarily do that.

In one of Durbin’s exercises he gives a more “mathematical” example: let , and define by iff . The “odd one out” here is of course …

Incidentally, there’s an erroneous counterexample floating around on the web (e.g. on the Wikipedia page for “equivalence relation”): let denote “is a sibling to”. The claim is that this is symmetric and transitive but not reflexive. It’s a good exercise to look for the error!