Topper notes

CHAPTER



1 Relations and Functions



Relations Equivalence Relation
If A and B are two non-empty sets, then a relation R from A to B A relation R on a set A is said to be an equivalence relation, if it is
is a subset of A × B. simultaneously reflexive, symmetric and transitive on A.
Functions
Representation of a Relation
Let and B be two non-empty sets, then a function f from set A
Roster form: In this form, we represent the relation by the set of to set B is a rule which associates each element of A to a unique
all ordered pairs belongs to R. element of B.
Set-builder form: In this form, we represent the relation R from Domain, Codomain and Range of a Function
set A to set B as If f : A → B is a function from A to B, then
R = {(a, b) : a ∈ A, b ∈ B and the rule which relate the elements (i) the set A is called the domain of f(x).
of A  and  B}. (ii) the set B is called the codomain of f(x).
(iii) the subset of B containing only the images of elements of A
Domain, Codomain and Range of a Relation is called the range of f(x).
Let R be a relation from a non-empty set A to a non-empty set  B.
Number of Functions
Then, set of all first components or coordinates of the ordered
Let X and Y be two finite sets having m and n elements respectively.
pairs belonging to R is called the domain of R, while the set of all
Then each element of set X can be associated to any one of n
second components or coordinates of the ordered pairs belonging elements of set Y. So, total number of functions from set X to set
to R is called the range of R. Also, the set B is called the codomain Y is nm.
of relation R.
Number of One-One Functions
Thus, domain of R = {a : (a, b) ∈ R} and range of R = {b : (a, b)
Let A and B are finite sets having m and n elements repectively,
∈ R}
 nP , n ≥ m
then the number of one-one functions from A to B is  m
Types of Relations  0, n < m
Empty or Void Relation: As f ⊂ A × A, for any set A, so f is a
n(n − 1)(n − 2)...(n − (m − 1)), n ≥ m
relation on A, called the empty or void relation. = 
 0, n<m
Universal Relation: Since, A × A ⊆ A × A, so A × A is a relation
on A, called the universal relation.
Number of Onto (or Surjective) Functions
Identity Relation: The relation IA = {(a, a): a ∈ A} is called the
Let A and B are finite sets having m and n elements respectively,
identity relation on A. then number of onto (or surjective) functions from A to B is
Reflexive Relation: A relation R on a set A is said to be reflexive
n m − nC1 (n − 1) m + n C2 (n − 2) m − nC3 (n − 3) m + ..., n < m
relation, if every element of A is related to itself. 
= n !, n=m
Thus, (a, a) ∈ R, ∀ a ∈ A ⇒ R is reflexive. 0,
 n >m
Symmetric Relation: A relation R on a set A is said to be
symmetric relation iff (a, b) ∈ R ⇒ (b, a) ∈ R, ∀ a, b ∈ A Number of Bijective Functions
i.e. a R b ⇒ bRa, ∀ a, b ∈ A Let A and B are finite sets having m and n elements respectively,
Transitive Relation: A relation R on a set A is said to be transitive them number of bijective functions from A to B is
relation, iff (a, b) ∈ R and (b, c) ∈ R n !, if n = m
= 
⇒ (a, c) ∈ R, ∀ a, b, c ∈ A 0, if n > m or n < m