Durbin’s problem

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 \sim on a set S. A relation is an equivalence relation if it is:

(a) Reflexive: for all x \in S, x \sim x;

(b) Symmetric: if for some x, y \in S, x \sim y, then y \sim x;

(c) Transitive: if for some x,y,z \in S, x \sim y and y \sim z, then x \sim z.

For example, let S=\mathbb{Z} and define \sim as follows: For x,y \in \mathbb{Z}, x \sim y if and only if x-y is divisible by 7 without remainder. So 4 \sim 11.

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 \sim. Since it is transitive and symmetric by assumption, all we need to prove is that it is reflexive. So let x \sim y. By symmetry, we have then that y \sim x. But by transitivity, if x \sim y and y \sim x (taking z=x in the definition of transitivity), then x \sim x, i.e. the relation is reflexive, hence an equivalence relation.

So where is the flaw?


This entry was posted in Puzzles. Bookmark the permalink.

3 Responses to Durbin’s problem

  1. Dave says:

    Very nice problem!

  2. nigelmottram says:

    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!

    • strathmaths says:

      I think that’s fine, just so long as your set S is the set \{\mathrm{Andre},\ \mathrm{Brian},\ \mathrm{Chris},\ \mathrm{David}\} (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 x, some y such that x \sim y, and we can’t necessarily do that.

      In one of Durbin’s exercises he gives a more “mathematical” example: let S = \mathbb{R}, and define \sim by x \sim y iff xy > 0. The “odd one out” here is of course x = 0

      Incidentally, there’s an erroneous counterexample floating around on the web (e.g. on the Wikipedia page for “equivalence relation”): let \sim 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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.