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 ax²+bxy+cy², the discriminant d = b²–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(b₁) by r(b₂), we land in the coset with representative r(b₁b₂), but don’t necessarily hit this element; so there is a “fudge factor”, depending on b₁ and b₂. 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 H²(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.