394
Relations, Functions, and Matrices
We’ve introduced a lot of terminology about functions. Table 5.2 gives an
informal summary of these terms.
table 5.2
term
meaning
function
Mapping from one set to another that associates with each member of the starting
set exactly one member of the ending set
domain
Starting set for a function
codomain
Ending set for a function
image
Point that results from a mapping
preimage
Starting point for a mapping
range
Collection of all images of the domain
onto (surjective)
Range is the whole codomain; every codomain element has a preimage
one-to-one (injective) No two elements in the domain map to the same place
bijection
One-to-one and onto
identity function
Maps each element of a set to itself
inverse function
For a bijection, a new function that maps each codomain element back where it
came from
permutation Functions
Bijections that map a set to itself are given a special name.
DefInItIon peRMutationS oF a Set
For a given set A, S A = 5 f 0 f: A S A and f is a bijection6. S A is thus the set of
all bijections of set A into (and therefore onto) itself; such functions are called
permutations of A.
If f and g both belong to S A , then they each have domain = range = A. Therefore the composition function g + f is defined and maps A S A. Furthermore,
because f and g are both bijections, our theorem on composing bijections says
that g + f is a bijection, a (unique) member of S A . Thus, function composition is a
binary operation on the set S A .
In Section 4.4 we described a permutation of objects in a set as being an ordered arrangement of those objects. Is this now a new use of the word “permutation”? Not exactly; permutation functions represent ordered arrangements of the
objects in the domain. If A = 51, 2, 3, 46, one permutation function of A, call it
f, is given by f = 5(1, 2), (2, 3), (3, 1), (4, 4)6. We can also describe function f in
array form by listing the elements of the domain in a row and, directly beneath,
the images of these elements under f. Thus,
f = a
1 2 3 4
2 3 1 4
b
The bottom row is an ordered arrangement of the objects in the top row.
Relations, Functions, and Matrices
We’ve introduced a lot of terminology about functions. Table 5.2 gives an
informal summary of these terms.
table 5.2
term
meaning
function
Mapping from one set to another that associates with each member of the starting
set exactly one member of the ending set
domain
Starting set for a function
codomain
Ending set for a function
image
Point that results from a mapping
preimage
Starting point for a mapping
range
Collection of all images of the domain
onto (surjective)
Range is the whole codomain; every codomain element has a preimage
one-to-one (injective) No two elements in the domain map to the same place
bijection
One-to-one and onto
identity function
Maps each element of a set to itself
inverse function
For a bijection, a new function that maps each codomain element back where it
came from
permutation Functions
Bijections that map a set to itself are given a special name.
DefInItIon peRMutationS oF a Set
For a given set A, S A = 5 f 0 f: A S A and f is a bijection6. S A is thus the set of
all bijections of set A into (and therefore onto) itself; such functions are called
permutations of A.
If f and g both belong to S A , then they each have domain = range = A. Therefore the composition function g + f is defined and maps A S A. Furthermore,
because f and g are both bijections, our theorem on composing bijections says
that g + f is a bijection, a (unique) member of S A . Thus, function composition is a
binary operation on the set S A .
In Section 4.4 we described a permutation of objects in a set as being an ordered arrangement of those objects. Is this now a new use of the word “permutation”? Not exactly; permutation functions represent ordered arrangements of the
objects in the domain. If A = 51, 2, 3, 46, one permutation function of A, call it
f, is given by f = 5(1, 2), (2, 3), (3, 1), (4, 4)6. We can also describe function f in
array form by listing the elements of the domain in a row and, directly beneath,
the images of these elements under f. Thus,
f = a
1 2 3 4
2 3 1 4
b
The bottom row is an ordered arrangement of the objects in the top row.