SET and FUNCTIONS
FUNCTIONS
Let A and B be nonempty sets. A function f from A to B is
an assignment of exactly one element of B to each element
of A.
We write f (a) = b if b is the unique element of B assigned
by the function f to the element a of A.
If f is a function from A to B, we write
f:A→B
FUNCTIONS
Functions are sometimes also called mappings or
transformations.
Every element in A will be used in the mapping, but not all
elements in B needs to be used.
Each element in A must be used only once.
FUNCTIONS
Example
Suppose that each student in a discrete mathematics class is
assigned a letter grade from the set {A,B,C,D, F}.
Adams – A
Chou – C
Goodfriend – B
Rodriguez – A
Stevens - F
FUNCTIONS
Example
Let A = {1, 2, 3 } and B = {A,B,C,D, F}
Assume f is defined as:
• 1 A
• 1 B
• 3 A
Is f a function?
NO – f(1) is assigned both A and B
Representing FUNCTIONS
Representing Functions
Explicitly state the assignments between
elements in the two sets. Roster notation.
Set builder notation
e.g F(x) = x2
Tabular
Digraph
Mathematical graph
Representing FUNCTIONS
Mathematical graph
Display the graph of the function f (x) = x2 from the set of integers to the set of
integers.
Solution: The graph of f is the set of ordered pairs of the form (x, f (x)) = (x,
x2), where x is an integer.
FUNCTIONS
If f is a function from A to B, we say that A is the domain
of f and B is the codomain of f.
If f (a) = b, we say that b is the image of a and a is a
preimage of b.
The range, or image, of f is the set of all images of
elements of A.
Also, if f is a function from A to B, we say that f maps A to
B.
FUNCTIONS
Example
Let G be the function that assigns a grade to a student in our
discrete mathematics class.
For instance G(Adams) = A
Domain of G = {Adams, Chou, Goodfriend, Rodriguez,
Stevens}
Codomain = {A,B,C,D, F}
Range of G = {A,B,C, F}, because each grade except D is
assigned to some student.
Image of Subset
Let f be a function from A to B and let S be a subset of A. The image of S
under the function f is the subset of B that consists of the images of the
elements of S.
We denote the image of S by f (S)
f (S) = {t | ∃s ∈S (t = f (s))}.
We also use the shorthand {f (s) | s ∈ S} to denote this set.
Image of Subset
Example
Let A = {a, b, c, d, e} and B = {1, 2, 3, 4}
f (a) = 2, f (b) = 1, f (c) = 4, f (d) = 1,
f (e) = 1.
The image of the subset S = {b, c, d} is the
set f (S) = {1, 4}.
Types of Functions
Injective
Surjective
Bijective
Identity
Inverse
Injective / one-to-one
A function f is said to be one-to-one, or injective, if and only if f (a) = f (b)
implies that a = b for all a and b in the domain of f.
Injective / one-to-one
Example
Determine whether the function f from {a, b, c, d} to {1, 2, 3, 4, 5} with f (a) =
4, f (b) = 5, f (c) = 1, and f (d) = 3 is one-to-one.
Solution: The function f is one-to-one because f takes on different values at
the four elements of its domain.
Surjective / onto
A function f from A to B is called onto, or a surjective, if and only if for every
element b ∈ B there is an element a ∈ A with f (a) = b
Surjective / onto
Example
Let f be the function from {a, b, c, d} to {1, 2, 3} defined by f (a) = 3, f (b) = 2, f
(c) = 1, and f (d) = 3. Is f an onto function?
Solution: Because all three elements of the codomain are images of elements
in the domain, we see that f is onto.
Bijective / one-to-one and onto
The function f is a one-to-one correspondence, or a bijective, if it is both
one-to-one and onto.
Also known as isomorphism
Bijective / one-to-one and onto
Example
Let f be the function from {a, b, c, d} to {1, 2, 3, 4} with f (a) = 4, f (b) = 2, f (c)
= 1, and f (d) = 3. Is f a bijection?
Solution: The function f is one-to-one and onto. It is one-to-one because no
two values in the domain are assigned the same function value.
It is onto because all four elements of the codomain are images of elements
in the domain. Hence, f is a bijection.
a 1
b 2
c 3
d 4
Tips
Suppose that f : A → B.
To show that f is injective Show that if f (x) = f (y) for arbitrary x, y ∈ A with
x = y,then x = y.
To show that f is not injective Find particular elements x, y ∈ A such that x =
y and f (x) = f (y).
To show that f is surjective Consider an arbitrary element y ∈ B and find an
element x ∈ A such that f (x) = y.
To show that f is not surjective Find a particular y ∈ B such that f (x) = y for
all x ∈ A.
Identity
Let A be a set. The identity function on A is the function ιA : A → A, where
ιA(x) = x for all x ∈ A.
In other words, the identity function ιA is the function that assigns each
element to itself.
The function ιA is one-to-one and onto, so it is a bijection.
(Note that ι is the Greek letter iota.)
Inverse
Let f be a one-to-one correspondence from the set A to the set B. The inverse
function of f is the function that assigns to an element b belonging to B the
unique element a in A such that f (a) = b.
The inverse function of f is denoted by f−1.
Hence, f−1(b) = a when f (a) = b.
Inverse
Example
Let f be the function from {a, b, c} to {1, 2, 3} such that f (a) = 2, f (b) = 3, and f
(c) = 1. Is f invertible, and if it is, what is its inverse?
Solution: The function f is invertible because it is a one-to-one
correspondence.
The inverse function f−1 reverses the correspondence given by f
so f−1(1) = c, f−1(2) = a, and f−1 (3) = b.
Composition
Let g be a function from the set A to the set B and let f be a function from
the set B to the set C. The composition of the functions f and g, denoted for
all a ∈ A by f ◦ g, is defined by
(f ◦ g)(a) = f (g(a))
Composition
Example
Let A = {1,2,3} and B = {a,b,c,d}
f: A → A g: A → B
1→3 1→b
2→1 2→a
3→2 3→d
(f ◦ g)
1→d
2→b
3→a
Composition
Example
Let f and g be the functions from the set of integers to the set of integers
defined by f (x) = 2x + 3 and g(x) = 3x + 2.
What is the composition of f and g?
(f ◦ g)(x) = f (g(x)) = f (3x + 2) = 2(3x + 2) + 3 = 6x + 7
What is the composition of g and f ?
(g ◦ f )(x) = g(f (x)) = g(2x + 3) = 3(2x + 3) + 2 = 6x + 11.
Note: f ◦ g and g ◦ f are not equal, hence they are not commutative.
