### Definition 8.1.1.

A relation, \(R\text{,}\) on \(A\times B\text{,}\) is a set of ordered pairs in \(A\times B\text{.}\)

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.

A relation, \(R\text{,}\) on \(A\times B\text{,}\) is a set of ordered pairs in \(A\times B\text{.}\)

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{.}\)

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.

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{.}\)

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

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{.}\)

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{.}\)

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)\}\)

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*}

Find the set of ordered pairs given by this relation.

Draw the arrow diagram for this relation.

Give the inverse relation for \(R\text{.}\) Remember, it is a set of ordered pairs.

Is the relation \(R\) a function?

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{.}\)

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.

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*}

Find the set of ordered pairs given by this relation.

Draw the directed graph for this relation.

Give the inverse relation for \(R\text{.}\) Remember, it is a set of ordered pairs.

Is the relation \(R\) a function?

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*}

Find the set of ordered pairs given by this relation.

Draw the directed graph for this relation.

Give the inverse relation for \(R\text{.}\)

Hint.

Remember, it is a set of ordered pairs.

Is the relation \(R\) a function?

- \((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*}

- \((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*}

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{.}\)

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{.}\)

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.

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.

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{.}\)

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{?}\)

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{?}\)

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{.}\)

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{.}\)

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{.}\)

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{.}\)

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{.}\)