Discrete12
Functions
FUNCTION
• extremely important in mathematics and
computer science
• used in the definition of such discrete
structures as sequences and strings
• also used to represent how long it takes a
computer to solve problems of a given
size
FUNCTION
• In many instances, we assign to each
element of a set a particular element of
a second set.
• For example, suppose that each
student in a discrete mathematics class
is assigned a letter grade from the set
{A, B, C, D, F}.
FUNCTION
• And suppose that the grades are:
• A for Adams;
• C for Chou;
• B for Goodfriend;
• A for Rodriguez; and
• F for Stevens.
FUNCTION
Definition 6
Functions and Nonfunctions
• Which of the following arrow diagrams define
functions from X = {a, b, c} to Y = {1, 2, 3, 4}?
Function: Visualization
Range
Preimage Image, f(a)=b
f
a b
c
A B
Domain Co-Domain
A function, f: A → B
Functions - image & preimage
image ({Michael, Toby}) = ? image (John) = ?
image (A) = ?
pre-image (Kathy) = ?
Kathy
Michael
Toby Carol
John
Mary
Chris
Brad
B
A
FUNCTIONS
What are the domain, co-domain, and range of
the function that assigns grades to students?
Let G be the function that
assigns a grade to a student.
FUNCTIONS
• A function is something that associates each
element of a set with an element of another
set.
• Non-technical examples:
• a social security number uniquely identifies
the person
• the income tax rate varies depending on
the income
• letter grade for a course is often
determined by exam scores
Functions
• Injective Function - One-to-One Functions
• Surjective Function - Onto Functions
• Bijective Function - Both One-to-One and Onto
Injective Function
Functions - Injection
Every b B has
An injection simply means
at most 1
that each element in the
preimage.
range has at most one
preimage (antecedent).
Not one-to-one
Michael Kathy
Toby Carol
John
Chris Mary
Brad
Surjective Function
Functions - Surjection
Every b B has • A surjection means that every
at least 1 element in the codomain is
preimage. mapped (i.e., it is an image, has
an antecedent).
Not onto
Michael Kathy
Toby Carol
John
Chris Mary
Brad
Bijective Function
Functions: Example1
A B
a1 b1
a2 b2
a3 b3
a4 b4
• Is this function
▫ One-to-one (injective)? Why?
▫ Onto (surjective)? Why?
Functions: Example2
A B
a1 b1
a2 b2
a3 b3
b4
• Is this function
▫ One-to-one (injective)? Why?
▫ Onto (surjective)? Why?
Functions: Example3
A B
a1 b1
a2 b2
a3 b3
a4
• Is this function
▫ One-to-one (injective)? Why?
▫ Onto (surjective)? Why?
Functions: Example4
• Let A = {1, 2, 3} and B = {a, b, c}
• Is f a bijection? Why?
f:A→B
A B
1 a
2 b
3 c
END
