You have probably encountered functions before. In introductory calculus, for instance, you typically deal with functions from \(\R\) to \(\R\) (e.g., the function \(f(x)=x^2\)). More generally, functions “send” elements of one set to elements of another set; these sets may or may not be sets of real numbers. We provide below a “good enough for government work” definition of a function.

#####
Definition1.2.1

A *function* \(f\) from a set \(S\) to a set \(T\) is a “rule” that assigns to each element \(s\) in \(S\) a unique element \(f(s)\) in \(T\text{;}\) the element \(f(s)\) is called the *image of \(s\) under \(f\)*. If \(f\) is a function from \(S\) to \(T\text{,}\) we write \(f: S \to T\text{,}\) and call \(S\) the *domain* of \(f\) and \(T\) the *codomain* of \(f\text{.}\) The *range* of \(f\) is

\begin{equation*}
f(S)=\{f(s) \in T : s \in S\} \subseteq T.
\end{equation*}
More generally, if \(U \subseteq S\text{,}\) the *image of \(U\) in \(T\) under \(f\)* is

\begin{equation*}
f(U)=\{f(u)\in T : u\in U\}.
\end{equation*}
If \(V\subseteq T\text{,}\) the *preimage of \(V\) in \(S\) under \(f\)* is the set

\begin{equation*}
f^{\leftarrow}(V)=\{s\in S: f(s)\in V\}.
\end{equation*}
#####
Example1.2.2

Consider the function \(f: \Z \to \R\) defined by \(f(x)=x^2\text{.}\) The domain of \(f\) is \(\Z\) and the codomain of \(f\) is \(\R\text{;}\) the range of \(f\) is \(\{x^2\,:\,x\in \Z\}=\{0,1,4,9,\ldots\}\text{.}\) The image of \(\{-2,-1,1,2\}\) under \(f\) is the two-element set \(\{1,4\} \subseteq
\R\text{,}\) and the preimage of \(\{4,25,\pi\}\) under \(f\) is the set \(\{\pm 2, \pm 5\}\text{.}\) (Do you see why \(\pm \sqrt{\pi}\) are not in this preimage?) What is the preimage of just \(\{\pi\}\) under \(f\text{?}\)

The following definitions will be very important in our future work.

#####
Definition1.2.3

Let \(S\) and \(T\) be sets, and \(f:S\to T\text{.}\)

Function \(f\) is *one-to-one* (1-1) if whenever \(s_1, s_2\in S\) with \(f(s_1)=f(s_2)\text{,}\) we have \(s_1=s_2\text{.}\) Equivalently, \(f\) is one-to-one if whenever \(s_1\neq s_2 \in S\text{,}\) then \(f(s_1)\neq f(s_2) \in T\text{.}\)

Function \(f\) is *onto* if for every \(t\in T\text{,}\) there exists an element \(s\in S\) such that \(f(s)=t\text{.}\) Equivalently, \(f\) is onto if \(f(S)=T\text{.}\)

Function \(f\) is a *bijection* if it is both one-to-one and onto.

#####
Example1.2.5

Consider the function \(f: \R^* \to \R^+\) defined by \(f(x)=x^2\text{.}\) Function \(f\) is *not* one-to-one: indeed, \(-1\) and \(1\) are in \(\R^*\) with \(f(-1)=1=f(1)\) in \(\R^+\text{.}\) However, \(f\) *is* onto: indeed, let \(t\in \R^+\text{.}\) Then \(\sqrt{t} \in \R^*\) with \(t=f(\sqrt{t})\text{,}\) so we're done.

#####
Example1.2.6

Consider the function \(f: \Z^+ \to \R\) defined by \(f(x)=x/2\text{.}\) Function \(f\) *is* one-to-one: indeed, let \(s_1, s_2 \in \Z^+\) with \(f(s_1)=f(s_2)\text{.}\) Then \(s_1/2=f(s_1)=f(s_2)=s_2/2\text{;}\) multiplying both sides of the equation \(s_1/2=s_2/2\) by 2, we obtain \(s_1=s_2\text{.}\) However, \(f\) is *not* onto: for example, \(\pi\in \R\) but there is no positive integer \(s\) for which \(f(s)=s/2=\pi\text{.}\)

Recall that we can combine certain functions using *composition*:

#####
Definition1.2.7

If \(f:S\to T\) and \(g:T\to U\text{,}\) then the *composition of \(f\) and \(g\)* is the function \(g\circ f: S\to U\) defined by

\begin{equation*}
(g\circ f)(s)=g(f(s))
\end{equation*}
for all \(s\in S\text{.}\) (More generally, you can *compose* functions \(f:S\to T\) and \(g:R\to U\) to form \(g\circ f:S\to U\text{,}\) as long as \(f(S)\subseteq R\text{.}\)) Also recall that given any set \(S\text{,}\) the *identity function on \(S\)* is the function \(1_S: S\to S\) defined by \(1_S(s)=s\) for every \(s\in S\text{.}\)

#####
Definition1.2.8

Let \(f\) be a function from \(S\) to \(T\text{.}\) A function \(g\) from \(T\) to \(S\) is an *inverse* of \(f\) if \(g\circ f\) and \(f\circ g\) are the identity functions on \(S\) and \(T\text{,}\) respectively; that is, if for all \(s\in S\) and \(t\in
T\text{,}\) \(g(f(s))=s\) and \(f(g(t))=t\text{.}\)

We say a function is *invertible* if it has an inverse.

We have the following useful theorems.

#####
Theorem1.2.9

Function \(f:S\to T\) is invertible if and only if \(f\) is a bijection.

##### Proof

Suppose \(f\) has inverse \(g\text{.}\) Let \(t\in T\text{.}\) Then \(f(g(t))=t\text{,}\) so \(f\) is onto. Next, suppose \(s_1,s_2\in S\) with \(f(s_1)=f(s_2)\text{.}\) Then

\begin{equation*}
s_1=g(f(s_1))=g(f(s_2))=s_2,
\end{equation*}
so \(f\)is one-to-one.

Conversely, suppose \(f\) is a bijection. Then for every \(t\in T\text{,}\) there exists a unique element \(s_t\in S\) such that \(f(s_t)=t\text{.}\) It is then straighforward to show that the function \(g:T\to S\) defined by

\begin{equation*}
g(t)=t_s \text{ for every }t\in T
\end{equation*}
is an inverse of \(f\text{.}\)

#####
Theorem1.2.10

Let \(f:S\to T\) be invertible. Then the inverse of \(f\) is unique; we denote the unique inverse of \(f\) by \(f^{-1}\text{.}\)

##### Proof

Suppose \(f\) has inverses \(g\) and \(h\text{.}\) Then for every \(t\in T,\) \(f(g(t))=t=f(h(t))\text{.}\) But since \(f\) is invertible, it's one-to-one, so we must have \(g(t)=h(t)\) for every \(t\in T\text{.}\) Thus, \(g=h\text{,}\) and so \(f\) cannot have two or more distinct inverses.

#####
Theorem1.2.11

Let \(f:S\to T\) and \(g:T\to U\) be functions. If \(f\) and \(g\) are both 1-1 [resp., onto], then \(g\circ f: S\to U\) is 1-1 [resp., onto]. It follows that if \(f\) and \(g\) are both bijections, then \(g\circ f: S\to U\) is a bijection.

##### Proof

Assume \(f\) and \(g\) are 1-1. Let \(s_1, s_2\in S\) with \((g\circ f)(s_1)=(g\circ f)(s_2)\text{.}\) Then \(g(f(s_1))=g(f(s_2))\text{;}\) since \(g\) is one-to-one, this shows that \(f(s_1)=f(s_2)\text{.}\) Then since \(f\) is one-to-one, we must have \(s_1=s_2\text{.}\) Thus, \(g\circ f\) is one-to-one.

The proof that \(g\circ f\) is onto if \(f\) and \(g\) are onto is left as an exercise for the reader.