Skip to main content
Mathematics LibreTexts

Appendix A: Relations

  • Page ID
    77605
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    A.1: Relations as Sets of Ordered Pairs

    A.1.1: The Relation of a Function

    Exercise \(328\)

    Consider the functions from \(S = \{−2, −1, 0, 1, 2\}\) to \(T = \{1, 2, 3, 4, 5\}\) defined by \(f(x) = x + 3\), and \(g(x) = x^5 − 5x^3 + 5x + 3\). Write down the set of ordered pairs \((x, f(x))\) for \(x ∈ S\) and the set of ordered pairs \((x, g(x))\) for \(x ∈ S\). Are the two functions the same or different?

    Problem 328 points out how two functions which appear to be different are actually the same on some domain of interest to us. Most of the time when we are thinking about functions it is fine to think of a function casually as a relationship between two sets. In Problem 328 the set of ordered pairs you wrote down for each function is called the relation of the function. When we want to distinguish between the casual and the careful in talking about relationships, our casual term will be “relationship” and our careful term will be “relation.” So relation is a technical word in mathematics, and as such it has a technical definition. A relation from a set \(S\) to a set \(T\) is a set of ordered pairs whose first elements are in S and whose second elements are in \(T\). Another way to say this is that a relation from \(S\) to \(T\) is a subset of \(S × T\).

    A typical way to define a function \(f\) from a set \(S\), called the domain of the function, to a set \(T\), called the range, is that \(f\) is a relationship between \(S\) to \(T\) that relates one and only one member of \(T\) to each element of \(X\). We use \(f(x)\) to stand for the element of \(T\) that is related to the element \(x\) of \(S\). If we wanted to make our definition more precise, we could substitute the word “relation” for the word “relationship” and we would have a more precise definition. For our purposes, you can choose whichever definition you prefer. However, in any case, there is a relation associated with each function. As we said above, the relation of a function \(f: S → T\) (which is the standard shorthand for “\(f\) is a function from \(S\) to \(T\)” and is usually read as \(f\) maps \(S\) to \(T\)) is the set of all ordered pairs \((x, f(x))\) such that \(x\) is in \(S\).

    Exercise \(329\)

    Here are some questions that will help you get used to the formal idea of a relation and the related formal idea of a function. \(S\) will stand for a set of size \(s\) and \(T\) will stand for a set of size \(t\).

    a. What is the size of the largest relation from \(S\) to \(T\)?

    b. What is the size of the smallest relation from \(S\) to \(T\)?

    c. The relation of a function \(f: S → T\) is the set of all ordered pairs \((x, f(x))\) with \(x ∈ S\). What is the size of the relation of a function from \(S\) to \(T\)? That is, how many ordered pairs are in the relation of a function from \(S\) to \(T\)? (Hint).

    d. We say \(f\) is a one-to-one function or injection from \(S\) to \(T\) if each member of \(S\) is related to a different element of \(T\). How many different elements must appear as second elements of the ordered pairs in the relation of a one-to-one function (injection) from \(S\) to \(T\)?

    e. A function \(f: S → T\) is called an onto function or surjection if each element of \(T\) is \(f(x)\) for some \(x ∈ S\) What is the minimum size that \(S\) can have if there is a surjection from \(S\) to \(T\)?

    Exercise \(330\)

    When \(f\) is a function from \(S\) to \(T\), the sets \(S\) and \(T\) play a big role in determining whether a function is one-to-one or onto (as defined in Problem 329). For the remainder of this problem, let \(S\) and \(T\) stand for the set of nonnegative real numbers.

    a. If \(f: S → T\) is given by \(f(x) = x^2\), is \(f\) one-to-one? Is \(f\) onto?

    b. Now assume \(S′\) is the set of all real numbers and \(g : S′ → T\) is given by \(g(x) = x^2\). Is \(g\) one-to-one? Is \(g\) onto?

    c. Assume that \(T′\) is the set of all real numbers and \(h : S → T′\) is given by \(h(x) = x^2\). Is \(h\) one-to-one? Is \(h\) onto?

    d. And if the function \(j : S′ → T′\) is given by \(j(x) = x^2\), is \(j\) one-to-one? Is \(j\) onto?

    Exercise \(331\)

    If \(f : S → T\) is a function, we say that \(f\) maps \(x\) to \(y\) as another way to say that \(f(x) = y\). Suppose \(S = T = \{1, 2, 3\}\). Give a function from \(S\) to \(T\) that is not onto. Notice that two different members of \(S\) have mapped to the same element of \(T\). Thus when we say that \(f\) associates one and only one element of \(T\) to each element of \(S\), it is quite possible that the one and only one element \(f(1)\) that \(f\) maps \(1\) to is exactly the same as the one and only one element \(f(2)\) that \(f\) maps \(2\) to.

    A.1.2: Directed Graphs

    We visualize numerical functions like \(f(x) = x^2\) with their graphs in Cartesian coordinate systems. We will call these kinds of graphs coordinate graphs to distinguish them from other kinds of graphs used to visualize relations that are non-numerical.

    clipboard_e688cd12c12ba9fffa74cae49aec75922.png
    Figure \(A.1.2.1\): The alphabet digraph. (Copyright; author via source)

    In Figure A.1.2.1, we illustrate another kind of graph, a “directed graph” or “digraph” of the “comes before in alphabetical order" relation on the letters \(a\), \(b\), \(c\), and \(d\). To draw a directed graph of a relation on a set \(S\), we draw a circle (or dot, if we prefer), which we call a vertex, for each element of the set, we usually label the vertex with the set element it corresponds to, and we draw an arrow from the vertex for \(a\) to that for \(b\) if \(a\) is related to \(b\), that is, if the ordered pair \((a, b)\) is in our relation. We call such an arrow an edge or a directed edge. We draw the arrow from \(a\) to \(b\), for example, because \(a\) comes before \(b\) in alphabetical order. We try to choose the locations where we draw our vertices so that the arrows capture what we are trying to illustrate as well as possible. Sometimes this entails redrawing our directed graph several times until we think the arrows capture the relationship well.

    We also draw digraphs for relations from a set \(S\) to a set \(T\); we simply draw vertices for the elements of \(S\) (usually in a row) and vertices for the elements of \(T\) (usually in a parallel row) draw an arrow from \(x\) in \(S\) to \(y\) in \(T\) if \(x\) is related to \(y\). Notice that instead of referring to the vertex representing \(x\), we simply referred to \(x\). This is a common shorthand. Here are some exercises just to practice drawing digraphs.

    Exercise \(332\)

    Draw the digraph of the “is a proper subset of” relation on the set of subsets of a two element set. How many arrows would you have had to draw if this problem asked you to draw the digraph for the subsets of a three-element set? (Hint).

    We also draw digraphs for relations from finite set \(S\) to a finite set \(T\); we simply draw vertices for the elements of \(S\) (usually in a row) and vertices for the elements of \(T\) (usually in a parallel row) and draw an arrow from \(x\) in \(S\) to \(y\) in \(T\) if \(x\) is related to \(y\). Notice that instead of referring to the vertex representing \(x\), we simply referred to \(x\). This is a common shorthand.

    Exercise \(333\)

    Draw the digraph of the relation from the set \(\{\text{A, M, P, S}\}\) to the set \(\{\text{Sam, Mary, Pat, Ann, Polly, Sarah}\}\) given by “is the first letter of.”

    Exercise \(334\)

    Draw the digraph of the relation from the set \(\{\text{Sam, Mary, Pat, Ann, Polly, Sarah}\}\) to the set \(\{\text{A, M, P, S}\}\) given by “has as its first letter.”

    Exercise \(335\)

    Draw the digraph of the relation on the set \(\{\text{Sam, Mary, Pat, Ann, Polly, Sarah}\}\) given by “has the same first letter as.”

    A.1.3: Digraphs of Functions

    Exercise \(336\)

    When we draw the digraph of a function \(f\), we draw an arrow from the vertex representing \(x to the vertex representing \(f(x). One of the relations you considered in Problems 333 and Problem 334 is the relation of a function.

    a. Which relation is the relation of a function?

    b. How does the digraph help you visualize that one relation is a function and the other is not?

    Exercise \(337\)

    Digraphs of functions help us to visualize whether or not they are onto or one-to-one. For example, let both \(S\) and \(T\) be the set \(\{−2, −1, 0, 1, 2\}\) and let \(S′\) and \(T′\) be the set \(\{0, 1, 2\}\). Let \(f(x)=2 − |x|\).

    a. Draw the digraph of the function \(f\) assuming its domain is \(S\) and its range is \(T\). Use the digraph to explain why or why not this function maps \(S\) onto \(T\).

    b. Use the digraph of the previous part to explain whether or not the function is one-to-one.

    c. Draw the digraph of the function \(f\) assuming its domain is \(S\) and its range is \(T′\). Use the digraph to explain whether or not the function is onto.

    d. Use the digraph of the previous part to explain whether or not the function is one-to-one.

    e. Draw the digraph of the function \(f\) assuming its domain is \(S′\) and its range is \(T′\). Use the digraph to explain whether the function is onto.

    f. Use the digraph of the previous part to explain whether the function is one-to-one.

    g. Suppose the function \(f\) has domain \(S′\) and range \(T\). Draw the digraph of \(f\) and use it to explain whether \(f\) is onto.

    h. Use the digraph of the previous part to explain whether \(f\) is one-to-one.

    A one-to-one function from a set \(X\) onto a set \(Y\) is frequently called a bijection, especially in combinatorics. Your work in Problem 337 should show you that a digraph is the digraph of a bijection from \(X\) to \(Y\)

    • if the vertices of the digraph represent the elements of \(X\) and \(Y\),
    • if each vertex representing an element of \(X\) has one and only one arrow leaving it, and
    • each vertex representing an element of \(Y\) has one and only one arrow entering it.

    Exercise \(338\)

    If we reverse all the arrows in the digraph of a bijection \(f\), we get the digraph of another function \(g\). Is \(g\) a bijection? What is \(f(g(x))\)? What is \(g(f(x))\)?

    If \(f\) is a function from \(S\) to \(T\), if \(g\) is a function from \(T\) to \(S\), and if \(f(g(x)) = x\) for each \(x\) in \(T\) and \(g(f(x)) = x\) for each \(x\) in \(S\), then we say that \(g\) is an inverse of \(f\) (and \(f\) is an inverse of \(g\)).

    More generally, if \(f\) is a function from a set \(R\) to a set \(S\), and \(g\) is a function from \(S\) to \(T\), then we define a new function \(f ◦ g\), called the composition of \(f\) and \(g\), by \(f ◦ g(x) = f(g(x))\). Composition of functions is a particularly important operation in subjects such as calculus, where we represent a function like \(h(x) = \sqrt{x^2 + 1}\) as the composition of the square root function and the square and add one function in order to use the chain rule to take the derivative of \(h\).

    The function \(ι\) (the Greek letter iota is pronounced eye-oh-ta) from a set \(S\) to itself, given by the rule \(ι(x) = x\) for every \(x\) in \(S\), is called the identity function on \(S\). If \(f\) is a function from \(S\) to \(T\) and \(g\) is a function from \(T\) to \(S\) such that \(g(f(x)) = x\) for every \(x\) in \(S\), we can express this by saying that \(g ◦ f = ι\), where \(ι\) is the identity function of \(S\). Saying that \(f(g(x)) = x\) is the same as saying that \(f ◦ g = ι\), where \(ι\) stands for the identity function on \(T\). We use the same letter for the identity function on two different sets when we can use context to tell us on which set the identity function is being defined.

    Exercise \(339\)

    If \(f\) is a function from \(S\) to \(T\) and \(g\) is a function from \(T\) to \(S\) such that \(g(f(x)) = x\), how can we tell from context that \(g ◦ f\) is the identity function on \(S\) and not the identity function on \(T\)? (Hint).

    Exercise \(340\)

    Explain why a function that has an inverse must be a bijection.

    Exercise \(341\)

    Is it true that the inverse of a bijection is a bijection?

    Exercise \(342\)

    If \(g\) and \(h\) are inverse of \(f\), then what can we say about \(g\) and \(h\)?

    Exercise \(343\)

    Explain why a bijection must have an inverse.

    Since a function with an inverse has exactly one inverse \(g\), we call \(g\) the inverse of \(f\). From now on, when \(f\) has an inverse, we shall denote its inverse by \(f −1\). Thus \(f(f −1(x)) = x\) and \(f −1(f(x)) = x\). Equivalently, \(f ◦ f −1 = ι\) and \(f −1 ◦ f = ι\).

    A.2: Equivalence Relations

    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 · 11 · 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 · 11 · 10\) lists. Even with five flavors of ice cream, we would need one vertex for each of \(5·4·3 = 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.

    Exercise \(344\)

    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?

    \(\rightarrow\) Exercise \(345\)

    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? (Hint).

    Exercise \(346\)

    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\), then there was an arrow from \(L_1\) to \(L_3\). 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\), we say \(R\) is reflexive if \((x, x) ∈ R\) for every \(x ∈ X\).
    • If \(R\) is a relation on a set \(X\), we say \(R\) is symmetric if \((x, y)\) is in \(R\) whenever \((y, x)\) is in \(R\).
    • If \(R\) is a relation on a set \(X\), we say \(R\) is transitive if whenever \((x, y)\) is in \(R\) and \((y, z)\) is in \(R\), 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) ∈ R\) to say that \(a\) is related to \(B\) is going to get in the way. It is really more common to write \(aRb\) to mean that a is related to \(b\). For example, if our relation is the less than relation on \(\{1, 2, 3\}\), you are much more likely to use \(x < y\) than you are \((x, y) ∈ <\), aren’t you? The reflexive law then says \(xRx\) for every \(x\) in \(X\), the symmetric law says that if \(xRy\), then \(yRx\), and the transitive law says that if \(xRy\) and \(yRz\), then \(xRz\).

    Exercise \(347\)

    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.

    Exercise \(348\)

    Which of the reflexive, symmetric and transitive properties does the \(<\) relation on the integers have?

    Exercise \(349\)

    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\). Show that this relation is an equivalence relation. In what context did you learn about this relation in grade school? (Hint).

    Exercise \(350\)

    Another relation that you may have learned about in school, perhaps in the guise of “clock arithmetic,” is the relation of equivalence modulo \(n\). For integers (positive, negative, or zero) \(a\) and \(b\), we write \(a ≡ b (\text{mod } n)\) to mean that \(a − b\) is an integer multiple of \(n\), and in this case, we say that \(a\) is congruent to \(b\) modulo \(n\) and write \(a ≡ b (\text{mod } n)\). Show that the relation of congruence modulo \(n\) is an equivalence relation.

    Exercise \(351\)

    Define a relation on the set of all lists of n distinct integers chosen from \(\{1, 2,..., n\}\), 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.

    Exercise \(352\)

    Suppose that \(R\) is an equivalence relation on a set \(X\) and for each \(x ∈ X\), let \(C_x = \{y|y ∈ X \text{ and } yRx\}\). 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 \(Cx\)? 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\). Explain why the union of the sets \(C_x\) is \(X\). 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\). You have just proved that if \(R\) is an equivalence relation of the set \(X\), then each element of \(X\) is in exactly one equivalence class of \(R\). Recall that a partition of a set \(X\) is a set of disjoint sets whose union is \(X\). For example, \(\{1, 3\}, \{2, 4, 6\}, \{5\}\) is a partition of the set \(\{1, 2, 3, 4, 5, 6\}\). Thus another way to describe what you proved in Problem 352 is the following:

    Theorem \(A.2.1\)

    If \(R\) is an equivalence relation on \(X\), then the set of equivalence classes of \(R\) is a partition of \(X\).

    Since a partition of \(S\) is a set of subsets of \(S\), 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.

    Exercise \(353\)

    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.) (Hint).

    Exercise \(354\)

    Given the partition \(\{1, 3\}\), \(\{2, 4, 6\}\), \(\{5\}\) of the set \(\{1, 2, 3, 4, 5, 6\}\), 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.

    Exercise \(355\)

    Suppose \(P = \{S_1, S_2, S_3,..., S_k \}\) is a partition of \(S\). Define two elements of \(S\) to be related if they are in the same set \(S_i\), 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\).

    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.

    Theorem \(A.2.2\)

    A relation \(R\) is an equivalence relation on a set \(S\) if and only if \(S\) may be partitioned into sets \(S_1, S_2,..., 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 · 3 · 2 = 24\) lists of three distinct flavors chosen from V, C, S, and P. Each list was equivalent to \(3 · 2 · 1 = 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 · 3 · 2\) 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\), 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\), so there are \(\dfrac{24}{3} = 8\) equivalence classes.

    Exercise \(356\)

    If we have an equivalence relation that divides a set with \(k\) elements up into equivalence classes each of size \(m\), what is the number \(n\) of equivalence classes? Explain why.

    Exercise \(357\)

    In Problem 347, what is the number of equivalence classes? Explain in words the relationship between this problem and the Problem 39.

    Exercise \(358\)

    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.

    Exercise \(359\)

    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

    Theorem \(A.2.3\)

    If an equivalence relation on a set \(S\) size \(k\) has \(n\) equivalence classes each of size \(m\), then the number of equivalence classes is \(k/m\).