Equivalence Classes and Equivalence Relations

In a recent post, I mentioned that we often don’t directly define the objects we care about.  We define ways to represent the objects we care about, and then we define what it means for two representations to represent the same object.  This may seem like a roundabout way to explain something, but in fact it is very common.  The example I gave there was fractions.

I thought it was worth a little more attention to see the machinery that makes this go.  The key ideas are “equivalence relation” and “equivalence class”.

So what is an equivalence relation?

Equivalence relations are a very important kind of binary relation.  A relation is a sort of function which just expresses whether things do or do not have some property.  Binary in this context means that this is a relation on pairs of things.  Binary relations are ubiquitous: “equals” and “is greater than” are binary relations on numbers, “is a factor of” and “has no common prime factor with” are binary relations on integers, “is a direct descendant of” and “has never met” are binary relations on people, “shares a border with” is a binary relation on countries, etc.

In order to count as an equivalence relation, a binary relation (which I’ll write as ) must have three properties.

• Reflexivity. For every object , .
• Symmetry. Whenever , then also .
• Transitivity. Whenever and , then also .

If this is confusing, then in order understand the significance of these properties, it might help to read what I just said again, interpreting as “equals”.  Indeed, = is the prototypical equivalence relation.  Reflexivity, symmetry, and transitivity, taken together, are what you need for it to make sense to use a symbol “the same way” we use =.

From Equivalence Relations to Equivalence Classes

Whenever we have a set of objects with an equivalence relation, we can define the corresponding equivalence classes.  Essentially, an equivalence class is the set of all things equivalent to a particular object.  If , then are in the same equivalence class.

In the interesting cases, we then focus on the equivalence classes themselves; they become the objects of interest.  An example: if by fractions we understand “pairs of integers, the second of which cannot be zero”, then 2/3 and 4/6 are different fractions.  Define an equivalence relation on fractions by if .  Then the equivalence classes are precisely the rational numbers.  And it’s those that we care about, not fractions per se.

When we’re being super-formal, we often use brackets to represent an equivalence class.  So I might use to stand for the set of all numbers congruent to 3 modulo 12.  With that formalism, and are the same thing, even though 3 and 15 retain their identities as different numbers.

More commonly though the notion of the equivalence class is built into our context, so we would just say that 3 and 15 are the same object (in suitable context).

A similar situation occurs with (the unnecessarily confusing) distinction between the expressions and .  I’m just going to write it and get it over with.

People who know a small-to-medium amount of mathematics often come to blows over that equal sign.  Why?  Because there is some confusion about what the objects are, about what “the same” means.  Certainly and 1 are different expressions.  They are different strings of digits.

But numbers are equivalence classes of numerical expressions, and these two expressions are in the same class.

So what?

Equivalence relations and classes are closely related to well-definition, and are likewise pervasive in the way we organize ideas, think about problems, and recognize patterns.  What we mean by “the same” and “different” is highly context-dependent; this just means that we carry around a repository of equivalence relations and try to select the most appropriate in a particular context.  Words like “similar”, which are easy to intuitively understand but not so easy to explain, usually mean that objects are equivalent with respect to some interesting equivalence relations, but not with respect to others.  (Similar triangles, for example.)

The trick is to understand, in any given situation, which distinctions are significant and which are not, and to be aware of the equivalence classes and abstractions implicit in our language.  And I stress the context dependence.  Is a lowercase a “the same object” as a capital A?  Depends.  Is a 90 degree angle the same as a 450 degree angle, or are they different?  Again, it depends.

Is a 3 written in red the same thing as a 3 written in black?  It depends whether you’re doing arithmetic or playing canasta!