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.
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.
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{.}\)
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.
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{.}\)
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.
Theorem5.3.21.
If \(f:X\rightarrow Y\) is a bijection, then there exists a function \(f^{-1}:Y\rightarrow X\) such that
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{.}\)
Theorem5.3.23.
If \(f:X\rightarrow Y\) is one-to-one and onto \(Y\text{,}\) then \(f^{-1}:Y\rightarrow X\) is one-to-one and onto \(X\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{.}\)