EF Composition of functions

🔗

Section 10.4 Composition of functions

🔗

composition function: 🔗
a function $A \to C$ created from given functions $f : A \to B$ and $g : B \to C$ by $a \mapsto g (f (a))$
$g \circ f$: 🔗
the composition of functions $f : A \to B$ and $g : B \to C,$ so that $g \circ f : A \to C$ by $(g \circ f) (a) = g (f (a))$

🔗
Figure 10.4.1. A Venn diagram of a function composition.

🔗

Example 10.4.2. A composition of two functions.

🔗

Consider the functions

\begin{aligned} f : R & \to R_{\geq 0}, & g : R_{\geq 0} & \to R_{\geq 0}, \\ x & \mapsto x^{2}, & x & \mapsto \sqrt{x}, \end{aligned}

🔗

Then we have

\begin{aligned} g \circ f : R & \to R_{\geq 0}, \\ x & \mapsto \sqrt{x^{2}} = | x | . \end{aligned}

🔗

Warning 10.4.3. Composition order matters.

🔗

The notation for the composition of functions

f

and

g

involves a reversal of order, so that we write

g \circ f .

This is so that when we use this notation with input-output notation

(g \circ f) (a),

the notation reminds us that

f

must first be applied to the input

a,

and then

g

is applied to the result

f (a) .

🔗

In general,

f \circ g \neq g \circ f .

Usually, one of the two is not even defined, because domains and codomains of

f

and

g

will not necessarily match up in both orders. And when both are defined, the two different orders of composition usually have different domains and codomains.

🔗

Example 10.4.4. Comparing composition order.

🔗

Consider functions

\begin{aligned} f : N & \to N, & g : N & \to N, \\ n & \mapsto n^{2}, & n & \mapsto n + 1. \end{aligned}

🔗

Then, both

f \circ g : N \to N

and

g \circ f : N \to N

are defined. But they are not equal, as

\begin{aligned} (f \circ g) (n) & = (n + 1)^{2} = n^{2} + 2 n + 1, & (g \circ f) (n) & = n^{2} + 1. \end{aligned}

🔗

Example 10.4.5. An undefined composition.

🔗

Consider functions

\begin{aligned} sqrt : N & \to R, & flr : R & \to Z, \\ n & \mapsto \sqrt{n}, & x & \mapsto ⌊ x ⌋ . \end{aligned}

🔗

(See Example 10.3.14 for a description of the

flr

function.)

🔗

Then,

flr \circ sqrt : N \to Z

is defined, with

(flr \circ sqrt) (n) = ⌊ \sqrt{n} ⌋ .

🔗

But

sqrt \circ flr

is not defined, as the codomain of

flr

does not match the domain of

sqrt .

In particular,

flr

will sometimes return a negative output, and we cannot use such an output as an input in

sqrt .

🔗

Checkpoint 10.4.6. Properties of compositions.

🔗

Consider functions

f : A \to B

and

g : B \to C .

🔗
If $g \circ f$ is injective, are either or both of $f, g$ necessarily injective?
🔗
Answer the same question as above with “injective” replaced by “surjective”.
🔗
Demonstrate that if both $f$ and $g$ are bijective, then the composition $g \circ f$ is also bijective.

🔗

Of course, we can compose any number of functions.

🔗

Example 10.4.7. A composition of three functions.

🔗

Let us reconsider the function defined by algorithm in Example 10.1.5. As the function description involved a multi-step algorithm, we should be able to break the steps involved into their own functions, then recreate the original functions as a composition.

🔗

First, define

abs : P (Z) \to P (N)

abs (X) = {| x | | x \in X} .

🔗

Next, define

min : P (N) \to N

so that

min (X)

outputs the minimum number in input set

X,

and outputs

0

in case

X = \emptyset .

🔗

Finally, define

f : N \to N

f (n) = 2 n + 1 .

🔗

Each of these functions represents one step in the algorithm defining the function in Example 10.1.5, but to recreate that function we need to compose the functions in the correct order: write

φ = f \circ min \circ abs,

so that

φ (X) = 2 min (abs (X)) + 1

🔗

computes the same result for an input set

X

as the algorithm described in Example 10.1.5.

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 10.4 Composition of functions

Example 10.4.2. A composition of two functions.

Warning 10.4.3. Composition order matters.

Example 10.4.4. Comparing composition order.

Example 10.4.5. An undefined composition.

Checkpoint 10.4.6. Properties of compositions.

Example 10.4.7. A composition of three functions.