Equivalence Classes

You've actually dealt with modular arithmetic for most of your life: the clock face represents arithmetic with modulus 12. If you've ever served in the military or listened to the BBC World Service, you're familiar with arithmetic modulo 24 as well.

When we deal with time, we feel free to use the symbol to denote any time that is a multiple of 12 hours away from a particular 1 am or 1 pm. Notice that transitivity means we don't actually care  which particular reference 1 am or 1 pm we choose -- but if you're worried about it, we could follow Bishop Ussher and say that our archetypal is 1 am on Sunday, 23 October 4004 BC. It is very useful to have a symbol for all of the one-o'clocks, a symbol for all of the two-o'clocks, etc., so that we can write things like

Seven hours after is .

The following definition makes this idea precise.

Definition. Let be an equivalence relation on the set , and let . The equivalence class of under the equivalence is the set

of all elements of which are equivalent to .

E.g. Consider the relation on given by if . Then , , etc.

E.g. Consider the equivalence relation on given by if . Then

and it's easy to see that all other equivalence classes will be circles centered at the origin. Note that we have .

Definition. Given an equivalence relation on , the set of all equivalence classes is called the {\em quotient of by }. We write

Notice that the quotient of by an equivalence relation is a set of sets of elements of .

E.g. Consider the relation on given by if . Then

E.g.  If is the equivalence relation on given by if , then is the set of circles centered at the origin.

E.g. has 12 elements:

A convenient way to represent them is , , , etc. Notice that the mathematical convention is to start at 0 and go up to 11, which is different from how clocks are numbered.

Theorem. Let be an equivalence relation on . Let . iff .

Proof. Suppose . Since , we have , so by definition of , we have .

Suppose . We'll show . Let . Then . Since is transitive, we have . Since is symmetric, this means , i.e. .

The proof that is similar. .

Theorem. consists of exactly the elements , , \ldots, .

Proof. We are asked to show set equality. It is clear that each for is an equivalence class, so we have one set inclusion.

To get the other set inclusion, suppose is an equivalence class. Then there is some with . We apply the Division Algorithm to write

where . Then is a multiple of , so . Thus , and since , we have shown that is on our list of equivalence classes. .

An important property of equivalence classes is they cut up" the underlying set:

Theorem. Let be a set and be an equivalence relation on . Then:

1. No equivalence class is empty.
2. The equivalence classes cover ; that is, .
3. Equivalence classes do not overlap.

Proof. The first two are fairly straightforward from reflexivity.

1. Any equivalence class is for some . Since is reflexive, , i.e. . So is nonempty.
2. Let . We need to show that . That is, we need to find some for which . Using and the observation above, we have .

The third clause is trickier, mostly because we need to understand what it means. Consider the case of , . Then and certainly overlap--they both contain , for example. So if we take equivalence classes do not overlap" too literally it cannot be true.

But notice that and not only overlap, but in fact are equal. So we'll amend

equivalence classes do not overlap

to

distinct equivalence classes do not overlap

that is,

Theorem. If then .

Proof. We'll prove the contrapositive: if , then .

Assume is nonempty. Then there is some . So and .

Since is symmetric, .

Since is transitive, . So . .

This theorem shows, for example, that there are in no redundancies on the list , , \ldots, of equivalence classes modulo .

An example from arithmetic: rational numbers

Exercise. Consider the relation on given by: if . Show that is an equivalence relation. Do not use fractions in your proof.

What are the equivalence classes under the relation ?

Claim. is the set of all pairs of the form .

Proof. First we show that every . This is equivalent to showing . But by definition of , all we need to show is --which is clear since both sides are .

Now we show that if , then it must be the case that . means that , i.e. that . .

Exercise. Show that is the set of all pairs of the form .

We write for the equivalence class , and we define:

Definition. The set of rational numbers is . That is, a rational number is an equivalence class of pairs of integers.