Discrete Mathematics: An Active Approach to Mathematical Reasoning

Section7.1Functions

Functions are familar mathematical objects from algebra and calculus. We also saw them in Section 1.3.

Definition7.1.1.

A function, $$f:X\rightarrow Y\text{,}$$ is a map in which each input is related to one and only one output.
We say $$X$$ is the domain and $$Y$$ is the codomain of $$f\text{.}$$
Let $$f: X\rightarrow Y$$ be a map as shown in the figure.
Figure 7.1.3 shows a map that is not a function since $$x_2$$ maps to two different outputs.
Let $$g: X\rightarrow Y$$ be a map as shown in the figure.
Figure 7.1.4 shows a map that is not a function since $$x_1$$ does not map to any output.
Let $$h: X\rightarrow Y$$ be a map as shown in the figure.
Figure 7.1.5 shows a map that is a function since each $$x_i$$ maps to exactly one $$y_i\text{.}$$
For a given $$x\in X\text{,}$$ $$f(x)$$ is
• the output of $$f\text{,}$$
• the value of $$f$$ at $$x\text{,}$$
• the image of $$x$$ under $$f\text{.}$$

Definition7.1.6.

The image or range of a set $$X$$ under $$f$$ is the set of outputs of $$f$$ corresponding to inputs from $$X\text{.}$$ In notation
\begin{equation*} \text{Im}(f)=\{y\in Y : y=f(x) \text{ for some } x\in X\}. \end{equation*}
If $$f(x)=y$$ we say $$x$$ is a preimage or an inverse image of $$y\text{.}$$
Since $$y$$ can have several preimages, we usually care about the set of all of them.

Definition7.1.7.

Let $$f:X\rightarrow Y$$ be a function. The set $$\{x\in X : f(x)=y\}$$ is the preimage of $$y\text{.}$$

Activity7.1.1.

Define $$f:\mathbb{Z}\rightarrow\mathbb{Z}$$ by $$f(n)=r$$ where $$r$$ is the remainder when $$n$$ is divided by 3.

(a)

Find $$f(0), f(9), f(5), f(-7), f(10)\text{.}$$

(b)

What is the image of $$\mathbb{Z}$$ under $$f\text{?}$$

(c)

What is the set of preimages of 0? In other words, find the preimage of 0.
If we have a map from a finite set to a finite set, we can draw an arrow diagram in which we use arrows to represent the map from $$X$$ to $$Y\text{,}$$ as in Example 7.1.2.
Let $$X=\{a, b, c, d\}$$ and $$Y=\{0, 1, 2\}\text{.}$$ Let $$f: X\rightarrow Y$$ be the function given by the following arrow diagram.
Find the domain of $$f\text{.}$$
$$\{a, b, c, d\}$$
Find the codomain of $$f\text{.}$$
$$\{0, 1, 2\}$$
Find the range or image of $$f\text{.}$$
$$\{0, 2\}$$
Find $$f(a)\text{.}$$
$$0$$
Find the preimage or inverse image of $$0\text{.}$$
$$\{a, b\}$$
Let $$f:\mathbb{R}\rightarrow \mathbb{R}$$ be given by $$f(x)=x^2\text{.}$$
Find the domain of $$f\text{.}$$
$$\mathbb{R}$$
Find the codomain of $$f\text{.}$$
$$\mathbb{R}$$
Find the range of $$f\text{.}$$
$$[0, \infty)$$
Find the preimage (or inverse image) of $$1\text{.}$$
$$\{1, -1\}$$
Let $$f, g$$ be functions from $$X$$ to $$Y\text{.}$$ Then $$f=g$$ if $$f(x)=g(x)$$ for all $$x\in X\text{.}$$
In this course we want to look at functions to and from sets other than just the real numbers. For example, we may have functions from finite sets to finite sets.
A sequence is a function from $$\mathbb{Z}^+$$ to $$\mathbb{R}\text{.}$$ For example, $$f(n)=\frac{1}{n}\text{.}$$
We may also have functions involving Cartesian products of sets. For example, $$f:\mathbb{Z}\times\mathbb{Z}\rightarrow\mathbb{Z}$$ given by $$f(a, b)=a+b\text{.}$$

Activity7.1.2.

Define $$f:\mathbb{Z}\times\mathbb{Z}\rightarrow\mathbb{Z}$$ by $$f(a, b)=a-b\text{.}$$

(a)

Find $$f(0, 2), f(1, 1), f(2, 0), f(3, 2), f(n, 0)\text{.}$$

(b)

What is the image of $$\mathbb{Z}\times\mathbb{Z}$$ under $$f\text{?}$$

(c)

What is the preimage of 0?

Activity7.1.3.

Define $$f:\mathbb{Z}\rightarrow\mathbb{Z}\times\mathbb{Z}$$ by $$f(a)=(a, a)\text{.}$$

(a)

Find $$f(0), f(2), f(-3)\text{.}$$

(b)

What is the image of $$\mathbb{Z}$$ under $$f\text{?}$$ Is $$(1, 1)$$ in the image? Is $$(-1, 1)$$ in the image?

(c)

What is the preimage of $$(0, 0)\text{?}$$
Since a function needs to satisfy the property that each $$x\in X$$ can only map to one $$y \in Y\text{,}$$ we say a function is well-defined if whenever $$a=b\text{,}$$ $$f(a)=f(b)\text{.}$$ Most of the functions you've seen in algebra and calculus are clearly well-defined since when $$a=b\text{,}$$ $$f(a)=f(b)\text{.}$$ This property is really only interesting when elements of $$X$$ have multiple representations. In other words, when two equal elements in $$X$$ have two different forms. The most familiar set where this happens is $$\mathbb{Q}\text{.}$$ For example, $$\frac{1}{2}=\frac{2}{4}\text{.}$$
Let $$f:\mathbb{Q}\rightarrow \mathbb{Z}$$ be given by $$f(p/q)=p+q\text{.}$$
Then $$1/2=2/4$$ in $$\mathbb{Q}\text{,}$$ but $$f(1/2)=1+2=3$$ and $$f(2/4)=2+4=6\text{.}$$ Thus, $$1/2=2/4$$ but $$f(1/2)\neq f(2/4)\text{.}$$
Thus $$f$$ is not well-defined, and hence, $$f$$ is not a function.

Activity7.1.4.

Let $$f:\mathbb{Q}\rightarrow\mathbb{Z}$$ be given by $$f(m/n)=m\text{.}$$ Show $$f$$ is not well-defined by finding two equivalent fractions in $$\mathbb{Q}$$ that map to two different integers.

1.

Let $$A=\{1, 2, 3\}, B=\{2, 4, 6, 8\}\text{.}$$
Let $$f:A\rightarrow B$$ be given by $$f(1)=4, f(2)=8, f(3)=2\text{.}$$
True or false: $$f$$ is a function.
• True.

• False.

2.

Let $$A=\{1, 2, 3\}, B=\{2, 4, 6, 8\}\text{.}$$
Let $$f:A\rightarrow B$$ be given by $$f(1)=2, f(2)=4, f(3)=2\text{.}$$
True or false: $$f$$ is a function.
• True.

• False.

3.

Let $$B=\{2, 4, 6, 8\}, C=\{0, 1\}\text{.}$$
Let $$f:B\rightarrow C$$ be given by $$f(2)=0, f(4)=1\text{.}$$
True or false: $$f$$ is a function.
• True.

• $$6, 8$$ don't map anywhere.
• False.

• $$6, 8$$ don't map anywhere.

4.

Let $$B=\{2, 4, 6, 8\}, C=\{0, 1\}\text{.}$$
Let $$f:B\rightarrow C$$ be given by $$f(2)=0, f(4)=1, f(6)=1, f(8)=1\text{.}$$
True or false: $$f$$ is a function.
• True.

• False.

5.

Let $$C=\{0, 1\}\text{.}$$
Let $$f:C\rightarrow C$$ be given by $$f(0)=0, f(0)=1, f(1)=0, f(1)=1\text{.}$$
True or false: $$f$$ is a function.
• True.

• 0 maps to two different values.
• False.

• 0 maps to two different values.

6.

Let $$A=\{1, 2, 3\}, C=\{0, 1\}\text{.}$$
Let $$f:A\times C\rightarrow C$$ be given by $$f(a, c)=c\text{.}$$
Which of the following are in the preimage of $$0\in C\text{.}$$
• (1, 0)
• $$(1, 0)$$ is in the preimage.
• (2, 0)
• $$(2, 0)$$ is in the preimage.
• (3, 0)
• $$(3, 0)$$ is in the preimage.
• (0, 0)
• $$(0, 0)$$ is not in $$A\times C\text{.}$$
• 0
• $$0$$ is not in $$A\times C\text{.}$$
• (0, 1)
• $$(0, 1)$$ is not in $$A\times C\text{,}$$ and would not map to 0.
• 1
• $$1$$ is not in $$A\times C\text{.}$$

ExercisesExercises

1.

Let $$X=\{1, 3, 5\}$$ and $$Y=\{a, b, c, d\}\text{.}$$ Define the function $$g:X\rightarrow Y$$ as the set of ordered pairs
\begin{equation*} \{(1, b), (3, b), (5, b)\}. \end{equation*}
1. Write the domain and codomain of $$g\text{.}$$
2. What is the range of $$g\text{?}$$
3. Is 3 an inverse image of $$a\text{?}$$ Is 1 an inverse image of $$b\text{?}$$
4. What is the inverse image of $$b\text{?}$$ What is the inverse image of $$c\text{?}$$
5. Represent $$g$$ as an arrow diagram.

2.

Determine if the following are true or false. Justify your answer.
1. If two elements in the domain of a function are equal, then their images in the codomain are equal.
2. If two elements in the codomain of a function are equal, then their preimages in the domain are equal.
3. A function can have the same output for more than one input.
4. A function can have the same input for more than one output.

3.

Let $$A=\{1, 2, 3, 4, 5\}$$ and define a function $$F:{\cal P}(A)\rightarrow \mathbb{Z}$$ where for all sets $$X$$ in $${\cal P}(A)\text{,}$$
\begin{equation*} F(X)= \begin{cases} 0 &\text{if $X$ has an even number of elements}\\ 1 &\text{if $X$ has an odd number of elements.} \end{cases} \end{equation*}
1. Find $$F(\{1, 3, 4\})\text{.}$$
2. Find $$F(\emptyset)\text{.}$$
3. Find $$F(\{2, 3\})\text{.}$$
4. $$F(\{2, 3, 4, 5\})\text{.}$$

4.

Let $$D$$ be the set of all finite subsets of positive integers. Let $$T:\mathbb{Z}^+\rightarrow D$$ be the function where for each positive integer $$n\text{,}$$ $$T(n)$$ is the set of positive divisors of $$n\text{.}$$
1. Find $$T(1)\text{.}$$
2. Find $$T(15)\text{.}$$
3. Find $$T(17)\text{.}$$
4. Find $$T(5)\text{.}$$
5. Find $$T(18)\text{.}$$
6. Find $$T(21)\text{.}$$

5.

Define the function $$F:\mathbb{Z}\times\mathbb{Z}\rightarrow \mathbb{Z}\times\mathbb{Z}$$ where for all ordered pairs $$(a, b)$$ of integers, $$F(a, b)=(2a+1, 3b-2)\text{.}$$
1. Find $$F(4, 4)\text{.}$$
2. Find $$F(2, 1)\text{.}$$
3. Find $$F(3, 2)\text{.}$$
4. Find $$F(1, 5)\text{.}$$

6.

Let $$X=\{1, 2, 3, 4\}$$ and $$Y=\{a, b, c, d, e\}\text{.}$$ Define $$g:X\rightarrow Y$$ by $$g(1)=a, g(2)=a, g(3)=a$$ and $$g(4)=d\text{.}$$
1. Draw an arrow diagram for $$g\text{.}$$
2. Let $$A=\{2, 3\}, C=\{a\}\text{,}$$ and $$D=\{b, c\}\text{.}$$ Find $$g(A), g(X), g^{-1}(C), g^{-1}(D)\text{,}$$ and $$g^{-1}(Y)\text{.}$$

7.

Show that each of the following maps is not a function by showing it is not well-defined.
1. Define $$g:\mathbb{Q}\rightarrow\mathbb{Z}$$ by the rule
\begin{equation*} g\Big(\frac{m}{n}\Big)=m-n \end{equation*}
for all integers $$m$$ and $$n$$ with $$n\neq 0\text{.}$$
2. Define $$h:\mathbb{Q}\rightarrow\mathbb{Q}$$ by the rule
\begin{equation*} h\Big(\frac{m}{n}\Big)=\frac{m^2}{n} \end{equation*}
for all integers $$m$$ and $$n$$ with $$n\neq 0\text{.}$$