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?

About these ads

2 thoughts on “What Are Equivalence Classes?

  1. Are you going to lead us into the land of cardinal numbers and strange paradoxa involving sets of sets?

Please Write Something Good

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s