Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \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}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section7.3Function Composition

Now that we have a good understanding of what a function is, our next step is to consider an important operation on functions. Our purpose is not to develop the algebra of functions as completely as we did for the algebras of logic, matrices, and sets, but the reader should be aware of the similarities between the algebra of functions and that of matrices. We first define equality of functions.

Subsection7.3.1Function Equality

Definition7.3.1Equality of Functions

Let \(f, g:A \rightarrow B\); that is, let \(f\) and \(g\) both be functions from \(A\) into \(B\). Then \(f\) is equal to \(g\) (denoted \(f=g\)) if and only if \(f(x) = g(x)\) for all \(x \in A\).

Two functions that have different domains cannot be equal. For example, \(f: \mathbb{Z}\to \mathbb{Z}\) defined by \(f(x)=x^2\) and \(g: \mathbb{R}\to \mathbb{R}\) defined by \(g(x)=x^2\) are not equal even though the formula that defines them is the same.

On the other hand, it is not uncommon for two functions to be equal even though they are defined differently. For example consider the functions \(h\) and \( k\), where \(h: \{-1,0,1,2\}\to \{0,1,2\}\) is defined by \(h(x)=|x|\) and \(k: \{-1,0,1,2\}\to \{0,1,2\}\) is defined by \(k(x) = -\frac{x^3}{3}+x^2+\frac{x}{3}\) appear to be very different functions. However, they are equal because \(h(x)= k(x)\) for \(x = -1, 0, 1, \text{ and } 2\).

Subsection7.3.2Function Composition

One of the most important operations on functions is that of composition.

Definition7.3.2Composition of Functions.

Let \(f:A \rightarrow B\) and \(g:B \rightarrow C\). Then the composition of \(f\) followed by \(g\), written \(g\circ f\), is a function from \(A\) into \(C\) defined by \((g \circ f)(x) = g(f(x))\), which is read “\(g\) of \(f\) of \(x\).”

The reader should note that it is traditional to write the composition of functions from right to left. Thus, in the above definition, the first function performed in computing \(g \circ f\) is \(f\). On the other hand, for relations, the composition \(r s\) is read from left to right, so that the first relation is \(r\).

Example7.3.3A basic example

Let \(f:\{1, 2, 3\}\rightarrow \{a, b\}\) be defined by \(f(1) = a\), \(f(2) = a\), and \(f(3) = b\). Let \(g:\{a, b\} \rightarrow \{5, 6, 7\}\) be defined by \(g(a) = 5\) and \(g(b) = 7\). Then \(g\circ f: \{1, 2, 3\}\rightarrow \{5, 6, 7\}\) is defined by \((g\circ f)(1)= 5\), \((g\circ f)(2)= 5,\) and \((g\circ f)(3)= 7\). For example, \((g\circ f)(1)= g(f(l)) = g(a) = 5\). Note that \(f\circ g\) is not defined. Why?

Let \(f:\mathbb{R} \rightarrow \mathbb{R}\) be defined by \(f(x) = x^3\) and let \(g:\mathbb{R} \rightarrow \mathbb{R}\) be defined by \(g(x) = 3x+1\). Then, since \[(g\circ f)(x) = g(f(x)) = g\left(x^3\right) = 3x^3 + 1\] we have \(g\circ f: \mathbb{R} \rightarrow \mathbb{R}\) is defined by \((g\circ f)(x)= 3x^3 + 1\). Here \(f\circ g\) is also defined and \(f\circ g:\mathbb{R}\rightarrow \mathbb{R}\) is defined by \((f\circ g)(x)=(3x + 1)^3\) . Moreover, since \(3x ^3+ 1 \neq (3x + 1)^3\) for at least one real number, \(g\circ f \neq f\circ g\). Therefore, the commutative law is not true for functions under the operation of composition. However, the associative law is true for functions under the operation of composition.

Proof

If \(f\) is a function on a set \(A\), then the compositions \(f\circ f\), \(f\circ f\circ f, \dots \) are valid, and we denote them as \(f^2\) , \(f^3, \dots \). These repeated composition of \(f\) with itself can be defined recursively:

Definition7.3.5Powers of Functions

Let \(f: A\to A\).

  • \(f^1= f\); that is, \(f^1(a) = f(a)\), for \(a \in A\).

  • For \(n\geq 1\), \(f^{n+1}= f\circ f^n\); that is, \(f^{n+1}(a)=f\left( f^n(a)\right)\) for \(a \in A\).

Two useful theorems concerning composition are given below. The proofs are left for the exercises.

We would now like to define the concepts of identity and inverse for functions under composition. The motivation and descriptions of the definitions of these terms come from the definitions of the terms in the set of real numbers and for matrices. For real numbers, the numbers 0 and 1 play the unique role that \(x + 0 = 0 + x = x\) and \(x \cdot 1 = 1 \cdot x = x\) for any real number \(x\). 0 and 1 are the identity elements for the reals under the operations of addition and multiplication, respectively. Similarly, the \(n \times n\) zero matrix 0 and the \(n \times n\) identity matrix \(I\) are such that for any \(n \times n\) matrix \(A\), \(A + 0 = 0 + A=A\) and \(A I = I A = I\). Hence, an elegant way of defining the identity function under the operation of composition would be to imitate the above well-known facts.

Definition7.3.8Identity Function

For any set \(A\), the identity function on \(A\) is a function from \(A\) onto \(A\), denoted by \(i\) (or, more specifically, \(i_A\)) such that \(i(a) = a\) for all \(a\in A\).

Based on the definition of \(i\), we can show that for all functions \(f:A\to A\), \(f\circ i=i\circ f = f\).

Example7.3.9The identity function on \(\{1,2,3\}\)

If \(A = \{1, 2, 3\}\), then the identity function \(i:A \to A\) is defined by \(i(1) = 1\), \(i(2) = 2,\) and \(i(3)= 3\).

Example7.3.10The identity function on \(\mathbb{R}\)

The identity function on \(\mathbb{R}\) is \(i : \mathbb{R} \rightarrow \mathbb{R}\) defined by \(i(x) = x\).

Subsection7.3.3Inverse Functions

We will introduce the inverse of a function with a special case: the inverse of a function on a set. After you've taken the time to understand this concept, you can read about the inverse of a function from one set into another. The reader is encouraged to reread the definition of the inverse of a matrix in Section 5.2 (5.2.5) to see that the following definition of the inverse function is a direct analogue of that definition.

Definition7.3.11Inverse of a Function on a Set

Let \(f: A\rightarrow A\). If there exists a function \(g : A \rightarrow A\) such that \(g\circ f = f\circ g = i\), then \(g\) is called the inverse of \(f\) and is denoted by \(f^{-1}\) , read “\(f\) inverse.”

Notice that in the definition we refer to “the inverse” as opposed to “an inverse.” It can be proven that a function can never have more than one inverse (see exercises).

An alternate description of the inverse of a function, which can be proven from the definition, is as follows: Let \(f: A \rightarrow A\) be such that \(f(a) = b\). Then when it exists, \(f^{-1}\) is a function from \(A\) to \(A\) such that \(f^{-1}(b)=a\). Note that \(f^{-1}\) “undoes” what \(f\) does.

Example7.3.12The inverse of a function on \(\{1,2,3\}\)

Let \(A = \{1, 2, 3\}\) and let \(f\) be the function defined on \(A\) such that \(f(1) = 2\), \(f(2) = 3\), and \(f(3) = 1\). Then \(f^{-1} : A \rightarrow A\) is defined by \(f^{-1}(1) = 3\), \(f^{-1}(2) = 1\), and \(f^{-1}(3) = 2\).

Example7.3.13Inverse of a real function

If \(g : \mathbb{R} \rightarrow \mathbb{R}\) is defined by \(g(x) =x^3\) , then \(g^{-1}\) is the function that undoes what \(g\) does. Since \(g\) cubes real numbers, \(g^{-1}\) must be the “reverse” process, namely, takes cube roots. Therefore, \(g^{-1} : \mathbb{R} \rightarrow \mathbb{R}\) is defined by \(g^{-1}(x)=\sqrt[3]{x}\). We should show that \(g^{-1}\circ g = i\) and \(g\circ g^{-1}=i\). We will do the first, and the reader is encouraged to do the second. \begin{equation*} \begin{split} \left(g^{-1}\circ g\right)(x) &= g^{-1}(g(x)) \quad \textrm{ Definition of composition}\\ &= g^{-1}\left(x^3\right)\quad \text{Definition of } g\\ &=\sqrt[3]{x^3}\quad\textrm{Definition of } g^{-1}\\ & = x\quad\text{Definition of cube root}\\ &= i(x)\quad\text{Definition of the identity function} \end{split} \end{equation*} Therefore, \(g^{-1}\circ g = i\). Why?

The definition of the inverse of a function alludes to the fact that not all functions have inverses. How do we determine when the inverse of a function exists?

Proof
Definition7.3.15Permutation

A bijection of a set \(A\) into itself is called a permutation of \(A\).

Next, we will consider the functions for which the domain and codomain are not necessarily equal. How do we define the inverse in this case?

Definition7.3.16Inverse of a Function (General Case)

Let \(f:A \rightarrow B\), If there exists a function \(g:B \rightarrow A\) such that \(g \circ f = i_A\) and \(f\circ g = i_B\) , then \(g\) is called the inverse of \(f\) and is denoted by \(f^{-1}\) , read “\(f\) inverse.”

Note the slightly more complicated condition for the inverse in this case because the domains of \(f\circ g\) and \(g \circ f\) are different if \(A\) and \(B\) are different. The proof of the following theorem isn't really very different from the special case where \(A=B\).

Example7.3.18Another inverse

Let \(A =\{1,2, 3\}\) and \(B = \{a, b, c\}\). Define \(f:A \rightarrow B\) by \(f(1) = a\), \(f(2) = b\), and { }\(f(3) = c\). Then \(g: B \rightarrow A\) defined by \(g(a) = 1\), \(g(b) = 2\), and \(g(c) = 3\) is the inverse of \(f\). \[\left. \begin{array}{c} (g\circ f)(1)= 1 \\ (g\circ f)(2)=2 \\ (g\circ f)(3)=3 \\ \end{array} \right\}\Rightarrow \text{ }g\circ f = i_A \textrm{ and } \left. \begin{array}{c} (f\circ g)(a)=a \\ (f\circ g)(b)=b \\ (f\circ g)(c)=c \\ \end{array} \right\}\Rightarrow \text{ }f\circ g = i_B\]

Subsection7.3.4Exercises for Section 7.3

1

Let \(A = \{1,2, 3, 4, 5\}\), \(B = \{a, b, c, d, e,f\}\), and \(C = \{+, -\}\). Define \(f: A \to B\) by \(f(k)\) equal to the \(k^{th}\) letter in the alphabet, and define \(g : B \rightarrow C\) by \(g(\alpha ) = +\) if \(\alpha\) is a vowel and \(g(\alpha ) = -\) if \(\alpha\) is a consonant.

  1. Find \(g\circ f\).

  2. Does it make sense to discuss \(f\circ g\)? If not, why not?

  3. Does \(f^{-1}\) exist? Why?

  4. Does \(g^{-1}\) exist? Why?

Answer
2

Let \(A = \{1, 2, 3\}\). Define\(f:A\rightarrow A\) by \(f(1) = 2\), \(f(2) = 1\), and \(f(3) = 3\). Find \(f^2\) , \(f^3\) , \(f^4\) and \(f^{-1}\).

3

Let \(A = \{1, 2, 3\}\).

  1. List all permutations of \(A\).

  2. Find the inverse of each of the permutations of part a.

  3. Find the square of each of the permutations of part a.

  4. Show that the composition of any two permutations of \(A\) is a permutation of \( A\).

  5. Prove that if \(A\) be any set where the \(|A|=\text{\textit{$n$}}\), then the number of permutations of \(A\) is \(n!\).

Answer
4

Define \(s\), \(u\), and \(d\), all functions on the integers, by \(s(n) = n^2\) , \(u(n) = n + 1\), and \(d(n) = n-1\). Determine:

  1. \(u \circ s \circ d\)

  2. \(s \circ u\circ d\)

  3. \(d \circ s \circ u\)

5

Based on the definition of the identity function, show that for all functions \(f:A\to A\), \(f\circ i=i\circ f = f\).

6

Inverse images. If \(f\) is any function from \(A\) into \(B\), we can describe the inverse image as a function from \(B\) into \(\mathcal{P}(A)\), which is also commonly denoted \(f^{-1}\). If \(b \in B\), \(f^{-1}(b) = \{a \in A\mid f(a) = b\}\). If \(f\) does have an inverse, the inverse image of \(b\) is \(\left\{f^{-1}(b)\right\}\).

  1. Let \(g : \mathbb{R} \to \mathbb{R}\) be defined by \(g(x) = x^2\). What are \(g^{-1}(4)\), \(g^{-1}(0)\) and \(g^{-1}(-1)\)?

  2. If \(r: \mathbb{R}\to \mathbb{Z}\), where \(r(x) = \lceil x\rceil\), what is \(r^{-1}(1)\)?

7

Let \( f,\) \(g\), and \(h\) all be functions from \(\mathbb{Z}\) into \(\mathbb{Z}\) defined by \(f(n) = n + 5\), \(g(n) = n - 2,\) and \(h(n)=n^2\). Define:

  1. \(f\circ g\)

  2. \(f^3\)

  3. \(f\circ h\)

Answer
8

Define the following functions on the integers by \(f(k) = k + 1\), \(g(k) = 2k\), and \(h(k)=\lceil k/2\rceil\)

  1. Which of these functions are one-to-one?

  2. Which of these functions are onto?

  3. Express in simplest terms the compositions \(f\circ g\), \(g \circ f\), \(g \circ h\), \(h \circ g\), and \(h^2\) ,

9

Let \(A\) be a nonempty set. Prove that if \( f \) is a bijection on \(A\) and \(f \circ f=f\), then \(f\) is the identity function, \(i\)

Hint
10

For the real matrix \(A=\left( \begin{array}{cc} a & b \\ c & d \end{array} \right)\), \(\det(A)= a d-b c\).

Recall that a bijection from a set to itself is also referred to as a permutation of the set. Let \(\pi\) be a permutation of \(\{a,b,c,d\}\) such that \(a\) becomes \(\pi (a)\), \(b\) becomes \(\pi (b)\), etc.

Let \(B=\left( \begin{array}{cc} \pi(a)& \pi(b)\\ \pi(c)& \pi(d)\\ \end{array} \right)\). How many permutations of \(\pi\) leave the determinant of \(A\) invariant, that is, \(\det A = \det B\)?

11

State and prove a theorem on inverse functions analogous to the one that says that if a matrix has an inverse, that inverse is unique.

Answer
12

Let \(f\) and \(g\) be functions whose inverses exist. Prove that \((f\circ g)^{-1}= g^{-1}\circ f^{-1}\).

Hint
13

Prove Theorem 7.3.6 and Theorem 7.3.7.

Answer
15

Prove by induction that if \(n\geq 2\) and \(f_1\), \(f_2\) , \ldots , \(f_n\) are invertible functions on some nonempty set A, then { }\(\left( f_1\circ f_2\circ \cdots \circ f_n \right){}^{-1}= f_n^{-1}\circ \cdots \circ f_2^{-1}\circ f_1^{-1}\). The basis has been taken care of in Exercise 10.

Answer
16

  1. Our definition of cardinality states that two sets, \(A\) and \(B\), have the same cardinality if there exists a bijection between the two sets. Why does it not matter whether the bijection is from \(A\) into \(B\) or \(B\) into \(A\)?
  2. Prove that “has the same cardinality as” is an equivalence relation on sets.

17

Construct a table listing as many “Laws of Function Composition” as you can identify. Use previous lists of laws as a guide.