What Are Equivalence Classes?

(A couple weeks ago I published a little lemma of an essay. This is the next lemma; if my prose style holds out this’ll all lead to something neat.)

If you have the idea of equivalence — that you can pick elements of a set out and say whether they share some property, and that the sharing of that property works in some of the ways that equality works — then you can create equivalence classes. This is the dividing of your original set up into smaller parts according to the rule that everything in one of those parts is equivalent to anything else in that same part.

Since I think about mathematics so much, the most familiar equivalence classes to my mind comes from the counting numbers, that familiar old group of 1, 2, 3, and so on. The equivalence relationship I’d like to use looks a little more alien; it’s “has the same remainder when divided by two as”. But every integer, divided by two, has a remainder of either zero or one, and it’s not hard to follow the divisions here: 4 divided by two has a remainder of zero; 5 divided by two has a remainder of one; 6 divided by two has a remainder of zero; 7 divided by two has a remainder of one; and so on. Using this equivalence relationship, 4 and 6 and 8 and for that matter 2 are in the same class. 3 and 5 and 7 and 9 and so on also share a class, though not the same one that 4 and 6 and 8 had. And, yeah, that’s just the even and the odd numbers, presented in a way that uses much more abstraction than you needed to learn odds and evens.

But we can do this dividing into classes for any set and for any equivalence relationship on that set: dividing a group of people up by those who have the same age; dividing clothes up by those which are the same color; dividing functions up by which ones share some interesting property; whatever you like. There aren’t necessarily just the two equivalence classes. For example, “has the same remainder when divided by four as” will split the counting numbers into four classes, and “is the same age as” will split a group of people up into from as few as one class to as many classes as there are people.

So, why split sets up into equivalence classes? Besides the giddy fun of doing it, the most useful reason I know is that it can often be easier to prove something about a whole set of things if you can break the problem up into smaller ones, proving something about a special case of things. If you need to test something that you know will be the same for all the elements in an equivalence class, you just have to pick one element from that class and test that; that can be a wonderful time-saver.

If you do pick one of the elements of your class that’s called a “class representative”, which is one of mathematics’s less exotic terms. If you’ve picked your representative — let me call it a — and want to talk about the equivalence class that contains it, then that’s normally written with braces around it: [a]. Everything in [a] is equivalent to a, by definition. For the example of odds and evens you could use 1 and 2 — the sets [1] and [2] — although that’s just because we tend to look at nice familiar small numbers when we can. We wouldn’t be doing anything wrong if we wrote the sets as [147] and [2038] instead. We’ve entered a realm without uniquely right answers, just answers that are more attractive because we think they’re easier to work with or we think they look nicer.

But when we write down [147] and [2038] we’ve exhausted the odd-and-even partitioning of the counting numbers. We’ve also written down the quotient set, the collection of all the equivalence classes. This is a set whose elements are themselves sets, which is something a little odd to encounter at first, but not anything too exotic.

Here’s a neat little equivalence relation and quotient set I’d like to toss out for folks to consider. The original set is all the real numbers — positive and negative, rational and irrational. The equivalence relation is “is a whole number different from” — so that, for example, 0, 1, 3, and 35 are all in one equivalence class; 0.5, -3.5, and 147.5 are all in another class together; π, π + 1, π – 8, and &pi + 35 are in yet another class. How many equivalence classes are there for this set and this relation, and, what might a quotient set for them look like?

What Is Equivalence?

(I’m putting this little post out because I want to do something more impressive, and I’ll need this lurking in the background. If it seems unmotivated, then, please treat it as a lemma of an essay.)

Most of us have a fairly decent idea of “equals”; at least, we’re fairly sure we know what it means to say “x is equal to y” and can draw from that other conclusions, such as, the controversial “y is equal to x”. Usually we get the idea early in learning arithmetic, and get used to it in working with numbers, and maybe stretch the idea (within the bounds of mathematics) to include things like two angles being equal or two shapes being equal.

Equivalence is a kind of generalizing of this equality idea: we’ll take a bit of what’s interesting about the idea of two things being equal, and use it in a new context. In this new context two things that might not be equal are still similar in some way that’s of interest for whatever we’re working on right now.

To write that “x is equal to y” efficiently we call on the equals sign and just put “x = y”. “x is equivalent to y” also begs for a shorthand notation, at least if you’re doing a lot of work with the idea, and the easiest way to type that is probably just to use a tilde: “x ~ y”, though I admit I prefer using a double tilde, “x ≈ y”, which isn’t too hard to do in HTML but is more work.

For two things to be equivalent you need to say equivalent with respect to what property. Sugar, sand, and salt are pretty much the same if all you’re interested in is how heaps of small-grained particles move; they’re not at all equivalent if you’re baking; and they’re only sort-of equivalent if you’re trying to melt sidewalk ice. You also need to say what set of things you’re drawing from; it’s very hard to answer whether sugar is equivalent to birds if you thought the discussion was about real numbers. Usually in practice the relationship — called the equivalence relation — carries with it an explicit statement of what the set of things is, unless it’s just blisteringly obvious from context.

To say that something is an equivalence relation means that it has to obey three rules, ones that look make it look a lot like ordinary old equality. The first is called reflexivity: any thing in the set is equivalent to itself. Any number equals itself; any article of clothing has the same color as itself; any person has the same gender as herself. Sounds like an unavoidably true property? Consider, for real numbers, the relationship “is less than”; there’s no number that is less than itself. “Is less than” can’t be an equivalence relationship.

The second is called symmetry: if one thing is equivalent to another, then, that other thing is equivalent to the first. If the number we’ve given the name “height” is equal to the number we’ve given the name “length”, so to does the number we’ve given the name “length” equal the number we’ve given the name “height”, and similarly good results can be found with shirts and people’s genders. For numbers, “Is less than” is ruled out right away; but the initially promising “Is less than or equal to”, which satisfies reflexivity, can flop on symmetry: 4 is less than or equal to 12, certainly, but not the other way around.

And the last is called transitivity: if one thing is equivalent to a second, and a second thing is equivalent to a third, then, the first thing has to be equivalent to the third. Ordinary old numbers being equal to one another are still transitive, and those shirts having the same colors work out too, and the same with people sharing a gender. Interestingly, both “Is less than” and “Is less than or equal to” are transitive, but since those fail on reflexivity or on transitivity they’re not equivalence relationships anyway.

There are a lot of equivalences out there, such as two geometric shapes being congruent, or for that matter just being similar (having the same shape but different sizes), or whole numbers having the same remainder when divided by, say, two (which is a fussy way of saying numbers are odd or are even), or two objects having the same temperature, or the like.