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:
If you're confused by this, let's think about our coloured blocks:
- Reflexivity: x ≡ x.
- Symmetry: If x ≡ y, then y ≡ x.
- Transitivity6: If x ≡ y and y ≡ z, then x ≡ z.
Seems reasonable doesn't it?
- A block is always the same colour as itself.
- If one block is the same colour as a second block, then the second is the same colour as the first.
- 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.
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:
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?
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.
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.
≥ ('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.