Monday, January 10, 2005

Equivalence and weirdness

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.