$\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{\nmid} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\transpose}{\text{t}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \setcounter{chapter}{-1}$

## Subsection5.2Cartesian Products and Mappings

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

###### 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

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

###### Example5.12

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*}
###### Example5.13

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.

###### Example5.14

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{.}$

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{.}$

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

and

\begin{equation*} f^{-1}(f(x)) = f^{-1}(\ln x) = e^{\ln x} = x \end{equation*}

whenever composition makes sense.

###### Example5.18

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{.}$

###### Example5.19

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.

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{.}$