• Recall the Hamming distance function, which
we calculated as the density of the XOR of two
equal length binary strings.
• This functions is calculated by chaining or
composing two functions in such a way that the
output of the first becomes the input of the
second.
• This chaining process demonstrates the
composition of two functions.
• Definition: Let f:X -> Y and g:Y -> Z be
functions such that the image of f is a subset of
the domain of g. Define the new function
g 
f:X -> Z as (g f )(x) = g( f (x)) for all x in X.
We call g f the composition of f and g, putting f
first since it acts upon x first.
Example on Finite Sets
• Let f = {(1,4),(2,3),(3,4),(4,5),(5,6)}
and g = {(1,3),(2,5),(3,1),(4,2),(5,3),(6,4)}.
Then g f = {(1,2),(2,1),(3,2),(4,3),(5,4)}
Example on Infinite Sets
• If f:R-> R is given by f (x) = 3x + 7, and
g:R -> R given by g(x) = x2, then
(g f )(x) = g(f (x)) = g(3x + 7) = (3x + 7)2, and
(f g )(x) = f (g(x)) = f (x2) = 3x2 + 7.
• Note: this example illustrates that in general:
(g f )(x) ≠ (f g )(x),
since (3x + 7)2 ≠ 3x2 + 7
Identity Functions
• Definition: Given a set X, the identity function on
X, iX:X -> X is the function iX(x) = x.
• In pictures: If X = {1,2,3,4} then
• When composing the identity function with a
general function f:X -> Y, we see f iX = f and
iY f = f.
Inverse Functions
• Definition: Given a one-to- one and onto function
f:X -> Y, the inverse function of f, is the function
f-1:Y -> X such that f f-1 = iY and f-1 f = iX.
• In pictures:
Composition of 1-1 Functions
• Theorem: Given one-to-one functions f:X -> Y,
and g:Y -> Z, then the composition g f: X -> Z
is a one-to-one function.
• In pictures:
Composition of Onto Functions
• Theorem: Given onto functions f:X -> Y, and
g:Y -> Z, then the composition g f: X -> Z is an
onto function.
• In pictures:
