Definition 8.1.1.
A relation, \(R\text{,}\) on \(A\times B\text{,}\) is a set of ordered pairs in \(A\times B\text{.}\)
Section 8.1 Relations on Sets
We first saw relations in Section 1.3. In this section we revisit the definition, look at several examples, and connect the idea of a function to a relation.
Simply put, a relation is just a subset, \(R\text{,}\) of \(A\times B\text{.}\)
We often use the notation \(x R y\) to mean “\(x\) is related to \(y\text{.}\)” In particular, \((x, y)\in R\) if and only if \(x R y\text{.}\)
Example 8.1.2. Relation Defined by a Set.
Let \(A=\{1, 2, 3, 4\}\text{,}\) \(B=\{1, 3, 5\}\) define the relation on \(A\times B\) by
\begin{equation*}
R=\{(1, 1), (1, 5), (3, 5), (2, 1), (4, 3)\}.
\end{equation*}
Then \(1 R 1, 3 R 5, 4 R 3\text{,}\) for example. But 3 is not related to 1, for example.
Example 8.1.3. Relation Defined by Less Than.
We can also define relations with familiar mathematical relationships.
Let \(A=\{1, 2, 3, 4\}\text{,}\) \(B=\{1, 3, 5\}\) define the relation on \(A\times B\) by
\begin{equation*}
x R y \Leftrightarrow x< y.
\end{equation*}
Find the set of ordered pairs for \(R\text{.}\)
Answer.
\(R=\{(1, 3), (1, 5), (2, 3), (2, 5), (3, 5), (4, 5)\}\)
As with functions, we can draw an arrow diagram from \(A\) to \(B\) representing the relationship. We have an arrow from \(a\) to \(b\) if \(aRb\text{,}\) or \((a, b)\in R\text{.}\)
The arrow diagram for the relation “a< b”, given in Example 8.1.2 is given in the following figure.
A function is a relation. Let \(f:A\rightarrow B, f(a)=b\text{.}\) Then define \(R\) by
\begin{equation*}
(a, b)\in R \Leftrightarrow f(a)=b.
\end{equation*}
We can see that Example 8.1.3 is not a function since an element of \(A\) can map to two different elements of \(B\text{:}\) \((1, 3), (1, 5)\text{.}\)
Example 8.1.5. A Function as a Relation.
Let \(f:\mathbb{Z}\rightarrow\mathbb{Z}\) be given by \(f(n)=n^2\text{.}\) Let \(F\) be the relation given by \(f\text{:}\)
\begin{equation*}
(a, b)\in F \Leftrightarrow f(a)=b.
\end{equation*}
True or false: \((1, 1)\in F\text{.}\)
Answer 1.
True
True or false: \((3, 9)\in F\text{.}\)
Answer 2.
True
True or false: \((9, 3)\in F\text{.}\)
Answer 3.
False
True or false: \((-2, 4)\in F\text{.}\)
Answer 4.
True
True or false: \((2, -4)\in F\text{.}\)
Answer 5.
False
True or false: \((1, 3)\in F\text{.}\)
Answer 6.
False
Determining if a Relation Is a Function.
A relation is a function if the following two properties hold:
- For every \(a\in A\) there must be a \(b\in B\) related to \(a\text{.}\)
- Each \(a\in A\) can only be related in one \(b\in B\text{.}\)
We can translate this idea into the ordered pair notation:
- For every \(a\in A\) there must be a \(b\in B\) such that \((a, b)\in F\text{.}\)
- If \((a, b)\in F\) and \((a, c)\in F\) then \(b=c\text{.}\)
Definition 8.1.6.
Let \(R\) be a relation on \(A\times B\text{.}\) The inverse relation, \(R^{-1}\text{,}\) on \(B\times A\) is
\begin{equation*}
R^{-1}=\{(b, a)\in B\times A : (a, b)\in R\}.
\end{equation*}
In other words, \((a, b)\in R\) if and only if \((b, a)\in R^{-1}\text{.}\)
Example 8.1.7. Inverse Relation.
Let \(R=\{(1, 3), (1, 5), (2, 3), (2, 5), (3, 5), (4, 5)\}\text{.}\) This is the relation in Example 8.1.3.
Find \(R^{-1}\text{.}\)
Answer.
\(\{(3, 1), (5, 1), (3, 2), (5, 2), (5, 3), (5, 4)\}\)
Activity 8.1.1.
Let \(A=\{1, 2, 3, 4\}\) and \(B=\{0, 1\}\text{.}\) Define the relation from \(A\) to \(B\) by
\begin{equation*}
(x, y)\in R \iff x-y\ \text{is even}.
\end{equation*}
(a)
Find the set of ordered pairs given by this relation.
(b)
Draw the arrow diagram for this relation.
(c)
Give the inverse relation for \(R\text{.}\) Remember, it is a set of ordered pairs.
(d)
Is the relation \(R\) a function?
Definition 8.1.8.
A relation on \(A\) is a relation on \(A\times A\text{.}\) We also say a relation from \(A\) to \(A\text{.}\)
We can use a directed graph to represent a relation on \(A\text{.}\) We label the vertices with the elements from \(A\) and draw and arrow from \(a\) to \(b\) if \(aRb\text{.}\) Note, if \(aRa\text{,}\) then we get a “loop” at \(a\text{.}\)
Example 8.1.9. Directed Graph of a Relation.
Let \(A=\{1, 2, 3\}\text{.}\) Let \(R=\{(x, y) : x< y\}\text{.}\) Then we get the following directed graph for \(R\text{.}\)
If we now want the relations for less than or equal to, \(R=\{(x, y) : x\leq y\}\text{,}\) we have the following directed graph.
Activity 8.1.2.
Let \(A=\{0, 1, 2, 3, 4, 5\}\text{.}\) Define the relation on \(A\) by
\begin{equation*}
(x, y)\in R \iff 3 \mid (x-y).
\end{equation*}
(a)
Find the set of ordered pairs given by this relation.
(b)
Draw the directed graph for this relation.
(c)
Give the inverse relation for \(R\text{.}\) Remember, it is a set of ordered pairs.
(d)
Is the relation \(R\) a function?
Activity 8.1.3.
Let \(A=\{0, 1, 2, 3, 4, 5\}\text{.}\) Define the relation on \(A\) by
\begin{equation*}
(x, y)\in R \iff x\ \text{divides}\ y.
\end{equation*}
(a)
Find the set of ordered pairs given by this relation.
(b)
Draw the directed graph for this relation.
(c)
Give the inverse relation for \(R\text{.}\)
Hint.
Remember, it is a set of ordered pairs.
(d)
Is the relation \(R\) a function?
Reading Questions Check Your Understanding
1.
- \((2, 2)\)
- Correct, \(2\geq 2\)
- \((3, 2)\)
- Correct, \(3\geq 2\)
- \((2, 6)\)
- Is \(2 \geq 6\text{?}\)
- \((4, 2)\)
- Is 4 in \(A\text{?}\)
Let \(A=\{1, 2, 3\}, B=\{2, 4, 6, 8\}\text{.}\) Determine which of the ordered pairs are in the relation on \(A\times B\) given by
\begin{equation*}
a R b \Leftrightarrow a\geq b
\end{equation*}
2.
- \((0, 0)\)
- Correct, \(0+0=0\text{,}\) which is even.
- \((1, 1)\)
- Correct, \(1+1=2\text{,}\) which is even.
- \((0, 1)\)
- Is \(0+1\) even?
- \((1, 3)\)
- Is 3 in \(C\text{?}\)
Let \(C=\{0, 1\}\text{.}\) Determine which of the ordered pairs are in the relation for the relation on \(C\) given by
\begin{equation*}
a R b \Leftrightarrow a+b \text{ is even}
\end{equation*}
3.
True.
- 1 does not map to anything in \(B\text{.}\)
False.
- 1 does not map to anything in \(B\text{.}\)
Let \(A=\{1, 2, 3\}, B=\{2, 4, 6, 8\}\text{.}\) True or false: the relation on \(A\times B\) given by
\begin{equation*}
a R b \Leftrightarrow a\geq b
\end{equation*}
is a function from \(A\) to \(B\text{.}\)
4.
True.
False.
Let \(C=\{0, 1\}\text{.}\) True or false: the relation on \(C\) given by
\begin{equation*}
a R b \Leftrightarrow a+b \text{ is even}
\end{equation*}
is a function on \(C\text{.}\)
5.
Let \(B=\{2, 4, 6, 8\}\text{.}\) Give the ordered pairs for the relation on \(B\) given by
\begin{equation*}
a R b \Leftrightarrow a\mid b.
\end{equation*}
Hint.
Your answer should have 8 ordered pairs.
6.
Give the ordered pairs for the inverse relation, \(R^{-1}\) on \(B\) when \(R\) is given by
\begin{equation*}
a R b \Leftrightarrow a\mid b.
\end{equation*}
Hint.
Your answer should have 8 ordered pairs.
Exercises Exercises
1.
Define the congruence modulo 3 relation, \(T\text{,}\) on \(\mathbb{Z}\) by
\begin{equation*}
m\ T\ n \iff 3\mid (m-n).
\end{equation*}
- Is \(10\ T\ 1\text{?}\) Is \(1\ T\ 10\text{?}\) Is \((2, 2)\in T\text{?}\) Is \((8, 1)\in T\text{?}\)
- List five integers \(n\) such that \(n\ T\ 0\text{.}\)
- List five integers \(n\) such that \(n\ T\ 1\text{.}\)
- List five integers \(n\) such that \(n\ T\ 2\text{.}\)
2.
Let \(X=\{a, b, c\}\) and \({\cal P}(X)\) be the power set of \(X\text{.}\) Define the relation \(R\) on \({\cal P}(X)\) by
\begin{equation*}
A \ R\ B \iff A \text{ has the same number of elements as } B.
\end{equation*}
- Is \(\{a, b\}\ R\ \{b, c\}\text{?}\)
- Is \(\{a\}\ R\ \{a, b\}\text{?}\)
- Is \(\{c\}\ R\ \{b\}\text{?}\)
3.
Define the relation, \(S\text{,}\) on \(\mathbb{Z}\) by
\begin{equation*}
m\ S\ n \iff 5\mid (m^2-n^2).
\end{equation*}
- Is \(1\ S\ (-9)\text{?}\)
- Is \(2\ S\ 13\text{?}\)
- Is \(2\ S\ (-8)\text{?}\)
- Is \((-8)\ S\ 2\text{?}\)
4.
Let \(A=\{3, 4, 5\}\) and \(B=\{4, 5, 6\}\) and let \(R\) be the “less than” relation. That is, for all \((x, y)\in A\times B\text{,}\)
\begin{equation*}
x\ R\ y \iff x<y.
\end{equation*}
- Find the set of ordered pairs in \(R\text{.}\)
- Find the set of ordered pairs in \(R^{-1}\text{.}\)
5.
Let \(A=\{3, 4, 5\}\) and \(B=\{4, 5, 6\}\) and let \(S\) be the “divides” relation. That is, for all \((x, y)\in A\times B\text{,}\)
\begin{equation*}
x\ S\ y \iff x\mid y.
\end{equation*}
- Find the set of ordered pairs in \(S\text{.}\)
- Find the set of ordered pairs in \(S^{-1}\text{.}\)
6.
Let \(A=\{a, b, c, d\}\text{.}\) Define the relation \(R\) on \(A\) by
\begin{equation*}
R=\{(a, b), (a, c), (b, c), (d, d)\}\text{.}
\end{equation*}
Draw the directed graph for \(R\text{.}\)
7.
Let \(A=\{2, 3, 4, 5, 6, 7, 8\}\text{.}\) Define the relation \(S\) on \(A\) by
\begin{equation*}
x\ S\ y \iff x\mid y.
\end{equation*}
Draw the directed graph for \(S\text{.}\)
8.
Let \(A=\{2, 3, 4, 5, 6, 7, 8\}\text{.}\) Define the relation \(T\) on \(A\) by
\begin{equation*}
x\ T\ y \iff 3\mid (x-y).
\end{equation*}
Draw the directed graph for \(T\text{.}\)
You have attempted of activities on this page.
