# Discrete Mathematics: An Active Approach to Mathematical Reasoning

## Section1.3Introduction to Relations and Functions

We are familiar with the idea of a function from previous math courses. In this class we want to understand functions as an important mathematical tool to relate objects to each other. We are used to functions from the real numbers to the real numbers in calculus. All math courses use functions in some way, often relating other mathematical objects, such as vectors in vector calculus, matrices in linear algebra, complex numbers in complex analysis, or strings of characters in computer science.
A function really describes a relationship, so we will start with the more general mathematical concept of a relation.

### Definition1.3.1.

A relation, $$R\text{,}$$ from a set $$A$$ to a set $$B$$ is a subset of $$A\times B\text{.}$$
We can describe a relation as a subset, $$(a, b)\in R$$ or in the form $$aRb$$, which means “$$a$$ is related to $$b\text{.}$$
It is important to note that a relation is just a set. As long as the first coordinate comes from $$A$$ and the second from $$B\text{,}$$ we have a relation. The notation $$aRb$$ is a convenient way to describe whether two elements are related. In this case, we are thinking of $$R$$ as a symbol representing the relationship, rather than as a set.
Let $$A=\{1, 2, 3\}, B=\{2, 3, 4\}\text{.}$$ Let $$R=\{(1, 4), (3, 2)\}\text{.}$$ Then $$R$$ is a subset of $$A\times B\text{.}$$ Thus, it is a relation.
Since $$(1, 4)\in R\text{,}$$ $$1R4$$ is true.
Since $$(2, 3)\notin R\text{,}$$ $$2R3$$ is false. Note, since $$R$$ consists of ordered pairs, the order matters.
There are lots of familiar relations in math. For example, $$\geq$$ is a relation.
Let $$A=\{1, 2, 3\}, B=\{2, 3, 4\}\text{.}$$ Find $$R$$ from $$A$$ to $$B$$ if
$$aRb$$ is given by $$a\geq b\text{.}$$
$$R=\{(2, 2), (3, 2), (3, 3)\}$$
If $$R$$ is a relation from $$A$$ to $$B\text{,}$$ then $$A$$ is the domain of the relation, and $$B$$ is the codomain of the relation.
An arrow diagram for a relation is a picture of the two sets with an arrow from $$a$$ to $$b$$ if $$aRb\text{.}$$

### Definition1.3.5.

A function, $$f\text{,}$$ from a set $$A$$ to a set $$B\text{,}$$ $$f:A \rightarrow B\text{,}$$ is a mapping such that for every $$a\in A$$ there is a unique $$b\in B$$ with $$f(a)=b\text{.}$$
Let $$A=\mathbb{R}, B=\mathbb{R}\text{.}$$ Let $$f(x)=x+2\text{.}$$ Then $$f:\mathbb{R}\rightarrow\mathbb{R}\text{.}$$ We can check that it is a function: if we choose an $$x\in A\text{,}$$ we can see that there is a corresponding real number $$x+2\text{,}$$ which always exists. We can also see that for any $$x\in A\text{,}$$ there is only one possible number as output.
A function is really a relation with some additional properties. First, for each $$a$$ in $$A\text{,}$$ a corresponding $$b$$ must exist. Second, $$b$$ must be unique. In other words, every $$a$$ must map somewhere and each $$a$$ can only map to one $$b\text{.}$$
Since a function is a relation, we can use relation notation to represent a function. Often we use $$F$$ for the relation. In particular, $$f(x)=y$$ if and only if $$(x, y)\in F\text{.}$$
Let $$A=\mathbb{R}, B=\mathbb{R}\text{.}$$ Let $$f(x)=x+2\text{.}$$ Then $$F$$ is a subset of $$\mathbb{R}\times \mathbb{R}\text{,}$$ thus it is a relation. Give 3 examples of ordered pairs in $$F\text{.}$$
There are lots of examples, $$(1, 3), (-2, 0), (5/2, 9/2)$$ are a few.
Let $$A=\mathbb{R}, B=\mathbb{R}\text{.}$$ Let $$(x, y)\in R$$ if and only if $$x^2=y^2\text{.}$$ Then $$R$$ is a subset of $$\mathbb{R}\times \mathbb{R}\text{,}$$ thus it is a relation. Give 3 examples of ordered pairs in $$R\text{.}$$
There are lots of examples, $$(2, 2), (-5, 5), (2, -2)$$ are a few.
Note, this relation is not a function since if $$x=2\text{,}$$ we can have $$y=2$$ or $$y=-2\text{.}$$ Thus $$y$$ is not unique for a given $$x\text{.}$$

### Activity1.3.1.

Let $$A=\{1, 2, 3, 4, 5\}$$ and $$B=\{0, 2, 4\}\text{.}$$ Let $$R$$ be the relation from $$A$$ to $$B$$ where $$(x, y)\in R$$ if $$x=y\text{.}$$

#### (a)

List the elements of $$R\text{.}$$

#### (b)

Draw the arrow diagram for $$R\text{.}$$

#### (c)

Is the relation $$R$$ a function? Why or why not?

### Activity1.3.2.

Let $$A=\{1, 2, 3, 4, 5\}$$ and $$B=\{0, 2, 4\}\text{.}$$ Let $$S$$ be the relation from $$A$$ to $$B$$ where $$(x, y)\in S$$ if $$x-y$$ is positive.

#### (a)

List the elements of $$S\text{.}$$

#### (b)

Draw the arrow diagram for $$S\text{.}$$

#### (c)

Is the relation $$S$$ a function? Why or why not?

### Activity1.3.3.

The successor function is given by $$g(n)=n+1\text{.}$$ Let the domain be $$A=\{1, 2, 3, 4, 5\}\text{.}$$ Give the ordered pairs for $$g\text{.}$$

### Activity1.3.4.

Let $$U$$ be the relation from $$\mathbb{R}$$ to $$\mathbb{R}$$ given by $$(x, y)\in U$$ if $$x^2+y^2=1\text{.}$$ Is $$U$$ a function? Draw the set $$U$$ in the Cartesian plane.
Hint.
Keep in mind that relations are just sets of ordered pairs, so we can graph them in the $$xy$$-plane.

#### 1.

Let $$A=\{2, 4, 6\}, B=\{3, 4, 5\}\text{,}$$ then $$\{(2, 2), (3, 3), (4, 4)\}$$ is a relation from $$A$$ to $$B\text{.}$$
• True.

• False.

#### 2.

Let $$A=\{2, 4, 6\}, B=\{3, 4, 5\}\text{,}$$ then $$\{(2, 2), (4, 4), (6, 6)\}$$ is a relation from $$A$$ to $$A\text{.}$$
• True.

• False.

#### 3.

Let $$A=\{2, 4, 6\}, B=\{3, 4, 5\}\text{,}$$ then $$\{(2, 3), (4, 3), (6, 3)\}$$ is a relation from $$A$$ to $$B\text{.}$$
• True.

• False.

#### 4.

Let $$A=\{2, 4, 6\}, B=\{3, 4, 5\}\text{,}$$ then $$\{(2, 3), (2, 4), (2, 5)\}$$ is a relation from $$A$$ to $$B\text{.}$$
• True.

• False.

#### 5.

Let $$A=\{2, 4, 6\}, B=\{3, 4, 5\}\text{,}$$ then $$\{(4, 3), (2, 5)\}$$ is a relation from $$A$$ to $$B\text{.}$$
• True.

• False.

#### 6.

Let $$A=\{2, 4, 6\}, B=\{3, 4, 5\}\text{,}$$ then $$\{(2, 2), (3, 3), (4, 4)\}$$ is a function from $$A$$ to $$B\text{.}$$
• True.

• False.

#### 7.

Let $$A=\{2, 4, 6\}, B=\{3, 4, 5\}\text{,}$$ then $$\{(2, 2), (4, 4), (6, 6)\}$$ is a function from $$A$$ to $$A\text{.}$$
• True.

• False.

#### 8.

Let $$A=\{2, 4, 6\}, B=\{3, 4, 5\}\text{,}$$ then $$\{(2, 3), (4, 3), (6, 3)\}$$ is a function from $$A$$ to $$B\text{.}$$
• True.

• False.

#### 9.

Let $$A=\{2, 4, 6\}, B=\{3, 4, 5\}\text{,}$$ then $$\{(2, 3), (2, 4), (2, 5)\}$$ is a function from $$A$$ to $$B\text{.}$$
• True.

• False.

#### 10.

Let $$A=\{2, 4, 6\}, B=\{3, 4, 5\}\text{,}$$ then $$\{(4, 3), (2, 5)\}$$ is a function from $$A$$ to $$B\text{.}$$
• True.

• False.

### ExercisesExercises

#### 1.

Let $$A=\{2, 3, 4\}$$ and $$B=\{4, 6, 8\}$$ and let $$R$$ be the relation from $$A$$ to $$B$$ where
\begin{equation*} (x, y)\in R \textrm{ if } \frac{y}{x} \textrm{ is an integer.} \end{equation*}
1. Is $$4\ R\ 6$$ ? Is $$4\ R\ 8$$ ? Is $$(3, 8) \in R$$ ? Is $$(3, 6)\in R$$ ?
2. Write $$R$$ as a set of ordered pairs.
3. Write the domain and codomain of $$R\text{.}$$
4. Draw an arrow diagram for $$R\text{.}$$

#### 2.

Let $$C=\{-2, 0, 2\}$$ and $$D=\{4, 6, 8\}$$ and let $$S$$ be the relation from $$C$$ to $$D$$ where
\begin{equation*} (x, y)\in S \textrm{ if } \frac{x-y}{4} \textrm{ is an integer.} \end{equation*}
1. Is $$2\ S\ 6$$ ? Is $$2\ S\ 8$$ ? Is $$(0, 6) \in S$$ ? Is $$(2, 4)\in S$$ ?
2. Write $$S$$ as a set of ordered pairs.
3. Write the domain and codomain of $$S\text{.}$$
4. Draw an arrow diagram for $$S\text{.}$$

#### 3.

Let $$T$$ be the relation from $$\mathbb{R}$$ to $$\mathbb{R}$$ where
\begin{equation*} (x, y)\in T \textrm{ if } y=x^2. \end{equation*}
1. Is $$-3\ T\ 9$$ ? Is $$9\ T\ -3$$ ? Is $$(2, 4) \in T$$ ? Is $$(4, 2)\in T$$ ?
2. Draw the graph of $$T$$ in the Cartesian plane.

#### 4.

Let $$H$$ be the relation from $$\mathbb{R}$$ to $$\mathbb{R}$$ where
\begin{equation*} (x, y)\in H \textrm{ if } y^2-x^2=1. \end{equation*}
Is $$H$$ a function? Explain your answer.

#### 5.

Let $$A=\{-1, 0, 1\}$$ and $$B=\{w, x, y, z\}$$ and let $$F$$ be the function $$F: A\rightarrow B$$ given by the set $$F=\{(-1, y), (0, w), (1, y)\}\text{.}$$
1. Write the domain and codomain of $$F\text{.}$$
2. Explain why $$F$$ is a function.
3. Find $$F(-1), F(0),$$ and $$F(1)\text{.}$$