As far as mathematical notions go, the idea of a relation is a basic. Formally, a relation on a set S is a subset of the Cartesian product S × S. If the pair (s,t) is in this subset, we say that s is related to t, and write s ~ t.

An *equivalence* relation has the following properties:

- Reflexivity: for all s, s ~ s.
- Symmetry: if s ~ t, then t ~ s.
- Transitivity: if r ~ s and s ~ t, then r ~ t

An equivalence relation cuts up the set S into disjoint subsets, or
equivalence classes. Two elements are in the same equivalence class
if and only if they are related under an equivalence relation. This
works both ways: for any partitioning of S into disjoint subsets,
there is a corresponding equivalence relation. Mathematicians
usually use the word modulo

(or just mod

) to describe
this partitioning into equivalence classes: for example, if ~ is an
equivalence relation and s ~ t, I might say that s and t are
equivalent modulo the relation.

Now, I think I know most of the people who read what I write here, and most of you know more than the average bear about mathematics: basic calculus, probability, linear algebra, discrete mathematics, and some programming for most of you (a couple of you might not have formal courses in all those topics, but you've probably had some exposure). So why do I drag out a definition which is probably familiar to everyone who has actually read this far? Because the equivalence relations really are ubiquitous -- and in some cases they correspond to really strange equivalence classes.

Let me give an example: the example, in fact, that led me to
thinking about this topic right now. It involves the rational
numbers (which are defined in terms of equivalence classes among
pairs of integers) and real numbers (which may be defined in terms
of equivalence classes among sequences of rational numbers). Let's
say x ~ y if x-y is a rational number. We would usually write the
equivalence classes under this relation as **R / Q** (the reals
mod the rationals). Now, what if I make a set X by taking one
member in the interval [0,1] from each equivalence class? The
answer is that I get something *weird*. In fact, I've pulled
a fast one in even describing the set. Taking one member from each
equivalence class sounds like a natural enough operation -- probably
more natural than dividing up the real numbers this way to start
with -- but there are an *uncountably infinite* number of
equivalence classes (**R** is a lot bigger than **Q** in a
well-defined sense, but I don't want to get distracted by a
discussion of power sets and cardinality, so I'll leave it at that).
Anyhow, the ability to make this choice in each equivalence class is
not granted to me as a consequence of some theorem: it is an axiom
of its own, called, appropriately enough, the Axiom of Choice. Some
logicians find the Axiom of Choice distasteful, but most of us think
it's convenient to assume it anyhow, as I will do here.

Now, **R/Q** has some structure -- it has a well-defined addition
operation, though the fact that 0 ~ 1 messes up the multiplicative
structure. But X is a truly awful, wonderful, bizarre set: to
paraphrase a line from a book I read recently, Most sets have

Suppose I define some probability distribution on the
real line, and ask for the probability I'll draw an element of X.
In general, I can't get a consistent answer to the question! If you
don't find this disturbing, think about it some more: it's as though
I'd told you that you could throw darts at the interval [0,1], and I
would arrange the target in a way that a probability that you'd hit
the target *some* redeeming virtue; this one is something special, as it
has none.*couldn't be defined*. In the formal development
of measure theory -- which is the real underpinning of probability
theory -- the first thing we usually do is deliberately discard
pathological sets like X, which are called *unmeasurable*.
If I recall correctly, the existence of (Lebesgue) unmeasurable sets
is a consequence of the Axiom of Choice; that is, if I'd found some
other way to build an unmeasurable set, I'd have to invoke the
Axiom of Choice again. Unless you have special training, you
probably won't be able to find an unmeasurable set; and if you can
find it, your intuition will fail. The strangeness of X makes it a
great test case for sanity-checking statements about sets of real
numbers.

Oh, brave new world that has such constructions in it!

Expect further invocations of the definition of an equivalence
relation in the coming week or two, as I seem to be firmly planted in
random lecture mode.