Equivalence Relations - The mathematics of distinction Content from the guide to life, the universe and everything

Equivalence Relations - The mathematics of distinction

3 Conversations

There are two kinds of people in the world, those who believe there are two kinds of people in the world and those who don't.
- Benchley's1 law of distinction.

What is an Equivalence Relation?

An equivalence relation in mathematics is a way of dividing things up into categories, known as equivalence classes2. For example, imagine you are a child with a bunch of alphabet blocks to sort out. You might decide to sort the blocks by colour (red, green, blue and so on) or by whether the letter on them is in your name or not (yes or no) or by what they hit first when you throw them randomly about (floor, chair, cat, priceless Ming vase, etc). The important thing is that each block belongs in exactly one category3.

Let's Get Mathsy

If two things (x and y)4 are in the same category, mathematicians might write 'x ≡ y'. Other symbols5 can stand in place of , notably and .

The intuitive idea of putting things into categories is represented mathematically by the following properties, which need to be satisfied by something before it can be called an equivalence relation:

  1. Reflexivity: x ≡ x.
  2. Symmetry: If x ≡ y, then y ≡ x.
  3. Transitivity6: If x ≡ y and y ≡ z, then x ≡ z.
If you're confused by this, let's think about our coloured blocks:
  1. A block is always the same colour as itself.
  2. If one block is the same colour as a second block, then the second is the same colour as the first.
  3. If one block is the same colour as a second and the second is the same colour as a third, then the first block must also be the same colour as the third.
Seems reasonable doesn't it?

On the other hand if you're a smart aleck, you may be thinking, 'We don't need property one, because by symmetry x ≡ y means y ≡ x, but then we can apply transitivity (with x in place of z) to get x ≡ x. Aren't I smart?' However, you'd be wrong because you're assuming x is equivalent to at least one other object, which it might not be.

What isn't an equivalence relation?

Sometimes understanding what something is can be made easier by looking at what it isn't. So let's look at some things that aren't equivalence relations:

Proximity

Maybe you decide to sort blocks by whether they're near each other (say within a foot of one another). After a bit of thinking you decide it's reasonable to say a block is near itself, so we're okay with reflexivity. Symmetry's fine, too.

Unfortunately, you might be able to go from a block to a nearby block to a nearby block and suddenly realise you're not quite so near to the original block. Oops, this relation isn't transitive, so it can't be an equivalence relation.

So how about a few mathematical examples?

Equality

The humble equals sign defines an equivalence relation. Daft, you say? Well think about it. x = x is certainly true, whence reflexivity, and because x is only equal to itself there's not really anything to prove for the other properties.

Geometric similarity

Two objects are similar if they are the same shape, regardless of size. You may have seen similar triangles, which have corresponding angles that are the same - in which case you'll probably remember them being quite useful in those questions where you have to figure out an angle given a couple of angles on the other side of a complicated diagram.

Congruence modulo n

Now we're getting technical. Pick your favourite positive integer,7 maybe 42, and you can make an equivalence relation on the integers as follows:

x ≡ y if the difference between x and y is a multiple of 42.
So 5 47, 0 42, and -567 -105. This is known as congruence modulo 42 (or just congruence mod 42). You may well see it written x ≡ y mod 42.

Now here's the clever bit: Take any two congruence classes, that is classes of numbers that are all congruent to each other8. Then take one number from each of these classes and add them together. You get a number. Take two different numbers, again one from each class, and add them together. You get a number which probably isn't the same as the first number, but will be congruent with it.

The same thing happens with subtraction and multiplication. Division is a different matter, but if the number you picked at the beginning was prime it works without even bringing in fractions, as long as the number you divide by is not congruent with 0. This is called modulo arithmetic or clock arithmetic9 and could easily fill an article itself.

Ordering

≥ ('greater than or equal to') is an example of an ordering on the real numbers. It is reflexive and transitive, but not symmetric. In fact it is anti-symmetric, meaning that if x ≥ y then it cannot also be true that y ≥ x, unless x = y. So it's not an equivalence relation, it's just here to see whether or not you're paying attention.

Well What's the Use of That Then?

So what do they use equivalence relations for? Well, pretty much everything. You see, absolutely any set of anything can be put into equivalence classes. It's sometimes not obvious what properties some relation has, so to point at it and say 'it's an equivalence relation' can make things a lot clearer. Furthermore, if you choose the right equivalence relation, you may be able to treat entire equivalence classes of objects in the same way, instead of having to do your calculations separately for every single object. Andrew Wiles's proof of Fermat's Last Theorem made good use of this.

1Robert Benchley (1889 - 1945), American humorist and drama critic, who also noted, 'The surest way to make a monkey of a man is to quote him.' Sorry about this, Robert.2To mathematicians 'category' means something else, but that's not important right now.3That 'exactly' is commonly used by mathematicians to prevent the equivalent of the old joke: 'How many months have 28 days?' 'All of them.'4In mathematical papers, variables (letters representing things) are often written in italics so that they do not get confused with the surrounding text. This convention will be used here.5Apologies if some of these don't work on your browser. You should see three horizontal lines, a tilde and two horizontal lines with a tilde above them. If you can't even see the first, reading this Entry might be a bit tricky.6Compare this with the Zeroth Law of Thermodynamics.7That's what the n is in the term, 'congruence modulo n': it just means pick a positive integer. At least that's what it usually means, but all mathematical conventions are rules that may be broken.8If the equivalence relation is called something like 'congruence' we no longer refer to 'equivalence classes'.9Because counting round a clock face is counting modulo 12.

Bookmark on your Personal Space


Edited Entry

A1920467

Infinite Improbability Drive

Infinite Improbability Drive

Read a random Edited Entry

Categorised In:


Written by

References

h2g2 Entries

Write an Entry

"The Hitchhiker's Guide to the Galaxy is a wholly remarkable book. It has been compiled and recompiled many times and under many different editorships. It contains contributions from countless numbers of travellers and researchers."

Write an entry
Read more