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
some redeeming virtue; this one is something special, as it
has none.
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 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.