7.1: Relations

While there is no agreed upon universal definition of mathematics, one could argue that mathematics focuses on the study of patterns and relationships. Certain types of relationships occur over and over in mathematics. One way of formalizing the abstract nature and structure of these relationships is with the notion of relations. In Chapter 8, we will see that a function is a special type of relation.

Recall from Section 3.5 that the Cartesian product of two sets \(A\) and \(B\), written \(A\times B\), is the set of all ordered pairs \((a,b)\), where \(a\in A\) and \(b\in B\). That is, \(A\times B=\{(a,b)\mid a\in A, b\in B\}\).

Definition 7.1. Let \(A\) and \(B\) be sets. A relation \(R\) from \(A\) to \(B\) is a subset of \(A \times B\). If \(R\) is a relation from \(A\) to \(B\) and \((a,b)\in {R}\), then we say that \(a\) is related to \(b\) and we may write \(aR\) \(b\) in place of \((a,b)\in{R}\). If \(R\) is a relation from \(A\) to the same set \(A\), then we say that \(R\) is a relation on \(A\).

Example 7.2. The set \(\mathbb{N}\times \mathbb{R}\) from Problem 3.55 is an example of a relation on \(\mathbb{R}\) since \(\mathbb{N}\times \mathbb{R}\) is a subset of \(\mathbb{R}\times \mathbb{R}\).

It is important to notice that the order in which we write things for relations matters. In particular, if \(R\) is a relation from \(A\) to \(B\) and \(a R b\), then it may or may not be the case that \(bR a\).

Example 7.3. If \(A=\{a,b,c,d,e\}\) and \(B=\{1,2,3,4\}\), then the set of ordered pairs \[R=\{(a,1),(a,2),(a,4),(c,2),(d,2),(e,2),(e,4)\}\] is an example of a relation from \(A\) to \(B\). In this case, we could write \((c,2)\in{R}\) or \(cR 2\). We could also say that \(a\) is related to 1, 2, and 4.

Example 7.4. As in the previous example, let \(A=\{a,b,c,d,e\}\). One possible relation on \(A\) is given by \[R=\{(a,a),(a,b),(a,c),(b,b),(b,a),(b,c),(c,d),(c,e),(d,d),(d,a),(d,c),(e,a)\}.\]

Example 7.5. Consider the set of accounts \(A\) on the social media platform Twitter. On Twitter, each account has a set of accounts that they follow. We can model this situation mathematically using a relation on \(A\). Define \(T\) on \(A\) via \(xTy\) if \(x\) follows \(y\) on Twitter. As a set \[T=\{(x,y)\in A\times A\mid x\text{ follows }y\text{ on Twitter}\}.\]

Example 7.6. You are already familiar with many relations. For example, \(=\), \(\leq\), and \(<\) are each examples of relations on the real numbers. We could say that \((3,\pi)\) is in the relation \(\leq\) and the relation \(<\) since \(3\leq \pi\) and \(3<\pi\). However, \((3,\pi)\) is not in the relation \(=\) since \(3\neq \pi\). Also, notice that order matters for the relations \(\leq\) and \(<\) yet does not for \(=\). For example, \((-\sqrt{2}, 4)\) is in the relation \(\leq\) while \((4,-\sqrt{2})\) is not.

Example 7.7. Define the relation \(S\) from \(\{-1,1\}\) to \(\mathbb{Z}\) via \(1Sx\) if \(x\) is even and \(-1Sx\) if \(x\) is odd. That is, \(1\) is related to all even integers and \(-1\) is related to all odd integers.

Example 7.8. Let \(A\) be any set. Since \(\emptyset \subseteq A\times A\), the empty set forms a relation on \(A\). This relation is called the empty relation on \(A\).

Relations can be represented using digraphs. A digraph (short for directed graph) is a discrete graph that consists of a set of vertices connected by edges, where the edges have a direction associated with them. If \(R\) is a relation from \(A\) to \(B\), then the elements of \(A\) and \(B\) are the vertices of the digraph and there is a directed edge from \(a\in A\) to \(b\in B\) if \((a,b)\) is in the relation \(R\) (i.e., \(aR b\)). We can visually represent digraphs by using dots to represent the vertices and arrows to represent directed edges. We will not make a distinction between a digraph and its visual representation. Utilizing a digraph to represent a relation may be impractical if there is a large number of vertices or directed edges.

Example 7.9. Consider the relation given in Example 7.3. The corresponding digraph is depicted in Figure 7.1. Notice that we have placed the vertices corresponding to elements of \(A\) on the left and the elements of \(B\) on the right. This is standard practice, but what really matters is the edge connections not how the vertices are placed on the page.

= [circle, draw, fill=grey,inner sep=0pt, minimum size=5mm] = [draw,-stealth]

Problem 7.10. Let \(A=\{1,2,3,4,5,6\}\) and \(B=\{1,2,3,4\}\) and define \(D\) from \(A\) to \(B\) via \((a,b)\in D\) if \(a-b\) is divisible by 2. List the ordered pairs in \(D\) and draw the corresponding digraph.

If \(R\) is a relation on \(A\) (i.e., a relation from \(A\) to \(A\)), then we can simplify the structure of the digraph by only utilizing one copy of \(A\) for the vertices. In this case, we may have directed edges that point from a vertex to itself. When drawing digraphs for a relation on a set, we will default to this simplified digraph (like the one depicted in Figure 7.2(b)).

Example 7.11. Figure 7.2(a) represents the relation of Example 7.4 as a digraph from \(A\) to \(A\) while the digraph in Figure 7.2(b) provides a streamlined representation of the same relation that uses the elements in \(A\) only once instead of twice.

Problem 7.12. Let \(A=\{1,2,3,4,5,6\}\) and define \(|\) on \(A\) via \(x|y\) if \(x\) divides \(y\). List the ordered pairs in \(|\) and draw the corresponding digraph.

Figure 7.1: Digraph for a relation from A = {a,b, c, d, e} to B = {1,2,3,4}.

Figure 7.2: Two variations of digraphs for a relation on A = {a,b, c, d, e}.

Problem 7.13. Let \(A=\{a,b,c,d\}\) and define \(R\) on \(A\) via \[{R}=\{(a,a),(a,b),(a,c),(b,b),(b,a),(b,c),(c,c),(c,a),(c,b),(d,d)\}.\]

1. Draw the digraph for \(R\).
2. Draw the digraph for the empty relation on \(A\).

We can also visually represent a relation by plotting the points in the relation. In particular, if \(R\) is a relation from \(A\) to \(B\) and \(aR b\), we can plot all points \((a,b)\) that satisfy \(aR b\) in two dimensions, where we interpret the set \(A\) to be the horizontal axis and \(B\) to be the vertical axis. We will refer to this visual representation of a relation as the graph of the relation.

Example 7.14. When we write \(x^2+y^2=1\), we are implicitly defining a relation. In particular, the relation is the set of ordered pairs \((x,y)\) satisfying \(x^2+y^2=1\), namely \(\{(x,y)\in \mathbb{R}^2 \mid x^2+y^2=1\}\). The graph of this relation in \(\mathbb{R}^2\) is the unit circle centered at the origin in the plane as shown in Figure 7.3.

Figure 7.3: Graph of the relation determined by x² + y² = 1.

Problem 7.15. For each of the following, draw a portion of the graph that represents the relation as a subset of \(\mathbb{R}^2\).

1. \(\{(x,y)\in \mathbb{R}^2 \mid y=x^2\}\)
2. \(\{(x,y)\in \mathbb{Z}^2 \mid y=x^2\}\)
3. \(\{(x,y)\in \mathbb{R}^2 \mid y^2=x\}\)
4. \(\{(x,y)\in \mathbb{N}\times \mathbb{R} \mid y^2=x\}\)

Problem 7.16. Draw a portion of the graph that represents the relation \(\leq\) on \(\mathbb{R}\).

For a relation on a set, it is natural to consider the collection of elements that a given element is related to. For example, a user’s “Following List" on Twitter is the set of accounts on Twitter that the user is following.

Definition 7.17. Let \(R\) be a relation on a set \(A\). For each \(a\in A\), we define the set of relatives of \(a\) with respect to \(R\) via \[rel(a,R):= \{b\in A\mid aR b\}.\] We also define the collection of the sets of relatives with respect to \(R\) by \[Rel(R):= \{rel(a)\mid a\in A\}.\]

If \(R\) is clear from the context, we will usually write \(rel(a)\) in place of \(rel(a,R)\). In terms of digraphs, \(rel(a)\) is the collection of vertices that have a directed edge pointing towards them from the vertex labeled by \(a\). In graph theory, this collection of vertices is called the out neighborhood of \(a\) and each such vertex is called an out neighbor. Notice that \(Rel(R)\) is a set of sets. In particular, an element in \(Rel(R)\) is a subset of \(A\)—equivalently, an element of \(\mathcal{P}(A)\).

Problem 7.18. Consider the relation given in Example 7.4. By inspecting the ordered pairs in \(R\) or by looking at the digraph in Figure 7.2(b), we see that \[rel(a) = \{a,b,c\},\ rel(b) = \{a,b,c\},\ rel(c) = \{d,e\},\ rel(d) = \{a,c,d\},\ rel(e) = \{a\},\] so that \(Rel(R) = \{\{a,b,c\},\{d,e\},\{a,c,d\},\{a\}\}\).

Problem 7.19. Consider the relation given in Problem 7.13(a). Find \(Rel(R)\) by determining \(rel(x)\) for each \(x\in A\).

Problem 7.20. Describe the collection of the sets of relatives with respect to the empty relation from Problem 7.13(b).

Problem 7.21. Let \(P\) denote the set of all people with accounts on Facebook and define the relation \(F\) on \(P\) via \(xFy\) if \(x\) is friends with \(y\). Describe \(rel(\text{Maria})\), where Maria is the name of a specific Facebook user. What is \(Rel(F)\)?

Problem 7.22. Define the relation \(\equiv_5\) on \(\mathbb{Z}\) via \(a\equiv_5 b\) if \(a-b\) is divisible by 5. Find \(rel(1)\), \(rel(2)\), and \(rel(6)\). How many distinct sets are in \(Rel(\equiv_5)\)? List the distinct sets in \(Rel(\equiv_5)\).

Problem 7.23. Consider the relation \(\leq\) on \(\mathbb{R}\). If \(x\in \mathbb{R}\), what is \(rel(x)\)?

Problem 7.24. Suppose \(R\) is a relation on \(A=\{1,2,3,4,5\}\) such that \(rel(1)=\{1,3,4\}\), \(rel(2)=\{4\}\), \(rel(3)=\{3,4,5\}\), \(rel(4)=\{1,2\}\), and \(rel(5)=\emptyset\). List the ordered pairs in \(R\) and draw the corresponding digraph.

We will now examine three important properties that a relation on a set may or may not possess.

Definition 7.25. Let \(R\) be a relation on a set \(A\).

1. The relation \(R\) is reflexive if for all \(a\in A\), \(aR a\).
2. The relation \(R\) is symmetric if for all \(a,b\in A\), if \(aR b\), then \(bR a\).
3. The relation \(R\) is transitive if for all \(a,b,c\in A\), if \(aR b\) and \(bR c\), then \(aR c\).

Example 7.26. Here are a few examples that illustrate the concepts in the previous definition.

1. The relation \(=\) on \(\mathbb{R}\) is reflexive, symmetric, and transitive.
2. The relation \(\leq\) is reflexive and transitive on \(\mathbb{R}\), but not symmetric. However, notice that \(<\) is transitive on \(\mathbb{R}\), but neither symmetric nor reflexive.
3. If \(S\) is a set, then \(\subseteq\) on \(\mathcal{P}(S)\) is reflexive and transitive, but not symmetric.

Problem 7.27. Determine whether the relations given in each of the following is reflexive, symmetric, or transitive.

1. Example 7.4
2. Problem 7.13

Problem 7.28. Suppose \(R\) is a relation on a set \(A\).

1. Explain what it means for \(R\) to not be reflexive.
2. Explain what it means for \(R\) to not be symmetric.
3. Explain what it means for \(R\) to not be transitive.

Problem 7.29. Let \(A=\{a,b,c,d,e\}\).

1. Define a relation \(R\) on \(A\) that is reflexive but not symmetric nor transitive.
2. Define a relation \(S\) on \(A\) that is symmetric but not reflexive nor transitive.
3. Define a relation \(T\) on \(A\) that is transitive but not reflexive nor symmetric.

Problem 7.39. Given a relation \(R\) on a finite set \(A\), describe what each of reflexive, symmetric, and transitive look like in terms of a digraph. That is, draw pictures that represent each of reflexive, symmetric, and transitive. One thing to keep in mind is that the elements used in the definitions of symmetric and transitive do not have to be distinct. So, you might need to consider multiple cases.

Below, we provide skeleton proofs for proving that a relation is reflexive, symmetric, or transitive. Notice that the skeleton proof for proving that a relation is reflexive is a special case of Skeleton Proof 2.81. Similarly, the skeleton proofs involving symmetric and transitive are both special cases of Skeleton Proof 2.82. It is important to point out that every relation on the empty set is vacuously reflexive, symmetric, and transitive. In the skeleton proofs below, we are implicitly assuming that the set in question is nonempty. In some circumstances, it may be necessary to mention the possibility of the empty set.

Skeleton Proof 7.31. Here is the general structure for proving that a relation is reflexive.

Assume \(R\) is a relation on \(A\) defined by (or satisfying)…[Use the given definition (or describe the given property) of \(R\)]. Let \(a\in A\).

\(\ldots\) [Use the definition (or property) of \(R\) to verify that \(aR a\)] \(\ldots\)

Therefore, the relation \(R\) is reflexive on \(A\).

Skeleton Proof 7.32. Here is the general structure for proving that a relation is symmetric.

Assume \(R\) is a relation on \(A\) defined by (or satisfying)…[Use the given definition (or describe the given property) of \(R\)]. Let \(a, b\in A\) and suppose \(aR b\).

\(\ldots\) [Use assumption that \(aR b\) with definition (or property) of \(R\) to verify that \(bR a\)] \(\ldots\)

Therefore, the relation \(R\) is symmetric on \(A\).

Skeleton Proof 7.33. Here is the general structure for proving that a relation is transitive.

Assume \(R\) is a relation on \(A\) defined by (or satisfying)…[Use the given definition (or describe the given property) of \(R\)]. Let \(a, b, c\in A\) and suppose \(aR b\) and \(bR c\).

\(\ldots\) [Use assumption that \(aR b\) and \(bR c\) with definition (or property) of \(R\) to verify that \(aR c\)] \(\ldots\)

Therefore, the relation \(R\) is transitive on \(A\).

Problem 7.34. Determine whether each of the following relations is reflexive, symmetric, or transitive. In each case, you should either provide a specific counterexample or a proof.

1. Consider the relation \(T\) described in Example 7.5.
2. Consider the relation \(F\) described in Problem 7.21.
3. Consider the relation \(\equiv_5\) described in Problem 7.22.
4. Let \(P\) be the set of all people and define \(H\) via \(xHy\) if \(x\) and \(y\) have the same height.
5. Let \(P\) be the set of all people and define \(T\) via \(xTy\) if \(x\) is taller than \(y\).
6. Consider the relation “divides" on \(\mathbb{N}\).
7. Let \(L\) be the set of lines and define \(||\) via \(l_1||l_2\) if \(l_1\) is parallel to \(l_2\).
8. Let \(C[0,1]\) be the set of continuous functions on \([0,1]\). Define \(f\sim g\) if \[\int_0^1|f(x)|\ dx=\int_0^1|g(x)|\ dx.\]
9. Define \(R\) on \(\mathbb{N}\) via \(nR m\) if \(n+m\) is even.
10. Define \(D\) on \(\mathbb{R}\) via \((x,y)\in D\) if \(x=2y\).
11. Define \(F\) on \(\mathbb{Z}\times \left(\mathbb{Z}\setminus \{0\}\right)\) via \((a,b)F(c,d)\) if \(ad=bc\). Do you recognize this relation? Think about fractions.
12. Define \(\sim\) on \(\mathbb{R}^2\) via \((x_1,y_1)\sim (x_2,y_2)\) if \(x_1^2+y_1^2=x_2^2+y_2^2\).
13. Define \(S\) on \(\mathbb{R}\) via \(xS y\) if \(\lfloor x\rfloor =\lfloor y\rfloor\), where \(\lfloor x\rfloor\) is the greatest integer less than or equal to \(x\) (e.g., \(\lfloor \pi\rfloor=3\), \(\lfloor -1.5\rfloor=-2\), and \(\lfloor 4\rfloor=4\)).
14. Define \(C\) on \(\mathbb{R}\) via \(xCy\) if \(|x-y|<1\).