# Introduction to Proofs: An Active Exploration of Mathematical Language

## Section5.3Functions

Functions are familar mathematical objects from algebra and calculus.

### Definition5.3.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{.}$$
1. Let $$f: X\rightarrow Y$$ be a map as shown in the figure.
Figure 5.3.3 shows a map that is not a function since $$x_2$$ maps to two different outputs.
2. Let $$g: X\rightarrow Y$$ be a map as shown in the figure.
Figure 5.3.4 shows a map that is not a function since $$x_1$$ does not map to any output.
3. Let $$h: X\rightarrow Y$$ be a map as shown in the figure.
Figure 5.3.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{.}$$

### Definition5.3.6.

The image or range of a set $$X$$ under $$f$$ is the set of outputs of $$f$$ corresponding to inputs from $$X\text{:}$$
\begin{equation*} \text{Im}(f)=\{y\in Y : y=f(x) \text{ for some } x\in X\}. \end{equation*}
In Section 4.1 we defined sequences as lists. Now we can define them as functions. A sequence is a function from $$\mathbb{Z}^+$$ to $$\mathbb{R}\text{.}$$ For example, $$f(n)=\frac{1}{n}\text{.}$$
We may have functions involving Cartesian products of sets. This is common when we want to define algebraic operations. For example, we can define addition on the integers as the function $$f:\mathbb{Z}\times\mathbb{Z}\rightarrow\mathbb{Z}$$ given by $$f(a, b)=a+b\text{.}$$
1. Find $$f(3, 2), f(5, 5), f(2, -4)\text{.}$$
$$5, 10, -2$$
2. What is the image of $$\mathbb{Z}\times\mathbb{Z}$$ under $$f\text{?}$$
$$\mathbb{Z}$$
3. Find all ordered pairs that map to 0.
$$\{(n, -n) : n\in \mathbb{Z}\}$$

### Activity5.3.1.Multiplication as a Function.

Define $$f:\mathbb{Z}\times\mathbb{Z}\rightarrow\mathbb{Z}$$ by $$f(a, b)=ab\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)

Find all ordered pairs that map to 0.
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{,}$$ we have $$f(a)=f(b)\text{.}$$ Most of the functions you've seen in 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 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{.}$$
Therefore $$f$$ is not well-defined, and hence, $$f$$ is not a function.

### Activity5.3.2.Showing a Map is Not Well-Defined.

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.
Now we will look at specific properties of functions. We will learn how to prove a function is one-to-one and/or onto its codomain. These properies are important as they are the exact properties we need in order for a function to have an inverse function.

### Definition5.3.9.

A function, $$f:X\rightarrow Y\text{,}$$ is one-to-one or injective if for all $$x_1, x_2\in X\text{,}$$ if $$f(x_1)=f(x_2)$$ then $$x_1=x_2\text{.}$$
Equivalently, $$f$$ is one-to-one if $$x_1\neq x_2$$ implies $$f(x_1)\neq f(x_2)\text{.}$$ We note, this is just the contrapositive of the definition.
Although it is easier to prove a function is one-to-one using the definition, the contrapositive can be helpful for deciding if a function is one-to-one.

### Proving and Disproving One-to-One.

To prove $$f:X\rightarrow Y$$ is one-to-one:
• Assume $$f(x_1)=f(x_2).$$
• Show $$x_1=x_2.$$
To prove $$f:X\rightarrow Y$$ is NOT one-to-one:
• Find a counterexample.
• In particular, find $$x_1, x_2\in X$$ with $$x_1\neq x_2$$ and $$f(x_1)=f(x_2)\text{.}$$
Note that a one-to-one proof is really a proof of uniqueness. We are proving there is a unique input $$x$$ for each output.
The function given in Figure 5.3.11 in not one-to-one since $$c$$ and $$d$$ both map to the same value in $$Y\text{.}$$
Let $$f:\mathbb{R}\rightarrow \mathbb{R}$$ be given by $$f(x)=3x+2\text{.}$$ Prove $$f$$ is one-to-one.
Assume $$f(x_1)=f(x_2)\text{.}$$ Then
\begin{align*} 3x_1+2&=3x_2+2\\ 3x_1&=3x_2\\ x_1&=x_2 \end{align*}
which is what we wanted to show.
Let $$f:\mathbb{Z}\rightarrow \mathbb{Z}$$ be given by $$f(x)=x^2-1\text{.}$$ Disprove $$f$$ is one-to-one.
We need a counterexample with $$x_1\neq x_2$$ and $$f(x_1)=f(x_2)\text{.}$$ Let $$x_1=2, x_2=-2\text{.}$$
Then $$f(2)=4-1=3$$ and $$f(-2)=4-1=3\text{.}$$ So $$f(x_1)=f(x_2)\text{,}$$ but $$2\neq-2\text{.}$$

### Definition5.3.14.

A function, $$f:X\rightarrow Y\text{,}$$ is onto $$Y$$ or surjective if for all $$y\in Y$$ there exists $$x\in X$$ such that $$f(x)=y\text{.}$$
Although we need the definition for onto to be able to write a proof, the concept of onto is easier to understand without the definition. Basically, we need every $$y\in Y$$ to get mapped to by some $$x\in X\text{.}$$ We can also think about onto in terms of sets. A function is onto $$Y$$ if $$Y$$ is the range or image of $$f\text{.}$$

### Proving and Disproving Onto.

To prove $$f:X\rightarrow Y$$ is onto $$Y\text{:}$$
• Let $$y$$ be a general element of $$Y\text{.}$$ You should not be using any information about the function at this point.
• Find $$x\in X$$ such that $$f(x)=y\text{.}$$ Finding $$x$$ may involve scratchwork.
• In your proof, state $$x\text{,}$$ show $$x\in X\text{,}$$ and show $$f(x)=y\text{.}$$
To prove $$f:X\rightarrow Y$$ is NOT onto $$Y\text{:}$$
• Find a counterexample.
• In particular, find $$y\in Y$$ such that no $$x\in X$$ will map to $$y\text{.}$$
An onto proof is really an existence proof: state your candidate $$x\text{,}$$ show $$x$$ satifies the required properties. In particular we show $$x\in X$$ and $$f(x)=y\text{.}$$
The function given in Figure 5.3.16 in not onto $$Y$$ since 2 is not mapped to by any value in $$X\text{.}$$
Let $$f:\mathbb{R}\rightarrow \mathbb{R}$$ be given by $$f(x)=3x+2\text{.}$$ Prove $$f$$ is onto $$\mathbb{R}\text{.}$$
Let $$y\in\mathbb{R}\text{.}$$
[Scratchwork: we want to find $$x$$ so that $$f(x)=y\text{.}$$ So we want $$3x+2=y\text{,}$$ or $$x=\frac{y-2}{3}\text{.}$$]
Let $$x=\frac{y-2}{3}\text{.}$$ Then since $$y\in \mathbb{R}, x\in\mathbb{R}\text{.}$$ Furthermore,
\begin{equation*} f(x)=f(\frac{y-2}{3})=3(\frac{y-2}{3})+2=y-2+2=y, \end{equation*}
which is what we wanted to show.
Let $$f:\mathbb{Z}\rightarrow \mathbb{Z}$$ be given by $$f(x)=3x+2\text{.}$$ Prove $$f$$ is NOT onto $$\mathbb{Z}\text{.}$$
Let $$y\in\mathbb{Z}\text{.}$$
We saw in the previous example $$x=\frac{y-2}{3}\text{.}$$ But $$x$$ is not necessarily in $$\mathbb{Z}\text{.}$$ So for our counterexample, let $$y=1\text{.}$$ Then we would need $$x=\frac{-1}{3}\notin \mathbb{Z}\text{.}$$
Hence, no element in $$\mathbb{Z}$$ will map to $$y=1\text{.}$$ Therefore, $$f$$ is not onto $$\mathbb{Z}\text{.}$$
Let $$f:\mathbb{R}\rightarrow \mathbb{R}$$ be given by $$f(x)=x^2-1\text{.}$$ Prove or disprove $$f$$ is onto $$\mathbb{R}\text{.}$$
Let $$y=-2\text{.}$$ Then if $$f$$ is onto $$\mathbb{R}\text{,}$$ we could find $$x$$ with $$f(x)=-2\text{.}$$
But if $$f(x)=-2\text{,}$$ then $$x^2-1=-2\text{,}$$ or $$x^2=-1\text{.}$$ We know there are no real solutions to this equation. Hence no element in $$\mathbb{R}$$ will map to $$y=-2\text{.}$$ Therefore, $$f$$ is not onto $$\mathbb{R}\text{.}$$

### Activity5.3.3.Multiplication in the Reals.

Define $$f:\mathbb{R}\rightarrow\mathbb{R}$$ by $$f(x)=5x\text{.}$$

#### (a)

Prove or disprove $$f$$ is one-to-one.

#### (b)

Prove or disprove $$f$$ is onto $$\mathbb{R}\text{.}$$

### Activity5.3.4.Multiplication in the Integers.

Define $$f:\mathbb{Z}\rightarrow\mathbb{Z}$$ by $$f(n)=5n\text{.}$$

#### (a)

Prove or disprove $$f$$ is one-to-one.

#### (b)

Prove or disprove $$f$$ is onto $$\mathbb{Z}\text{.}$$

### Activity5.3.5.Remainders.

Define $$g:\mathbb{Z}\rightarrow\{0, 1, 2\}$$ by $$g(n)=r$$ where $$r$$ is the remainder when $$n$$ is divided by 3.

#### (a)

Prove or disprove $$g$$ is one-to-one.

#### (b)

Prove or disprove $$g$$ is onto $$\{0, 1, 2\}\text{.}$$

### Activity5.3.6.Subtraction.

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

#### (a)

Prove or disprove $$h$$ is one-to-one.

#### (b)

Prove or disprove $$h$$ is onto $$\mathbb{Z}\text{.}$$

### Definition5.3.20.

A function $$f:X\rightarrow Y$$ is a one-to-one correspondence or bijection if $$f$$ is one-to-one and onto $$Y\text{.}$$
We showed in the above examples that $$f:\mathbb{R}\rightarrow\mathbb{R}$$ given by $$f(x)=3x+2$$ is one-to-one and onto $$\mathbb{R}\text{.}$$ Thus, it is an example of a bijection.
If it exists, we say $$f^{-1}$$ is the inverse of $$f\text{.}$$
Since $$f:\mathbb{R}\rightarrow\mathbb{R}$$ given by $$f(x)=3x+2$$ is one-to-one and onto, it has an inverse. We can find the inverse as we did in calculus.
Let $$y=3x+2\text{,}$$ solve for $$x\text{.}$$
We get $$x=\frac{y-2}{3}\text{.}$$ Thus $$f^{-1}(x)=\frac{x-2}{3}\text{.}$$
Show $$f^{-1}$$ is one-to-one: assume $$f^{-1}(y_1)=f^{-1}(y_2)\text{.}$$ Then $$f^{-1}(y_1)=f^{-1}(y_2)=x$$ for some $$x\in X\text{.}$$ Thus, $$f(x)=y_1$$ and $$f(x)=y_2\text{.}$$ Since $$f$$ is a function, $$y_1=y_2\text{.}$$
Show $$f^{-1}$$ is onto $$X\text{.}$$ Let $$x\in X\text{.}$$ Then there exists $$y\in Y$$ such that $$f(x)=y$$ since $$f$$ is a function from $$X\text{.}$$ Now, $$f^{-1}(y)=x\text{.}$$ Therefore, there exists $$y\in Y$$ such that $$f^{-1}(y)=x\text{.}$$

### ExercisesExercises

#### 1.

Let $$X=\{1, 5, 9\}$$ and $$Y=\{3, 4, 7\}\text{.}$$
1. Define $$f:X\rightarrow Y$$ by specifying that $$f(1)=4, f(5)=7, f(9)=4\text{.}$$
Is $$f$$ one-to-one? Is $$f$$ onto? Explain your answers.
2. Define $$g:X\rightarrow Y$$ by specifying that $$g(1)=7, g(5)=3, g(9)=4\text{.}$$
Is $$g$$ one-to-one? Is $$g$$ onto? Explain your answers.

#### 2.

Let $$X=\{1, 2, 3\}\text{,}$$ $$Y=\{1, 2, 3, 4\}$$ and $$Z=\{1, 2\}\text{.}$$
1. Define a function $$f:X\rightarrow Y$$ that is one-to-one but not onto.
2. Define a function $$g:X\rightarrow Z$$ that is onto but not one-to-one.
3. Define a function $$h:X\rightarrow X$$ that is neither one-to-one nor onto.
4. Define a function $$k:X\rightarrow X$$ that is one-to-one and onto, but is not the identity function (does not send every element to itself).

#### 3.

Let $$f$$ be a function from the integers to the even integers given by $$f(a)=2a\text{.}$$
1. Prove $$f$$ is one-to-one.
2. Prove $$f$$ is onto.

#### 4.

Define $$f:\mathbb{Z}\rightarrow\mathbb{Z}$$ by $$f(n)=4n-5\text{.}$$
1. Prove or disprove $$f$$ is one-to-one.
2. Prove or disprove $$f$$ is onto $$\mathbb{Z}\text{.}$$

#### 5.

Define $$g:\mathbb{R}\rightarrow\mathbb{R}$$ by $$f(x)=4x-5\text{.}$$
1. Prove or disprove $$g$$ is one-to-one.
2. Prove or disprove $$g$$ is onto $$\mathbb{R}\text{.}$$

#### 6.

Let $$A={\mathbb R}-\{-1\}\text{.}$$ Define $$f:A\rightarrow {\mathbb R}$$ by
\begin{equation*} f(a)={2a\over a+1}. \end{equation*}
Prove $$f$$ is one-to-one but not onto.

#### 7.

Define $$F:{\cal P}(\{a, b, c\})\rightarrow\mathbb{Z}$$ by
$$F(A)=$$ the number of elements in $$A\text{.}$$
1. Prove or disprove $$F$$ is one-to-one.
2. Prove or disprove $$F$$ is onto $$\mathbb{Z}\text{.}$$

#### 8.

Let $$f:{\mathbb Z}\times{\mathbb Z}\rightarrow{\mathbb Z}$$ be given by $$f(a, b)=a\text{.}$$
1. Prove or disprove $$f$$ is one-to-one.
2. Prove or disprove $$f$$ is onto.
Note: this map is called a projection.

#### 9.

Let $$f:{\mathbb Z}\rightarrow{\mathbb Z}\times{\mathbb Z}$$ be given by $$f(a) =(a, a)\text{.}$$
1. Prove or disprove $$f$$ is one-to-one.
2. Prove or disprove $$f$$ is onto.
Note: this map is called an embedding.

#### 10.

Define $$G:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}\times\mathbb{R}$$ by
$$G(x, y)=(2y, -x)\text{.}$$
1. Prove or disprove $$G$$ is one-to-one.
2. Prove or disprove $$G$$ is onto $$\mathbb{R}\times\mathbb{R}\text{.}$$

#### 11.

Define $$H:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}\times\mathbb{R}$$ by
$$H(x, y)=(x+1, 2-y)\text{.}$$
1. Prove or disprove $$H$$ is one-to-one.
2. Prove or disprove $$H$$ is onto $$\mathbb{R}\times\mathbb{R}\text{.}$$

#### 12.

Let $$f:{\mathbb Q}\times{\mathbb Q}\rightarrow{\mathbb Q}\times{\mathbb Q}$$ be given by $$f(a, b) =(2a, a+b)\text{.}$$
1. Prove or disprove $$f$$ is one-to-one.
2. Prove or disprove $$f$$ is onto.