# Discrete Mathematics: An Active Approach to Mathematical Reasoning

## Section7.2One-to-One, Onto, Inverse Functions

In this section 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.

### Definition7.2.1.

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

### Example7.2.2.Arrow Diagram: Not One-to-One.

The function given in Figure 7.2.3 in not one-to-one since $$c$$ and $$d$$ both map to the same value in $$Y\text{.}$$

### Example7.2.4.Proving One-to-One.

Let $$f:\mathbb{R}\rightarrow \mathbb{R}$$ be given by $$f(x)=3x+2\text{.}$$ Prove $$f$$ is one-to-one.

#### Proof.

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.

### Example7.2.5.Disproving One-to-One.

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

### Definition7.2.6.

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 of $$f\text{.}$$

### Proving a Function is 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{.}$$

### Example7.2.7.Arrow Diagram: Not Onto.

The function given in Figure 7.2.8 in not onto $$Y$$ since 2 is not mapped to by any value in $$X\text{.}$$

### Example7.2.9.Proving Onto.

Let $$f:\mathbb{R}\rightarrow \mathbb{R}$$ be given by $$f(x)=3x+2\text{.}$$ Prove $$f$$ is onto $$\mathbb{R}\text{.}$$

#### Proof.

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.

### Example7.2.10.Disproving Onto.

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

### Example7.2.11.Prove or Disprove Onto.

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

### Activity7.2.1.

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

### Activity7.2.2.

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

### Activity7.2.3.

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

### Activity7.2.4.

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

### Activity7.2.5.

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

#### (a)

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

#### (b)

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

### Definition7.2.12.

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 one-to-one correspondence.
If it exists, we say $$f^{-1}$$ is the inverse of $$f\text{.}$$

### Example7.2.14.Inverse Function.

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

### Proof.

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

#### 1.

True or false: $$f:\mathbb{R}\rightarrow \mathbb{R}, f(x)=5x-2$$ is one-to-one.
• True.

• False.

#### 2.

True or false: $$f:\mathbb{R}\rightarrow \mathbb{R}, f(x)=5x-2$$ is onto $$\mathbb{R}\text{.}$$
• True.

• False.

#### 3.

True or false: $$f:\mathbb{Z}\rightarrow \mathbb{Z}, f(x)=5x-2$$ is one-to-one.
• True.

• False.

#### 4.

True or false: $$f:\mathbb{Z}\rightarrow \mathbb{Z}, f(x)=5x-2$$ is onto $$\mathbb{Z}\text{.}$$
• True.

• False.

#### 5.

True or false: $$f:\mathbb{R}\rightarrow \mathbb{R}, f(x)=x^3-3$$ is one-to-one.
• True.

• False.

#### 6.

True or false: $$f:\mathbb{R}\rightarrow \mathbb{R}, f(x)=x^3-3$$ is onto $$\mathbb{R}\text{.}$$
• True.

• False.

#### 7.

True or false: $$f:\mathbb{Z}\rightarrow \mathbb{Z}, f(x)=x^3-3$$ is one-to-one.
• True.

• False.

#### 8.

True or false: $$f:\mathbb{Z}\rightarrow \mathbb{Z}, f(x)=x^3-3$$ is onto $$\mathbb{Z}\text{.}$$
• True.

• False.

#### 9.

True or false: $$f:\mathbb{Z}\times\mathbb{Z}\rightarrow \mathbb{Z}, f(x, y)=x$$ is one-to-one.
• True.

• False.

#### 10.

True or false: $$f:\mathbb{Z}\times\mathbb{Z}\rightarrow \mathbb{Z}, f(x, y)=x$$ is onto $$\mathbb{Z}\text{.}$$
• True.

• False.

#### 11.

True or false: $$f:\mathbb{Z}\times\mathbb{Z}\rightarrow \mathbb{Z}\times\mathbb{Z}, f(x, y)=(y, x)$$ is one-to-one.
• True.

• False.

#### 12.

True or false: $$f:\mathbb{Z}\times\mathbb{Z}\rightarrow \mathbb{Z}\times\mathbb{Z}, f(x, y)=(y, x)$$ is onto $$\mathbb{Z}\times\mathbb{Z}\text{.}$$
• True.

• False.

### ExercisesExercises

#### 1.

All but two of the following are correct ways to express the fact that a function $$f$$ is onto. Find the two that are incorrect.
1. $$f$$ is onto if and only if every element in its codomain is the image of some element in its domain.
2. $$f$$ is onto if and only if every element in its domain has a corresponding image in its codomain.
3. $$f$$ is onto if and only if $$\forall y\in Y, \exists x\in X$$ such that $$f(x)=y\text{.}$$
4. $$f$$ is onto if and only if $$\forall x\in X, \exists y\in Y$$ such that $$f(x)=y\text{.}$$
5. $$f$$ is onto if and only if the range of $$f$$ is the same as the codomain of $$f\text{.}$$

#### 2.

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.

#### 3.

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.

#### 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 $$g(x)=4x-5\text{.}$$
1. Prove or disprove $$g$$ is one-to-one.
2. Prove or disprove $$g$$ is onto $$\mathbb{R}\text{.}$$

#### 6.

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

#### 7.

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

#### 8.

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{.}$$
You have attempted of activities on this page.