Equivalence Relations

An equivalence relation is a relation which "looks like" ordinary equality of numbers, but which may hold between other kinds of objects. Here are three familiar properties of equality of real numbers:

1. Every number is equal to itself: for all .

2. Equalities can be "reversed": If and , then .

3. You can "chain" equalities together: If and and , then .

These three properties are captured in the axioms for an equivalence relation.

Definition. An equivalence relation on a set X is a relation on X such that:

1. for all . (The relation is reflexive.)

2. If , then . (The relation is symmetric.)

3. If and , then . (The relation is transitive.)

Example. Show that the less-than relation on the set of real numbers is not an equivalence relation. What about the relation ? For no real number x is it true that , so reflexivity never holds.

If x and y are real numbers and , it is false that . For example, is true, but is false.

It is true that if and , then . Thus, is transitive.

Suppose instead I consider less-than-or-equal-to, the relation on .

Reflexivity now holds, since for any it is true that . Transitivity holds just as before.

However, symmetry still doesn't hold: , but . Thus, is not an equivalence relation.

Example. (a) Is the relation whose graph is drawn below an equivalence relation?

(b) Is the relation whose graph is drawn below an equivalence relation?

(c) Is the relation whose graph is drawn below an equivalence relation?

(a) The relation is not an equivalence relation. is not in the relation, so the relation is not reflexive.

(b) is in the relation, but is not. Therefore, the relation is not symmetric, so it's not an equivalence relation.

(c) This relation is reflexive and symmetric. However, and are in the relation, but is not. The relation is not transitive, and therefore it's not an equivalence relation.

Example. A relation is defined on by

Check each axiom for an equivalence relation. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.

but , and . Hence, and the relation is not reflexive.

Suppose . Then , so . Hence, . The relation is symmetric.

, because and .

, because and .

However, , as I showed above. Hence, the relation is not transitive.

Example. Define a relation on by

Check each axiom for an equivalence relation. If the axioms holds, prove it. If the axiom does not hold, give a specific counterexample.

For all ,

Therefore, for all x, and is reflexive.

Suppose . This means that . By commutativity of addition, . Hence, . Therefore, is symmetric.

Transitivity does not hold.

However, , because

Therefore, and do not imply .

Example. A relation is defined on by

Check each axiom for an equivalence relation. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.

In words, the definition says two pairs are related if either their first components are equal or their second components are equal.

, because the first components are both a and hence equal.

Suppose . Then either or . In the first case, if , then , because their first components are equal: implies . In the second case, if , then , because their second components are equal: implies .

, because their first components are equal. And , because their second components are equal. But , because neither their first nor their second components are equal.

Example. Define a relation on by if and only if is divisible by 3.

Check each axiom for an equivalence relation. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.

For example, , since , and 24 is divisible by 3. And , since , and -9 is divisible by 3.

However, , since , and 34 is not divisible by 3.

If x is an integer, is divisible by 3. Therefore, for all , and is reflexive.

Suppose x and y are integers. If , then is divisible by 3. Say , where . Now

Therefore, is divisible by 3, so . Hence, is symmetric.

You might be wondering how I knew to start with " ". I reasoned backwards on scratch paper this way.

To prove symmetry, I had to show that if , then .

By the definition of , that's the same as showing: If is divisible by 3, then is divisible by 3.

If being divisible by 3 is going to force to be divisible by 3, there's probably be some connection involving 3, , and .

As in many proofs, you often reach a point where you need to play around with the stuff you have. You don't know in advance what will work, and there isn't a step-by-step method for finding out. You have to experiment.

So you think: "3?" " ?" " ?" You might try various ways of combining the expressions ... and maybe you realize that and (notice the 3's!), and then:

Since the "then" part of what I want to prove involves , I'll solve the last equation for :

And there's the equation I started with.

Now suppose x, y, and z are integers. Assume and . This means that is divisible by 3, and is divisible by 3. I'll express these as equations:

I want to show that is divisible by 3. My proof looks like this so far, with the assumptions at the top and the conclusion at the bottom.

How can I get from and to ? Make what you've got look like what you want. What I have involves x, y, and z, but what I want seems to involve only x and z. It looks like I want to get rid of the y's. How can I do that? One way is to solve the second equation for y:

Then plug into the first:

I look at my target equation . Make what you've got look like what you want. I need on the left side, so I'll just do algebra to force it to happen:

The left side is what I want ( ), but I need on the right ... oh, just factor out 3:

I'll plug this derivation into the proof outline above:

This is a complete proof of transitivity, though some people might prefer more words. Thus, is an equivalence relation.

Notice that if you were presented with this proof without any of the scratchwork or backward reasoning, it might look a little mysterious: You can see each step is correct, but you might wonder how anyone would think of doing those things in that order. This is an unfortunate consequence of the way math is often presented: After the building is finished, the scaffolding is removed, and you may then wonder how the builders managed to get the materials up to the roof!

The lesson here is that you should not look at a finished proof and assume that the person who wrote it had a flash of genius and then wrote the thing down from start to finish. While that can happen, more often proofs involve messing around and attempts that don't work and lots of scratch paper!

Equivalence relations give rise to partitions. As a real-world example, consider a deck of playing cards. It is divided into 4 suits: spades, hearts, diamonds, and clubs. Define two cards in the deck to be equivalent if they belong to the same suit. This is an equivalence relation. Every card in the deck belongs to one and only one suit, which is the set of all cards in the same suit as the given card.

In general, if is an equivalence relation on a set X and , the equivalence class of x consists of all the elements of X which are equivalent to x. In the previous example, the suits are the equivalence classes.

Definition. Let X be a set. A partition of X is a collection of subsets of X such that:

1. .

2. If and , then . (The subsets are pairwise disjoint.)

Thus, the elements of a partition are like the pieces of a jigsaw puzzle:

Example. Why don't the following sets partition the set of integers ?

(a)

(b)

(a) Every integer is in one of these sets, but the two sets overlap (at 0).

(b) The sets don't overlap, but -1 is not contained in either set.

Example. Prove: If X is a set and S is a subset of X, then is a partition of X.

If , then either or . In the second case, . Thus, every element of X is either in S or in .

If , then and , which is a contradiction. Hence, S and are disjoint.

Therefore, is a partition of X.

Here is how equivalence relations are related to partitions.

Theorem. Let X be a set. An equivalence relation on X gives rise to a partition of X into equivalence classes. Conversely, a partition of X gives rise to an equivalence relation on X whose equivalence classes are exactly the elements of the partition.

Proof. Suppose is an equivalence relation on X. If , let

Thus, is the equivalence class of x. Now , so . Clearly, .

Now some of the 's may be identical; throw out the duplicates. This means that I have 's where , and Y is a subset of X --- and if and , then . Since I've just thrown out duplicates, I still have . I will have a partition if I show that the remaining 's don't intersect.

Suppose , , but . I'll show that this gives a contradiction. By definition, and , so by symmetry and transitivity, .

Now I'll show . I'll show each is contained in the other. Suppose . Then , but , so , and . This shows . But the argument clearly works the other way around, so . Hence, .

Since I threw out all the duplicates earlier, this is a contradiction. Hence, there is no such z: . This means that the 's for partition X.

Conversely, suppose is a partition of X. Define a relation on X by saying if and only if for some .

If , for some i because . Now x is in the same as itself --- --- so . It's reflexive.

If , then for some i. Obviously, , so . It's symmetric.

Finally, if and , then and for some i and j. Now , but this can only happen if . Then , so . It's transitive, and hence it's an equivalence relation.

The equivalence classes of are exactly the 's, by construction.

Example. Suppose . Consider the following partition of X:

What is the equivalence relation defined by this partition?

The equivalence relation defined by this partition is: for all , and

In other words, 1, 4, and 5 are equivalence to each other, 2 and 6 are equivalent, and 3 is only equivalent to itself.

Example. Consider the relation on defined by if and only if --- that is, if is an integer.

Check each axiom for an equivalence relation. If the axioms holds, prove it. If the axiom does not hold, give a specific counterexample.

Let . Then . Therefore, , and is reflexive.

Suppose , so . Since the negative of an integer is an integer, . Hence, , and is symmetric.

Suppose and . Then and . But the sum of integers is an integer, so

Therefore, , and is transitive. Thus, is an equivalence relation.

Here's a typical equivalence class for :

A little thought shows that all the equivalence classes look like like one: All real numbers with the same "decimal part". Each class will contain one element --- 0.3942 in the case of the class above --- in the interval . Therefore, the set of equivalence classes of looks like . Moreover, since , it's as if this interval had its ends "glued together":

This is an important use of equivalence relations in mathematics --- to "glue together" or identify parts of a set to create a new set.

Example. Let , the x-y plane. Define to mean that

In words, this means that and are the same distance from the origin.

Show that this is an equivalence relation, and sketch the partition of into equivalence classes that it determines.

Since , it follows that . Hence, the relation is reflexive.

Suppose , so

Then

Hence, . Hence, the relation is symmetric.

Suppose and . Then

Hence,

Therefore, . Hence, the relation is transitive. This show that is an equivalence relation.

The resulting partition of into equivalence classes consists of circles centered at the origin. The origin is in an equivalence class by itself.

Notice that the axioms for a partition are satisfied: Every point in the plane lies in one of the circles, and no point lies in two of the circles.

Example. An equivalence relation is defined on the set by:

List the elements of the equivalence classes of .

Two numbers are in the same class if they differ by a multiple of 3. So the equivalence classes are:

Contact information