Skip to main content
\(\def\Z{\mathbb{Z}} \def\zn{\mathbb{Z}_n} \def\znc{\mathbb{Z}_n^\times} \def\R{\mathbb{R}} \def\Q{\mathbb{Q}} \def\C{\mathbb{C}} \def\N{\mathbb{N}} \def\M{\mathbb{M}} \def\G{\mathcal{G}} \def\0{\mathbf 0} \def\Gdot{\langle G, \cdot\,\rangle} \def\phibar{\overline{\phi}} \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\Ker}{Ker} \def\siml{\sim_L} \def\simr{\sim_R} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)


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.


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*}

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.


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

  1. 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{.}\)

  2. 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{.}\)

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


We will often have to show functions are one-to-one or onto. Given a function \(f:S\to T\text{,}\) the following methods are recommended.

  • To prove that \(f\) is one-to-one: Let \(s_1,s_2 \in S\) with \(f(s_1)=f(s_2)\) and prove that then \(s_1=s_2\text{.}\)

    Note: It is not sufficient to prove that if \(s_1=s_2\) in \(S\) then \(f(s_1)=f(s_2)\text{;}\) that holds true for ANY function from \(S\) to \(T\text{!}\) Be careful to assume and prove the correct facts.

  • To prove that \(f\) is not one-to-one: Identify two elements \(s_1 \neq s_2\) of \(S\) such that \(f(s_1)=f(s_2)\text{.}\)

  • To prove that \(f\) is onto: Let \(t\in T\) and prove that there exists an element \(s\in S\) with \(f(s)=t\text{.}\)

    Note: It is not sufficient to prove that if \(s\in S\) then \(f(s)\) is in \(T\text{;}\) that holds true for ANY function from \(S\) to \(T\text{!}\) Again, be careful to assume and prove the correct facts.

  • To prove that \(f\) is not onto: Identify an element \(t\in T\) for which there is no \(s\in S\) with \(f(s)=t\text{.}\)


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.


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:


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{.}\)


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.