Chapter 8 Equivalence Relations and Partitions
Our goal in this chapter is to understand the relationship between partitions and equivalence relations. Before we delve into the formal definitions, lets look at two examples that illustrate our goal.
Suppose we break our class into four subsets by rank: freshmen, sophomores, juniors and seniors. Our collection of subsets is called a partition of the class because the collection has three properties. (1) The union of the subsets is the entire class. (2) The intersection of any two of the subsets is empty. (3) Each subset is non-empty. We can use our partition to define what it means for two students to be equivalent, by saying that two students in the class are equivalent if they have the same class rank. Thus if we have a partition of a set, we have a way to define equivalence.
Now consider the set of all integers. Let's define equivalence for this set by saying that two integers are equivalent if they have the same remainder when divided by 3. For example, 4 and 7 both have remainder 1, so they are equivalent. Since there are only three possible remainders when dividing an integer by 3, we can put all the integers with remainder 0 into one set, put all the integers with remainder 1 into another set and put all the integers with remainder 2 into a third set. These three sets partition the integers because they satisfy the three properties above. (1) Their union is all integers. (2) No number has two different remainders when divided by 3, so the intersection of any two of our sets is empty. (3) Each set is non-empty.
Summarizing, if you have a partition of a set, then you can define what it means for two elements of the set to be equivalent. Conversely, if you have a definition of what it means for elements in a set to be equivalent, then you can create a partition of the set from that definition.
Definition 8.1.
A collection \(P\) of sets is said to be pairwise disjoint if the intersection of any two sets in the collection is empty.
Definition 8.2.
A collection \(P\) of subsets of a set \(A\) is said to be a partition of the set \(A\) if the collection is pairwise disjoint, the union of the sets in \(P\) is \(A\) and each set is non-empty.
Problem 8.3.
Construct three different partitions of the integers.
Let's recall what we know about relations before we move to a special kind of relation called an equivalence relation.
Recall from Definition 1.29 and Definition 2.1 that if \(\A\) and \(\B\) are sets, then the Cartesian product of \(\A\) and \(\B\) is the set of all ordered pairs \((x,y)\) where \(x\in \A\) and \(y\in \B\text{,}\)
and that a relation on \(A \times B\) is any subset of this set.
Problem 8.4.
Let \(R = \Big\{(x, y) \mid x \in \{a,b,c,d,e\} \mbox{ and } y \in \{u,v, w\}\Big\}\text{.}\) List all the elements of this relation. Is \(R\) a function? Create some type of graphical representation for this relation.
Problem 8.5.
Let \(A= \{1,2,3\}\text{.}\) Write out all elements of \(A \times A\text{.}\) List two examples of relations on the set \(A= \{1,2,3\}\text{,}\) one which is not a function and one which is a function.
Functions are one example of relations and equivalence relations are a second example of relations.
Definition 8.6.
If \(R\) is any relation, then \(xRy\) means \((x,y) \in R\text{.}\)
Definition 8.7.
Suppose \(A\) is a set and \(R \subseteq A \times A\) is a relation on \(A\text{.}\)
If for every \(x \in A\) we have \(xRx\text{,}\) then \(R\) is said to be reflexive.
If for every \(x,y \in A\) satisfying \(xRy\) we have \(yRx\text{,}\) then \(R\) is said to be symmetric.
If for every \(x,y,z \in A\) satisfying \(xRy\) and \(yRz\) we have \(xRz\text{,}\) then \(R\) is said to be transitive.
If \(R\) is reflexive, symmetric and transitive, then \(R\) is said to be an equivalence relation.
Note that for equivalence relations, the domain and range must be the same.
Example 8.8.
Suppose \(X = \{\mbox{ all people in the world } \}\) and \(x\) is related to \(y\) means \(x\) is a friend of \(y\text{.}\) Reflexive, symmetric, transitive? Can we construct a partition based on this relation?
Example 8.9.
Suppose \(X = \{\mbox{ students in our class } \}\) and \(x\) is related to \(y\) means \(x\) and \(y\) have the same class rank (freshman, sophomore, junior, senior). Reflexive, symmetric, transitive? Can we construct a partition based on this relation?
Example 8.10.
Need another example or two? Consider the relations over \(\R\) (or perhaps some subset of \(\R\)) where \(xRy\) if \(xy > 0\) or \(xRy\) if \(xy \geq 0\text{.}\)
Problem 8.11.
Let \(A\) be the set of all real numbers. Suppose that \(x\) is related to \(y\) if \(x\) and \(y\) are equal. In other words, \(xRy\) if \(x=y\text{.}\) Which of these properties hold for the relation \(R\text{?}\)
reflexive (Is \(x\) related to \(x\text{?}\) I.e. Does \(x=x\text{?}\))
symmetric (If \(xRy\text{,}\) then is \(yRx\text{?}\) I.e. If \(x=y\text{,}\) then does \(y=x\text{?}\))
transitive (If \(xRy\) and \(yRz\text{,}\) then must \(xRz\text{?}\))
Can you construct a partition of \(A\) based on this relation?
Problem 8.12.
Let \(A\) be the set of all real numbers. Let \(xRy\) if \(x \leq y\text{.}\) Check whether \(R\) is reflexive, symmetric and transitive. Is \(R\) an equivalence relation? Can you construct a partition based on this relation?
Definition 8.13.
Given two integers \(x\) and \(y\) we say that \(x\) is a multiple of \(y\) if there is an integer \(k\) so that \(x=ky\text{.}\)
Problem 8.14.
Let \(A\) be the set of all positive integers. Define a relation \(R\) by \(xRy\) if \(x\) is a multiple of \(y\text{.}\) Which of these properties hold for the relation \(R\text{?}\)
reflexive (Is \(x\) a multiple of \(x\text{?}\))
symmetric (If \(x\) is a multiple of \(y\text{,}\) then must \(y\) be a multiple of \(x\text{?}\))
transitive (If \(x\) is a multiple of \(y\) and \(y\) is a multiple of \(z\text{,}\) then must \(x\) be a multiple of \(z\text{?}\))
Can you construct a partition based on this relation?
Problem 8.15.
Let \(A\) be the set of all integers. Suppose that \(xRy\) if \(x\) and \(y\) have the same remainder when divided by \(5\text{.}\) Is \(R\) an equivalence relation? Can you construct a partition based on this relation?
Recall the equivalence relation on our class where two students are related if they have the same class rank. This equivalence relation partitions our class into subsets where everyone in a given subset is related to everyone else in that subset, no person is in two different subsets, and the union of all the subsets is the entire class. The next definition gives us a name for the subsets in the partition.
Definition 8.16.
If \(R\) is an equivalence relation on the set \(A\) and \(a \in A\text{,}\) then the equivalence class of \(a\) is the set \(\{y \in A \mid yRa\}\) and is denoted by \([a]\text{.}\)
To determine what the equivalence classes are, just pick an element and ask yourself, “What other elements are related to this element?” Once you've done this for a few elements, you'll understand all the equivalence classes for that particular relation.
Problem 8.17.
For Problem 8.11 through Problem 8.15 where \(R\) turned out to be an equivalence relation, define the equivalence classes.
Up to this point, we were given a relation and we checked to see if it was reflexive, symmetric, and transitive. If it was, then we listed all the equivalence classes and they formed a partition. Thus each equivalence relation yielded a partition. The fact that this always works is stated formally as the following theorem and the proof is the first problem in Section .
Theorem 8.18.
If \(R\) is an equivalence relation on the set \(A\text{,}\) then the set of all equivalence classes defined by \(R\) form a partition of \(A\text{.}\)
We now consider the converse of this process, showing that every partition yields an equivalence relation. Suppose we have a set that we partition into a collection of non-empty subsets which are pairwise disjoint and whose union is our set. Then we can define a relation by saying that \(x\) and \(y\) are related if, and only if, they are in the same subset in the partition. This relation will be an equivalence relation, so we now have a way to create equivalence relations from partitions. In other words, equivalence relations and partitions are the exact same idea written in different mathematical language.
Problem 8.19.
Suppose \(P\) is a partition of the set \(A\text{.}\) Define the relation \(R\) on \(A\) by \(xRy\) if there is \(B \in P\) such that \(x\) and \(y\) are both in \(B\text{.}\) Prove that \(R\) is an equivalence relation on \(A\text{.}\)
Problem 8.20.
Let \(\A\) be the set of points \((x,y)\) in the plane and suppose that \((x,y) R (x',y')\) if \((x,y)\) and \((x',y')\) are the same distance from the origin. Describe the equivalence class for (0,2), that is, describe \([(0,2)] = \{ (x,y) \in \R^2 \mid (x,y)R(0,2) \}\text{.}\) Determine if \(R\) is an equivalence relation and if so, describe all the equivalence classes.
Problem 8.21.
Let \(A\) be the set of all integers. Suppose \(x R y\) if \(x\) and \(y\) are integers and \(x - y\) is a multiple of \(3\text{.}\) Determine if \(R\) is an equivalence relation and if so, describe the equivalence classes.
Problem 8.22.
Let \(A\) be the set of integers. Suppose \(x R y\) if \(x\) and \(y\) are integers and \(x + y\) is even. Determine if \(R\) is an equivalence relation and if so, describe the equivalence classes.
Problem 8.23.
There is a standard and important notion of equivalence between sets. Let \(\textbf{S}\) denote the collection of all sets. For \(X, Y \in \textbf{S}\text{,}\) we say that \(X R Y\) if there is a bijection \(f:X \to Y\) from \(X\) to \(Y\text{.}\) Thus finite sets \(X\) and \(Y\) are equivalent if and only if they have the same number of elements, but in general they need not be finite. Show that \(R\) is reflexive, symmetric and transitive.