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.

Eliminating Your Footprints

When last we discussed divisibility rules, particularly, rules for just adding up the digits in a number to tell what it might divide by, we had worked out rules for testing divisibility by eight. In that, we take the sum of four times the hundreds digit, plus two times the tens digit, plus the units digit, and if that sum is divisible by eight, then so was the original number. This hasn’t got the slick, smooth memorability of the rules for three and nine — just add all the numbers up — or the simplicity of checking for divisibility by ten, five, or two — just look at the last digit — but it’s not a complicated rule either.

Still, we came at it through an experimental method, fiddling around with possible rules until we found one which seemed to work. It seemed to work, and since we found out there are only a thousand possible cases to consider we can check that it works in every one of those cases. That’s tiresome to do, but functions, and it’s a legitimate way of forming mathematical rules. Quite a number of proofs amount to dividing a problem into several different cases and show that whatever we mean to prove is so in each ase.

Let’s see what we can do to tidy up the proof, though, and see if we can make it work without having to test out so many cases. We can, or I’d have been foolish to start this essay rather than another; along the way, though, we can remove the traces that show the experimenting that lead to the technique. We can put forth the cleaned-up reasoning and look all the more clever because it isn’t so obvious how we got there. This is another common property of proofs; the most attractive or elegant method of presenting them can leave the reader wondering how it was ever imagined.

A Quick Impersonation Of Base Nine

I now resume the thread of spotting multiples of numbers easily. Thanks to the way positional notation lets us write out numbers as some multiple of our base, which is so nearly always ten it takes some effort to show where it’s not, it’s easy to spot whether a number is a multiple of that base, or some factor of the base, just by looking at the last digit. And if we’re interested in factors of some whole power of the base, of the ten squared which is a hundred, or the ten cubed which is a thousand, or so, we can find all we want to know just by looking at the last two or last three or last or-so digits.

Sadly, three and nine don’t go into ten, and never go into any power of ten either. Six and seven won’t either, although that exhausts the numbers below ten which don’t go into any power of ten. Of course, we also have the unpleasant point that eleven won’t go into a hundred or thousand or ten-thousand or more, and so won’t many other numbers we’d like.

If we didn’t have to use base ten, if we could use base nine, then we could get the benefits of instantly recognizing multiples of three or nine that we get for multiples of five or ten. If the digits of a number are some strand R finished off with an a, then the number written as Ra means the number gotten by multiplying nine by R and adding to that a. The whole strand will be divisible by nine whenever a is, which is to say when a is zero; and the whole strand will be divisible by three when a is, that is, when a is zero, three, or six.

How To Recognize Multiples Of 100 From Not So Far Away

MJ Howard last week answered my little demonstration that it was easy to tell multiples of two, five, and ten by looking at just the last digit of a whole number, but that there weren’t any ways to tell from just the last digit whether it was divisible by four. He pointed out we could look at the last two digits, and if those were divisible by four, then the entire number would be. This is perfectly true, and it’s only by asserting that I was looking for a rule based on the last digit alone that my forecast of doom about an instant check for divisibility-by-four could be sustained.

Remember the reasoning by which we wrote out a whole number as some string of digits which I call R followed by whatever goes in the units column, which I call a. (I had been thinking of R as in the “rest” of the number, but it struck me over the week that R is also the symbol used in organic chemistry to denote a chain of carbon atoms when one doesn’t really care how many of them are lined up. This interests me as I got on this thread with a set of numbers I called “alcoholic” due to their structural resemblance to organic chemistry’s idea of alcohols.) Since we’re writing in base ten, then, the number written as Ra is ten times R plus a. Ten times R can’t help being divisible by ten, or by any of the factors of ten, which are two and five (and one, which nobody cares about).

How To Recognize Multiples Of Ten From Quite A Long Way Away

I got so caught up last week talking about the different possible bases that I forgot to the interesting thing I had wanted to talk about those bases. I suppose that will happen as long as I write to passion rather than plan. It gives me something to speak about today, at least.

Here is one thing implied by having a consistent base for all these numbers in which position is relevant: a one in each column represents the base-number of units of whatever the next column over represents. That is, in base ten, a one in the tens column represents ten units of one; a one in the thousands column represents ten units of one hundred. I mention this obvious point because it is so familiar and simple as to pass into invisibility. (It also extends past the decimal point; a one in the hundredths column is equivalent to ten units of a thousandth. But I want to talk about divisibility, in the whole numbers, and so leave fractions for some later time.)

This is tidy, in a way that we don’t see in variable bases. It will give us one tool for neat little divisibility rules. That tool appears just by writing things in the appropriate way, which is the best sort of tool. It saves on time trying to prove it works.

Bases For Comparison

Back to the theme of divisibility of numbers. Since we have the idea of writing numbers with a small set of digits, and with the place of those digits carrying information about how big the number is, we can think about what’s implied by that information.

In the number 222, the first two is matched to blocks (hundreds) that are ten times as large as those for the second two (tens), and the second two is matched to units (tens) which are ten times as large as those for the third two (units). It is now extremely rare to have the size of those blocks differ from one place to the next; that is, a number before the initial two here we take without needing it made explicit to represent ten times that hundreds unit, and a number after the final two (and therefore after the decimal point) would represent units which are one-tenth that of the final two’s size.

It has also become extremely rare for the relationship between blocks to be anything but a factor of ten, with two exceptions which I’ll mention next paragraph. The only block other than those with common use which comes to my mind is the sixty-to-one division of hours or degrees into minutes, and then of minutes into seconds. Even there the division of degrees of arc into minutes and seconds might be obsolete, as it’s so much easier on the computer to enter a latitude and longitude with decimals instead. So blocks of ten, decimals, it is, or in the way actual people speak of such things, a number written in base ten.

What Are Numbers Made Of?

To return to my second major theme: my Dearly Beloved told me that I must explain that trick where one adds up the digits of a number and finds out from that whether it’s divisible by 9. I wanted to anyway, but a request like that is irresistible. The answer can be given quickly — and several of my hopefully faithful readers did, in comments, last Friday — but I’d like to take the long way around because I do that and because it lets a lot of other interesting divisibility properties show themselves.

We use ten numerals and the place where we write them to express all the counting numbers out there. We put one of the numerals, such as `2′, in a place which denotes whether we mean to say two tens, or two hundreds, or two millions. That’s a clever tool, and not one inherent to the idea of numbers. We could as easily use different symbols for different magnitudes; the only familiar example of this (in the west) is Roman numerals, where we use I, X, C, and M for increasing powers of ten, and then notice we aren’t really quite sure what to do past M.

The Romans were not very sure either, and individual variations developed when someone found they needed to express an M of M very often. The system has fewer numerals, symbols representing numbers, than ours does, with V and L and D the only additional numerals reasonably common. By the Middle Ages some symbols were improvised to allow for extremely large numbers such as the hundred thousands, and some extra symbols were pulled in for numbers such as 7 or 40, but they have faded to the point of obscurity. This is a numbering system which runs out when the numbers get too large, which seems impossibly limited at first glance. But we haven’t changed much from these times: while we have a numbering system that can, in principle, work with arbitrarily big or tiny numbers, in practice we only use a small range of them. When we turn over arithmetic to computers, in fact, we accept numbering systems which have limits on how big (positive or negative) a number may be, or how close to zero one may work. We accept those limits because of their convenience and are only sometimes annoyed to find, for example, that the spreadsheet trying to calculate a bill has decided we want 0.9999999 of a penny.

Something Cute Without 9’s and a 6

The cute little thing about a string of 9’s followed by a 6 being a number divisible by 6 inspired my Dearly Beloved, who spent some time looking for other patterns in this kind of number. I’m glad for that; this sort of pattern, while it may not be terribly important, is often fun to play with. And interesting things can be found in play.

I don’t know a good name for this kind of number, and admit it feels awkward to say just “this kind of number”. If I have to talk about them much longer some group name is probably worth devising. Unfortunately the only names which come to my mind come there through organic chemistry, where it’s reasonably common to have an arbitrarily long chain of carbon atoms terminated with some distinctly different group. For example, an alcohol is a string of carbons ending with an oxygen and hydrogen molecule. But an “alcoholic number”, while an imagination-capturing name, doesn’t quite fit. I suppose aldehydes, which end on a double-bond to an oxygen atom, preserves the metaphor, but no one knows the adjective form of aldehyde.

My Dearly Beloved’s experiments found no other numbers for which a repeated string, terminated by a 6, would produce a number divisible by 6. This overlooked the obvious case, though: a string of 6’s, followed by another 6, is itself divisible by 6. Obvious cases are like that, and many people would think of a uniform string of 6’s not part of the pattern “an arbitrary number of one digit, followed by a 6”.

Something Cute With 9’s and a 6.

After the last few essays I’d like to take a moment for a distinct, cute little problem of no practical use but cute.

Write down as many 9’s as you like, and when finished with that place a 6 at the right end. The result is divisible by 6.

That is, whatever number you’ve written, divided by 6, produces a whole number. Divisibility is one of those things which turns up whenever you have a collection of things which can be multiplied, and one thing is divisible by the second if you can find something in your collection so that the second multiplied by your find equals the first. It’s most often used to talk about the integers — the positive counting numbers, their negative counterparts, and zero if we didn’t include that already — and if it isn’t said divisible-with-respect-to-what then integers are what is usually meant. Partly that’s because integers are the first thing where divisibility stands out: if we look at the real numbers, everything is divisible by everything else (as long as that “else” is not zero), and a property that’s (almost) always true is usually too dull to mention. The next topic where divisibility gets mentioned much is usually polynomials, with a few eccentrics holding out for the complex numbers where the real part and the imaginary part are both integers.

There are several ways to prove this string of 9’s followed by 6 is divisible by 6. Here’s a proof which I like.