Given sets \(A\) and \(B\text{,}\) we can define a new set \(A \times B\text{,}\) called the Cartesian product of \(A\) and \(B\text{,}\) as a set of ordered pairs. That is,
\begin{equation*} A \times B = \{ (a,b) : a \in A \text{ and } b \in B \}. \end{equation*}If \(A = \{ x, y \}\text{,}\) \(B = \{ 1, 2, 3 \}\text{,}\) and \(C = \emptyset\text{,}\) then \(A \times B\) is the set
\begin{equation*} \{ (x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3) \} \end{equation*}and
\begin{equation*} A \times C = \emptyset. \end{equation*}We define the Cartesian product of \(n\) sets to be
\begin{equation*} A_1 \times \cdots \times A_n = \{ (a_1, \ldots, a_n): a_i \in A_i \text{ for } i = 1, \ldots, n \}. \end{equation*}If \(A = A_1 = A_2 = \cdots = A_n\text{,}\) we often write \(A^n\) for \(A \times \cdots \times A\) (where \(A\) would be written \(n\) times). For example, the set \({\mathbb R}^3\) consists of all of 3-tuples of real numbers.
Subsets of \(A \times B\) are called relations. We will define a mapping or function \(f \subset A \times B\) from a set \(A\) to a set \(B\) to be the special type of relation where \((a, b) \in f\) if for every element \(a \in A\) there exists a unique element \(b \in B\text{.}\) Another way of saying this is that for every element in \(A\text{,}\) \(f\) assigns a unique element in \(B\text{.}\) We usually write \(f:A \rightarrow B\) or \(A \stackrel{f}{\rightarrow} B\text{.}\) Instead of writing down ordered pairs \((a,b) \in A \times B\text{,}\) we write \(f(a) = b\) or \(f : a \mapsto b\text{.}\) The set \(A\) is called the domain of \(f\) and
\begin{equation*} f(A) = \{ f(a) : a \in A \} \subset B \end{equation*}is called the range or image of \(f\text{.}\) We can think of the elements in the function's domain as input values and the elements in the function's range as output values.
Suppose \(A = \{1, 2, 3 \}\) and \(B = \{a, b, c \}\text{.}\) In Figure 5.6 we define relations \(f\) and \(g\) from \(A\) to \(B\text{.}\) The relation \(f\) is a mapping, but \(g\) is not because \(1 \in A\) is not assigned to a unique element in \(B\text{;}\) that is, \(g(1) = a\) and \(g(1) = b\text{.}\)
Given a function \(f : A \rightarrow B\text{,}\) it is often possible to write a list describing what the function does to each specific element in the domain. However, not all functions can be described in this manner. For example, the function \(f: {\mathbb R} \rightarrow {\mathbb R}\) that sends each real number to its cube is a mapping that must be described by writing \(f(x) = x^3\) or \(f:x \mapsto x^3\text{.}\)
Consider the relation \(f : {\mathbb Q} \rightarrow {\mathbb Z}\) given by \(f(p/q) = p\text{.}\) We know that \(1/2 = 2/4\text{,}\) but is \(f(1/2) = 1\) or \(2\text{?}\) This relation cannot be a mapping because it is not well-defined. A relation is well-defined if each element in the domain is assigned to a unique element in the range.
If \(f:A \rightarrow B\) is a map and the image of \(f\) is \(B\text{,}\) i.e., \(f(A) = B\text{,}\) then \(f\) is said to be onto or surjective. In other words, if there exists an \(a \in A\) for each \(b \in B\) such that \(f(a) = b\text{,}\) then \(f\) is onto. A map is one-to-one or injective if \(a_1 \neq a_2\) implies \(f(a_1) \neq f(a_2)\text{.}\) Equivalently, a function is one-to-one if \(f(a_1) = f(a_2)\) implies \(a_1 = a_2\text{.}\) A map that is both one-to-one and onto is called bijective.
Let \(f:{\mathbb Z} \rightarrow {\mathbb Q}\) be defined by \(f(n) = n/1\text{.}\) Then \(f\) is one-to-one but not onto. Define \(g : {\mathbb Q} \rightarrow {\mathbb Z}\) by \(g(p/q) = p\) where \(p/q\) is a rational number expressed in its lowest terms with a positive denominator. The function \(g\) is onto but not one-to-one.
Given two functions, we can construct a new function by using the range of the first function as the domain of the second function. Let \(f : A \rightarrow B\) and \(g : B \rightarrow C\) be mappings. Define a new map, the composition of \(f\) and \(g\) from \(A\) to \(C\text{,}\) by \((g \circ f)(x) = g(f(x))\text{.}\)
Consider the functions \(f: A \rightarrow B\) and \(g: B \rightarrow C\) that are defined in Figure 5.9 (top). The composition of these functions, \(g \circ f: A \rightarrow C\text{,}\) is defined in Figure 5.9 (bottom).
Let \(f(x) = x^2\) and \(g(x) = 2x + 5\text{.}\) Then
\begin{equation*} (f \circ g)(x) = f(g(x)) = (2x + 5)^2 = 4x^2 + 20x + 25 \end{equation*}and
\begin{equation*} (g \circ f)(x) = g(f(x)) = 2x^2 + 5. \end{equation*}In general, order makes a difference; that is, in most cases \(f \circ g \neq g \circ f\text{.}\)
Sometimes it is the case that \(f \circ g= g \circ f\text{.}\) Let \(f(x) = x^3\) and \(g(x) = \sqrt[3]{x}\text{.}\) Then
\begin{equation*} (f \circ g )(x) = f(g(x)) = f( \sqrt[3]{x}\, ) = (\sqrt[3]{x}\, )^3 = x \end{equation*}and
\begin{equation*} (g \circ f )(x) = g(f(x)) = g( x^3) = \sqrt[3]{ x^3} = x. \end{equation*}Given a \(2 \times 2\) matrix
\begin{equation*} A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}, \end{equation*}we can define a map \(T_A : {\mathbb R}^2 \rightarrow {\mathbb R}^2\) by
\begin{equation*} T_A (x,y) = (ax + by, cx +dy) \end{equation*}for \((x,y)\) in \({\mathbb R}^2\text{.}\) This is actually matrix multiplication; that is,
\begin{equation*} \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} ax + by \\ cx +dy \end{pmatrix}. \end{equation*}Maps from \({\mathbb R}^n\) to \({\mathbb R}^m\) given by matrices are called linear maps or linear transformations.
Suppose that \(S = \{ 1,2,3 \}\text{.}\) Define a map \(\pi :S\rightarrow S\) by
\begin{equation*} \pi( 1 ) = 2, \qquad \pi( 2 ) = 1, \qquad \pi( 3 ) = 3. \end{equation*}This is a bijective map. An alternative way to write \(\pi\) is
\begin{equation*} \begin{pmatrix} 1 & 2 & 3 \\ \pi(1) & \pi(2) & \pi(3) \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}. \end{equation*}For any set \(S\text{,}\) a one-to-one and onto mapping \(\pi : S \rightarrow S\) is called a permutation of \(S\text{.}\)
Let \(f : A \rightarrow B\text{,}\) \(g : B \rightarrow C\text{,}\) and \(h : C \rightarrow D\text{.}\) Then
The composition of mappings is associative; that is, \((h \circ g) \circ f = h \circ (g \circ f)\text{;}\)
If \(f\) and \(g\) are both one-to-one, then the mapping \(g \circ f\) is one-to-one;
If \(f\) and \(g\) are both onto, then the mapping \(g \circ f\) is onto;
If \(f\) and \(g\) are bijective, then so is \(g \circ f\text{.}\)
We will prove (1) and (3). Part (2) is left as an exercise. Part (4) follows directly from (2) and (3).
(1) We must show that
\begin{equation*} h \circ (g \circ f) = (h \circ g) \circ f. \end{equation*}For \(a \in A\) we have
\begin{align*} (h \circ (g \circ f))(a) & = h((g \circ f)(a))\\ & = h(g(f(a))) \\ & = (h \circ g)(f(a))\\ & = ((h \circ g) \circ f)(a). \end{align*}(3) Assume that \(f\) and \(g\) are both onto functions. Given \(c \in C\text{,}\) we must show that there exists an \(a \in A\) such that \((g \circ f)(a) = g(f(a)) = c\text{.}\) However, since \(g\) is onto, there is an element \(b \in B\) such that \(g(b) = c\text{.}\) Similarly, there is an \(a \in A\) such that \(f(a) = b\text{.}\) Accordingly,
\begin{equation*} (g \circ f)(a) = g(f(a)) = g(b) = c. \end{equation*}If \(S\) is any set, we will use \(id_S\) or \(id\) to denote the identity mapping from \(S\) to itself. Define this map by \(id(s) = s\) for all \(s \in S\text{.}\) A map \(g: B \rightarrow A\) is an inverse mapping of \(f: A \rightarrow B\) if \(g \circ f = id_A\) and \(f \circ g = id_B\text{;}\) in other words, the inverse function of a function simply “undoes” the function. A map is said to be invertible if it has an inverse. We usually write \(f^{-1}\) for the inverse of \(f\text{.}\)
The function \(f(x) = x^3\) has inverse \(f^{-1}(x) = \sqrt[3]{x}\) by Example 5.12.
The natural logarithm and the exponential functions, \(f(x) = \ln x\) and \(f^{-1}(x) = e^x\text{,}\) are inverses of each other provided that we are careful about choosing domains. Observe that
\begin{equation*} f(f^{-1}(x)) = f(e^x) = \ln e^x = x \end{equation*}and
\begin{equation*} f^{-1}(f(x)) = f^{-1}(\ln x) = e^{\ln x} = x \end{equation*}whenever composition makes sense.
Suppose that
\begin{equation*} A = \begin{pmatrix} 3 & 1 \\ 5 & 2 \end{pmatrix}. \end{equation*}Then \(A\) defines a map from \({\mathbb R}^2\) to \({\mathbb R}^2\) by
\begin{equation*} T_A (x,y) = (3x + y, 5x + 2y). \end{equation*}We can find an inverse map of \(T_A\) by simply inverting the matrix \(A\text{;}\) that is, \(T_A^{-1} = T_{A^{-1}}\text{.}\) In this example,
\begin{equation*} A^{-1} = \begin{pmatrix} 2 & -1 \\ -5 & 3 \end{pmatrix}; \end{equation*}hence, the inverse map is given by
\begin{equation*} T_A^{-1} (x,y) = (2x - y, -5x + 3y). \end{equation*}It is easy to check that
\begin{equation*} T^{-1}_A \circ T_A (x,y) = T_A \circ T_A^{-1} (x,y) = (x,y). \end{equation*}Not every map has an inverse. If we consider the map
\begin{equation*} T_B (x,y) = (3x , 0 ) \end{equation*}given by the matrix
\begin{equation*} B = \begin{pmatrix} 3 & 0 \\ 0 & 0 \end{pmatrix}, \end{equation*}then an inverse map would have to be of the form
\begin{equation*} T_B^{-1} (x,y) = (ax + by, cx +dy) \end{equation*}and
\begin{equation*} (x,y) = T \circ T_B^{-1} (x,y) = (3ax + 3by, 0) \end{equation*}for all \(x\) and \(y\text{.}\) Clearly this is impossible because \(y\) might not be \(0\text{.}\)
Given the permutation
\begin{equation*} \pi = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \end{equation*}on \(S = \{ 1,2,3 \}\text{,}\) it is easy to see that the permutation defined by
\begin{equation*} \pi^{-1} = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} \end{equation*}is the inverse of \(\pi\text{.}\) In fact, any bijective mapping possesses an inverse, as we will see in the next theorem.
A mapping is invertible if and only if it is both one-to-one and onto.
Suppose first that \(f:A \rightarrow B\) is invertible with inverse \(g: B \rightarrow A\text{.}\) Then \(g \circ f = id_A\) is the identity map; that is, \(g(f(a)) = a\text{.}\) If \(a_1, a_2 \in A\) with \(f(a_1) = f(a_2)\text{,}\) then \(a_1 = g(f(a_1)) = g(f(a_2)) = a_2\text{.}\) Consequently, \(f\) is one-to-one. Now suppose that \(b \in B\text{.}\) To show that \(f\) is onto, it is necessary to find an \(a \in A\) such that \(f(a) = b\text{,}\) but \(f(g(b)) = b\) with \(g(b) \in A\text{.}\) Let \(a = g(b)\text{.}\)
Conversely, let \(f\) be bijective and let \(b \in B\text{.}\) Since \(f\) is onto, there exists an \(a \in A\) such that \(f(a) = b\text{.}\) Because \(f\) is one-to-one, \(a\) must be unique. Define \(g\) by letting \(g(b) = a\text{.}\) We have now constructed the inverse of \(f\text{.}\)
