# FA18:Lecture 11 equivalence

We will discuss the equivalence classes of an equivalence relation.

# Equivalence classes

Consider the following equivalence relation on the set :

Notice that the elements of are split up into three groups, with everything in one group related to everything else in the same group, and nothing in one group related to anything in any other group.

In this example, the three groups are , and .

In fact, this is a general phenomenon, and the groups often represent something important. For example, if were a set of people and R was the is-related-to relation, then the groups of related people would be called "families". Two people are in the same family if and only if they are related to each other.

In general, the groups are referred to as equivalence classes. Formally, we have the following definition:

Definition: Equivalence class
If is an equivalence relation on a set , then the equivalence class of by (written ) is the set of elements with .

In other words,

Note: I usually use the symbols [ and ] instead of ⟦ and ⟧, but the wiki syntax makes this difficult. You may use either notation.

When is clear from context, we just write ⟦a⟧.

In the above example, we have three equivalence classes: , , and .

You can see in this example that ⟦a⟧=⟦b⟧ if and only if aRb; this is always the case.

Definition: A/R
If is an equivalence relation on a set , then A mod R (written ) is the set of all equivalence classes of by . In other words, .

Continuing the above example, we have . Note that is also in , but we don't need to list it separately, since it is equal to .

One more piece of terminology:

Definition: representative
If is an equivalence class of by , and , we say that is a representative of if . Note that is a representative of .

# Equivalence classes form a partition

In our example of an equivalence relation, we noted that the equivalence classes partition the set into disjoint subsets.

In fact, this is a general phenomenon, which we prove here. We begin with a definition:

Definition: Partition
A collection of subsets of a set form a partition of if:
1. The cover , i.e. .
2. The are disjoint, i.e. unless .

The Venn diagram of a partition looks like this:

Now we can prove the following claim:

partitions . In other words,
1. Every element of is in some equivalence class, and
2. Two equivalence classes are either disjoint or identical
Proof:
For the first part, note that . This is because must be an equivalence relation, and is thus reflexive. This means so , and thus there exists some equivalence class containing .

For the second part, suppose that . We want to show that . We will show that ; the reverse direction is similar.

Choose an arbitrary ; we want to show that .

Since , we know that there exists some . By definition of ⟦a⟧ and ⟦b⟧, we have , , and as in the following picture:

We wish to show that . Since and is symmetric we have (arrow (i) in the picture below). We can then use transitivity to find that (since and ) (arrow (ii) in the picture below), and then again (since ) to conclude that (arrow (iii) in the picture below).

By definition, since , we have , as required.

# Defining functions from A/R to X

Often, we want to define functions from to another set by giving their values on representatives. For example, we might wish to define a function from the set of families to the set of eye colors by defining .

However, this does not give a well-defined function, because we can choose different representatives and of the same family, and would give different values for the two representatives. For to be a function, it would need to be unambiguous.

Therefore, when defining a function in this way, it is important to check that if (in other words, if ) then .

## Example: Java .equals and .hashCode

Many programming languages allow you to redefine the notion of .equals for objects of different types. For example, Java lets you to override the .equals function for comparing objects, Python lets you write a __eq__ function, OCaml lets you define (=).

When you redefine equality for a new type, you are really saying that you want to think of objects of that type as equivalence classes of objects. I might represent the set as the array [x,y,z] or as the array [y,z,x] (or possibly even as the array [x,x,y,z,y], depending on my implementation). But as a user, I want to think of all of these as different representatives of the same object: the set itself is in some sense the equivalence class containing those different representations.

For this high-level view of a type as an equivalence class to make sense, there are some important things you should check when defining .equals:

For example, the Java specification requires you to redefine a function called .hashCode whenever you redefine .equals. The reason for this is that it might no longer be a well-defined function if two different objects are in the same equivalence class.

.hashCode is used to look up objects in some data structures. For example, it might be the case that [1,2,3].hashCode() = 17 but [3,1,2].hashCode() = 5, meaning that [1,2,3] should be stored in slot 17 and [3,1,2] should be stored in slot 5. That's not a problem if [1,2,3] and [3,1,2] are different objects, but if we are thinking of them both as representatives of the set , then the set might end up in two different places in our data structure, causing it to behave incorrectly.