Week 3: Functions

Section…………………………………………………………………………………………….Page

Section 1: Definition of Functions ………………………………………….…………………….2

Section 2: Domain, Co-domain and the Range of a Function ………………………………….....3

Section 3: Direct and Inverse Images ……………………………………………………………..5

Section 4: Injective, Surjective and Bijective Functions ………………………………….………7

Section 5: Composite and Inverse Functions…………………………………..………………….10

Bibliography ………………………………………………………………………………………14

UU-MTH- 1005 Discrete Mathematics Page 1

 Section 1: Definition of Functions

Given two sets and , a function is a rule of correspondence from set to set which assigns each
element of set exactly one element in set .

Input, Relationship, Output

A function associates with itself elements in set called input, a rule of correspondence from set to
set called relationship and results of a rule of correspondence put in set called output.

The set of inputs is called the domain and the set of outputs is called the range.

Names of Functions
There are several names that can be given to functions such as but the most commonly
used name is

Example
The following is an example of a function

( )
Where,

With functions, two elements from set can be assigned to only one element in set but one element
from set A cannot be assigned to two elements of set .

Given three figures below

UU-MTH- 1005 Discrete Mathematics Page 2

 figure 1 and figure 2 are representative of functions while figure 3 is not representative of a function.

Example

Find the range (outputs) of the following values using the function ( )

( )

Solution

( ) ( )
( ) ( )
( ) ( )
( ) ( )

Therefore, the range is

( )

Section 2: Domain, Co-domain and the Range of a

Function

UU-MTH- 1005 Discrete Mathematics Page 3

 Because we have already looked at what domain and range are in the previous section, here we will use
an example to illustrate what a co-domain is in relation to domain and range.

Using the immediate previous example, for the function ( ) , we had each element of

( )

assigned to

( )

* + * +
The other way of writing the above function is .

Now, let us have

( ) and ( ), the above expression can now be rewritten as

is the domain and is the range.

Suppose now that and , this and the above may as well be written as

( )

UU-MTH- 1005 Discrete Mathematics Page 4

 Therefore,

The domain is a possible set of all inputs

The codomain is a possible set of all outputs

The range is the actual set of all outputs

The range is then a subset of the co-domain.

Section 3: Direct and Inverse Images

Given the function , where and .

The direct image of A is defined by ( ) * ( ) | + and

the inverse image of B is defined by ( ) * | ( ) +, where, ( ) and ( ) are

representatives of sets.

Note: here, is strictly for inverse image of and not in any way standing for the inverse function
of because there are some conditions (not applicable to the case in this section) necessary
before we conclude that the function has an inverse function.

Example

For a function defined by ( ) , find the following images given that * + and
* +

i) ( )
ii) ( )
iii) ( ) ( )

Solutions

i) ( ) * ( ) | +
* ( ) ( ) ( )+ * +
ii) ( ) * ( ) | + * (* + * +)+ * (* +)+
* ( ) ( )+ * +
iii) ( ) ( ) * ( ) | +
{* ( ) ( ) ( )+ * ( ) ( ) ( ) ( )+} {* + * +} * +

UU-MTH- 1005 Discrete Mathematics Page 5

 Example

For a function defined by ( ) , find the following inverse images given that
* + and * +

i) ( )
ii) ( ( ))

Solutions

i) ( ) * | ( ) + * | ( ) ( ) ( ) +
* | + * √ √ +

ii) ( ( )) (* ( ) | +) (* ( ) ( ) ( )+) (* +)
{ | ( ) * +} * | + { √ √ √ }
* +

Theorem:
When we have as subsets of and as subsets of Y, for , then,

i. ( ) ( );

ii. ( ) ( ) ( );

iii. ( ) ( ) ( );

iv. Generally, ( ) ( );

v. ( ) ( );

vi. ( ) ( ) ( );

vii. ( ) ( ) ( );

viii. ( ) ( );

ix. ( ( ));

x. ( ( )) .

UU-MTH- 1005 Discrete Mathematics Page 6

 Example
Although all of them can be proved, from the theorem above, prove i. and ii.

i) ( ) ( );
ii) ( ) ( ) ( );

Solutions
i) If we have any ( ), it means there exists such that ( ). And since
it means , hence, ( ) ( ) because .

Hence, we have proved that ( ) ( ).

ii) To prove ( ) ( ) ( ), we need to prove that ( ) ( ) ( )

and ( ) ( ) ( ).

First, ( ) ( ) ( )
( ) ( ),
or ,
or ( ) ( ) or ( ) ( ),
( ) ( ) ( ) ( ) ( ) ( )

And second, ( ) ( ) ( )
( ) ( )
+ ( ) ( ) ( )
( ) ( )

Hence, we have proved that ( ) ( ) ( )

Section 4: Injective, Surjective and Bijective Functions

Sometimes functions may have two elements in a domain assigned to one element in the co-domain,
each element in the domain assigned to exactly one element for itself alone in the co-domain or some
elements in the domain assigned to some elements in the co-domain, i.e. other elements may not be
assigned to any element. All these are some of the characteristics of functions which we will look at in
this sub-section.

Injective Functions

UU-MTH- 1005 Discrete Mathematics Page 7

 Given the function ; when for all , having ( ) ( ) means then the
function is injective. Graphically, this is illustrated as

This means two different elements of the domain can never be assigned to one same element in the co-
domain. It is the same case even for more than two elements of the domain. In other words, injective
functions are called one-to-one functions.

Example

Given the function defined by ( ) . Show that it is injective.

Solution

We are going to show that for all , having ( ) ( ) means .

, ( ) ( )

Hence, we have shown that the function is injective.

Surjective Functions
Given the function ; when for all we have such that ( ) , then the function
is surjective. Graphically, this is illustrated as

UU-MTH- 1005 Discrete Mathematics Page 8

 This means, to every element of (co-domain = range) is assigned one or more elements of the co-
domain . In this case, surjective functions are called onto functions.

Example

Given the function defined by ( ) . Show that it is surjective.

Solution

We are going to show that for all , we have such that ( ) .

,
( )
( )

( ) ( )

If we replace ( ) in , we will have .

( )

Hence, we have shown that the function is surjective.

Bijective Functions

UU-MTH- 1005 Discrete Mathematics Page 9

 When a function is both injective and surjective it is called a bijective function. Graphically, bijective
functions illustrated as

There is a perfect one-to-one correspondence among elements of the sets. In other words, each element
of the domain is assigned to exactly one element (for itself alone) of the range and no element of the
range is left out in being assigned an element of the domain.

Example

Given the function defined by ( ) . Show that it is bijective.

Solution

Since we have already shown in the examples above that the same function is both injective and
surjective, the function is bijective.

Section 5: Composite and Inverse Functions

Composite Functions

UU-MTH- 1005 Discrete Mathematics Page 10

 Given the two functions and ; the combined function of and , defined by ,
is called the composite function. It is from to and defined by ( )( ) ( ( )), .

What actually happens is that, for , we assign an element of set to ( ) an element in set
. And for , knowing that ( ) , we will assign ( ) an element of set to ( ( )) an
element of . Since ( )( ) ( ( )), we can conclude that we have defined a new function
called the composite function of and directly assigning elements of set to elements
of set . Graphically, this is shown as

If we have and where , we will have being a composite function if the

range of from into is a subset of

For example, given where * + and * +; also, given where

* + and * +. To have as a composite function from to , the range of
from to will have to be a subset of as shown in the graph below

UU-MTH- 1005 Discrete Mathematics Page 11

 And to, algebraically, determine the action of on each element from set to set we use the
definition of each as follows

( )( ) ( ( )) ( )
( )( ) ( ( )) ( )
( )( ) ( ( )) ( )

For a composite function,

 (the composite function is not commutative)

 If is injective and is injective, then is injective
 If is surjective and is surjective, then is surjective
 If is bijective and is bijective, then is bijective

Examples
Given the functions defined by ( ) and defined by ( ) .
Find

i) ( )( )
ii) ( )( )

Solutions
i) ( )( ) ( ( )) ( ) ( ) ( )
ii) ( )( ) ( ( )) ( ) ( )

UU-MTH- 1005 Discrete Mathematics Page 12

 Inverse Functions
Given the function . The function is called an inverse of if it satisfies the
conditions ( ) ( ( )) and ( ) ( ( )) , where and . In this
case, we have .

Theorem

For , the function is bijective if and only if its inverse function, , exists.

Therefore, sometimes it is alright to conclude that the inverse of the function exists if we can prove
that is bijective because if is surjective, then came from some and also if is injective,
then came from exactly one . This leads us to another definition of an inverse function as
follows,

( ) ( )

Example
Given the function defined by ( ) .

Does exist? If does, give it.

Solution
We first begin by proving if is injective:

, we have ( ) ( ) . Hence,
we have shown that is injective.

Secondly, we prove if is surjective:

, such that ( ) . We then make the subject of the formula:

√ . Since ( √ ) (√ ) ,
we have proved that is surjective.

Having proved that is injective and surjective, we can then conclude that is bijective. Hence,
exists and we give it as

( ) √

UU-MTH- 1005 Discrete Mathematics Page 13

 Bibliography

Daepp U., Gorkin P.(2003). Reading, Writing and Proving: A Closer Look at
Mathematics. Springer- Verlag New York, Inc.

Gersting J. L. (2014). Mathematical Structures for Computer Science (7th ed.).

W.H. Freeman and Company.

Larson R., Hodgkins A.V.(2009). College Algebra - With Applications For

Business and the Life Sciences. Houghton Mifflin Company

Rosen K. H. (2011). Discrete Mathematics and its applications (7th ed.).

McGraw Hill Education (India) Private Limited

UU-MTH- 1005 Discrete Mathematics Page 14