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

Example5.5

If \(A = \{ x, y \}\text{,}\) \(B = \{ 1, 2, 3 \}\text{,}\) and \(C = \emptyset\text{,}\) then \(A \times B\) is the set

\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.

Example5.7

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.

Example5.8

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

Example5.10

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).

Example5.11

Let \(f(x) = x^2\) and \(g(x) = 2x + 5\text{.}\) Then

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.

Example5.14

Suppose that \(S = \{ 1,2,3 \}\text{.}\) Define a map \(\pi :S\rightarrow S\) by

(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,

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

Example5.16

The function \(f(x) = x^3\) has inverse \(f^{-1}(x) = \sqrt[3]{x}\) by Example 5.12.

Example5.17

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

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