Basic Discrete Structure : Function

Lecture 7-8

1
 Function
Definition: Let A and B be two sets. A function from A to B,
denoted f : A → B , is an assignment of exactly one element
of B to each element of A. We write f(a) = b to denote the
assignment of b to an element a of A by the function f.

2
 Function
Definition: Let A and B be two sets. A function from A to B,
denoted f : A → B , is an assignment of exactly one element
of B to each element of A. We write f(a) = b to denote the
assignment of b to an element a of A by the function f.

3
 Representing Function
Representations of functions:
1. Explicitly state the assignments in between elements of the two sets
2. Compactly by a formula. (using ‘standard’ functions)

Example1:
• Let A = {1,2,3} and B = {a,b,c}
• Assume f is defined as:
•1→c
•2→ a
•3→ c
• Is f a function ?
• Yes. since f(1)=c, f(2)=a, f(3)=c. each element of A is
assigned an element from B
4
 Representing Function
Representations of functions:
1. Explicitly state the assignments in between elements of the
two sets
2. Compactly by a formula. (using ‘standard’ functions)

Example 2:
• Let A = {1,2,3} and B = {a,b,c}
• Assume g is defined as:
•1→c
•1→b
•2→ a
•3→ c
• Is g a function ?

5
 Representing Function
Representations of functions:
1. Explicitly state the assignments in between elements of the
two sets
2. Compactly by a formula. (using ‘standard’ functions)

Example 2:
• Let A = {1,2,3} and B = {a,b,c}
• Assume g is defined as:
•1→c
•1→b
•2→ a
•3→ c
• Is g a function ?
• No. since g(1) is assigned both c and b.
6
 Representing Function
Representations of functions:
1. Explicitly state the assignments in between elements of the
two sets
2. Compactly by a formula. (using ‘standard’ functions)

Example 3:
• A = {0,1,2,3,4,5,6,7,8,9}, B = {0,1,2}
• Define h: A → B as:
h(x) = x mod 3.
• (the result is the remainder after the division by 3)
• Assignments:
• 0 →0 3 → 0
•1→1 4→ 1
•2→ 2 …
7
 Notation of Set
Definitions: Let f be 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, b is the image of a and a is a pre-image of b.

• The range of f is the set of all images of elements of A. Also, if

f is a function from A to B, we say f maps A to B.

Example: Let A = {1,2,3} and B = {a,b,c}

• Assume f is defined as: 1 → c, 2 → a, 3 → c
• What is the image of 1?
• 1 → c c is the image of 1
• What is the pre-image of a?
• 2 → a 2 is a pre-image of a.
• Domain of f ? {1,2,3}
• Codomain of f ? {a,b,c}
• Range of f ? {a,c} 8
 Image of subset
Definition: Let f be a function from set A to set B and let S be a
subset of A. The image of S is a subset of B that consists of the
images of the elements of S. We denote the image of S by f(S),
so that f(S) = { f(s) | s ϵ S }.

Example:
• Let A = {1,2,3} and B = {a,b,c} and f: 1 → c, 2 → a, 3 → c
• Let S = {1,3} then image f(S) = ?
9
 Image of subset
Definition: Let f be a function from set A to set B and let S be a
subset of A. The image of S is a subset of B that consists of the
images of the elements of S. We denote the image of S by f(S),
so that f(S) = { f(s) | s ϵ S }.

Example:
• Let A = {1,2,3} and B = {a,b,c} and f: 1 → c, 2 → a, 3 → c
• Let S = {1,3} then image f(S) = {c}
10
 Injective function
Definition: A function f is said to be one-to-one, or injective, if
and only if f(x) = f(y) implies x = y for all x, y in the domain of
f. A function is said to be an injection if it is one-to-one.

A function for which every element of the range of the function

corresponds to exactly one element of the domain.

11
 Injective function
Example 1: Let A = {1,2,3} and B = {a,b,c}
• Define f as
–1→c
–2→a
–3→c
• Is f one to one?

12
 Injective function
Example 1: Let A = {1,2,3} and B = {a,b,c}
• Define f as
–1→c
–2→a
–3→c
• Is f one to one?
• No, it is not one-to-one
• since f(1) = f(3) = c, and 1 ≠ 3.

Example 2: Let g : Z →Z, where g(x) = 2x - 1.

• Is g one-to-one?

13
 Injective function
Example 1: Let A = {1,2,3} and B = {a,b,c}
• Define f as
–1→c
–2→a
–3→c
• Is f one to one?
• No, it is not one-to-one
• since f(1) = f(3) = c, and 1 ≠ 3.

Example 2: Let g : Z →Z, where g(x) = 2x - 1.

• Is g is one-to-one?
• Yes.
• Why? g(a) = g(b), i.e., 2a - 1 = 2b - 1 => 2a = 2b=> a = b.
14
 Surjective function
Definition: A function f from A to B is called onto, or surjective,
if and only if for every b ϵ B there is an element a ϵ A such
that f(a) = b.
Alternative: all co-domain elements are covered

15
 Surjective function
Example 1: Let A = {1,2,3} and B = {a,b,c}
– Define f as
•1→c
•2→ a
•3→ c
• Is f an onto?

16
 Surjective function
Example 1: Let A = {1,2,3} and B = {a,b,c}
– Define f as
•1→c
•2→ a
•3→ c
• Is f an onto?
• No. f is not onto, since b ϵ B has no pre-image.

Example 2: A = {0,1,2,3,4,5,6,7,8,9}, B = {0,1,2}

– Define h: A → B as h(x) = x mod 3.
• Is h an onto function?

17
 Surjective function
Example 1: Let A = {1,2,3} and B = {a,b,c}
– Define f as
•1→c
•2→ a
•3→ c
• Is f an onto?
• No. f is not onto, since b ϵ B has no pre-image.

Example 2: A = {0,1,2,3,4,5,6,7,8,9}, B = {0,1,2}

– Define h: A → B as h(x) = x mod 3.
• Is h an onto function?
• Yes. h is onto since a pre-image of 0 is 6, a pre-image of 1
is 4, a pre-image of 2 is 8.
18
Determine whether the function f (x) = x + 1 from
the set of real numbers to itself is one-to-one.

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

the set of integers onto?

19
 Bijective function

Definition: A function f is called a bijection if it is both one-to

one and onto.

20
onto One to one and onto
 Bijective function

Example 1:
• Let A = {1,2,3} and B = {a,b,c}
– Define f as
•1→c
•2→ a
•3→ b
• Is f a bijection?

21
 Bijective function

Example 1:
• Let A = {1,2,3} and B = {a,b,c}
– Define f as
•1→c
•2→ a
•3→ b
• Is f is a bijection? Yes. It is both one-to-one and onto.

22
 Bijective function

Example 2:
• Define g : W → W (whole numbers), where
g(n) = [n/2] (floor function).

• 0 → [0/2] = [0] = 0
• 1 → [1/2] = [1/2] = 0
• 2 → [2/2] = [1] = 1
• 3 → [3/2] = [3/2] = 1
• ...
• Is g a bijection?
– No. g is onto but not 1-1 (g(0) = g(1) = 0 however 0 ≠ 1.

23
 Identity function

Definition: Let A be a set. The identity function on A is the

function iA: A → A where iA (x) = x.

Example:

• Let A = {1,2,3}

Then:
• iA (1) = ?

24
 Identity function

Definition: Let A be a set. The identity function on A is the

function iA: A → A where iA (x) = x.

Example:

• Let A = {1,2,3}

Then:
• iA (1) = 1
• iA (2) = 2
• iA (3) = 3.

25
 Inverse Function

Definition: Let f be a bijection from set A to set B. The inverse

function of f is the function that assigns to an element b from 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. If the inverse function of f exists, f is called
invertible.

26
 Inverse Function

Note: if f is not a bijection then it is not possible to define the

inverse function of f. Why?

Assume f is not one-to-one:

?

27
 Inverse Function

Note: if f is not a bijection then it is not possible to define the

inverse function of f. Why?

Assume f is not one-to-one:

f is not a Inverse function. One element of B is mapped to two

different elements.

28
 Inverse Function

Note: if f is not a bijection then it is not possible to define the

inverse function of f. Why?

Assume f is not onto:

?

29
 Inverse Function

Note: if f is not a bijection then it is not possible to define the

inverse function of f. Why?

Assume f is not onto:

f is not a Inverse function. One element of B is not assigned
any
value in A.

30
 Inverse Function

Example 1:

• Let A = {1,2,3} and iA be the identity function

• iA(1) = 1 iA-1 (1) = 1

• iA(2) = 2 iA-1 (2) = 2
• iA(3) = 3 iA-1 (3) = 3

• Therefore, the inverse function of iA is iA.

31
 Inverse Function

Example 2:
• Let g : R → R, where g(x) = 2x - 1.

• What is the inverse function g-1 ?

32
 Inverse Function

Example 2:
• Let g : R → R, where g(x) = 2x - 1.

• What is the inverse function g-1 ?

g(x) =y
g-1(y)=x
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x

• Define g-1(y) = x= (y+1)/2

Test the correctness of inverse:

• g(3) = .. 33
 Inverse Function

Example 2:
• Let g : R → R, where g(x) = 2x - 1.

• What is the inverse function g-1 ?

Approach to determine the inverse:

y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x

• Define g-1(y) = x= (y+1)/2

Test the correctness of inverse:

• g(3) = 2*3 - 1 = 5
• g-1 (5) = 34
 Inverse Function

Example 2:
• Let g : R → R, where g(x) = 2x - 1.

• What is the inverse function g-1 ?

Approach to determine the inverse:

y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x

• Define g-1(y) = x= (y+1)/2

Test the correctness of inverse:
• g(3) = 2*3 - 1 = 5
• g-1 (5) = (5+1)/2 = 3
35
 Composition of Function

Definition: Let f be a function from set A to set B and let g be a

function from set B to set C. The composition of the functions
g and f, denoted by g O f is defined by (g O f)(a) = g(f(a)).

36
 Composition of Function

Example 1:
• Let A = {1,2,3} and B = {a,b,c,d}

g : A → A, f: A → B
1 →3 1→b
2 →1 2→a
3 →2 3→d

f O g : A → B:
•1→?

37
 Composition of Function

Example 1:
• Let A = {1,2,3} and B = {a,b,c,d}

g : A → A, f: A → B
1 →3 1→b
2 →1 2→a
3 →2 3→d

f O g : A → B:
•1→d
•2→b
•3→a
38
 Composition of Function

Example 2:
• Let f and g be two functions from Z to Z, where

• f(x) = 2x and g(x) = x2.

•fOg:Z→ Z

• (f O g)(x) = f(g(x))
= f( x2 )
= 2(x2)

•gOf:Z→ Z
• (g O f)(x) = ?

39
 Composition of Function

Example 2:
• Let f and g be two functions from Z to Z, where

• f(x) = 2x and g(x) = x2.

•fOg:Z→ Z

• (f O g)(x) = f(g(x))
= f( x2 )
= 2(x2)

•gOf:Z→ Z
• (g O f)(x) = g(f(x))
= f(2x)
= 4x2 40
 Composition of Function

Example 3:

• (f O f -1)(x) = x and (f -1 O f)(x) = x, for all x.

• Let f : R → R, where f(x) = 2x – 1 and f -1 (x) = (x+1)/2.

• (f O f -1 )(x) = f(f -1 (x))

= f( (x+1)/2 )
= 2( (x+1)/2 ) - 1
= (x+1) - 1
=x

41
 Composition of Function
Example 3:

• (f O f -1)(x) = x and (f -1 O f)(x) = x, for all x.

• Let f : R → R, where f(x) = 2x – 1 and f -1 (x) = (x+1)/2.

• (f O f -1 )(x) = f(f -1 (x))

= f( (x+1)/2 )
= 2( (x+1)/2 ) - 1
= (x+1) - 1
=x

•(f -1 O f)(x) = f -1 (f(x))

= f -1 ( 2x - 1 )
= (2x)/2
42
=x
 Some Function
Definitions:
• The floor function assigns a real number x the largest integer
that is less than or equal to x. The floor function is denoted by
.
• The ceiling function assigns to the real number x the smallest
integer that is greater than or equal to x. The ceiling function is
denoted by

Other important functions:

• Factorials: n! = n(n-1) such that 1! = 1

43
Thank You

44