2.7: Relations

In Section 2.4, we saw that “mother of” is a functional relationship because every person has one and only one mother, but that “child of” is not a functional relationship, because a person can have no children or more than one child. However, the relationship expressed by “child of” is certainly one that we have a right to be interested in and one that we should be able to deal with mathematically.

There are many examples of relationships that are not functional re- lationships. The relationship that holds between two natural numbers nand m when \(n \leq m\) is an example in mathematics. The relationship be- tween a person and a book that that person has on loan from the library is another. Some relationships involve more than two entities, such as the relationship that associates a name, an address, and a phone number in an address book or the relationship that holds among three real numbers \(x, y\), and \(z\) if \(x^{2}+y^{2}+z^{2}=1\) Each of these relationships can be represented mathematically by what is called a “relation.”

A relation on two sets, A and B, is defined to be a subset of A×B. Since a function from A to B is defined, formally, as a subset of A × B that satisfies certain properties, a function is a relation. However, relations are more general than functions, since any subset of A × B is a relation. We also define a relation among three or more sets to be a subset of the cross product of those sets. In particular, a relation on A, B, and C is a subset of A × B × C.

For example, if P is the set of people and B is the set of books owned by a library, then we can define a relation \(\mathcal{R}\) on the sets P and B to be the set \(\mathcal{R}=\{(p, b) \in P \times B | p\) has \(b\) out on loan \(\}\). The fact that a particular \((p, b) \in \mathcal{R}\) is a fact about the world that the library will certainly want to keep track of. When a collection of facts about the world is stored on a computer, it is called a database. We’ll see in the next section that relations are the most common means of representing data in databases.

If A is a set and R is a relation on the sets A and A (that is, on two copies of A), then R is said to be a binary relation on A. That is, a binary relation on the set A is a subset of A × A. The relation consisting of all ordered pairs (c,p) of people such that c is a child of p is a binary relation on the set of people. The set \(\{(n, m) \in \mathbb{N} \times \mathbb{N} | n \leq m\}\) is a binary relation on \(\mathbb{N}\). Similarly, we define a ternary relation on a set A to be a subset of A×A×A. The set \(\left\{(x, y, z) \in \mathbb{R} \times \mathbb{R} \times \mathbb{R} | x^{2}+y^{2}+z^{2}=1\right\}\) is a ternary relation on \(\mathbb{R}\). For complete generality, we can define an n-ary relation on A, for any positive integer n, to be a subset of A×A×···×A, where A occurs n times in the cross product. For the rest of this section, we will be working exclusively with binary relations. Suppose that \(\mathcal{R} \subseteq A \times A\). That is, suppose that \(\mathcal{R}\) is a binary relation on a set A. If \((a, b) \in \mathcal{R}\), then we say that \(a\) is related to \(b\) by \(\mathcal{R}\). Instead of writing "(a,b) \(\in \mathcal{R}^{\prime \prime},\) we will often write "a \(\mathcal{R} b^{\prime \prime}\). This notation is used in analogy to the notation \(n \leq m\) to express the relation that n is less than or equal to m. Remember that \(a \mathcal{R} b\) is just an alternative way of writing \((a, b) \in \mathcal{R}\). In fact, we could consider the relation \(\leq\) to be a set of ordered pairs and write \((n, m) \in \leq\) in place of the notation \(n \leq m\).

In many applications, attention is restricted to relations that satisfy some property or set of properties. (This is, of course, just what we do when we study functions.) We begin our discussion of binary relations by considering several important properties. In this discussion, let A be a set and let \(\mathcal{R}\) be a binary relation on A, that is, a subset of A×A.

\(\mathcal{R}\) is said to be reflexive if \(\forall a \in A(a \mathcal{R} a)\). That is, a binary relation on a set is reflexive if every element of the set is related to itself. This is true, for example, for the relation \(\leq\) on the set \(\mathbb{N},\) since \(n \leq n\) for every \(n \in \mathbb{N}\). On the other hand, it is not true for the relation \(<\) on \(\mathbb{N}\), since, for example, the statement \(17<17\) is false. \(^{7}\).

\(\mathcal{R}\) is called transitive if \(\forall a \in A, \forall b \in A, \forall c \in A((a \mathcal{R} b \wedge b \mathcal{R} c) \rightarrow\) \((a \mathcal{R} c) )\). Transitivity allows us to “chain together” two true statements \(a \mathcal{R} b\) and \(b \mathcal{R} c\) , which are “linked” by the b that occurs in each statement, to deduce that \(a \mathcal{R} c\). For example, suppose P is the set of people, and define the relation C on \(P\) such that \(x \mathcal{P} y\) if and only if x is a child of y. The relation \(\mathcal{P}\) is not transitive because the child of a child of a person is not a child of that person. Suppose, on the other hand, that we define a relation \(\mathcal{D}\) on P such that \(x \mathfrak{D} y\) if and only if x is a descendent of y. Then D is a transitive relation on the set of people, since a descendent of a descendent of a person is a descendent of that person. That is, from the facts that Elizabeth is a descendent of Victoria and Victoria is a descendent of James, we can deduce that Elizabeth is a descendent of James. In the mathematical world, the relations \(\leq\) and \(<\) on the set \(\mathbb{N}\) are both transitive.

\(\mathcal{R}\) is said to be symmetric if \(\forall a \in A, \forall b \in B(a \Re b \rightarrow b \mathcal{R} a)\). Thatis, whenever a is related to b, it follows that b is related to a. The relation “is a first cousin of” on the set of people is symmetric, since whenever x is a first cousin of y, we have automatically that y is a first cousin of x. On the other hand, the “child of” relation is certainly not symmetric. The relation \(\leq\) on \(\mathbb{N}\) is not symmetric. From the fact that \(n \leq m\) , we cannot conclude that \(m \leq n\). It is true for some \(n\) and \(m\) in \(\mathbb{N}\) that \(n \leq m \rightarrow m \leq n\), but it is not true for all \(n\) and \(m\) in \(\mathbb{N} .\)

Finally, \(\mathcal{R}\) is antisymmetric if \(\forall a \in A, \forall b \in B((a \mathcal{R} b \wedge b \mathcal{R} a) \rightarrow a=b)\). Finally, The relation \(\mathcal{R}\) is antisymmetric if for any two distinct elements x and y of A, we can’t have both \(x \mathcal{R} y\) and \(y \mathcal{R} x\). The relation \(\leq\) on \(\mathbb{N}\) is antisymmetric because from the facts that \(n \leq m\) and \(m \leq n\), we can deduce that n = m.The relation “child of” on the set of people is antisymmetric since it’s impossible to have both that x is a child of y and y is a child of x.

There are a few combinations of properties that define particularly useful types of binary relations. The relation \(\leq\) on the set \(\mathbb{N}\) is reflexive, antisymmetric, and transitive. These properties define what is called a partial order: A partial order on a set A is a binary relation on A that is reflexive, antisymmetric, and transitive.

Another example of a partial order is the subset relation, \(\subseteq\), on the powersetofanyset. IfX is a set, then of course \(\mathcal{P}(X)\) is a set in its own right, and \(\subseteq\) can be considered to be a binary relation on this set. Two elements A and B of \(\mathcal{P}(X)\) are related by \(\subseteq\) if and only if \(A \subseteq B\). This relation is reflexive since every set is a subset of itself. The fact that it is antisymmetric follows from Theorem 2.1. The fact that it is transitive was Exercise 11 in Section 2.1.

The ordering imposed on \(\mathbb{N}\) by \(\leq\) has one important property that the ordering of subsets by \(\subseteq\) does not share. If n and m are natural numbers, then at least one of the statements \(n \leq m\) and \(m \leq n\) must be true. However, if A and B are subsets of a set X, it is certainly possible that both \(A \subseteq B\) and \(B \subseteq A\) are false. A binary relation \(\mathcal{R}\) on a set \(A\) is said to be a total order if it is a partial order and furthermore for any two elements \(a\) and \(b\) of \(A,\) either \(a \mathcal{R} b\) or \(b \mathcal{R} a\). The relation \(\leq\) on the set \(\mathbb{N}\) is a total order. The relation \(\subseteq\) on \(\mathcal{P}(X)\) is not. (Note once again the slightly odd mathematical language: A total order is a kind of partial order—not, as you might expect, the opposite of a partial order.)

For another example of ordering, let L be the set of strings that can be made from lowercase letters. L contains both English words and nonsense strings such as “sxjja”. There is a commonly used total order on the set L, namely alphabetical order.

We’ll approach another important kind of binary relation indirectly, through what might at first appear to be an unrelated idea. Let A be a set. A partition of A is defined to be a collection of non-empty subsets of A such that each pair of distinct subsets in the collection is disjoint and the union of all the subsets in the collection is A. A partition of A is just a division of all the elements of A into non-overlapping subsets. For example, the sets \(\{1,2,6\},\{3,7\},\{4,5,8,10\},\) and \(\{9\}\) form a partition of the \(\{1,2, \ldots, 10\} .\) Each element of \(\{1,2, \ldots, 10\}\) occurs in exactly one of the sets that make up the partition. As another example, we can partition the set of all people into two sets, the set of males and the set of females. Biologists try to partition the set of all organisms into different species. Librarians try to partition books into various categories such as fiction, bi- ography, and poetry. In the real world, classifying things into categories is an essential activity, although the boundaries between categories are not al- ways well-defined. The abstract mathematical notion of a partition of a set models the real-world notion of classification. In the mathematical world, though, the categories are sets and the boundary between two categories is sharp.

In the real world, items are classified in the same category because they are related in some way. This leads us from partitions back to relations. Suppose that we have a partition of a set A. We can define a relation Ron A by declaring that for any a and b in A, \(a \mathcal{R} b\) if and only if a and bare members of the same subset in the partition. That is, two elements ofA are related if they are in the same category. It is clear that the relation defined in this way is reflexive, symmetric, and transitive.

An equivalence relation is defined to be a binary relation that is reflexive, symmetric, and transitive. Any relation defined, as above, from a partition is an equivalence relation. Conversely, we can show that any equivalence relation defines a partition. Suppose that \(\mathcal{R}\) is an equivalence relation on a set A. Let \(a \in A\). We define the equivalence class of aunder the equivalence relation \(\mathcal{R}\) to be the subset \([a]_{\mathcal{R}}\) defined as \([a]_{\mathcal{R}}=\) \(\{b \in A | b \mathcal{R} a\}\). That is, the equivalence class of a is the set of all elements of A that are related to a. In most cases, we’ll assume that the relation in question is understood, and we’ll write \([a]\) instead of \([a]_{\mathcal{R}}\). Note that each equivalence class is a subset of A. The following theorem shows that the collection of equivalence classes form a partition of A.

Theorem 2.12.

Let \(A\) be a set and let \(\mathcal{R}\) be an equivalence relation on \(A .\) Then the collection of all equivalence classes under \(\mathcal{R}\) is a partition of \(A\)

Proof. To show that a collection of subsets of A is a partition, we must show that each subset is non-empty, that the intersection of two distinct subsets is empty, and that the union of all the subsets is A.

If \([a]\) is one of the equivalence classes, it is certainly non-empty, since \(a \in[a] .\) (This follows from the fact that \(\mathcal{R}\) is reflexive, and hence \(a \mathcal{R} a . )\)To show that A is the union of all the equivalence classes, we just have to show that each element of A is a member of one of the equivalence classes. Again, the fact that \(a \in[a]\) for each \(a \in A\) shows that this is true.

Finally, we have to show that the intersection of two distinct equivalence classes is empty. Suppose that a and b are elements of A and consider the equivalence classes \([a]\) and \([b] .\) We have to show that if \([a] \neq[b]\), then \([a] \cap[b]=\emptyset\). Equivalently, we can show the converse: If \([a] \cap[b] \neq \emptyset\) then \([a]=[b]\). So, assume that \([a] \cap[b] \neq \emptyset .\) Saying that a set is not empty just means that the set contains some element, so there must be an \(x \in A\) such that \(x \in[a] \cap[b] .\) Since \(x \in[a], x \mathcal{R} a .\) Since \(\mathcal{R}\) is symmetric, we also have \(a \mathcal{R} x .\) since \(x \in[b], x \mathcal{R} b .\) since \(\mathcal{R}\) is transitive and since \((a \mathcal{R} x) \wedge(x \mathcal{R} b)\) it follows that \(a \mathcal{R} b\).

Our object is to deduce that \([a]=[b] .\) since \([a]\) and \([b]\) are sets, they are equal if and only if \([a] \subseteq[b]\) and \([b] \subseteq[a] .\) To show that \([a] \subseteq[b],\) let \(c\) be an arbitrary element of \([a] .\) We must show that \(c \in[b] .\) since \(c \in[a]\), we have that \(c \mathcal{R}\) a. And we have already shown that \(a \mathcal{R} b\). From these two facts and the transitivity of \(\mathcal{R},\) it follows that \(c \mathcal{R} b\). By definition, this means that \(c \in[b] .\) We have shown that any member of \([a]\) is a member of \([b]\) and therefore that \([a] \subseteq[b] .\) The fact that \([b] \subseteq[a]\) can be shown in the same way. We deduce that \([a]=[b],\) which proves the theorem.

The point of this theorem is that if we can find a binary relation that satisfies certain properties, namely the properties of an equivalence relation, then we can classify things into categories, where the categories are the equivalence classes.

For example, suppose that U is a possibly infinite set. Define a binary relation \(\sim\) on \(\mathcal{P}(U)\) as follows: For \(X\) and \(Y\) in \(\mathcal{P}(U), X \sim Y\) if and only if there is a bijective function from the set X to the set Y . In other words, \(X \sim Y\) means that \(X\) and \(Y\) have the same cardinality. Then \(\sim\) is an equivalence relation on \(\mathcal{P}(U)\) . (The symbol \(\sim\) is often used to denote equivalence relations. It is usually read “is equivalent to.”) If \(X \in\) \(\mathcal{P}(U),\) then the equivalence class \([X]_{\sim}\) consists of all the subsets of \(U\) that have the same cardinality as X. We have classified all the subsets of U according to their cardinality—even though we have never said what an infinite cardinality is. (We have only said what it means to have the same cardinality.)

You might remember a popular puzzle called Rubic’s Cube, a cube made of smaller cubes with colored sides that could be manipulated by twisting layers of little cubes. The object was to manipulate the cube so that the colors of the little cubes formed a certain configuration. Define two configurations of the cube to be equivalent if it’s possible to manipulate one configuration into the other by a sequence of twists. This is, in fact, an equivalence relation on the set of possible configurations. (Symmetry fol- lows from the fact that each move is reversible.) It has been shown that this equivalence relation has exactly twelve equivalence classes. The interesting fact is that it has more than one equivalence class: If the configuration that the cube is in and the configuration that you want to achieve are not in the same equivalence class, then you are doomed to failure.

Suppose that \(\mathcal{R}\) is a binary relation on a set \(A .\) Even though \(\mathcal{R}\) might not be transitive, it is always possible to construct a transitive relation from \(\mathcal{R}\) in a natural way. If we think of \(a \mathcal{R} b\) as meaning that \(a\) is related by \(\mathcal{R}\) to b “in one step,” then we consider the relationship that holds between two elements x and y when x is related by R to y “in one or more steps.” This relationship defines a binary relation on A that is called the transitive closure of \(\mathcal{R} .\) The transitive closure of \(\mathcal{R}\) is denoted \(\mathcal{R}^{*} .\) Formally, \(\mathcal{R}^{*}\) is defined as follows: For a and b in A, \(a \mathcal{R}^{*} b\) if there is a sequence \(x_{0}, x_{1}, \ldots x_{n}\) of elements of A,where \(n>0\) and \(x_{0}=a\) and \(x_{n}=b,\) such that \(x_{0} \mathcal{R} x_{1}\), \(x_{1} \mathcal{R} x_{2}, \ldots,\) and \(x_{n-1} \mathcal{R} x_{n}\).

For example, if \(a \mathcal{R} c, c \mathcal{R} d,\) and \(d \mathcal{R} b,\) then we would have that \(a \mathcal{R}^{*} b\). Of course, we would also have that \(a \mathcal{R}^{*} c,\) and \(a \mathcal{R}^{*} d\).

For a practical example, suppose that C is the set of all cities and letA be the binary relation on C such that for x and y in C, \(x \mathcal{A} y\) if there is a regularly scheduled airline flight from x to y. Then the transitive closure \(\mathcal{A}^{*}\) has a natural interpretation: \(x \mathcal{A}^{*} y\) if's possible to get from \(x\) to \(y\) by a sequence of one or more regularly scheduled airline flights. You’ll find a few more examples of transitive closures in the exercises.

Exercises

1. For a finite set, it is possible to define a binary relation on the set by listing the elements of the relation, considered as a set of ordered pairs. Let A be the set \(\{a, b, c, d\},\) where \(a, b, c,\) and \(d\) are distinct. Consider each of the following binary relations on A. Is the relation reflexive? Symmetric? Antisymmetric? Transitive? Is it a partial order? An equivalence relation?

a) \(\mathcal{R}=\{(a, b),(a, c),(a, d)\}\)
b) \(\mathcal{S}=\{(a, a),(b, b),(c, c),(d, d),(a, b),(b, a)\}\)
c) \(\mathcal{T}=\{(b, b),(c, c),(d, d)\}\)
d) \(C=\{(a, b),(b, c),(a, c),(d, d)\}\)
e) \(D=\{(a, b),(b, a),(c, d),(d, c)\}\)

2. Let \(A\) be the set \(\{1,2,3,4,5,6\}\) . Consider the partition of \(A\) into the subsets
\(\{1,4,5\},\{3\},\) and \(\{2,6\} .\) Write out the associated equivalence relation on \(A\)
as a set of ordered pairs.

3. Consider each of the following relations on the set of people. Is the relation reflexive? Symmetric? Transitive? Is it an equivalence relation?

a) \(x\) is related to \(y\) if \(x\) and \(y\) have the same biological parents.
b) \(x\) is related to \(y\) if \(x\) and \(y\) have at least one biological parent in common.
c) \(x\) is related to \(y\) if \(x\) and \(y\) were born in the same year.
d) \(x\) is related to \(y\) if \(x\) is taller than \(y\) .
e) \(x\) is related to \(y\) if \(x\) and \(y\) have both visited Honolulu.

4. It is possible for a relation to be both symmetric and antisymmetric. For example, the equality relation, =, is a relation on any set which is both symmetric and antisymmetric. Suppose that \(A\) is a set and \(\mathcal{R}\) is a relation on \(A\) that is both symmetric and antisymmetric. Show that \(\mathcal{R}\) is a subset of \(=\) (when both relations are considered as sets of ordered pairs). That is, show that for any \(a\) and \(b\) in \(A,(a \mathcal{R} b) \rightarrow(a=b)\)

5. Let \(\sim\) be the relation on \(\mathbb{R},\) the set of real numbers, such that for \(x\) and \(y\) in \(\mathbb{R}, x \sim y\) if and only if \(x-y \in \mathbb{Z}\) . For example, \(\sqrt{2}-1 \sim \sqrt{2}+17\) because the difference, \((\sqrt{2}-1)-(\sqrt{2}+17),\) is \(-18,\) which is an integer. Show that \(\sim\) is an equivalence relation. Show that each equivalence class \([x] \sim\) contains exactly one number \(a\) which satisfies \(0 \leq a<1 .\) (Thus, the set of equivalence classes under \(\sim\) is in one-to-one correspondence with the half-open interval \([0,1)\) .)

6. Let \(A\) and \(B\) be any sets, and suppose \(f : A \rightarrow B .\) Define a relation \(\sim\) on \(B\) such that for any \(x\) and \(y\) in \(A, x \sim y\) if and only if \(f(x)=f(y) .\) Show that \(\sim\) is an equivalence relation on \(A .\)

7. Let \(\mathbb{Z}^{+}\) be the set of positive integers \(\{1,2,3, \ldots\}\) . Define a binary relation \(\mathcal{D}\) on \(\mathbb{Z}^{+}\) such that for \(n\) and \(m\) in (\mathbb{Z}^{+}, n \mathcal{D} m\) if \(n\) divides evenly into \(m,\) with no remainder. Equivalently, \(n \mathcal{D} m\) if \(n\) is a factor of \(m,\) that is, if there is a \(k\) in \(\mathbb{Z}^{+}\) such that \(m=n k .\) Show that \(\mathcal{D}\) is a partial order.

8. Consider the set \(\mathbb{N} \times \mathbb{N},\) which consists of all ordered pairs of natural numbers since \(\mathbb{N} \times \mathbb{N}\) is a set, it is possible to have binary relations on \(\mathbb{N} \times \mathbb{N}\) . Such a relation would be a subset of \((\mathbb{N} \times \mathbb{N}) \times(\mathbb{N} \times \mathbb{N}) .\) Define a binary relation \(\preceq\) on \(\mathbb{N} \times \mathbb{N}\) such that for \((m, n)\) and \((k, \ell)\) in \(\mathbb{N} \times \mathbb{N},(m, n) \preceq(k, \ell)\) if and only if either \(m<k\) or \(((m=k) \wedge(n \leq \ell))\) . Which of the following are true?

\(\begin{array}{ll}{\text { a) }(2,7) \preceq(5,1)} & {\text { b) }(8,5) \preceq(8,0)} \\ {\text { c) }(0,1) \preceq(0,2)} & {\text { d) }(17,17) \preceq(17,17)}\end{array}\)

Show that \(\preceq\) is a total order on \(\mathbb{N} \times \mathbb{N}\) .

9. Let \(\sim\) be the relation defined on \(\mathbb{N} \times \mathbb{N}\) such that \((n, m) \sim(k, \ell)\) if and only if \(n+\ell=m+k .\) Show that \(\sim\) is an equivalence relation.

10. Let P be the set of people and let \(\Theta\) be the "child of" relation. That is \(x \mathrm{e} y\) means that x is a child of y. What is the meaning of the transitive closure \(\Theta^{*}\) Explain your answer.

11. Let \(\mathcal{R}\) be the binary relation on \(\mathbb{N}\) such that \(x \mathcal{R} y\) if and only if \(y=x+1\). Identify the transitive closure \(\mathcal{R}^{*} .\) (It is a well-known relation.) Explain your answer.

12. Suppose that \(\mathcal{R}\) is a reflexive, symmetric binary relation on a set \(A .\) Show that the transitive closure \(\mathcal{R}^{*}\) is an equivalence relation.