Module 12
Functions
1. Injective Functions
2. Surjective
Functions
3. Bijective Functions
4. Hash Function
5. Inverse of a
Function
6. Composition of
Function
FUNCTIONS
A special kind of function domain
R={x∈X| (x,y) ∈ R for some y ∈ Y}
Ifa relation from X to Y, in order for F
also to be a function, the domain of F
must equal x & if (x,y) & (x,y’) are in F,
we must have y=y’.
Functions are sometimes also called
mappings or transformations
FUNCTIONS PROPERTIES
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.
Iff is a function from A to B, we write f : A → B.
FUNCTIONS PROPERTIES
Determine if the following is a function:
1. F= {(1,a), (2,b), (3,a)} from x= {1,2,3} to Y = {a,b,c}
2. {R = {(1,a), (2,b), (3,a)} from x= {1,2,3} to Y
={a,b,c}
3. F= {(1,a), (2,b), (3,C), (1,B)} from x= {1,2,3} to Y =
{a,b,c}
One-to-One Functions
Some functions never assign the same value to
two different domain elements. These functions are
said to be one-to-one.
A function f is said to be one-to-one, or an
injunction, if and only iff(a)= f(b) implies that a = b
for all a and b in the domain of f. A function is said
to be injective if it is one-to-one.
One-to-One Functions
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.
Determine whether the function f(x)= x +1 from the
set of real numbers to itself is one-to-one.
One-to-One Functions
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.
One-to-One Functions
Determine whether the function f(x)= x +1 from the
set of real numbers to itself is one-to-one.
One-to-One Functions
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.
One-to-One Functions
A function f from A to B is called onto, or a
surjection, if and only if for every element b ∈ B
there is an element a ∈ A with f(a)= b. A function f
is called surjective if it is onto.
For some functions the range and the codomain
are equal. That is, every member of the codomain
is the image of some element of the domain.
Functions with this property are called onto
functions.
Onto Functions
A function f from A to B is called onto, or a
surjection, if and only if for every element b ∈ B
there is an element a ∈ A with f(a)= b. A function f
is called surjective if it is onto.
For some functions the range and the codomain
are equal. That is, every member of the codomain
is the image of some element of the domain.
Functions with this property are called onto
functions.
One-to-One and Onto Functions
Bijection – a function that is both one
to one & onto Y, or function f is a one-
to-one correspondence
Different Kinds of Correspondence
MODULUS OPERATOR
Involved in the field of engineering, computer
science & mathematics concerning functions.
Ex. 1. f(1) = a
Ex. 2. f(3) = b
“If x is a non-negative integer & y is a positive integer,
we define x mod y to be the remainder when x is
divided by y.”
Try this >
6 mod 2 =____
5 mod 1 = ____
8 mod 12 = ____
199373 mod 2 = ____
Floors and Ceilings
Floor of X, denoted └ x ┘,the greatest integer
less than or equal to x.
Ceiling of X, denoted ┌ x ┐, the least integer
greater than or equal to x.
Example:
1.└ 8.3 ┘ =
2. ┌ 9.1 ┐ =
3. └ -8.7 ┘=
4. ┌ 6 ┐ =
HASH FUNCTION
Takes a data item to be stored or retrieved &
computes the first choice for the location for the
item.
Example. To store or retrieve the no. n, we might
take as the first choice for a location n mod11.
h(n)=nmod11
Show result of storing 15, 558, 32, 132, 102 & 5 in this
order.
INVERSE OF A FUNCTION
Letf 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 OF A FUNCTION
A one-to-one correspondence is called invertible
because we can define an inverse of this function.
A function is not invertible if it is not a one-to-one
correspondence, because the inverse of such a
function does not exist.
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?
COMPOSITION OF A FUNCTION
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 OF A FUNCTION
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)).
Example: Given g={(1,a),(2,a),(3,c)} a function
from x{1,2,3} to y{a,b,c} and F={(a,y),(b,x),(c,z)} to
a function from y to z={x,y,z}. Find the composition
of function from x to z.
