Section 7.1 Relations
Beginning Activity Beginning Activity 1: The United States of America
Recall from Section 5.4 that the Cartesian product of two sets \(A\) and \(B\text{,}\) written \(A \times B\text{,}\) is the set of all ordered pairs \(\left( {a,b} \right)\text{,}\) where \(a \in A\) and \(b \in B\text{.}\) That is, \(A \times B = \left\{ {\left( {a,b} \right) \mid a \in A\text{ and } b \in B} \right\}\text{.}\)
Let \(A\) be the set of all states in the United States and let
For example, since California and Oregon have a land border, we can say that (California, Oregon) \(\in R\) and (Oregon, California) \(\in R\text{.}\) Also, since California and Michigan do not share a land border, (California, Michigan) \(\notin R\) and Michigan, California) \(\notin R\text{.}\)
1.
Use the roster method to specify the elements in each of the following sets:
(a)
\(B = \left\{ {y \in A\left| {\left( {\text{ Michigan, } y} \right) \in R} \right.} \right\}\)
(b)
\(C = \left\{ {x \in A\left| {\left( {x,\text{ Michigan } } \right) \in R} \right.} \right\}\)
(c)
\(D = \left\{ {y \in A\left| {\left( {\text{ Wisconsin, } y} \right) \in R} \right.} \right\}\)
2.
Find two different examples of two ordered pairs, \(\left( {x, y} \right)\) and \(\left( {y, z} \right)\) such that \(\left( {x, y} \right) \in R\text{,}\) \(\left( {y, z} \right) \in R\text{,}\) but \(\left( {x, z} \right)\not \in R\text{,}\) or explain why no such example exists. Based on this, is the following conditional statement true or false?
For all \(x, y, z \in A\text{,}\) if \((x, y) \in R\) and \((y, z) \in R\text{,}\) then \((x, z) \in R\text{.}\)
3.
Is the following conditional statement true or false? Explain. For all \(x, y \in A\text{,}\) if \((x, y) \in R\text{,}\) then \((y, x) \in R\text{.}\)
Beginning Activity Beginning Activity 2: The Solution Set of an Equation with Two Variables
In Section 2.3, we introduced the concept of the truth set of an open sentence with one variable. This was defined to be the set of all elements in the universal set that can be substituted for the variable to make the open sentence a true proposition. Assume that \(x\) and \(y\) represent real numbers. Then the equation
is an open sentence with two variables. An element of the truth set of this open sentence (also called a solution of the equation) is an ordered pair \(\left( {a, b} \right)\) of real numbers so that when \(a\) is substituted for \(x\) and \(b\) is substituted for \(y\text{,}\) the predicate becomes a true statement (a true equation in this case). We can use set builder notation to describe the truth set \(S\) of this equation with two variables as follows:
When a set is a truth set of an open sentence that is an equation, we also call the set the solution set of the equation.
1.
List four different elements of the set \(S\text{.}\)
2.
The graph of the equation \(4x^2 + y^2 = 16\) in the \(xy\)-coordinate plane is an ellipse. Draw the graph and explain why this graph is a representation of the truth set (solution set) of the equation \(4x^2 + y^2 = 16\text{.}\)
3.
Describe each of the following sets as an interval of real numbers:
(a)
\(A = \left\{ x \in \R \mid \text{ there exists a } y \in \R \text{ such that } 4x^2 + y^2 = 16 \right\}\text{.}\)
(b)
\(B = \left\{ y \in \R \mid \text{ there exists an } x \in \R \text{ such that } 4x^2 + y^2 = 16 \right\}\text{.}\)
Subsection Introduction to Relations
In Section 6.1, we introduced the formal definition of a function from one set to another set. The notion of a function can be thought of as one way of relating the elements of one set with those of another set (or the same set). A function is a special type of relation in the sense that each element of the first set, the domain, is “related” to exactly one element of the second set, the codomain.
This idea of relating the elements of one set to those of another set using ordered pairs is not restricted to functions. For example, we may say that one integer, \(a\text{,}\) is related to another integer, \(b\text{,}\) provided that \(a\) is congruent to \(b\) modulo 3. Notice that this relation of congruence modulo 3 provides a way of relating one integer to another integer. However, in this case, an integer \(a\) is related to more than one other integer. For example, since
we can say that 5 is related to 5, 5 is related to 2, and 5 is related to \(-1\text{.}\) Notice that, as with functions, each relation of the form \(a \equiv b \pmod 3\) involves two integers \(a\) and \(b\) and hence involves an ordered pair \(\left( {a, b} \right)\text{,}\) which is an element of \(\Z \times \Z\text{.}\)
Definition.
Let \(A\) and \(B\) be sets. A relation R from the set \(\boldsymbol{A}\) to the set \(\boldsymbol{B}\) is a subset of \(A \times B\text{.}\) That is, \(R\) is a collection of ordered pairs where the first coordinate of each ordered pair is an element of \(A\text{,}\) and the second coordinate of each ordered pair is an element of \(B\text{.}\)
A relation from the set \(A\) to the set \(A\) is called a relation on the set \(\boldsymbol{A}\). So a relation on the set \(A\) is a subset of \(A \times A\text{.}\)
In Section 6.1, we defined the domain and range of a function. We make similar definitions for a relation.
Definition.
If \(R\) is a relation from the set \(A\) to the set \(B\text{,}\) then the subset of \(A\) consisting of all the first coordinates of the ordered pairs in \(R\) is called the domain of \(R\text{.}\) The subset of \(B\) consisting of all the second coordinates of the ordered pairs in \(R\) is called the range of \(R\text{.}\)
We use the notation \(\text{ dom} ( R )\) for the domain of \(R\) and \(\text{ range} ( R )\) for the range of \(R\text{.}\) So using set builder notation,
Example 7.1. Domain and Range.
A relation was studied in each of the beginning activities for this section. For Beginning Activity 2, the set \(S = \left\{ (x, y) \in \R \times \R \mid 4x^2 + y^2 = 16 \right\}\!\) is a subset of \(\R \times \R\) and, hence, \(S\) is a relation on \(\R\text{.}\) In Exercise 3 of Beginning Activity 2, we actually determined the domain and range of this relation.
So from the results in Beginning Activity 2, we can say that the domain of the relation \(S\) is the closed interval \(\left[ -2, 2 \right]\) and the range of \(S\) is the closed interval \(\left[ -4, 4 \right]\text{.}\)
Progress Check 7.2.
(a)
Let \(T = \left\{ {\left( {x, y} \right) \in \mathbb{R} \times \mathbb{R} \mid x^2 + y^2 = 64} \right\}\text{.}\)
(i)
Explain why \(T\) is a relation on \(\mathbb{R}\text{.}\)
\(T\) is a relation on \(\mathbb{R}\) since \(S\) is a subset of \(\mathbb{R} \times \mathbb{R}\text{.}\)
(ii)
Find all values of \(x\) such that \(\left( {x, 4} \right) \in T\text{.}\) Find all values of \(x\) such that \(\left( {x, 9} \right) \in T\text{.}\)
Solve the equation \(x^2 + 4^2 = 64\text{.}\) This gives \(x = \pm \sqrt {48}\text{.}\) Solve the equation \(x^2 + 9^2 = 64\text{.}\) There are no real number solutions. So there does not exist an \(x \in \mathbb{R}\) such that \(\left( {x, 9} \right) \in S\text{.}\)
(iii)
What is the domain of the relation \(T\text{?}\) What is the range of \(T\text{?}\)
\(\text{ dom} ( T ) = \left\{ {\left. {x \in \mathbb{R} } \right| - 8 \leq x \leq 8} \right\}\) \(\text{ range} ( T ) = \left\{ {\left. {y \in \mathbb{R} } \right| - 8 \leq y \leq 8} \right\}\)
(iv)
Since \(T\) is a relation on \(\mathbb{R}\text{,}\) its elements can be graphed in the coordinate plane. Describe the graph of the relation \(T\text{.}\)
The graph is a circle of radius 8 whose center is at the origin.
(b)
From Beginning Activity 1, \(A\) is the set of all states in the United States, and
(i)
Explain why \(R\) is a relation on \(A\text{.}\)
\(R\) is a relation on \(A\) since \(R\) is a subset of \(A \times A\text{.}\)
(ii)
What is the domain of the relation \(R\text{?}\) What is the range of the relation \(R\text{?}\)
If we assume that each state except Hawaii has a land border in common with itself, then the domain and range of \(R\) are the set of all states except Hawaii. If we do not make this assumption, then the domain and range are the set of all states except Hawaii and Alaska.
(iii)
Are the following statements true or false? Justify your conclusions.
(A)
For all \(x, y \in A\text{,}\) if \((x, y) \in R\text{,}\) then \((y, x) \in R\text{.}\)
The first statement is true. If \(x\) has a land border with \(y\text{,}\) then \(y\) has a land border with \(x\text{.}\)
(B)
For all \(x, y, z \in A\text{,}\) if \((x, y) \in R\) and \((y, z) \in R\text{,}\) then \((x, z) \in R\text{.}\)
The second statement is false. Following is a counterexample: \(\left( {\text{ Michigan, } \text{ Indiana } } \right) \in R\text{,}\) \(\left( {\text{ Indiana,Illinois } } \right) \in R\text{,}\) but \(\left( {\text{ Michigan, } \text{ Illinois } } \right) \notin R\text{.}\)
Subsection Some Standard Mathematical Relations
There are many different relations in mathematics. For example, two real numbers can be considered to be related if one number is less than the other number. We call this the “less than” relation on \(\mathbb{R}\text{.}\) If \(x, y \in \mathbb{R}\) and \(x\) is less than \(y\text{,}\) we often write \(x \lt y\text{.}\) As a set of ordered pairs, this relation is \(R_{ \lt }\text{,}\) where
With many mathematical relations, we do not write the relation as a set of ordered pairs even though, technically, it is a set of ordered pairs. Table 7.3 describes some standard mathematical relations.
| Name | Open Sentence |
Relation as a Set of Ordered Pairs |
|---|---|---|
| The “less than” relation on \(\mathbb{R}\) |
\(x \lt y\) | \(\left\{ { {\left( {x, y} \right) \in \mathbb{R} \times \mathbb{R} } \mid x \lt y} \right\}\) |
| The “equality” relation on \(\mathbb{R}\) |
\(x=y\) | \(\left\{ { {\left( {x, y} \right) \in \mathbb{R} \times \mathbb{R} } \mid x = y} \right\}\) |
| The “divides” relation on \(\mathbb{Z}\) |
\(m \mid n\) | \(\left\{ { {\left( {m, n} \right) \in \mathbb{Z} \times \mathbb{Z} } \mid m \text{ divides } n} \right\}\) |
| The “subset” relation on \(\mathcal{P}\left( U \right)\) |
\(S \subseteq T\) | \(\left\{ { {\left( {S, T} \right) \in \mathcal{P}\left( U \right) \times \mathcal{P}\left( U \right) } \mid S \subseteq T} \right\}\) |
| The “element of” relation from \(U\) to \(\mathcal{P}\left( U \right)\) |
\(x \in S\) | \(\left\{ { {\left( {x, S} \right) \in U \times \mathcal{P}\left( U \right) } \mid x \in S} \right\}\) |
| The “congruence modulo \(n\)” relation on \(\mathbb{Z}\) |
\(a \equiv b \pmod n\) | \(\left\{ {\left( {a, b} \right) \in \mathbb{Z} \times \mathbb{Z} \mid a \equiv b \pmod n} \right\}\) |
Subsection Functions as Relations
If we have a function \(f\x A \to B\text{,}\) we can generate a set of ordered pairs \(f\) that is a subset of \(A \times B\) as follows:
This means that \(f\) is a relation from \(A\) to \(B\text{.}\) Since, \(\text{ dom} ( f ) = A\text{,}\) we know that
When \(\left( a, b \right) \in f\text{,}\) we write \(b = f( a )\text{.}\) In addition, to be a function, each input can produce only one output. In terms of ordered pairs, this means that there will never be two ordered pairs \(( {a, b} )\) and \(( {a, c} )\) in the function \(f\text{,}\) where \(a \in A\text{,}\) \(b, c \in B\text{,}\) and \(b \ne c\text{.}\) We can formulate this as a conditional statement as follows:
This means that a function \(f\) from \(A\) to \(B\) is a relation from \(A\) to \(B\) that satisfies conditions (1) and (2). (See Theorem 6.31 in Section 6.5.) Not every relation, however, will be a function. For example, consider the relation \(T\) in Progress Check 7.2.
This relation fails condition (2) above since a counterexample comes from the facts that \((0, 8) \in T\) and \((0, -8) \in T\) and \(8 \ne -8\text{.}\)
Progress Check 7.5. A Set of Ordered Pairs.
Let \(F = \left\{ (x, y) \in \R \times \R \mid y = x^2 \right\}\text{.}\) The set \(F\) can then be considered to be relation on \(\R\) since it is a subset of \(\R \times \R\text{.}\)
(a)
List five different ordered pairs that are in the set \(F\text{.}\)
Each element in the set \(F\) is an ordered pair of the form \((x, y)\) where \(y = x^2\text{.}\)
(b)
Use the roster method to specify the elements of each of the following the sets:
(i)
\(A = \left\{ x \in \R \mid (x, 4) \in F \right\}\)
\(A = \{ -2, 2 \}\)
(ii)
\(B = \left\{ x \in \R \mid (x, 10) \in F \right\}\)
\(B = \{ -\sqrt{10}, \sqrt{10} \}\)
(iii)
\(C = \left\{ y \in \R \mid (5, y) \in F \right\}\)
\(C = \{25 \}\)
(iv)
\(D = \left\{ y \in \R \mid (-3, y) \in F \right\}\)
\(D = \{ 9 \}\)
(c)
Since each real number \(x\) produces only one value of \(y\) for which \(y = x^2\text{,}\) the set \(F\) can be used to define a function from the set \(\R\) to \(\R\text{.}\) Draw a graph of this function.
The graph of \(y = x^2\) is a parabola with vertex at the origin that is concave up.
Subsection Visual Representations of Relations
In Progress Check 7.5, we were able to draw a graph of a relation as a way to visualize the relation. In this case, the relation was a function from \(\R\) to \(\R\text{.}\) In addition, in Progress Check 7.2, we were also able to use a graph to represent a relation. In this case, the graph of the relation \(T = \left\{ {\left( {x, y} \right) \in \mathbb{R} \times \mathbb{R} \mid x^2 + y^2 = 64} \right\}\) is a circle of radius 8 whose center is at the origin.
When \(R\) is a relation from a subset of the real numbers \(\R\) to a subset of \(\R\text{,}\) we can often use a graph to provide a visual representation of the relation. This is especially true if the relation is defined by an equation or even an inequality. For example, if
then we can use the following graph as a way to visualize the points in the plane that are also in this relation.
The points \((x, y)\) in the relation \(R\) are the points on the graph of \(y = x^2\) or are in the shaded region. This because for these points, \(y \geq x^2\text{.}\) One of the shortcomings of this type of graph is that the graph of the equation and the shaded region are actually unbounded and so we can never show the entire graph of this relation. However, it does allow us to see that the points in this relation are either on the parabola defined by the equation \(y = x^2\) or are “inside” the parabola.
When the domain or range of a relation is infinite, we cannot provide a visualization of the entire relation. However, if \(A\) is a (small) finite set, a relation \(R\) on \(A\) can be specified by simply listing all the ordered pairs in \(R\text{.}\) For example, if \(A = \left\{ {1, 2, 3, 4} \right\}\text{,}\) then
is a relation on \(A\text{.}\) A convenient way to represent such a relation is to draw a point in the plane for each of the elements of \(A\) and then for each \(\left( {x, y} \right) \in R\) (or \(x \mathrel{R} y\)), we draw an arrow starting at the point \(x\) and pointing to the point \(y\text{.}\) If \(\left( {x, x} \right) \in R\) (or \(x \mathrel{R} x\)), we draw a loop at the point \(x\text{.}\) The resulting diagram is called a directed graph or a digraph. The diagram in Figure 7.7 is a digraph for the relation \(R\text{.}\)
In a directed graph, the points are called the vertices. So each element of \(A\) corresponds to a vertex. The arrows, including the loops, are called the directed edges of the directed graph. We will make use of these directed graphs in the next section when we study equivalence relations.
Progress Check 7.8. The Directed Graph of a Relation.
Let \(A = \{ 1, 2, 3, 4, 5, 6 \}\text{.}\) Draw a directed graph for the following two relations on the set \(A\text{.}\) For each relation, it may be helpful to arrange the vertices of \(A\) as shown in Figure 7.9.
The directed graph for \(R\) is on the left and the directed graph for \(T\) is on the right.
Exercises Exercises
1.
Let \(A = \left\{ {a, b, c} \right\}\text{,}\) \(B = \left\{ {p, q, r} \right\}\text{,}\) and let \(R\) be the set of ordered pairs defined by \(R = \left\{ {\left( {a, p} \right), \left( {b, q} \right), \left( {c, p} \right), \left( {a, q} \right)} \right\}\text{.}\)
(a)
Use the roster method to list all the elements of \(A \times B\text{.}\) Explain why \(A \times B\) can be considered to be a relation from \(A\) to \(B\text{.}\)
The set \(A \times B\) contains nine ordered pairs. The set \(A \times B\) is a relation from \(A\) to \(B\) since \(A \times B\) is a subset of \(A \times B\text{.}\)
(b)
Explain why \(R\) is a relation from \(A\) to \(B\text{.}\)
The set \(R\) is a relation from \(A\) to \(B\) since \(R \subseteq A \times B\text{.}\)
(c)
What is the domain of \(R\text{?}\) What is the range of \(R\text{?}\)
\(\text{ dom} ( R ) = A\text{,}\) \(\text{ range} ( R ) = \left\{ {p, q} \right\}\)
2.
Let \(A = \left\{ {a, b, c} \right\}\) and let \(R = \left\{ {\left( {a, a} \right), \left( {a, c} \right), \left( {b, b} \right), \left( {b, c} \right), \left( {c, a} \right), \left( {c, b} \right)} \right\}\) (so \(R\) is a relation on \(A\)). Are the following statements true or false? Explain.
(a)
For each \(x \in A\text{,}\) \(x \mathrel{R} x\text{.}\)
The statement is false since \(\left( c, c \right) \notin R\text{,}\) which can be written as \(c \not \mathrel{R} d\text{.}\)
(b)
For every \(x, y \in A\text{,}\) if \(x \mathrel{R} y\text{,}\) then \(y \mathrel{R} x\text{.}\)
The statement is true since whenever \(\left( x, y \right) \in R\text{,}\) \(\left( y, x \right)\) is also in \(R\text{.}\) That is, whenever \(x \mathrel{R} y\text{,}\) \(y\mathrel{R} x\text{.}\)
(c)
For every \(x, y, z \in A\text{,}\) if \(x \mathrel{R} y\) and \(y \mathrel{R} z\text{,}\) then \(x \mathrel{R} z\text{.}\)
The statement is false since \(\left( a, c \right) \in R\text{,}\) \(\left( c, b \right) \in R\text{,}\) but \(\left( a, b \right) \notin R\text{.}\) That is, \(a\mathrel{R} c\text{,}\) \(c \mathrel{R} b\text{,}\) but \(a \not \mathrel{R} b\text{.}\)
(d)
\(R\) is a function from \(A\) to \(A\text{.}\)
The statement is false since \(\left( a, a \right) \in R\) and \(\left( a, c \right) \in R\text{.}\)
3.
Let \(A\) be the set of all female citizens of the United States. Let \(D\) be the relation on \(A\) defined by
That is, \(x \mathrel{D} y\) means that \(x\) is a daughter of \(y\text{.}\)
(a)
Describe those elements of \(A\) that are in the domain of \(D\text{.}\)
The domain of \(D\) consists of the female citizens of the United States whose mother is a female citizen of the United States.
(b)
Describe those elements of \(A\) that are in the range of \(D\text{.}\)
The range of \(D\) consists of those female citizens of the United States who have a daughter that is a female citizen of the United States.
(c)
Is the relation \(D\) a function from \(A\) to \(A\text{?}\) Explain.
4.
Let \(U\) be a nonempty set, and let \(R\) be the “subset relation” on \(\mathcal{P}( U )\text{.}\) That is,
(a)
Write the open sentence \(\left( {S, T} \right) \in R\) using standard subset notation.
\(( {S, T} ) \in R\) means that \(S \subseteq T\text{.}\)
(b)
What is the domain of this subset relation, \(R\text{?}\)
The domain of the subset relation is \(\mathcal{P} ( U )\text{.}\)
(c)
What is the range of this subset relation, \(R\text{?}\)
The range of the subset relation is \(\mathcal{P} ( U )\text{.}\)
(d)
Is \(R\) a function from \(\mathcal{P}( U )\) to \(\mathcal{P}( U )\text{?}\) Explain.
The relation \(R\) is not a function from \(\mathcal{P} ( U )\) to \(\mathcal{P} ( U )\) since any proper subset of \(U\) is a subset of more than one subset of \(U\text{.}\)
5.
Let \(U\) be a nonempty set, and let \(R\) be the “element of” relation from \(U\) to \(\mathcal{P}\left( U \right)\text{.}\) That is,
(a)
What is the domain of this “element of” relation, \(R\text{?}\)
(b)
What is the range of this “element of” relation, \(R\text{?}\)
(c)
Is \(R\) a function from \(U\) to \(\mathcal{P}( U )\text{?}\) Explain.
6.
Let \(S = \left\{ {\left( {x, y} \right) \in \mathbb{R} \times \mathbb{R} \mid x^2 + y^2 = 100} \right\}\text{.}\)
(a)
Determine the set of all values of \(x\) such that \(\left( {x, 6} \right) \in S\text{,}\) and determine the set of all values of \(x\) such that \(\left( {x, 9} \right) \in S\text{.}\)
\(\left\{ {\left. {x \in \mathbb{R}\,} \right| \left( {x, 6} \right) \in S} \right\} = \left\{ { - 8, 8} \right\}\text{.}\) \(\left\{ {\left. {x \in \mathbb{R}\,} \right| \left( {x, 9} \right) \in S} \right\} = \left\{ { - \sqrt {19} , \sqrt {19} } \right\}\text{.}\)
(b)
Determine the domain and range of the relation \(S\) and write each set using set builder notation.
The domain of the relation \(S\) is the closed interval \(\left[ -10, 10 \right]\text{.}\) The range of the relation \(S\) is the closed interval \(\left[ -10, 10 \right]\text{.}\)
(c)
Is the relation \(S\) a function from \(\mathbb{R}\) to \(\mathbb{R}\text{?}\) Explain.
The relation \(S\) is not a function from \(\mathbb{R}\) to \(\mathbb{R}\text{.}\)
(d)
Since \(S\) is a relation on \(\mathbb{R}\text{,}\) its elements can be graphed in the coordinate plane. Describe the graph of the relation \(S\text{.}\) Is the graph consistent with your answers in Task 6.a through Task 6.c? Explain.
The graph of the relation \(S\) is the circle of radius 10 whose center is at the origin.
7.
Repeat Exercise 6 using the relation on \(\R\) defined by
What is the connection between this relation and the relation in Exercise 6?
8.
Determine the domain and range of each of the following relations on \(\R\) and sketch the graph of each relation.
(a)
\(R = \left\{ {\left( {x, y} \right) \in \mathbb{R} \times \mathbb{R} \mid x^2 + y^2 = 10} \right\}\)
(b)
\(S = \left\{ {\left( {x, y} \right) \in \mathbb{R} \times \mathbb{R} \mid y^2 = x+10} \right\}\)
(c)
\(T = \left\{ {\left( {x, y} \right) \in \mathbb{R} \times \mathbb{R} \mid |x| + |y| = 10} \right\}\)
(d)
\(R = \left\{ {\left( {x, y} \right) \in \mathbb{R} \times \mathbb{R} \mid x^2 =y^2} \right\}\)
9.
Let \(\mathrel{R}\) be the relation on \(\Z\) where for all \(a, b \in \Z\text{,}\) \(a \mathrel{R} b\) if and only if \(\left| a - b \right| \leq 2\text{.}\)
(a)
Use set builder notation to describe the relation \(\mathrel{R}\) as a set of ordered pairs.
\(R = \left\{ (a, b) \in \Z \times \Z \left| \left| a - b \right| \leq 2 \right. \right\}\)
(b)
Determine the domain and range of the relation \(\mathrel{R}\text{.}\)
\(\text{ dom} (R) = \Z\) and \(\text{ range} (R) = \Z\)
(c)
Use the roster method to specify the set of all integers \(x\) such that \(x \mathrel{R} 5\) and the set of all integers \(x\) such that \(5 \mathrel{R} x\text{.}\)
(d)
If possible, find integers \(x\) and \(y\) such that \(x \mathrel{R} 8\text{,}\) \(8 \mathrel{R} y\text{,}\) but \(x \mathrel{\not \negthickspace R} y\text{.}\)
(e)
If \(b \in \Z\text{,}\) use the roster method to specify the set of all \(x \in \Z\) such that \(x \mathrel{R} b\text{.}\)
10.
Let \(R_{ \lt } = \left\{ { {\left( {x, y} \right) \in \mathbb{R} \times \mathbb{R} } \mid x \lt y} \right\}\text{.}\) This means that \(R_{ \lt }\) is the “less than” relation on \(\R\text{.}\)
(a)
What is the domain of the relation \(R_{ \lt }\text{?}\)
(b)
What is the range of the relation \(R_{ \lt }\text{?}\)
(c)
Is the relation \(R_{ \lt }\) a function from \(\mathbb{R}\) to \(\mathbb{R}\text{?}\) Explain.
Note: Remember that a relation is a set. Consequently, we can talk about one relation being a subset of another relation. Another thing to remember is that the elements of a relation are ordered pairs.
Activity 42. The Inverse of a Relation.
In Section 6.5, we introduced the inverse of a function. If \(A\) and \(B\) are nonempty sets and if \(f:A \to B\) is a function, then the inverse of \(f\text{,}\) denoted by \(f^{ - 1}\text{,}\) is defined as
Now that we know about relations, we see that \(f^{ - 1}\) is always a relation from \(B\) to \(A\text{.}\) The concept of the inverse of a function is actually a special case of the more general concept of the inverse of a relation, which we now define.
Definition.
Let \(R\) be a relation from the set \(A\) to the set \(B\text{.}\) The inverse of \(\boldsymbol{R}\), written \(R^{ - 1}\) and read “\(R\) inverse,” is the relation from \(B\) to \(A\) defined by
That is, \(R^{ - 1}\) is the subset of \(B \times A\) consisting of all ordered pairs \(\left( {y, x} \right)\) such that \(x \mathrel{R} y\text{.}\)
For example, let \(D\) be the “divides” relation on \(\mathbb{Z}\text{.}\) See Progress Check 7.4. So
This means that we can write \(m \mid n\) if and only if \(\left( {m, n} \right) \in D\text{.}\) So, in this case,
Now, if we would like to focus on the first coordinate instead of the second coordinate in \(D^{ - 1}\text{,}\) we know that “\(m\) divides \(n\)” means the same thing as “\(n\) is a multiple of \(m\text{.}\)” Hence,
We can say that the inverse of the “divides” relation on \(\mathbb{Z}\) is the “is a multiple of” relation on \(\mathbb{Z}\text{.}\) Theorem 7.10, which follows, contains some elementary facts about inverse relations.
Theorem 7.10.
Let \(R\) be a relation from the set \(A\) to the set \(B\text{.}\) Then
The domain of \(R^{ - 1}\) is the range of \(R\text{.}\) That is, \(\text{ dom} \!\left( {R^{ - 1} } \right) = \text{ range} ( R )\text{.}\)
The range of \(R^{ - 1}\) is the domain of \(R\text{.}\) That is, \(\text{ range} \!\left( {R^{ - 1} } \right) = \text{ dom} ( R )\text{.}\)
The inverse of \(R^{ - 1}\) is \(R\text{.}\) That is, \(\left( {R^{ - 1} } \right)^{ - 1} = R\text{.}\)
To prove the first part of Theorem 7.10, observe that the goal is to prove that two sets are equal,
One way to do this is to prove that each is a subset of the other. To prove that \(\text{ dom} \!\left( {R^{ - 1} } \right) \subseteq \text{ range} ( R )\text{,}\) we can start by choosing an arbitrary element of \(\text{ dom} \!\left( {R^{ - 1} } \right)\text{.}\) So let \(y \in \text{ dom} \!\left( {R^{ - 1} } \right)\text{.}\) The goal now is to prove that \(y~\in~\text{ range} ( R )\text{.}\) What does it mean to say that \(y \in \text{ dom} \!\left( {R^{ - 1} } \right)\text{?}\) It means that there exists an \(x \in A\) such that
Now what does it mean to say that \(( {y, x} ) \in R^{ - 1}\text{?}\) It means that \(( {x, y} ) \in R\text{.}\) What does this tell us about \(y\text{?}\) Complete the proof of the first part of Theorem 7.10. Then, complete the proofs of the other two parts of Theorem 7.10.