7  Relations

Using ordered pairs, we can formulate the mathematical theory of relations in set-theoretic language. By a relation we mean here something like marriage (between men and women) belonging (between elements and sets). More explicitly, what we shall call a relation is sometimes called a binary relation. An example of a ternary relation is parenthood for people (Adam and Eve are the parents of Cain). In this book we shall have no occasion to treat the theory of relations that are ternary, quaternary, or worse.

Looking at any specific relation, such as marriage for instance, we might be tempted to consider certain ordered pairs \((x,y)\), namely just those for which \(x\) is man, \(y\) is a woman, and \(x\) is married to \(y\). We have not yet seen the definition of the general concept of a relation, but it seems plausible that, just as in this marriage example, every relation should uniquely determine the set of all those ordered pairs for which the first coordinate does stand in that relation to the second. If we know the relation, we know the set, and, better yet, if we know the set, we know the relation. If, for instance, we were presented with the set of ordered pairs of people that corresponds to marriage, then, even if we forgot the definition of marriage, we could always tell when a man \(x\) is married to a woman \(y\) and when not; we would just have to see whether the ordered pair \((x,y)\) does or does not belong to the set.

We may not know what a relation is, but we do know what a set is, and the preceding considerations establish a close connection between relations and sets. The precise set-theoretic treatment of relations takes advantage of that heuristic connection; the simplest to do is to define a relation to be the corresponding set. This is what we do; we hereby define a relation as a set of ordered pairs. Explicitly: a set \(R\) is a relation if each element of \(R\) is an ordered pair; this means, of course, that if \(z \in R\), then there exist \(x\) and \(y\) so that \(z = (x,y)\). If \(R\) is relation, it is sometimes convenient to express the fact that \((x, y) \in R\) by writing

\[ xRy \]

and saying, as in everyday language, that \(x\) stands in the relation \(R\) to \(y\).

The least exciting relation is the empty one. (To prove that \(\emptyset\) is a set of ordered pairs, look for an element of \(\emptyset\) that is not an ordered pair.) Another dull example is the Cartesian product of any two sets \(X\) and \(Y\). Here is a slightly more interesting example: let \(X\) be any set, and let \(R\) be the set of all those pairs \((x, y)\) in \(X \times X\) for which \(x = y\). The relation \(R\) is just the relation of equality between elements of \(X\); if \(x\) and \(y\) are in \(X\), then \(xRy\) means the same as \(x = y\). One more example will suffice for now: let \(X\) be any set, and let \(R\) be the set of all those pairs \((x, A)\) in \(X \times \mathcal{P} (X)\) for which \(x \in A\). This relation \(R\) is just the relation of belonging between elements of \(X\) and subsets of \(X\); if \(x \in X\) and \(A \in \mathcal{P}(X)\), then \(x RA\) means the same as \(x \in A\).

In the preceding section we saw that associated with every set \(R\) of ordered pairs there are two sets called the projections of \(R\) onto the first and second coordinates. In the theory of relations these sets are known as the domain and the range of \(R\) (abbreviated \(\text{dom } R\) and \(\text{ran } R\)); we recall that they are defined by

\[ \text{dom } R = \{ x: \mathit{for\ some\ } y \: (x R y) \} \]

and

\[ \text{ran } R = \{ y: \mathit{\ for\ some\ } x \: (x R y) \}. \]

If \(R\) is the relation of marriage, so that \(xRy\) means that \(x\) is a man, \(y\) is a woman, and \(x\) and \(y\) are married to one another; then \(\text{dom } R\) is the set of married men and \(\text{ran } R\) is the set of married womem. Both the domain and the range of \(\emptyset\) are equal to \(\emptyset\). If \(R = X \times Y\), then \(\text{dom } R = X\) and \(\text{ran } R = Y\). If \(R\) is equality in \(X\), then \(\text{dom } R = \text{ran } R = X\). If \(R\) is belonging, between \(X\) and \(\mathcal{P}(X)\), then \(\text{dom } R = X\) and \(\text{ran } R = \mathcal{P}(X) - \{ \emptyset \}\).

If \(R\) is a relation included in a Cartesian product \(X \times Y\) (so that \(\text{dom } R \subset X\) and \(\text{ran } R \subset Y\)), it is sometimes convenient to say that \(R\) is a relation from \(X\) to \(Y\); instead of a relation from \(X\) to \(X\) we may speak of a relation in \(X\). A relation \(R\) in \(X\) is reflexive if \(xRx\) for every \(x\) in \(X\); it is symmetric if \(xRy\) implies that \(yRx\); and it is transitive if \(xRy\) and \(yRz\) imply that \(xRz\). (Exercise: for each of these three possible properties, find a relation that does not have that property but does have the other two.) A relation in a set is an equivalence relation if it is reflexive, symmetric, and transitive. The smallest equivalence relation in a set \(X\) is the relation of equality in \(X\); the largest equivalence relation in \(X\) is \(X \times X\).

There is an intimate connection between equivalence relations in a set \(X\) and certain collections (called partitions) of subsets of \(X\). A partition of \(X\) is a disjoint collection \(\mathcal{C}\) of non-empty subsets of \(X\) whose union is \(X\). If \(R\) is an equivalence relation in \(X\), and if \(x\) is in \(X\), the equivalence class of \(x\) with respect to \(R\) is the set of all those elements \(y\) in \(X\) for which \(xRy\). (The weight of tradition makes the use of the word “class” at this point unavoidable.) Examples: if \(R\) is equality in \(X\), then each equivalence class is a singleton; if \(R = X \times X\), then the set \(X\) itself is the only equivalence class. There is no standard notation for the equivalence class of \(x\) with respect to \(R\); we shall usually denote it by \(x/R\), and we shall write \(X/R\) for the set of all equivalence classes. (Pronounce \(X/R\) as “\(X\) modulo \(R\),” or, in abbreviated form, “\(X \text{ mod } R\).” Exercise: show that \(X/R\) is indeed a set by exhibiting a condition that specifies exactly the subset \(X/R\) of the power set \(\mathcal{P}(X)\).) Now forget \(R\) for a moment and begin anew with a partition \(\mathcal{C}\) of \(X\). A relation, which we shall call \(X/\mathcal{C}\), is defined in \(X\) by writing

\[ x \: X/ \mathcal{C} \: y \]

just in case \(x\) and \(y\) belong to the same set of the collection \(\mathcal{C}\). We shall call \(X/\mathcal{C}\) the relation induced by the partition \(\mathcal{C}\).

In the preceding paragraph we saw how to associate a set of subsets of \(X\) with every equivalence relation in \(X\) and how to associate a relation in \(X\) with every partition of \(X\). The connection between equivalence relations and partitions can be described by saying that the passage from \(\mathcal{C}\) to \(X/\mathcal{C}\) is exactly the reverse of the passage from \(R\) to \(X/R\). More explicitly: if \(R\) is an equivalence relation in \(X\), then the set of equivalence classes is a partition of \(X\) that induces the relation \(R\), and if \(\mathcal{C}\) is a partition of \(X\), then the induced relation is an equivalence relation whose set of equivalence classes is exactly \(\mathcal{C}\).

For the proof, let us start with an equivalence relation \(R\). Since each \(x\) belongs to some equivalence class (for instance \(x \in x/R\)), it is clear that the union of the equivalence classes is all \(X\). If \(z \in x/R \cap y/ R\), then \(xRz\) and \(zRy\), and therefore \(xRy\). This implies that if two equivalence classes have an element in common, then they are identical, or, in other words, that two distinct equivalence classes are always disjoint. The set of equivalence classes is therefore a partition. To say that two elements belong to the same set (equivalence class) of this partition means, by definition, that they stand in the relation \(R\) to one another. This proves the first half of our assertion.

The second half is easier. Start with a partition \(\mathcal{C}\) and consider the induced relation. Since every element of \(X\) belongs to some set of \(\mathcal{C}\), reflexivity just says that \(x\) and \(x\) are in the same set of \(\mathcal{C}\). Symmetry says that if \(x\) and \(y\) are in the same set of \(\mathcal{C}\), then \(y\) and \(x\) are in the same set of \(\mathcal{C}\), and this is obviously true. Transitivity says that if \(x\) and \(y\) are in the same set of \(\mathcal{C}\) and if \(y\) and \(z\) are in the same set of \(\mathcal{C}\), then \(x\) and \(z\) are in the same set of \(\mathcal{C}\), and this too is obvious. The equivalence class of each \(x\) in \(X\) is just the set of \(\mathcal{C}\) to which \(x\) belongs. This completes the proof of everything that was promised.