# Discrete Mathematics: An Active Approach to Mathematical Reasoning

## Section8.1Relations 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.

### Definition8.1.1.

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{.}$$

### Example8.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.

### Example8.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{.}$$
$$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{.}$$

### Example8.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{.}$$
True
True or false: $$(3, 9)\in F\text{.}$$
True
True or false: $$(9, 3)\in F\text{.}$$
False
True or false: $$(-2, 4)\in F\text{.}$$
True
True or false: $$(2, -4)\in F\text{.}$$
False
True or false: $$(1, 3)\in F\text{.}$$
False

### Determining if a Relation Is a Function.

A relation is a function if the following two properties hold:
1. For every $$a\in A$$ there must be a $$b\in B$$ related to $$a\text{.}$$
2. Each $$a\in A$$ can only be related in one $$b\in B\text{.}$$
We can translate this idea into the ordered pair notation:
1. For every $$a\in A$$ there must be a $$b\in B$$ such that $$(a, b)\in F\text{.}$$
2. If $$(a, b)\in F$$ and $$(a, c)\in F$$ then $$b=c\text{.}$$

### Definition8.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{.}$$

### Example8.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{.}$$
$$\{(3, 1), (5, 1), (3, 2), (5, 2), (5, 3), (5, 4)\}$$

### Activity8.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?

### Definition8.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{.}$$

### Example8.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.

### Activity8.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?

### Activity8.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?

#### 1.

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, 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{?}$$

#### 2.

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*}
• $$(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{?}$$

#### 3.

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.

• 1 does not map to anything in $$B\text{.}$$
• False.

• 1 does not map to anything in $$B\text{.}$$

#### 4.

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{.}$$
• True.

• False.

#### 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.

#### 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.

### ExercisesExercises

#### 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*}
1. Is $$10\ T\ 1\text{?}$$ Is $$1\ T\ 10\text{?}$$ Is $$(2, 2)\in T\text{?}$$ Is $$(8, 1)\in T\text{?}$$
2. List five integers $$n$$ such that $$n\ T\ 0\text{.}$$
3. List five integers $$n$$ such that $$n\ T\ 1\text{.}$$
4. 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*}
1. Is $$\{a, b\}\ R\ \{b, c\}\text{?}$$
2. Is $$\{a\}\ R\ \{a, b\}\text{?}$$
3. 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*}
1. Is $$1\ S\ (-9)\text{?}$$
2. Is $$2\ S\ 13\text{?}$$
3. Is $$2\ S\ (-8)\text{?}$$
4. 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*}
1. Find the set of ordered pairs in $$R\text{.}$$
2. 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*}
1. Find the set of ordered pairs in $$S\text{.}$$
2. 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{.}$$