Difference between revisions of "FA18:Lecture 11 equivalence"

From CS2800 wiki
Line 3: Line 3:
* [http://www.cs.cornell.edu/courses/cs2800/2017sp/lectures/lec07-equivalence.html Last year's notes]
* [http://www.cs.cornell.edu/courses/cs2800/2017sp/lectures/lec07-equivalence.html Last year's notes]
* [[File:fa18-lec11-board.pdf]]
* [[File:fa18-lec11-board.pdf]]
* [[Lecture 11 draft]]
= Equivalence classes =
{{:Equivalence class}}
= Equivalence classes form a partition =
{{:Proof:A/R partitions A}}
= Defining functions from A/R to X =
{{:Defining functions from A/R to X}}
== Example: Java .equals and .hashCode ==
{{:Example: Java .equals and .hashCode}}

Latest revision as of 09:39, 13 October 2018

We will discuss the equivalence classes of an equivalence relation.

Equivalence classes

Consider the following equivalence relation [math]R [/math] on the set [math]A := \{a,b,c,d,e,f\} [/math]:


Notice that the elements of [math]A [/math] 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 [math]\{a,b,c\} [/math], [math]\{d,e\} [/math] and [math]\{f\} [/math].

In fact, this is a general phenomenon, and the groups often represent something important. For example, if [math]A [/math] 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 [math]R [/math] is an equivalence relation on a set [math]A [/math], then the equivalence class of [math]a [/math] by [math]R [/math] (written [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7_R}{⟦a⟧_R} [/math]) is the set of elements [math]b \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] with [math]\href{/cs2800/wiki/index.php/ARb}{aRb} [/math].

In other words, [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7_R}{⟦a⟧_R} \href{/cs2800/wiki/index.php/Definition}{:=} \{b \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A \href{/cs2800/wiki/index.php/%5Cmid}{\mid} \href{/cs2800/wiki/index.php/ARb}{aRb}\} [/math]

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

When [math]R [/math] is clear from context, we just write ⟦a⟧.

In the above example, we have three equivalence classes: [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} = \{a,b,c\} = \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} = \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦c⟧} [/math], [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦d⟧} = \{d,e\} = \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦e⟧} [/math], and [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦f⟧} = \{f\} [/math].

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

Definition: A/R
If [math]R [/math] is an equivalence relation on a set [math]A [/math], then A mod R (written [math]\href{/cs2800/wiki/index.php/A/R}{A/R} [/math]) is the set of all equivalence classes of [math]A [/math] by [math]R [/math]. In other words, [math]\href{/cs2800/wiki/index.php/A/R}{A/R} := \{\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A\} [/math].

Continuing the above example, we have [math]\href{/cs2800/wiki/index.php/A/R}{A/R} = \{\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧}, \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦d⟧}, \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦f⟧}\} [/math]. Note that [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} [/math] is also in [math]\href{/cs2800/wiki/index.php/A/R}{A/R} [/math], but we don't need to list it separately, since it is equal to [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} [/math].

One more piece of terminology:

Definition: representative
If [math]c \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/A/R}{A/R} [/math] is an equivalence class of [math]A [/math] by [math]R [/math], and [math]a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math], we say that [math]a [/math] is a representative of [math]c [/math] if [math]a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} c [/math]. Note that [math]a [/math] is a representative of [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} [/math].

Equivalence classes form a partition

In our example of an equivalence relation, we noted that the equivalence classes partition the set [math]A [/math] 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 [math]A_1, A_2, \dots, A_n [/math] of a set [math]A [/math] form a partition of [math]A [/math] if:
  1. The [math]\href{/cs2800/wiki/index.php/Sequence_notation}{A_i} [/math] cover [math]A [/math], i.e. [math]A \href{/cs2800/wiki/index.php/Equality_(sets)}{=} A_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} A_2 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} A_n [/math].
  2. The [math]A_i [/math] are disjoint, i.e. [math]A_i \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} A_j = \href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math] unless [math]i = j [/math].

The Venn diagram of a partition looks like this:


Now we can prove the following claim:

[math]\href{/cs2800/wiki/index.php/A/R}{A/R} [/math] partitions [math]A [/math]. In other words,
  1. Every element of [math]A [/math] is in some equivalence class, and
  2. Two equivalence classes are either disjoint or identical
For the first part, note that [math]a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} [/math]. This is because [math]R [/math] must be an equivalence relation, and is thus reflexive. This means [math]\href{/cs2800/wiki/index.php/XRy}{aRa} [/math] so [math]a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} [/math], and thus there exists some equivalence class containing [math]a [/math].

For the second part, suppose that [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} \href{/cs2800/wiki/index.php/Equality_(sets)}{≠} \href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math]. We want to show that [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} \href{/cs2800/wiki/index.php/Equality_(sets)}{=} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} [/math]. We will show that [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} [/math]; the reverse direction is similar.

Choose an arbitrary [math]d \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} [/math]; we want to show that [math]d \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} [/math].

Since [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} \href{/cs2800/wiki/index.php/Equality_(sets)}{≠} \href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math], we know that there exists some [math]c \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a⟧} \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} [/math]. By definition of ⟦a⟧ and ⟦b⟧, we have [math]\href{/cs2800/wiki/index.php/XRy}{aRc} [/math], [math]\href{/cs2800/wiki/index.php/XRy}{bRc} [/math], and [math]\href{/cs2800/wiki/index.php/XRy}{aRd} [/math] as in the following picture:


We wish to show that [math]\href{/cs2800/wiki/index.php/XRy}{bRd} [/math]. Since [math]\href{/cs2800/wiki/index.php/XRy}{aRc} [/math] and [math]R [/math] is symmetric we have [math]\href{/cs2800/wiki/index.php/XRy}{cRa} [/math] (arrow (i) in the picture below). We can then use transitivity to find that [math]\href{/cs2800/wiki/index.php/XRy}{bRa} [/math] (since [math]bRc [/math] and [math]cRa [/math]) (arrow (ii) in the picture below), and then again (since [math]aRd [/math]) to conclude that [math]bRd [/math] (arrow (iii) in the picture below).


By definition, since [math]bRd [/math], we have [math]d \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦b⟧} [/math], as required.

Defining functions from A/R to X

Often, we want to define functions from [math]A/R [/math] to another set [math]X [/math] 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 [math]f([a]) := a\text{'s eye color} [/math].

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

Therefore, when defining a function [math]f [/math] in this way, it is important to check that if [math]\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7_R}{⟦a⟧_R} = \href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7_R}{⟦a'⟧_R} [/math] (in other words, if [math]\href{/cs2800/wiki/index.php/XRy}{aRa'} [/math]) then [math]f(\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7_R}{⟦a⟧_R}) = f(\href{/cs2800/wiki/index.php/%E2%9F%A6a%E2%9F%A7}{⟦a'⟧_R}) [/math].

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 [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{x,y,z\}} [/math] 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 [math]\{1,2,3\} [/math], then the set might end up in two different places in our data structure, causing it to behave incorrectly.