Equivalence relations

In an earlier post, I described the equivalence relation theorem as the pons asinorum of modern mathematics. It is a real obstacle for beginning mathematics students, but one which it is essential to master.

The theorem states that two kinds of object are essentially the same thing:

  • an equivalence relation on a set X, that is, a reflexive, symmetric and transitive binary relation on X;
  • a partition of X, a family of non-empty subsets covering each element of X exactly once.

These are completely different kinds of objects, and this difference is one thing that gives the theorem its power. An equivalence relation is a binary relation satisfying the reflexive, symmetric and transitive laws. These are local laws involving at most three elements of the set X. A partition, on the other hand, is a global thing which involves the whole of the set.

This is in my mind because in the last couple of weeks, in my Number Theory lectures, I have been talking about binary quadratic forms. Two such forms are equivalent if one is obtained from the other by an invertible linear substitution on the variables. The fact that this is an equivalence relation is a “local” calculation as described above; it is essentially the same calculation that shows that the 2×2 matrices with integer entries and determinant 1 form a group, the special linear group SL(2,Z).

It is also clear that equivalent forms must share any properties which are independent of the choice of coordinates, such as the set of integers represented by the form.

Of course, to understand quadratic forms, we need to describe the equivalence classes. In general, given an equivalence relation on a set, there are two ways in which we can go about understanding the equivalence classes:

  • If we are lucky, there is a complete set of invariants. An invariant is a function which can be calculated for each object in the set X and which takes the same values for equivalent objects. A set of invariants is complete if, given two inequivalent objects, at least one of the invariants in the set must differ on the two objects. So each equivalence class is described by one set of possible values of the invariants.
  • The other method is to choose canonical representatives of the equivalence class, that is, one element in each class. The word “canonical” has no mathematical meaning here, but we usually require that the chosen representatives are especially “nice” in some way. A mathematician might stop there, but we should go further and require that, from any element of the set, it is possible to find the canonical representative of its equivalence class in a constructive way.

For example, consider the equivalence relation “congruence modulo n” on the set of integers. There are n equivalence classes; we could choose any representatives at all, but the canonical choice consists of the integers 0,1,2,…,n–1. To find the canonical representative of an arbitrary integer x, we divide it by n, using the usual division algorithm, and take the remainder.

(Of course, in some applications, a different choice might be appropriate. For example, in Gauss’ method for deciding whether a given integer is a quadratic residue modulo an odd prime p or not, it is more convenient to take the representatives to be –(p–1)/2,…,(p–1)/2.)

In the case of binary quadratic forms ax2+bxy+cy2, the discriminant d = b2–4ac is an invariant. However, it is not a complete invariant, which leads to one of the really big problems of number theory over the last century or so. In the case of positive definite forms, there is a simple notion of a “reduced” form, a procedure for moving from an arbitrary form to an equivalent reduced one, and a theorem asserting that two different reduced forms cannot be equivalent. So the reduced forms make up a very satisfactory set of canonical representatives.

In this example, we see the role of equivalence relations in classification problems. A different kind of occurrence occurs in elementary algebra, in the construction of quotient groups or rings. The elements of a quotient ring are the cosets of an ideal of the original ring; these cosets are the equivalence classes of the equivalence relation, where two elements are equivalent if their difference belongs to the ideal. So we have to define a ring structure on the set of equivalence classes. We do this by choosing representatives and defining the operations on these, then showing that the results do not depend on the choice of representatives. Similar comments apply to groups.

In my experience, what students find difficult is the idea of a ring (or group) whose elements are subsets of another ring (or group), and so on and so on.

This line of thinking leads us quite soon to homological algebra. Suppose that we have a group G with a normal subgroup A, such that the factor group is isomorphic to B. To simplify things I will assume that A is abelian. Now the fact that G/A is isomorphic to B means that the cosets of A in G correspond to elements of B, so that we can choose a coset representative r(b) corresponding to each element b of B. Now, if we multiply r(b1) by r(b2), we land in the coset with representative r(b1b2), but don’t necessarily hit this element; so there is a “fudge factor”, depending on b1 and b2. These “fudge factors” are called 2-cocycles, never mind why. Now the fudge factors are partly “explained” by different choices of coset representatives (those which can be explained in this way are called 2-coboundaries), but maybe there is an unexplained part depending on the fact that there may be genuinely different groups G satisfying the specifications. This unexplained part (technically, the quotient group cocycles mod coboundaries) is the second cohomology group H2(B,A), and in some sense “measures” the different groups G which are extensions of A by B in this sense.

I think there are some interesting questions here which have not been investigated as much as they should be. For example:

  • What is the minimum weight (number of non-zero entries) in a 2-cocyle, or in a 2-coboundary?
  • What is the minimum number of entries in a 2-cycle that need to be changed to give a genuinely different group? (If I have in mind an extension of A by B and describe it to you by giving the fudge factors, how many mistakes have to be made before you actually get a different group from the one I intended?)

These questions belong to the subject coding theory. I feel that there are a number of links between coding theory and homological algebra, and I will probably return to this topic here one day.

To conclude, here is a metamathematical statement. I would be interested to hear any counterexamples to it. There is a close connection between equivalence relations and group actions; indeed, the three parts of the definition of an equivalence relation (reflexive, symmetric and transitive laws) correspond in a very precise way to the three parts in the definition of a group in the time of Galois, what we would now call a transformation group or permutation group (identity, inverse, and closure laws). Indeed, if a group G acts on the set X, and we define two elements of X to be related if there is an element of G which maps the first to the second, we obtain an equivalence relation, the orbit relation for the action. Now I contend:

All naturally occurring equivalence relations are orbit relations.

The examples I have mentioned (congruence in the integers, equivalence of quadratic forms, and belonging to the same coset of a subgroup of a group or a subring of a ring) are all orbit relations.

The subject descriptive set theory has more to say about this; again, I may get round to discussing this someday.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition. Bookmark the permalink.

8 Responses to Equivalence relations

  1. javier says:

    Concerning the “All eq. relations are orbit actions”, I cannot quite agree with that, unless the statement is relaxed a bit. An example that comes to mind is the space of leaves of a foliation. Whilst in many cases foliations on manifolds come from some group action, that doesn’t need to be the case. Something similar could be said for orbifolds.

    Of course, one might argue that these geometrical situations equivalence classes still “look like orbits”. And they are in a way, if we relax “orbits under a group action” to “orbits under a groupoid action”. To each equivalence relation R (seen as a subset of XxX) in a set X one can associate a groupoid (the “equivalence groupoid”) with objects X and arrows indexed by elements of R. Composition is given by (y,z)*(x,y) = (x,z), well defined by transitivity of the equivalence relation, identity in x is (x,x) (in R by reflexivity) and inverse of (x,y) is (y,x) (in R by symmetry). The equivalence classes determined by R coincide of course with the orbits by the action of the equivalence groupoid, so in that sense your statement holds true.

  2. I accept that the first paragraph is a possible counterexample. If I knew more about foliations I would no doubt simply agree.

    The second paragraph doesn’t meet the bill since every equivalence relation is a group orbit relation – groupoids not required. Just take all permutations of the set which preserve the equivalence relation. I don’t regard this as properly answering my own question, of course.

  3. Some examples spring to mind. You could define an equivalence relation on the set of Latin squares by: L and L’ are equivalent if L’ can be formed from L by a sequence of cycle switches.

    I’ve recently been studying the set of isotopisms theta for which there exists a Latin square L and theta(L)=L (i.e. theta is an autotopism). The equivalence “is (or is not) an autotopism of some Latin square” amongst isotopisms is quite messy.

    Also, is there some group orbit that describes the equivalence class of matrices with determinant X?

  4. Douglas: I agree that you could argue that the transitive closure of any symmetric relation (or, indeed, the symmetric and transitive closure of any relation) is an equivalence relation. Not all of these are orbit relations. However, some are. If the moves (like your cycle switches) are invertible, then they generate a group.

    A relation may be messy and still be an orbit relation. Groups can be messy things!

    Matrices with given determinant over a field form an orbit of the special linear group acting by right multiplication.

    In my previous comment, second paragraph, I meant “preserve the equivalence classes” not “preserve the equivalence relation”.

  5. Qiaochu Yuan says:

    I might be mistaken about this, but in most categories that I can think of, the equivalence relation coming from isomorphism doesn’t come from a group action in any natural way. For example, the category of topological spaces.

  6. It depends how you look at it, I think.

    On the one hand, for any kind of structure at all, there are so many structures (even in a single isomorphism class) that they don’t form a set, and I get a bit nervous about this.

    On the other hand, if you don’t mind that, then the cartesian product of the symmetric groups on the isomorphism classes is a group whose orbits are these classes. (The elements are just those mappings which act on each object as an isomorphism, so it isn’t really cheating – or is it?)

  7. Walter Sinclair says:

    A structure’s isomorphism class may be asymmetric — it may lack any non-trivial automorphism group — however, it may have a completion within a more blessed superstructure. The connectivity equivalence classes, for instance, may seem to have no more group to them than the passage of one point to another, until the key is supplied.

  8. Jon Awbrey says:

    See “Minimal Negation Operator” for a concise way of describing partitions in propositional calculus.

Leave a Reply

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