SP20:Lecture 11 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 , 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. were a set of people and R was the is-related-to relation
In general, the groups are referred to as equivalence classes. Formally, we have the following definition:
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.
One more piece of terminology:
Equivalence classes form a partition
In fact, this is a general phenomenon, which we prove here. We begin with a definition:
The Venn diagram of a partition looks like this:
Now we can prove the following claim:
We wish to show that 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).. Since and is
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.
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 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.