Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

COMPUTATIONAL MATHEMATICS
SUBJECT CODE-24BSCSMA11

Dr. Vishal Patil

Module-1: Relations and functions
Dr. Vishal Patil
AIML-A

Department of Basic Sciences- Mathematics

FET, Jain(Deemed-to-be-University)
CONTENT MODULE – I
Relations and functions
08hours

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Cartesian product of sets. • Definition and Examples

• Definition and Examples

Dr. Vishal Patil

Relations • Types of relations with Examples
• Problems

• Definitions and Examples

Functions • Types of functions and Examples
• Problems

Stirling Numbers of • Definition and Example

second kind • Problems

Composition of functions, • Definitions with Examples

Inverse Functions • Problems

11-09-2024 BRIDGE COURSE-2024 2

Cartesian Product of Sets

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Let 𝐴 and 𝐵 be two sets. Then the set of all ordered pairs (a, b), where 𝑎 ∈ 𝐴 and b ∈
𝐵, is called the Cartesian Product, or Cross Product or Product Set of 𝐴 𝑎𝑛𝑑 𝐵 (in this

Dr. Vishal Patil

order) and is denoted by 𝐴 × 𝐵 Thus,
𝐴 × 𝐵 = (𝑎, 𝑏)|𝑎 ∈ 𝐴 𝑎𝑛𝑑 𝑏 ∈ 𝐵 .

It is to be noted that the product set 𝐴 × 𝐵 is not the same as the product set B× 𝐴
that is, 𝐴 × 𝐵 ≠ B × 𝐴. in general. Because,

𝐵 × 𝐴 = (𝑏, 𝑎)|𝑏 ∈ 𝐵 𝑎𝑛𝑑 𝑎 ∈ 𝐴

And (𝑎, 𝑏) ≠ (𝑏, 𝑎)in general.

11-09-2024 BRIDGE COURSE-2024 3
Contd…

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

For example, if 𝐴 = {1, 0, − 1} and 𝐵 = 2, 3 , then

𝐴 × 𝐵 = {(1, 2), (1, 3), (0, 2), (0, 3), (− 1, 2), (− 1, 3)} and

Dr. Vishal Patil

𝐵 × 𝐴 = { 2, 1 , 2, 0 , 2, − 1 , 3, 1 , 3, 0 , 3, − 1 }

Evidently, 𝐴 × 𝐵 ≠ B × 𝐴.

It should be noted that 𝐴 × 𝐵 can be defined even when B = A Thus, we can have the
product of a set A with itself, and this product is defined by
𝐴 × 𝐴 = (𝑎, 𝑏)|𝑎 ∈ 𝐴 𝑎𝑛𝑑 𝑏 ∈ 𝐴

The product 𝐴 × 𝐴 is also denoted by 𝐴2 "

11-09-2024 BRIDGE COURSE-2024 4
Examples

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Note:

If A and B are finite then the Cardinality of 𝐴 × 𝐵 = 𝐴 × 𝐵 .

Dr. Vishal Patil

𝐴 = 𝑚, 𝐵 = 𝑛 then total number of relations from 𝐴 to 𝐵 formed is given by 2𝑚𝑛 .

Example 1: Let 𝐴 = 1,2,3 and B= {𝑝, 𝑞, 𝑟}, then

𝐴×𝐵 = 1, 𝑝 , 1, 𝑞 , 1, 𝑟 , 2, 𝑝 , 2, 𝑞 , 2, 𝑟 , 3, 𝑝 , 3, 𝑞 , 3, 𝑟

and 𝐴 × 𝐵 = 𝐴 × 𝐵 = 3 × 3 = 9.

11-09-2024 BRIDGE COURSE-2024 5

Examples

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Example 2: Let 𝐴 = {2,3,4} and 𝐵 = 4,5 . Find

i. 𝐴×𝐵

ii. 𝐵 × 𝐴

Dr. Vishal Patil

iii. |𝐴 × 𝐵|

iv. |𝐵 × 𝐴| iii. 𝐴 × 𝐵 = 6

Solution: iv. 𝐵 × 𝐴 = 6.

i. 𝐴 × 𝐵 = { 2,4 , 2,5 , 3,4 , 3,5 , 4,4 , (4,5)} Note:

ii. 𝐵 × 𝐴 = { 4,2 , 4,3 , 4,4 , 5,2 , 5,3 , (5,4)} Although we generally will not have 𝐴 × 𝐵 = 𝐵 × 𝐴,
but we will have 𝐴 × 𝐵 = 𝐵 × 𝐴 .
11-09-2024 BRIDGE COURSE-2024 6
Examples

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Example 3: Let 𝐴 = {𝟏, 𝟑, 𝟓}, 𝐵 = {𝟐, 𝟑} 𝒂𝒏𝒅 𝐶 = {𝟒, 𝟔}. Write down the following

I. 𝐴 × 𝐵
II. 𝐵 × 𝐴

Dr. Vishal Patil

III. 𝐵 × 𝐶
IV. 𝐴 × 𝐶
V. (𝐴 𝖴 𝐵) × 𝐶
VI. 𝐴 𝖴 (𝐵 × 𝐶)
VII. (𝐴 × 𝐵) 𝖴 𝐶
VIII.𝐴 ∩ (𝐵 × 𝐶)
IX. (𝐴 × 𝐵) 𝖴 (𝐵 × 𝐶)
X. (𝐴 × 𝐵) ∩ (𝐵 × 𝐴)
XI. (𝐴 × 𝐵) ∩ (𝐵 × 𝐶)

11-09-2024 BRIDGE COURSE-2024 7

Relations

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

A relation 𝑅 from a non-empty set 𝐴 to a non-empty set 𝐵 is a subset of a Cartesian
product 𝐴 × 𝐵, i.e., if 𝑎, 𝑏 ∈ 𝑅, we say that 𝑎 is related 𝑏 and we write 𝑎𝑅𝑏.

Dr. Vishal Patil

If 𝑅1 ⊆ 𝐴 × 𝐵, then 𝑅1 is called relation from A to B.

Note:

When a relation is defined on 𝐴 i.e., (𝐴 𝑡𝑜 𝐴) then the relation is called binary relation.

11-09-2024 BRIDGE COURSE-2024 8

Contd…

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Let 𝐴 = 1,2,3 and B= 𝑝, 𝑞, 𝑟

Let 𝑅1 = 1,1 , 2,2 , 3,3 .

Dr. Vishal Patil

Then 𝑅1 is not a subset of A × 𝐵. Therefore, 𝑅1 is not a relation from A to B.

Let 𝑅2 = 1, 𝑝 , 1, 𝑞 , 1, 𝑟

Let 𝑅2 = 1, 𝑝 , 1, 𝑞 , 1, 𝑟 ⊆ 𝐴 × 𝐵. Therefore, 𝑅2 is a relation from A to B.

Let 𝑅3 = 1, 𝑝 , 1, 𝑞 , 1, 𝑟 , 2, 𝑝 , 2, 𝑞 , 2, 𝑟 , 3, 𝑝 , 3, 𝑞 , 3, 𝑟 ,
since every set is a subset of itself, therefore, R 3 ⊆ 𝐴 × 𝐵. Therefore, 𝑅3 is also a relation from A to B.

11-09-2024 BRIDGE COURSE-2024 9

Different types of relations

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

1. Reflexive relation:

A relation 𝑅 defined on set 𝐴 is called reflexive relation if 𝑎𝑅𝑎, 𝑜𝑟 𝑎, 𝑎 ∈ 𝑅, ∀ 𝑎 ∈ 𝐴.

Dr. Vishal Patil

• Note:

• A relation in which no element is related to itself is called Irreflexive relation.

• In the relation if at least one element is not related itself then it is called Non-
reflexive.

11-09-2024 BRIDGE COURSE-2024 10

 Contd…

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Example: Let 𝐴 = 1,2,3,4 then

• 𝑅1 = 1,1 , 2,2 , 3,3 , 4,4 .

𝑅1 = 1,1 , 2,2 , 3,3 , 4,4 ⊆ 𝐴 × 𝐴, therefore 𝑅1 is a relation and is a reflexive relation.

Dr. Vishal Patil

• 𝑅2 = 1,1 , 2,2 , 3,2 , 4,4

Non-reflexive. Since (3,3) is not in 𝑅2

• 𝑅3 = 1,2 , 2,3 , 3,4 , 4,1

Irreflexive. Since no element is related to itself

• 𝑅4 = 1,1 , 1,2 , 2,2 , 3,3 , 4,4 , (4,3)

Reflexive. Since it contains every element which is connected to itself

11-09-2024 BRIDGE COURSE-2024 11
Contd…
2. Symmetric relation:

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Let 𝑅 be a relation defined on set 𝐴, then 𝑅 is called symmetric relation

if 𝑎𝑅𝑏 ⇒ 𝑏𝑅𝑎, i.e., whenever 𝑎, 𝑏 ∈ 𝑅, then 𝑏, 𝑎 ∈ 𝑅 for every 𝑎, 𝑏 ∈ 𝑅.

Dr. Vishal Patil

Example

• Let 𝐴 = 1,2,3,4 then

• 𝑅1 = 1,2 , 2,1 , 3,2 , 2,3 , 4,4 → Symmetric.

• 𝑅2 = 1,2 , 3,2 , 2,3 , 4,4 → Not symmetric (Asymmetric).

• 𝑅3 = 1,1 , 2,2 , 3,3 , 4,4 → Symmetric.

• 𝑅4 = ∅ → Symmetric.
11-09-2024 BRIDGE COURSE-2024 12
Contd…

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

3. Transitive relation:

Let 𝑅 is a relation defined on a set 𝐴. Then 𝑅 is called transitive relation

Dr. Vishal Patil

𝐼𝑓 𝑎𝑅𝑏 𝑎𝑛𝑑 𝑏𝑅𝑐 ⇒ 𝑎𝑅𝑐 .

Example

• Let 𝐴 = 1,2,3,4,5 then

• 𝑅1 = 1,2 , 2,3 , 1,3 , 3,4 , 4,5 , 3,5 , 1, 4 , (3, 5) → Transitive.

• 𝑅2 = 1,2 , 2,3 → Not Transitive.

11-09-2024 BRIDGE COURSE-2024 13

Contd…

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Equivalence relation:

A relation 𝑅 is defined on a set 𝐴. then 𝑅 is called an equivalence relation. If it is

Dr. Vishal Patil

reflexive, symmetric, and transitive.

Example

• Let 𝐴 = 1,2,3,4 then

• 𝑅1 = 1,1 , 1,2 , 2,1 , 2,2 , 3,3 , 4,4 → equivalence relation.

• 𝑅2 = 1,1 , 1,3 , 2,2 , 3,3 , 3,2 → Not equivalence relation .

11-09-2024 BRIDGE COURSE-2024 14

Problems

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

1. Let 𝐴 = 2,4,6,8 and 𝐵 = 1,2,3 and let relations 𝑅1 , 𝑅2 , 𝑅3 , 𝑅4 from 𝐴 to 𝐵 be defined as follows :

i. 𝑎𝑅1 𝑏 if 𝑎 ≤ 𝑏 ii. 𝑎𝑅2 𝑏 if 𝑎 > 𝑏 iii. 𝑎𝑅3 𝑏 if 𝑎 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑏

Dr. Vishal Patil

iv. 𝑎𝑅4 𝑏 if 𝑏 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑎.

Solution: Given that 𝐴 = 2,4,6,8 and 𝐵 = 1,2,3

∴𝐴×𝐵 = 2,1 , 2,2 , 2,3 , 4,1 , 4,2 , 4,3 , 6,1 , 6,2 , 6,3 , 8,1 , 8,2 , 8,3

i) 𝑅1 = 2,2 , 2,3

ii) 𝑅3 𝑅2 = 2,1 , 4,1 , 4,2 , 4,3 , 6,1 , 6,2 , 6,3 , 8,1 , 8,2 , 8,3

iii)= 2,2 and iv). 𝑅4 = 2,1 , 2,2 , 4,1 , 4,2 , 6,1 , 6,2 , 6,3 , 8,1 , 8,2
11-09-2024 BRIDGE COURSE-2024 15
2. Let 𝑨 and 𝑩 be finite sets with 𝑩 = 𝟑. If there are 4096 relations from 𝑨 𝒕𝒐 𝑩 then what is |𝑨|?

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Solution
We know that if 𝐴 = 𝑚, 𝐵 = 𝑛 then total number of relations from 𝐴 to 𝐵 formed is given by 2𝑚𝑛
It is given that 𝐵 = 3 = 𝑛
Thus, we have

Dr. Vishal Patil

23𝑚 = 4096
log 23𝑚 = log 4096
3𝑚 log 2 = log 4096

log 4096
𝑚=
3 log 2
𝑚 = 4 = |𝐴|
Or
23𝑚 = 4096 = 212 = 23×4
Hence 𝑚 = 4

16
3. Let 𝐴 = 1,2,3,4 and 𝐵 = 1,2,3 , 𝑅1 , 𝑅2 , 𝑅3 are relations on A defined as follows

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

i) 𝑎𝑅1 𝑏 if 𝑎 ≤ 𝑏
ii) 𝑎𝑅2 𝑏 if 𝑎 > 𝑏
iii)𝑎𝑅3 𝑏 if 𝑎 𝑖𝑠 𝑜𝑑𝑑 𝑏 𝑎𝑛𝑑 𝑏 𝑖𝑠 𝑒𝑣𝑒𝑛[Homework].

Dr. Vishal Patil

4.

Solution:

17
5. Show that the following relation 𝑹 defined on the set of all integers 𝒁 is an equivalence relation. 𝑹 = { 𝒙, 𝒚 : 𝒙, 𝒚 ∈ 𝒁 𝒂𝒏𝒅 (𝒙 −
𝒚)𝒊𝒔 𝒂𝒏 𝒆𝒗𝒆𝒏 𝒏𝒖𝒎𝒃𝒆𝒓} .

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Solution:
It is given that 𝑥𝑅𝑦 iff 𝑥 − 𝑦[= 2𝑚] is an even number
We shall show that 𝑅 is reflexive, symmetric, transitive.
Reflexive relation:
Let us consider 𝑥𝑅𝑥 i.e., 𝑥 − 𝑥 = 0 = 2(0) is an even number. Hence 𝑅 is Reflexive

Dr. Vishal Patil

Symmetric Relation:
Let 𝑥𝑅𝑦 ⇒ 𝑥 − 𝑦 = 2𝑚 is even integer 𝑚 ∈ 𝑍
∴ 𝑦𝑅𝑥 ⇒ 𝑦 − 𝑥 = − 𝑥 − 𝑦 = −2𝑚 = 2(−𝑚) is also an even integer
That is 𝑥𝑅𝑦 ⇒ 𝑦𝑅𝑥. Hence 𝑅 is Symmetric
Transitive Relation:
Let 𝑥𝑅𝑦 ⇒ (𝑥 − 𝑦) is even. That is 𝑥 − 𝑦 = 2𝑚(say), 𝑚 ∈ 𝑍.
𝑦𝑅𝑧 = (𝑦 − 𝑧) is even. That is 𝑦 − 𝑧 = 2𝑛(say), 𝑛 ∈ 𝑍.
Now 𝑥 − 𝑦 + 𝑦 − 𝑧 = 2𝑚 + 2𝑛
𝑥 − 𝑧 = 2 𝑚 + 𝑛 = 2𝑘(say) 𝑘 = 𝑚 + 𝑛 ∈ 𝑍 is also even ⇒ 𝑥𝑅𝑧
That is 𝑥𝑅𝑦, 𝑦𝑅𝑧 ⇒ 𝑥𝑅𝑧. Hence 𝑅 is transitive.
Thus, we conclude that the relation 𝑅 is equivalence relation.
6. Show that the following relation 𝑹 defined on the set of all integers 𝒁 is an equivalence relation. 𝑹 = { 𝒙, 𝒚 : 𝒙, 𝒚 ∈ 𝒁 𝒂𝒏𝒅 (𝒙 −
𝒚) 𝒊𝒔 𝒂 𝒎𝒖𝒍𝒕𝒊𝒑𝒍𝒆 𝒐𝒇 𝟓} [homework].

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

7. Show that the relation congruence modulo 𝒎, 𝒂 ≡ 𝒃 𝒎𝒐𝒅 𝒎 on the set of all positive integers 𝒁 is an equivalence relation.
Solution
By the definition of congruence modulo 𝑚, 𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑚 ⇒ 𝑚 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑎 − 𝑏 ⇒ 𝑎 − 𝑏 = 𝑘𝑚 where 𝑚 is fixed and 𝑎, 𝑏, 𝑘 ∈ 𝑍
We shall show that relation 𝑅 = { 𝑎, 𝑏 : (𝑎 − 𝑏) = 𝑘𝑚} is an equivalence relation

Dr. Vishal Patil

Reflexive relation:
𝑎𝑅𝑎 𝑖𝑠 𝑎 − 𝑎 = 0 and 𝑚 divides 0. Hence 𝑅 is reflexive.
Symmetric Relation:
𝑎𝑅𝑏 ⇒ 𝑎 − 𝑏 = 𝑘𝑚
∴ 𝑏𝑅𝑎 = 𝑏 − 𝑎 = − 𝑎 − 𝑏 = −𝑘𝑚 ⇒ 𝑚 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 (𝑏 − 𝑎)
That is 𝑎𝑅𝑏 ⇒ 𝑏𝑅𝑎. Hence 𝑅 is Symmetric
Transitive Relation:
𝑎𝑅𝑏 ⇒ 𝑎 − 𝑏 = 𝑘𝑚 and 𝑏𝑅𝑐 = (𝑏 − 𝑐) = 𝑙𝑚 where 𝑘, 𝑙 ∈ 𝑍.
Now 𝑎 − 𝑐 = 𝑎 − 𝑏 + 𝑏 − 𝑐 = 𝑘𝑚 + 𝑙𝑚 = 𝑘 + 𝑙 𝑚, 𝑘+𝑙 ∈𝑍
∴ 𝑎 − 𝑐 = 𝑘 + 𝑙 𝑚 ⇒ 𝑚 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑎 − 𝑐 𝑜𝑟 𝑎 ≡ 𝑐(𝑚𝑜𝑑 𝑚)
That is 𝑎𝑅𝑏, 𝑏𝑅𝑐 ⇒ 𝑎𝑅𝑐. Hence 𝑅 is transitive.
Thus, we conclude that the relation 𝑅 is equivalence relation.
Functions

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

A function in mathematical relationship among the inputs (i.e. the domain) and their
outputs (known as the codomain) where each input has exactly one output, and the

Dr. Vishal Patil

output can be traced back to its input.

An example of a simple function is f(x) = x2. In this function, the function f(x) takes the
value of “x” and then squares it. For instance, if x = 3, then f(3) = 9. A few more

examples of functions are: f(x) = sin x, f(x) = x2 + 3, f(x) = 1/x, f(x) = 2x + 3, etc.

11-09-2024 BRIDGE COURSE-2024 20

12-09-2024
Examples:

BRIDGE COURSE-2024
21

Dr. Vishal Patil

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)
One-to-One function/Injective function

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

One-to-One function/Injective function define that each element of one set, say Set (A) is mapped with
a unique element of another set, say, Set (B).

Dr. Vishal Patil

(or)

An injective function (injection) or one-to-one function is a

function that maps distinct elements of its domain to

distinct elements of its codomain.

Formally, it is stated as, if f(x) = f(y) implies x = y, then f is one-to-one mapped, or f is 1-1.

And equivalently, if x ≠ y, then f(x) ≠ f(y).

11-09-2024 BRIDGE COURSE-2024 22

Examples:

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

1. The function 𝑔 𝑥 = 𝑥 + 1 is a one to one function since it produces a different answer for every
input. Also, the function 𝑔(𝑥) = 𝑥2 is NOT a one to one function since it produces 4 as the answer when
the inputs are 2 and -2.

Dr. Vishal Patil

• In Fig(a), for each x value, there is only one unique value of f(x) and thus, f(x) is one to one function.

• In Fig (b), different values of x, 2, and -2 are mapped with a common g(x) value 4 and (also, the
different x values -4 and 4 are mapped to a common value 16). Thus, g(x) is a function that is not a one
to one function.
11-09-2024 BRIDGE COURSE-2024 23
Onto function or surjective function

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Consider two sets, Set A and Set B, which consist of elements. If for every element of B, there is at least
one or more than one element matching with A, then the function is said to be onto function or surjective
function.

Dr. Vishal Patil

Formally, a function f:A→B is onto if,
for every element b ∈ B, there exists an
element
a ∈ A such that f(a)=b.

In the first figure, you can see that for each element of B, there is a pre-image or a matching element in Set
A. Therefore, it is an onto function. But if you see in the second figure, one element in Set B is not mapped
with any element of set A, so it’s not an onto or surjective function.

11-09-2024 BRIDGE COURSE-2024 24

12-09-2024
BRIDGE COURSE-2024
25

Dr. Vishal Patil

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)
Examples:

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

1. Let A = {1, 5, 8, 9) and B {2, 4} And f={(1, 2), (5, 4), (8, 2), (9, 4)}. Then prove f is a onto function.

Solution:

From the question itself we get,

Dr. Vishal Patil

A={1, 5, 8, 9)

B{2, 4}

& f={(1, 2), (5, 4), (8, 2), (9, 4)}

So, all the element on B has a domain element on A or we can say element 1 and 8 & 5 and 9 has same
range 2 & 4 respectively.

Therefore, f: A → B is a surjective function.

11-09-2024 BRIDGE COURSE-2024 26
Examples:

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

2. Is f (x) = x³ one-to-one where f : R→R ?

Solution:

Dr. Vishal Patil

This function is One-to-One.

This cubic function possesses the property that each x-value has one unique y-value that is not used by any
other x-element. This characteristic is referred to as being 1-1.

Also, in this function, as you progress along the graph, every possible y-value is used, making the function
onto.

11-09-2024 BRIDGE COURSE-2024 27

Bijective or bijection

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

A function is said to be bijective or bijection, if a function f: A → B satisfies both the injective (one-to-one
function) and surjective function (onto function) properties.

Dr. Vishal Patil

From the above examples of bijective function, we can observe that every element of set B has been
related to a distinct element of set A. The non-bijective functions have some element in set B which do not
have a pre-image in set A, or some of the elements in set B is the image for more than one element in set
A.
11-09-2024 BRIDGE COURSE-2024 28
11-09-2024
Example

BRIDGE COURSE-2024
29

Dr. Vishal Patil

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)
 The Ceiling and Floor Function

30

Dr. Vishal Patil

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)
 The Ceiling and Floor Function

31

Dr. Vishal Patil

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)
 The Max Function

32

Dr. Vishal Patil

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)
 The Min Function

33

Dr. Vishal Patil

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)
 The Algebra of Functions

34

Dr. Vishal Patil

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)
 Example-1
The Algebra of Functions

35

Dr. Vishal Patil

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)
Applications of Onto Functions

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

• Linear transformations: In linear algebra, onto functions are used to represent linear transformations
that preserve the dimensionality of a vector space.
• Data compression: Onto functions are used in data compression algorithms to map high-dimensional
data onto lower-dimensional spaces. This reduces the amount of data required to represent the

Dr. Vishal Patil

original information.
• Cryptography: Onto functions are used in cryptography to create one-way functions that are easy to
compute in one direction but difficult to reverse. This makes them useful for generating public and
private keys in secure communication systems.
• Image and signal processing: In image and signal processing, onto functions are used to map high-
dimensional signals onto lower-dimensional spaces for analysis and compression.
• Computer science: Onto functions are used in computer science for a variety of applications, such as in
database queries, program optimization, and machine learning algorithms.

12-09-2024 BRIDGE COURSE-2024 36

Stirling Numbers of the Second kind

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Let 𝐴 and 𝐵 be finites sets with 𝐴 = 𝑚 and 𝐵 = 𝑛, where 𝑚 ≥ 𝑛. Then the number
of onto function from 𝐴 to 𝐵 is given by the formula:

Dr. Vishal Patil

𝑛

𝑝 𝑚, 𝑛 = ෍ −1 𝑘 𝑛𝐶 𝑛−𝑘 𝑚
𝑛−𝑘
𝑘=0
With 𝑝(𝑚, 𝑛) given by the above formula, the number 𝑝(𝑚, 𝑛)/𝑛! is called the Stirling
number of the second kind and is denoted by 𝑆(𝑚, 𝑛).
Thus by definition,
𝑛
𝑝 𝑚, 𝑛 1 𝑘 𝑛 𝑚
𝑆 𝑚, 𝑛 = = ෍ −1 𝐶𝑛−𝑘 𝑛−𝑘 𝑓𝑜𝑟 𝑚 ≥ 𝑛
𝑛! 𝑛!
𝑘=0

11-09-2024 BRIDGE COURSE-2024 37

Contd…

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

This number represents the number of ways in which it is possible to assign 𝑚 distinct
objects into 𝑛 identical places with no place left empty.

Dr. Vishal Patil

It is easy to check 𝑆 𝑚, 1 = 1 𝑎𝑛𝑑 𝑆 𝑚, 𝑚 = 1 for all 𝑚 ≥ 1.

It can be shown that the number of possible ways to assign 𝑚 distinct objects to 𝑛
identical places with empty places allowed is given by formula.

𝑝 𝑚 = ෍ 𝑆 𝑚, 𝑖 . 𝑓𝑜𝑟 𝑚 ≥ 𝑛
𝑖=1

11-09-2024 BRIDGE COURSE-2024 38

Problems

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

1. Let 𝐴 = 1, 2, 3, 4, 5, 6, 7 and 𝐵 = 𝑤, 𝑥, 𝑦, 𝑧 . Find the number of onto functions
from 𝐴 𝑡𝑜 𝐵.
Solution: Here 𝑚 = 𝐴 = 7 and n = 𝐵 = 4.

Dr. Vishal Patil

Therefore, the number of onto function from 𝐴 𝑡𝑜 𝐵 is

𝑝 𝑚, 𝑛 = ෍ −1 𝑘 𝑛𝐶 𝑛−𝑘 𝑚
𝑛−𝑘
𝑘=0

4
𝑘 4 7
𝑝 7, 4 = ෍ −1 𝐶4−𝑘 4−𝑘
𝑘=0

= 4𝐶4 × 47 − 4𝐶3 × 37 + 4𝐶2 × 27 − 4𝐶1 × 17 + 0 = 8400

11-09-2024 BRIDGE COURSE-2024 39
2. Evaluate 𝑆 5, 4 𝑎𝑛𝑑 𝑆 8, 6 .
Solution: By definition we have

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

𝑛
1 𝑘 𝑛𝐶 𝑚
𝑆 𝑚, 𝑛 = ෍ −1 𝑛−𝑘 𝑛−𝑘 𝑓𝑜𝑟 𝑚 ≥ 𝑛
𝑛!
𝑘=0
Therefore,
𝑛
1

Dr. Vishal Patil

𝑘 4 5
𝑆 5, 4 = ෍ −1 𝐶4−𝑘 4−𝑘
4!
𝑘=0

1 5 4 5 4 5 4 5
240
= 4 − 𝐶3 × 3 + 𝐶2 × 2 − 𝐶1 × 1 = = 10
4! 4!
𝑛
1 𝑘 6 8
𝑆 8, 6 = ෍ −1 𝐶6−𝑘 6−𝑘 = 266
6!
𝑘=0

11-09-2024 BRIDGE COURSE-2024 40

[Link] are six programmers who can assist eight executives. In how many ways can
the executives be assisted so that each programmer assists at least one executive?

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Solution:
Let A denote the set of executives and B denote the set of programmers. Then the
required number is equal to the number of onto functions from A to B.

Dr. Vishal Patil

This number 𝑖𝑠 𝑝(8, 6) = (6!) × 𝑆 (8,6).
1 𝑛 𝑘 6 8
𝑆 8, 6 = σ −1 𝐶6−𝑘 6−𝑘 = 266
6! 𝑘=0

Therefore, 𝑝(8, 6) = (6!) × 266

= 720 × 266 = 191520.
This is the required number.

11-09-2024 BRIDGE COURSE-2024 41

4. Find the number of ways of distributing four distinct objects among three identical containers, with
some container(s) possibly empty.

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Solution: Here, the number of objects is m = 4 and the number of containers is n = 3.
Therefore, the required number is
𝑛

𝑝 𝑚 = ෍ 𝑆 𝑚, 𝑖 .
𝑖=1

Dr. Vishal Patil

𝑝 4 = σ3𝑖=1 𝑆 4, 𝑖 = 𝑆 4, 1 + 𝑆 4, 2 + 𝑆 4, 3
1 1
• 𝑆 4, 1 = σ𝑘=0 −1 𝑘 1𝐶1−𝑘 1 − 𝑘 4 =1
1!
1
• 𝑆 4, 2 = σ2𝑘=0 −1 𝑘 2𝐶2−𝑘 2 − 𝑘 4
2!
1
= 24 − 2 × 14 = 7
2
1
• 𝑆 4, 3 = σ3𝑘=0 −1 𝑘 3𝐶3−𝑘 3 − 𝑘 4
3!
1
= 34 − 3 × 24 + 3 × 14 = 6
6
Thus required number is 𝑝 4 = 1 + 7 + 6 = 14
11-09-2024 BRIDGE COURSE-2024 42
Composition of Functions

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Consider three non-empty sets 𝐴, 𝐵, 𝐶 (which are not necessarily distinct) and the functions 𝑓 ∶ 𝐴 −>
𝐵 𝑎𝑛𝑑 𝑔 ∶ 𝐵 −> 𝐶 . The composition (or product) of these two functions is defined as the function
𝑔𝑜𝑓: 𝐴 −> 𝐶 with (𝒈 𝒐 𝒇) (𝒂) = 𝒈 𝒇(𝒂) . for all 𝑎 ∈ 𝐴.

Dr. Vishal Patil

The pictorial representation of 𝑔 𝑜 𝑓 is shown in Figure.

For a function f: A -> A fo f is denoted 𝑏𝑦 𝑓 2 , 𝑓𝑜𝑓 2 is denoted by 𝑓 3 and so on.

For any integer n >= 2 the function (𝑓 𝑛 ) : A -> A is defined recursively by

𝑓 1 = 𝑓, 𝑓 𝑛 = 𝑓 ∗ 𝑓 𝑛−1

11-09-2024 BRIDGE COURSE-2024 43

Examples

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

1. Let 𝐴 = {1, 2, 3, 4} 𝐵 = {𝑎, 𝑏, 𝑐} 𝑎𝑛𝑑 𝐶 = {𝑤, 𝑥, 𝑦, 𝑧} with 𝑓 ∶ 𝐴 −> 𝐵 𝑎𝑛𝑑 𝑔 ∶ 𝐵 −> 𝐶 given
by
𝑓 = {(1, 𝑎) , (2, 𝑎), (3, 𝑏), (4, 𝑐)}, and 𝑔 = 𝑎, 𝑥 , 𝑏, 𝑦 , 𝑐, 𝑧 . Find 𝑔 𝑜 𝑓

Dr. Vishal Patil

Solution: We find, by using the definitions of f and g, that
(𝑔 𝑜 𝑓) (1) = 𝑔(𝑓(1)) = 𝑔(𝑎) = 𝑥 ,
(𝑔 𝑜 𝑓)(2) = 𝑔{𝑓(2)} = 𝑔(𝑎) = 𝑥 .
(𝑔 𝑜 𝑓)(3) = 𝑔(𝑓(3)) = 𝑔(𝑏) = 𝑦
(𝑔 𝑜 𝑓)(4) = 𝑔(𝑓(4)) = 𝑔(𝑐) = 𝑧 .

𝑇ℎ𝑢𝑠, 𝑓 = {(1, 𝑥), (2, 𝑥), (3, 𝑦), (4, 𝑧)}.

11-09-2024 BRIDGE COURSE-2024 44

2. Consider the functions f and g defined by 𝒇(𝒙) = 𝒙𝟑 and 𝒈 𝒙 = 𝒙𝟐 + 𝟏. ∀𝒙 ∈ 𝑹
Find 𝒈 𝒐 𝒇, 𝒇 𝒐 𝒈, 𝒇𝟐 and 𝒈𝟐

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Solution: Here, both 𝑓 and 𝑔 are defined on 𝑅.
Therefore, all of the functions 𝑔 𝑜 𝑓, 𝑓 𝑜 𝑔, 𝑓 2 = 𝑓 𝑜 𝑓and 𝑔2 = 𝑔 𝑜 𝑔 defined on 𝑅,
and we find that

Dr. Vishal Patil

(𝑔 𝑜 𝑓) (𝑥) = 𝑔(𝑓(𝑥)) = 𝑔(𝑥 3 ) = (𝑥 3 )^2 + 1 = 𝑥 6 + 1 .

(𝑓 𝑜 𝑔) (𝑥) = 𝑓{𝑔(𝑥)} = 𝑓(𝑥 2 + 1) = 𝑥 2 + 1 3

𝑓 2 (𝑥) = (𝑓 𝑜 𝑓)(𝑥)= 𝑓(𝑓(𝑥)) = f(𝑥 3 ) = 𝑥 3 3 = 𝑥9.

𝑔2 (𝑥) = (𝑔 𝑜 𝑔) (𝑥) = 𝑔{𝑔(𝑥)} = 𝑔(𝑥 2 + 1) = 𝑥 2 + 1 2 + 1.

The above expressions define the function's 𝑔 𝑜 𝑓, 𝑓 𝑜 𝑔, 𝑓 2 and 𝑔2 respectively.

11-09-2024 BRIDGE COURSE-2024 45
3. Let 𝒇and 𝒈 be functions from 𝑹 𝒕𝒐 𝑹 defined by 𝒇 𝒙 = 𝒂𝒙 + 𝒃 and 𝒈 𝒙 = 𝟏 − 𝒙 + 𝒙𝟐
𝒊𝒇(𝒈 𝒐 𝒇) (𝒙) = 𝟗𝒙𝟐 − 𝟗𝒙 + 𝟑 , determine 𝒂, 𝒃.

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Solution:
We have.
9𝑥 2 − 9𝑥 + 3 = 𝑔 𝑜 𝑓 𝑥

Dr. Vishal Patil

= 𝑔 𝑓 𝑥 = 𝑔 𝑎𝑥 + 𝑏
= 1 − 𝑎𝑥 + 𝑏 + 𝑎𝑥 + 𝑏 2

= 𝑎2 × 𝑥 2 + (2𝑎𝑏 − 𝑎) × 𝑥 + (1 − 𝑏 + 𝑏2 ) .
Comparing the corresponding coefficients,
we get 9 = 𝑎2 , 9 = 𝑎 − 2𝑎𝑏, 3 = 1 − 𝑏 + 𝑏 2
The first of these gives 𝑎 = ± 3 For 𝑎 = 3 the second and third are satisfied if 𝑏 = − 1. For 𝑎 =
− 3 we get 𝑏 = 2 .
Thus, 𝑎 = 3 𝑏 = − 1 𝑎𝑛𝑑 𝑎 = − 3, 𝑏 = 2 are the required values of 𝑎, 𝑏.

11-09-2024 BRIDGE COURSE-2024 46

Theorem : (without Proof)
Let f : A -> B and g : B -> C be any two functions. Then the following are

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

true
(1) If 𝑓 𝑎𝑛𝑑 𝑔 are one-to-one, so is 𝑔 𝑜 𝑓
(2) If 𝑔 𝑜 𝑓 is one-to-one, then 𝑓 is one-to-one.

Dr. Vishal Patil

(3) If 𝑓 and g are onto, so is 𝑔 𝑜 𝑓.
(4) If 𝑔 𝑜 𝑓 is onto, then 𝑔 is onto.

11-09-2024 BRIDGE COURSE-2024 47

Invertible functions

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

A function f : A → B is said to be invertible if there exists a function g : B → A such that g ○ f = IA and f ○
g = IB , where IA, is the identity function on A and IB is the identity function on B.
• Then, g is called an inverse of f and we write g = f -1

Dr. Vishal Patil

12-09-2024 BRIDGE COURSE-2024 48
Examples:

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Example 1: Let A = {1, 2, 3, 4} and f and g be (f ○ g) (1) = f{g(1)} = f(2) = 1 = IA(1),
functions from A to A given by (f ○ g) (2) = f{g(2)} = f(3) = 2 = IA(2),
f ={(1,4), (2, 1), (3, 2), (4,3)} and g ={(1, 2) , (2, 3), (f ○ g) (3) = f{g(3)} = f(4) = 2 = I (3),

Dr. Vishal Patil

A
(3,4), (4, 1)}.
(f ○ g) (4) = f{g(4)} = f(1) = 2 = IA(4),
Prove that f and g are inverses of each other
Solution: We check that Thus, for all x e A we have (g ○ f ) (x) = IA(x) and

(g ○ f ) (1) = g{f(1)} = g(4) = 1 = IA(1), underline (f ○ g) (x) = IA(x). Therefore, g is an

(g ○ f ) (2) = g{f(2)} = g(1) = 2 = IA(2), inverse of f, f and is an inverse of g.

(g ○ f ) (3) = g{f(3)} = g(2) = 3 = IA(3),

(g ○ f ) (4) = g{f(4)} = g(3) = 4 = IA(4),

12-09-2024 BRIDGE COURSE-2024 49

Example 2: Consider 𝑓 ∶ 𝑅 → 𝑅 defined by 𝑓(𝑥) = 2𝑥 + 5. Let a 𝑔 ∶ 𝑅 → 𝑅 be defined by 𝑔(𝑥) =

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

1
(𝑥 − 5). Prove that g is an inverse of f.
2

Solution: Then, we check that, for any 𝑥 ∈ 𝑅

(𝑔 ○ 𝑓 ) (𝑥) = 𝑔{𝑓(𝑥)} = 𝑔 (2𝑥 + 5)

Dr. Vishal Patil

1
= (2𝑥 + 5 − 5) = 𝑥 = 𝐼𝑅 (𝑥)
2

1
(𝑓 ○ 𝑔) (𝑥) = 𝑓{𝑔(𝑥)} = 𝑓 (𝑥 − 5)
2

1
= 2 (𝑥 − 5) + 5 = 𝑥 = 𝐼𝑅 (𝑥)
2

These show that g is an inverse of f. It also follows that f is an inverse of g.

12-09-2024 BRIDGE COURSE-2024 50
Theorems:

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

• Theorem 1: If a function f : A → B is invertible then it has a unique inverse. Further, if f(a) = b then f -
1(b) = a.

• Theorem 2: If a function f : A → B is invertible then it has a unique inverse. Further, if f(a) = b then f -

Dr. Vishal Patil

1(b) = a.
• Theorem 3: Let A and B be finite sets with | A | = | B | and f be a function from A to B. Then the
following statements are equivalent.
(1) f is one-to-one (2) f is onto (3) f is invertible
• Theorem 4:If f : A → B and g : B → C are invertible functions, then (g ○ f ) : A → C is an invertible
function and (g ○ f )-1 = f -1 ○ g -1

12-09-2024 BRIDGE COURSE-2024 51

Example 3: Let A = B = R, the set of all real numbers, and the functions f : A → B and g : B → A be

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

1Τ
1 3
defined by f (x) = 2x3 – 1, ∀ 𝑥 ∈ 𝐴; 𝑔 𝑦 = 𝑦+1 , ∀ 𝑦 ∈ 𝐵. Show that each of f and g is the
2

inverse of the other

Solution: We find that, for any x e A,

Dr. Vishal Patil

1Τ
1 3
(g ○ f ) (x) = g{f(x)} = g(y) = 𝑦+1 , where y = f(x)
2

1Τ
1 3
= 2x3 – 1 + 1 where y = f(x) = 2x3 – 1
2

=1

Then g ○ f = IA

12-09-2024 BRIDGE COURSE-2024 52

 1Τ
1 3

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Next, for any y e B, (f ○ g) (y) = f{g(y)} = f 𝑦+1
2

1Τ 3
1 3
=2 𝑦+1 -1

Dr. Vishal Patil

2

1
= 2 (𝑦 + 1) - 1 = y
2

Thus f ○ g = IB

Accordingly, each of f and g is and invertible function, and further more each is the inverse of each other.

12-09-2024 BRIDGE COURSE-2024 53

Homework

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

1. Define Relation? If ‘𝐴’ is a set with ‘𝑚’ elements and ‘𝐵’ is a set with ‘𝑛’elements, find the numberof relations from 𝐴 to 𝐵?
2. Let 𝐴 and 𝐵 be finite sets with𝑛(𝐵) = 3. If there are 4096 relations from 𝐴 to𝐵.What is𝑛(𝐴)?
3. Let 𝐴 = {1,2,3,4,6} and R be the relation on 𝐴 defined by (𝑎, 𝑏) ∈ 𝑅 if and only if ′𝑎′ is a multiple of′𝑏′. Write down 𝑅 as a set of
ordered pairs?

Dr. Vishal Patil

4. Let 𝐴 = {1,2,3} and 𝐵 = {2,4,5}. Determine the following
a. 𝑛(𝐴 × 𝐵)
b. Number of relations from 𝐴 to 𝐵.
c. Number of relations on 𝐴.
5. Define function and the different types of functions with an example.
6. Give examples for

a. one-one function but not onto

b. onto but not one-one
c. both one-one and onto

12-09-2024 BRIDGE COURSE-2024 54

7. Let 𝐴 = {1, 2, 3}, 𝐵 = {2, 4, 5}, Determine the following
7. 𝑛(𝐴 × 𝐵)

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

8. Number of relations from 𝐴 to 𝐵.
9. Number of relations on 𝐴
10. Number of relations from 𝐴 to 𝐵 that contains {(1, 2), (1, 5)}
11. Number of relations from 𝐴 to 𝐵 that contains five ordered pairs

Dr. Vishal Patil

12. Number of relations from 𝐴 to 𝐵 that contain at least seven ordered pairs
8. Define composition of function and inverse of a function? Give Examples?
9. Let 𝐴 = {1, 2, 3}, B = {−1, 0} and 𝑅 be a relation from 𝐴 to 𝐵 defined by 𝑅 = {(1, −1), (1, 0), (2, −1), (3, 0)} Is 𝑅
a function from 𝐴 to 𝐵?
10. Let 𝐴 = {1, 2, 3} and 𝐵 = {−1, 0} and 𝑆 be defined as 𝑆 = {(1, −1), (2, −1), (3, 0)}. Is 𝑆 a function?

11. Let 𝐴 = {1, 2, 3, 4}. Determine whether or not the following relations on 𝐴 are

functions.
7. 𝑓 = {(2, 3), (1, 4), (2, 1), (3, 2), (4, 4)}
8. 𝑔 = {(3, 1), (4, 2), (1, 1)}
9. ℎ = {(2, 1), (3, 4), (1, 4), (4, 4)}
12-09-2024 BRIDGE COURSE-2024 55
12. Let 𝐴 = {0, ±1, ±2, 3}. Consider the function 𝑓 ∶ 𝐴 → 𝑅 defined by 𝑓(𝑥) = 𝑥3 − 2𝑥2 + 3𝑥 + 1 for
𝑥 ∈ 𝐴. Find the range of 𝑓.

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

13. Let 𝑓: 𝑅 → 𝑅 be defined by

3𝑥 − 5 𝑓𝑜𝑟 𝑥 > 0
𝑓 𝑥 ={
−3𝑥 + 1 𝑓𝑜𝑟 𝑥 ≤ 0

Dr. Vishal Patil

5 5
a) determine 𝑓 0 , 𝑓 −1 , 𝑓 , 𝑓(− 3).
3

b) Find 𝑓 −1 (0), 𝑓 −1 (1), 𝑓 −1 (3), 𝑓 −1 (−3), 𝑓 −1 (−6)

c) what are 𝑓 −1 ([−5, 5]) and 𝑓 −1 ([−6, 5])?

12-09-2024 BRIDGE COURSE-2024 56