Functions Section 2.3: MTK3013 Discrete Structures

http://fskik.upsi.edu.
my
FUNCTIONS
Section 2.3
MTK3013
DISCRETE STRUCTURES
http://fskik.upsi.edu.my
Recap 2.1
• Set – an UNORDERED collection of objects

– Element /member - an object in a set
– NOTATION….{a,b,c,d}
• Cardinality
– The number of distinct elements in a set
• Power Set
– The set of all subsets of a set
• Cartesian product of two sets A and B A  B
AB = {(a,b) | aA  bB}
Recap 2.2
• Union: AB = {x | xA  xB}

• Intersection: AB = {x | xA  xB}
• Difference: AB = {x | xA  xB}
• Complement: Ā = U- A
• Identities similar to those from logic, e.g.
Definitions
• Let A and B be 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 of A.
• If f is a function from A to B, we write
f:AB
Definitions
• If f : A  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.
• The range of f is the set of all images of
elements of A.
Example
• Suppose that each student in a class is assigned a letter
grade from the set {A,B,C,D,F}. Let g be the function
that assigns a grade to a student.
Chavez • •A
Stokes • •B Domain
Dees • •C
Dozier • •D Codomain
Holland • •F
Range
Example
• Consider a function f : Z  Z that assigns the

square of an integer to this integer.
• How can you write this function?
f(x) = x2
• What is the domain of f ? integers
• What is the codomain of f ? integers
• What is the range of f ? Nonnegative integers
{0,1,4,9,..}
One-to-One Functions
(injective)
• No value in the range is used by more than one value
in the domain.
• If f(x)=f(y), then x=y for all x and y in the domain of
•1
f. a • •2
b • •3
c • •4
• In other words x y (f(x)=f(y)  x=y),

or using the contrapositive
x y (x≠y  f(x)≠f(y))
One-to-One Functions
• Is the function f(x) = x2 from the set of integers to

the set of integers one-to-one?
• x y (x2=y2  x=y)?
• 12 =(-1)2 but 1 ≠-1
• NO
• Is the function f(x) = x+1 one-to-one?

• x y (x+1=y+1  x=y)?
• X+1 ≠ y+1 only when x≠y
• YES
Onto Functions
(surjective)
• For every value in the codomain, there is a
value in the domain that is mapped to it.
• •1
a • •2
b • •3
c •
d
• In other words, y x (f(x)=y)

• Codomain = range!
Onto Functions
• Is the function f(x) = x2 from the set of integers to
the set of integers onto?
– y x (x2=y)??
– There does not exists a x such that x2 = -1, for example.
-1 is one of the possible values of y.
– NO
• Is the function f(x) = x+1 onto?

– y x (x+1=y)??
– For every y, some x exist such that x=y -1.
– YES
One-to-One Correspondence
(bijection)
• If a function f is both one-to-one and onto,
then it is a one-to-one correspondence.
a • •1
•1 •1
a • a b • •2
•2 •2
b • b • c • •3
•3 •3
c • c • d • •4
•4
d •
•
One-to-One
Onto, but One-to-One Correspondence
But not onto
Not one-one
Monotonic Functions
• A monotonic function is
– either monotonically (strictly) increasing
– or monotonically (strictly) decreasing
• Consider a function f : R  R
• f is monotonically increasing
– if f(x) <= f(y) whenever x < y
• f is monotonically decreasing
– if f(x) >= f(y) whenever x < y
Inverse Functions
• Let f : AB be one-to-one correspondence

such that f(a) = b.
• The inverse of the function f is denoted by f -
1
(b) = a.
f 1
a  f 1(b) b  f(a)
A f B
F needs to be bijection
• If f is not a bijection (one-to-one correspondence)

– f is not injective (one-to-one)
– f is not surjective (onto)
• Why can’t invert such a function??
We cannot assign to each element b in the codomain a
unique element a in the domain such that f(a)=b.
because
– For some b there is either
• More than one a
• No such a
Inverse Functions
• Let f : Z  Z be a function with f(x) = x+1.
• Is f invertible? Is f a bijection?
 Is f one-to-one? YES
 Is f onto? YES
 So f is a one-to-one correspondence
and is therefore invertible.
• Then, what is its inverse? f(y)=y-1
Inverse Functions
• Let f : Z  Z be a function with f(x) = x2.
• Is f invertible?
 Is f one-to-one? NO
 So f is not a one-to-one correspondence.
 f is not invertible.
Compositions of Functions
• Let g : A  B and f : B  C.
• The composition of the functions f and g,
denoted by f  g, is defined by:
f  g(a) = f (g(a))
• f  g can’t be defined unless the range of g is
a subset of the domain of f.
Example
• Let,
f(x) = 2x + 3
g(x) = 3x + 2
• Find f  g(x).
• Find g  f(x).
Composition of Inverses
• f(a)=b
• f-1(b)=a
• f-1  f (a) =?
• f  f-1 (b)=?
Important functions – Floor
• Let x be a real number. The floor function is

the closest integer less than or equal to x…
• Examples:
½ =0
 –½  = ?
 3.1  = ?
7 =?
floor
http://mathworld.wolfram.com/FloorFunction.html
Important functions – Ceiling
• Let x be a real number. The ceiling function is

the closest integer greater than or equal to x.
• Examples:
½ =1
 –½  = ?
 3.1  = ?
7=?
Ceiling
http://mathworld.wolfram.com/CeilingFunction.html

Functions Section 2.3: MTK3013 Discrete Structures

Uploaded by

Copyright:

Available Formats

Functions Section 2.3: MTK3013 Discrete Structures

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Functions Section 2.3: MTK3013 Discrete Structures

Uploaded by

Copyright:

Available Formats

http://fskik.upsi.edu.

• Set – an UNORDERED collection of objects

• Union: AB = {x | xA  xB}

• Let A and B be sets. A function f from A to

• If f : A  B, we say that A is the domain of f

• Consider a function f : Z  Z that assigns the

• In other words x y (f(x)=f(y)  x=y),

• Is the function f(x) = x2 from the set of integers to

• Is the function f(x) = x+1 one-to-one?

• In other words, y x (f(x)=y)

• Is the function f(x) = x+1 onto?

• Let f : AB be one-to-one correspondence

• If f is not a bijection (one-to-one correspondence)

• Let f : Z  Z be a function with f(x) = x+1.

• Let f : Z  Z be a function with f(x) = x2.

Important functions – Floor

• Let x be a real number. The floor function is

Important functions – Ceiling

• Let x be a real number. The ceiling function is

You might also like