So far we've used relations primarily to talk about functions. There is another kind of relation, called an equivalence relation, that comes up in the counting problems with which we began. In Problem 8 with three distinct flavors, it was probably tempting to say there are 12 flavors for the first pint, 11 for the second, and 10 for the third, so there are \(12\cdot 11\cdot 10\) ways to choose the pints of ice cream. However, once the pints have been chosen, bought, and put into a bag, there is no way to tell which is first, which is second and which is third. What we just counted is lists of three distinct flavorsâone to one functions from the set \(\{1,2,3\}\) in to the set of ice cream flavors. Two of those lists become equivalent once the ice cream purchase is made if they list the same ice cream. In other words, two of those lists become equivalent (are related) if they list same subset of the set of ice cream flavors. To visualize this relation with a digraph, we would need one vertex for each of the \(12\cdot 11\cdot 10\) lists. Even with five flavors of ice cream, we would need one vertex for each of \(5\cdot4\cdot3=60\) lists. So for now we will work with the easier to draw question of choosing three pints of ice cream of different flavors from four flavors of ice cream.
Suppose we have four flavors of ice cream, V(anilla), C(hocolate), S(trawberry) and P(each). Draw the directed graph whose vertices consist of all lists of three distinct flavors of the ice cream, and whose edges connect two lists if they list the same three flavors. This graph makes it pretty clear in how many ways we may choose 3 flavors out of four. How many is it?
Now suppose again we are choosing three distinct flavors of ice cream out of four, but instead of putting scoops in a cone or choosing pints, we are going to have the three scoops arranged symmetrically in a circular dish. Similarly to choosing three pints, we can describe a selection of ice cream in terms of which one goes in the dish first, which one goes in second (say to the right of the first), and which one goes in third (say to the right of the second scoop, which makes it to the left of the first scoop). But again, two of these lists will sometimes be equivalent. Once they are in the dish, we can't tell which one went in first. However, there is a subtle difference between putting each flavor in its own small dish and putting all three flavors in a circle in a larger dish. Think about what makes the lists of flavors equivalent, and draw the directed graph whose vertices consist of all lists of three of the flavors of ice cream and whose edges connect two lists that we cannot tell the difference between as dishes of ice cream. How many dishes of ice cream can we distinguish from one another?
If we have scoops of vanilla, chocolate, and strawberry sitting in a circle in a dish, can we distinguish between VCS and VSC?
Draw the digraph for Problem 38 in the special case where we have four people sitting around the table.
In Problems 344, 345, and 346 (as well as Problems 34, 38, and 39) we can begin with a set of lists, and say when two lists are equivalent as representations of the objects we are trying to count. In particular, in Problems 344, 345, and 346 you drew the directed graph for this relation of equivalence. Technically, you should have had an arrow from each vertex (list) to itself. This is what we mean when we say a relation is reflexive. Whenever you had an arrow from one vertex to a second, you had an arrow back to the first. This is what we mean when we say a relation is symmetric.
When people sit around a round table, each list is equivalent to itself: if List1 and List 2 are identical, then everyone has the same person to the right in both lists (including the first person in the list being to the right of the last person). To see the symmetric property of the equivalence of seating arrangements, if List1 and List2 are different, but everyone has the same person to the right when they sit according to List2 as when they sit according to List1, then everybody better have the same person to the right when they sit according to List1 as when they sit according to List2.
In Problems 344, 345 and 346 there is another property of those relations you may have noticed from the directed graph. Whenever you had an arrow from \(L_1\) to \(L_2\) and an arrow from \(L_2\) to \(L_3\text{,}\) then there was an arrow from \(L_1\) to \(L_3\text{.}\) This is what we mean when we say a relation is transitive. You also undoubtedly noticed how the directed graph divides up into clumps of mutually connected vertices. This is what equivalence relations are all about. Let's be a bit more precise in our description of what it means for a relation to be reflexive, symmetric or transitive.
If \(R\) is a relation on a set \(X\text{,}\) we say \(R\) is reflexive if \((x,x)\in R\) for every \(x\in X\text{.}\)
If \(R\) is a relation on a set \(X\text{,}\) we say \(R\) is symmetric if \((x,y)\) is in \(R\) whenever \((y,x)\) is in \(R\text{.}\)
If \(R\) is a relation on a set \(X\text{,}\) we say \(R\) is transitive if whenever \((x,y)\) is in \(R\) and \((y,z)\) is in \(R\text{,}\) then \((x,z)\) is in \(R\) as well.
Each of the relations of equivalence you worked with in Problems 344, 345 and 346 had these three properties. Can you visualize the same three properties in the relations of equivalence that you would use in Problems 34, 38, and 39? We call a relation an equivalence relation if it is reflexive, symmetric and transitive.
After some more examples, we will see how to show that equivalence relations have the kind of clumping property you saw in the directed graphs. In our first example, using the notation \((a,b) \in R\) to say that \(a\) is related to \(B\) is going to get in the way. It is really more common to write \(a R b\) to mean that \(a\) is related to \(b\text{.}\) For example, if our relation is the less than relation on \(\{1,2,3\}\text{,}\) you are much more likely to use \(x\lt y\) than you are \((x,y)\in \ \lt\text{,}\) aren't you? The reflexive law then says \(xRx\) for every \(x\) in \(X\text{,}\) the symmetric law says that if \(xRy\text{,}\) then \(yRx\text{,}\) and the transitive law says that if \(xRy\) and \(yRz\text{,}\) then \(xRz\text{.}\)
For the necklace problem, Problem 43, our lists are lists of beads. What makes two lists equivalent for the purpose of describing a necklace? Verify explicitly that this relationship of equivalence is reflexive, symmetric, and transitive.
Which of the reflexive, symmetric and transitive properties does the \(\lt\) relation on the integers have?
A relation \(R\) on the set of ordered pairs of positive integers that you learned about in grade school in another notation is the relation that says \((m,n)\) is related to \((h,k)\) if \(mk =hn\text{.}\) Show that this relation is an equivalence relation. In what context did you learn about this relation in grade school?
To show a relation is an equivalence relation, you need to show it satisfies the definition of an equivalence relation.
Another relation that you may have learned about in school, perhaps in the guise of âclock arithmetic,â is the relation of equivalence modulo \(n\text{.}\) For integers (positive, negative, or zero) \(a\) and \(b\text{,}\) we write \(a \equiv b \pmod{n}\) to mean that \(a-b\) is an integer multiple of \(n\text{,}\) and in this case, we say that \(a\) is congruent to \(b\) modulo \(n\) and write \(a\equiv b \pmod{n}\text{..}\) Show that the relation of congruence modulo \(n\) is an equivalence relation.
Define a relation on the set of all lists of \(n\) distinct integers chosen from \(\{1,2,\ldots, n\}\text{,}\) by saying two lists are related if they have the same elements (though perhaps in a different order) in the first \(k\) places, and the same elements (though perhaps in a different order) in the last \(n-k\) places. Show this relation is an equivalence relation.
Suppose that \(R\) is an equivalence relation on a set \(X\) and for each \(x\in X\text{,}\) let \(C_x = \{y| y\in X \text{ and } yRx\}\text{.}\) If \(C_x\) and \(C_z\) have an element \(y\) in common, what can you conclude about \(C_x\) and \(C_z\) (besides the fact that they have an element in common!)? Be explicit about what property(ies) of equivalence relations justify your answer. Why is every element of \(X\) in some set \(C_x\text{?}\) Be explicit about what property(ies) of equivalence relations you are using to answer this question. Notice that we might simultaneously denote a set by \(C_x\) and \(C_y\text{.}\) Explain why the union of the sets \(C_x\) is \(X\text{.}\) Explain why two distinct sets \(C_x\) and \(C_z\) are disjoint. What do these sets have to do with the âclumpingâ you saw in the digraph of Problem 344 and Problem 345?
In Problem 352 the sets \(C_x\) are called equivalence classes of the equivalence relation \(R\text{.}\) You have just proved that if \(R\) is an equivalence relation of the set \(X\text{,}\) then each element of \(X\) is in exactly one equivalence class of \(R\text{.}\) Recall that a partition of a set \(X\) is a set of disjoint sets whose union is \(X\text{.}\) For example, \(\{1,3\}\text{,}\) \(\{2,4,6\}\text{,}\) \(\{5\}\) is a partition of the set \(\{1,2,3,4,5,6\}\text{.}\) Thus another way to describe what you proved in Problem 352 is the following:
If \(R\) is an equivalence relation on \(X\text{,}\) then the set of equivalence classes of \(R\) is a partition of \(X\text{.}\)
Since a partition of \(S\) is a set of subsets of \(S\text{,}\) it is common to call the subsets into which we partition \(S\) the blocks of the partition so that we don't find ourselves in the uncomfortable position of referring to a set and not being sure whether it is the set being partitioned or one of the blocks of the partition.
In each of Problems 38, Problem 39, Problem 43, Problem 344, and Problem 345, what does an equivalence class correspond to? (Five answers are expected here.)
To get you started, in Problem 38 the equivalence classes correspond to seating arrangements.
Given the partition \(\{1,3\}\text{,}\) \(\{2,4,6\}\text{,}\) \(\{5\}\) of the set \(\{1,2,3,4,5,6\}\text{,}\) define two elements of \(\{1,2,3,4,5,6\}\) to be related if they are in the same part of the partition. That is, define 1 to be related to 3 (and 1 and 3 each related to itself), define 2 and 4, 2 and 6, and 4 and 6 to be related (and each of 2, 4, and 6 to be related to itself), and define 5 to be related to itself. Show that this relation is an equivalence relation.
Suppose \(P = \{S_1, S_2, S_3, \ldots, S_k\}\) is a partition of \(S\text{.}\) Define two elements of \(S\) to be related if they are in the same set \(S_i\text{,}\) and otherwise not to be related. Show that this relation is an equivalence relation. Show that the equivalence classes of the equivalence relation are the sets \(S_i\text{.}\)
In Problem 353 you just proved that each partition of a set gives rise to an equivalence relation whose classes are just the parts of the partition. Thus in Problem 352 and Problem 353 you proved the following Theorem.
A relation \(R\) is an equivalence relation on a set \(S\) if and only if \(S\) may be partitioned into sets \(S_1\text{,}\) \(S_2\text{,}\) âŠ, \(S_n\) in such a way that \(x\) and \(y\) are related by \(R\) if and only if they are in the same block \(S_i\) of the partition.
In Problems 344, Problem 345, Problem 38 and Problem 43 what we were doing in each case was counting equivalence classes of an equivalence relation. There was a special structure to the problems that made this somewhat easier to do. For example, in Problem 344, we had \(4\cdot3\cdot2 =24\) lists of three distinct flavors chosen from V, C, S, and P. Each list was equivalent to \(3\cdot2\cdot1=3!=6\) lists, including itself, from the point of view of serving 3 small dishes of ice cream. The order in which we selected the three flavors was unimportant. Thus the set of all \(4\cdot3\cdot2\) lists was a union of some number \(n\) of equivalence classes, each of size 6. By the product principle, if we have a union of \(n\) disjoint sets, each of size 6, the union has \(6n\) elements. But we already knew that the union was the set of all 24 lists of three distinct letters chosen from our four letters. Thus we have \(6n=24\text{,}\) or \(n=4\) equivalence classes.
In Problem 345 there is a subtle change. In the language we adopted for seating people around a round table, if we choose the flavors V, C, and S, and arrange them in the dish with C to the right of V and S to the right of C, then the scoops are in different relative positions than if we arrange them instead with S to the right of V and C to the right of S. Thus the order in which the scoops go into the dish is somewhat importantâsomewhat, because putting in V first, then C to its right and S to its right is the same as putting in S first, then V to its right and C to its right. In this case, each list of three flavors is equivalent to only three lists, including itself, and so if there are \(n\) equivalence classes, we have \(3n=24\text{,}\) so there are \(24/3=8\) equivalence classes.
If we have an equivalence relation that divides a set with \(k\) elements up into equivalence classes each of size \(m\text{,}\) what is the number \(n\) of equivalence classes? Explain why.
In Problem 347, what is the number of equivalence classes? Explain in words the relationship between this problem and the Problem 39.
Describe explicitly what makes two lists of beads equivalent in Problem 43 and how Problem 356 can be used to compute the number of different necklaces.
What are the equivalence classes (write them out as sets of lists) in Problem 45, and why can't we use Problem 356 to compute the number of equivalence classes?
In Problem 356 you proved our next theorem. In Chapter 1 (Problem 42) we discovered and stated this theorem in the context of partitions and called it the Quotient Principle
If an equivalence relation on a set \(S\) size \(k\) has \(n\) equivalence classes each of size \(m\text{,}\) then the number of equivalence classes is \(k/m\text{.}\)
