Processing math: 100%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

7.3: Function Composition

( \newcommand{\kernel}{\mathrm{null}\,}\)

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.

Function Equality

Definition 7.3.1: Equality of Functions

Let f,g:AB; 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 xA.

Two functions that have different domains cannot be equal. For example, f:ZZ defined by f(x)=x2 and g:RR defined by g(x)=x2 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}{0,1,2} is defined by h(x)=|x| and k:{1,0,1,2}{0,1,2} is defined by k(x)=x33+x2+x3 appear to be very different functions. However, they are equal because h(x)=k(x) for x=1,0,1, and 2.

Function Composition

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

Definition 7.3.2: Composition of Functions

Let f:AB and g:BC. Then the composition of f followed by g, written gf, is a function from A into C defined by (gf)(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 gf is f. On the other hand, for relations, the composition rs is read from left to right, so that the first relation is r.

Example 7.3.1: A Basic Example

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

Let f:RR be defined by f(x)=x3 and let g:RR be defined by g(x)=3x+1. Then, since

(gf)(x)=g(f(x))=g(x3)=3x3+1

we have gf:RR is defined by (gf)(x)=3x3+1. Here fg is also defined and fg:RR is defined by (fg)(x)=(3x+1)3 . Moreover, since 3x3+1(3x+1)3 for at least one real number, gffg. 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.

Theorem 7.3.1: Function Composition is Associative

If f:AB, g:BC, and h:CD, then h(gf)=(hg)f.

Proof

Note: In order to prove that two functions are equal, we must use the definition of equality of functions. Assuming that the functions have the same domain, they are equal if, for each domain element, the images of that element under the two functions are equal.

We wish to prove that (h(gf))(x)=((hg)f)(x) for all xA, which is the domain of both functions.

(h(gf))(x)=h((gf)(x)) by the definition of composition=h(g(f(x))) by the definition of composition

Similarly,

((hg)f)(x)=(hg)(f(x)) by the definition of composition=h(g(f(x))) by the definition of composition.

Notice that no matter how the functions the expression hgf is grouped, the final image of any element of xA is h(g(f(x))) and so h(gf)=(hg)f.

If f is a function on a set A, then the compositions ff, fff, are valid, and we denote them as f2 , f3,. Repeated compositions of f with itself can be defined recursively. We will discuss this form of definition in detail in Section 8.1.

Definition 7.3.3: Powers of Functions

Let f:AA.

  • f1=f; that is, f1(a)=f(a), for aA.
  • For n1, fn+1=ffn; that is, fn+1(a)=f(fn(a)) for aA.

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

Theorem 7.3.2: The Composition of Injections is an Injection

If f:AB and g:BC are injections, then gf:AC is an injection.

Theorem 7.3.3: The Composition of Surjections is a Surjection

If f:AB and g:BC are surjections, then gf:AC is a surjection.

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 x1=1x=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×n zero matrix 0 and the n×n identity matrix I are such that for any n×n matrix A, A+0=0+A=A and AI=IA=A. Hence, an elegant way of defining the identity function under the operation of composition would be to imitate the above well-known facts.

Definition 7.3.4: Identity Function

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

Based on the definition of i, we can show that for all functions f:AA, fi=if=f.

Example 7.3.2: The Identity Function on {1,2,3}

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

Example 7.3.3: The Identity Function on R

The identity function on R is i:RR defined by i(x)=x.

Inverse 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 (Definition 5.2.3) to see that the following definition of the inverse function is a direct analogue of that definition.

Definition 7.3.5: Inverse of a Function on a Set

Let f:AA. If there exists a function g:AA such that gf=fg=i, then g is called the inverse of f and is denoted by f1 , 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:AA be such that f(a)=b. Then when it exists, f1 is a function from A to A such that f1(b)=a. Note that f1 “undoes” what f does.

Example 7.3.4: The 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 f1:AA is defined by f1(1)=3, f1(2)=1, and f1(3)=2.

Example 7.3.5: Inverse of a Real Function

If g:RR is defined by g(x)=x3 , then g1 is the function that undoes what g does. Since g cubes real numbers, g1 must be the “reverse” process, namely, takes cube roots. Therefore, g1:RR is defined by g1(x)=3x. We should show that g1g=i and gg1=i. We will do the first, and the reader is encouraged to do the second.

(g1g)(x)=g1(g(x)) Definition of composition=g1(x3)Definition of g=3x3Definition of g1=xDefinition of cube root=i(x)Definition of the identity function

Therefore, g1g=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?

Theorem 7.3.4: Bijections Have Inverses

Let f:AA. f1 exists if and only if f is a bijection; i. e. f is one-to-one and onto.

Proof

() In this half of the proof, assume that f1 exists and we must prove that f is one-to-one and onto. To do so, it is convenient for us to use the relation notation, where f(s)=t is equivalent to (s,t)f. To prove that f is one-to-one, assume that f(a)=f(b)=c. Alternatively, that means (a,c) and (b,c) are elements of f . We must show that a=b. Since (a,b),(c,b) f, (c,a) and (c,b) are in f1. By the fact that f1 is a function and c cannot have two images, a and b must be equal, so f is one-to-one.

Next, to prove that f is onto, observe that for f1 to be a function, it must use all of its domain, namely A. Let b be any element of A. Then b has an image under f1 , f1(b). Another way of writing this is (b,f1(b))f1, By the definition of the inverse, this is equivalent to (f1(b),b)f. Hence, b is in the range of f. Since b was chosen arbitrarily, this shows that the range of f must be all of A.

( ) Assume f is one-to-one and onto and we are to prove f1 exists. We leave this half of the proof to the reader.

Definition 7.3.6: Permutation

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?

Definition 7.3.7: Inverse of a Function (General Case)

Let f:AB, If there exists a function g:BA such that gf=iA and fg=iB , then g is called the inverse of f and is denoted by f1 , read “f inverse.”

Note the slightly more complicated condition for the inverse in this case because the domains of fg and gf 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.

Theorem 7.3.5: When Does a Function Have an Inverse?

Let f:AB. f1 exists if and only if f is a bijection.

Example 7.3.6: Another Inverse

Let A={1,2,3} and B={a,b,c}. Define f:AB by f(1)=a, f(2)=b, and f(3)=c. Then g:BA defined by g(a)=1, g(b)=2, and g(c)=3 is the inverse of f.

(gf)(1)=1(gf)(2)=2(gf)(3)=3} gf=iA and (fg)(a)=a(fg)(b)=b(fg)(c)=c} fg=iB

Exercises

Exercise 7.3.1

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

  1. Find gf.
  2. Does it make sense to discuss fg? If not, why not?
  3. Does f1 exist? Why?
  4. Does g1 exist? Why?
Answer
  1. gf:AC is defined by (gf)(k)={+ if k=1 or k=5 otherwise
  2. No, since the domain of f is not equal to the codomain of g.
  3. No, since f is not surjective.
  4. No, since g is not injective.

Exercise 7.3.2

Let A={1,2,3}. Definef:AA by f(1)=2, f(2)=1, and f(3)=3. Find f2, f3, f4 and f1.

Exercise 7.3.3

Let A={1,2,3}.

  1. List all permutations of A.
  2. Find the inverse and square of each of the permutations of part a, where the square of a permutation, f, is the composition ff.
  3. Show that the composition of any two permutations of A is a permutation of A.
  4. Prove that if A is any set where |A|=n, then the number of permutations of A is n!.
Answer
  1. The permutations of A are i,r1,r2,f1,f2, and f3, defined in Table 15.3.1.
  2. gg1g2iiir1r2r2r2r1r1f1f1if2f2if3f3i
  3. If f and g are permutations of A, then they are both injections and their composition, fg, is a injection, by Theorem 7.3.2. By Theorem 7.3.3, fg is also a surjection; therefore, fg is a bijection on A, a permutation.
  4. Proof by induction: Basis: (n=1). The number of permutations of A is one, the identity function, and 1! =1.

    Induction: Assume that the number of permutations on a set with n elements, n1, is n!. Furthermore, assume that |A|= n+1 and that A contains an element called σ. Let A=A{σ}. We can reduce the definition of a permutation, f, on A to two steps. First, we select any one of the n! permutations on A. (Note the use of the induction hypothesis.) Call it g. This permutation almost completely defines a permutation on A that we will call f. For all a in A, we start by defining f(a) to be g(a). We may be making some adjustments, but define it that way for now. Next, we select the image of σ, which can be done n+1 different ways, allowing for any value in A. To keep our function bijective, we must adjust f as follows: If we select f(σ)=yσ, then we must find the element, z, of A such that g(z)=y, and redefine the image of z to f(z)=σ. If we had selected f(σ)=σ, then there is no adjustment needed. By the rule of products, the number of ways that we can define f is n!(n+1)=(n+1)!

Exercise 7.3.4

Define s, u, and d, all functions on the integers, by s(n)=n2 , u(n)=n+1, and d(n)=n1. Determine:

  1. usd
  2. sud
  3. dsu

Exercise 7.3.5

Consider the following functions on the set of bit strings of length 4. In these definitions, addition is done modulo 2, so that 1+1=0. Which of these functions has an inverse? For those that have an inverse, what is it? For those that don't explain why.

  1. f1(b1b2b3b4)=b2b3b4b1
  2. f2(b1b2b3b4)=b4b3b2b1
  3. f3(b1b2b3b4)=(b1+b2)(b2+b3)(b3+b4)(b4+b1)
  4. f4(b1b2b3b4)=b1(b1+b2)(b1+b2+b3)(b1+b2+b3+b4)
Answer
  1. f1 has an inverse. f11=f31.
  2. f2 has an inverse. f12=f2.
  3. f3 does not have an inverse. One way to verify this is to note that f3 is not one-to-one because f3(0000)=0000=f3(1111).
  4. f4 has an inverse. f14=f34.

Exercise 7.3.6: Inverse Images

If f is any function from A into B, we can describe the inverse image as a function from B into P(A), which is also commonly denoted f1. If bB, f1(b)={aAf(a)=b}. If f does have an inverse, the inverse image of b is {f1(b)}.

  1. Let g:RR be defined by g(x)=x2. What are g1(4), g1(0) and g1(1)?
  2. If r:RZ, where r(x)=x, what is r1(1)?

Exercise 7.3.7

Let f, g, and h all be functions from Z into Z defined by f(n)=n+5, g(n)=n2, and h(n)=n2. Define:

  1. fg
  2. f3
  3. fh
Answer
  1. fg(n)=n+3
  2. f3(n)=n+15
  3. fh(n)=n2+5

Exercise 7.3.8

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

  1. Which of these functions are one-to-one?
  2. Which of these functions are onto?
  3. Express in simplest terms the compositions fg, gf, gh, hg, and h2.

Exercise 7.3.9

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

Hint

You have seen a similar proof in matrix algebra.

Exercise 7.3.10

For the real matrix A=(abcd), det(A)=adbc.

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

Let B=(π(a)π(b)π(c)π(d)). How many permutations of π leave the determinant of A invariant, that is, detA=detB?

Exercise 7.3.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

If f:AB and f has an inverse, then that inverse is unique.

Proof: Suppose that g and h are both inverses of f, both having domain B and codomain A.

g=giB=g(fh)=(gf)h=iAh=hg=h

Exercise 7.3.12

Let f and g be functions whose inverses exist. Prove that (fg)1=g1f1.

Hint

See Exercise 5.4.3 of Section 5.4.

Exercise 7.3.13

Prove Theorem 7.3.2 and Theorem 7.3.3.

Answer

Let x,x be elements of A such that gf(x)=gf(x); that is, g(f(x))=g(f(x)). Since g is injective, f(x)=f(x) and since f is injective, x=x.

Let x be an element of C. We must show that there exists an element of A whose image under gf is x. Since g is surjective, there exists an element of B, y, such that g(y)=x. Also, since f is a surjection, there exists an element of A, z, such that f(z)=y, gf(z)=g(f(z))=g(y)=x.

Exercise 7.3.14

Prove the second half of Theorem 7.3.4.

Exercise 7.3.15

Prove by induction that if n2 and f1, f2,,fn are invertible functions on some nonempty set A, then (f1f2fn)1=f1nf12f11. The basis has been taken care of in Exercise 7.3.12.

Answer

Basis: (n=2): (f1f2)1=f21f12 by Exercise 7.3.12.

Induction: Assume n2 and

(f1f2fn)1=fn1f21f11

and consider (f1f2fn+1)1.

(f1f2fn+1)1=((f1f2fn)fn+1)1=fn+11(f1f2fn)1 by the basis=fn+11(fn1f21f11) by the induction hypothesis=fn+11f21f11.

Exercise 7.3.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.

Exercise 7.3.17

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

Exercise 7.3.18

Based on the definition of the identity function, show that for all functions f:AA, fi=if=f.


This page titled 7.3: Function Composition is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Al Doerr & Ken Levasseur via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?