Relations and Functions

• A relation R from a set A to a set B is a subset of A × B obtained by describing a relationship

between the first element a and the second element b of the ordered pairs in A × B. That is, R ⊆
{(a, b) ∈ A × B, a ∈ A, b ∈ B}

• The domain of a relation R from set A to set B is the set of all first elements of the ordered pairs in
R.

• The range of a relation R from set A to set B is the set of all second elements of the ordered pairs
in R. The whole set B is called the co-domain of R. Range ⊆ Co-domain

• A relation R in a set A is called an empty relation, if no element of A is related to any element of

A. In this case, R = ⊂ A × A

Example: Consider a relation R in set A = {3, 4, 5} given by R = {(a, b): ab < 25, where a, b ∈ A}.
It can be observed that no pair (a, b) satisfies this condition. Therefore, R is an empty relation.

• A relation R in a set A is called a universal relation, if each element of A is related to every

element of A. In this case, R = A × A

Example: Consider a relation R in the set A = {1, 3, 5, 7, 9} given by R = {(a, b): a + b is an even
number}.
Here, we may observe that all pairs (a, b) satisfy the condition R. Therefore, R is a universal
relation.

• Both the empty and the universal relation are called trivial relations.

• A relation R in a set A is called reflexive, if (a, a) ∈ R for every a ∈ R.

Example: Consider a relation R in the set A, where A = {2, 3, 4}, given by R = {(a, b): ab = 4, 27
or 256}. Here, we may observe that R = {(2, 2), (3, 3), and (4, 4)}. Since each element of R is
related to itself (2 is related 2, 3 is related to 3, and 4 is related to 4), R is a reflexive relation.

• A relation R in a set A is called symmetric, if (a1, a2) ∈ R ⇒ (a2, a1) ∈ R, ∀ (a1, a2) ∈ R

Example: Consider a relation R in the set A, where A is the set of natural numbers, given by R =
{(a, b): 2 ≤ ab < 20}. Here, it can be observed that (b, a) ∈ R since 2 ≤ ba < 20 [since for natural
numbers a and b, ab = ba] Therefore, the relation R is symmetric.
• A relation R in a set A is called transitive, if (a1, a2) ∈ R and (a2, a3) ∈ R ⇒ (a1, a3) ∈ R for all a1,
a2, a3 ∈ A

Example: Let us consider a relation R in the set of all subsets with respect to a universal set U
given by R = {(A, B): A is a subset of B}
 Now, if A, B, and C are three sets in R, such that A ⊂ B and B ⊂ C, then we also have A ⊂ C.
Therefore, the relation R is a symmetric relation.

• A relation R in a set A is said to be an equivalence relation, if R is altogether reflexive, symmetric,

and transitive.

Example: Let (a, b) and (c, d) be two ordered pairs of numbers such that the relation between
them is given by a + d = b + c. This relation will be an equivalence relation. Let us prove this.
(a, b) is related to (a, b) since a + b = b + a. Therefore, Ris reflexive.
If (a, b) is related to (c, d), then a + d = b + c ⇒ c + b = d + a. This shows that (c, d) is related to
(a, b). Hence, R is symmetric.
Let (a, b) is related to (c, d); and (c, d) is related to (e, f), then a + d = b + c and c + f = d + e.
Now, (a + d) + (c + f) = (b + c) + (d + e) ⇒ a + f = b + e. This shows that (a, b) is related to (e, f).
Hence, R is transitive.
Since R is reflexive, symmetric, and transitive, R is an equivalence relation.

• Given an arbitrary equivalence relation R in an arbitrary set X, R divides X into mutually disjoint
subsets Ai called partitions or subdivisions of X satisfying:

• All elements of Ai are related to each other, for all i.

• No element of Ai is related to any element of Aj , i ≠ j

The subsets Ai are called equivalence classes.

• A function f from set X to Y is a specific type of relation in which every element x of X has one and
only one image y in set Y. We write the function f as f: X → Y, where f (x) = y

• A function f: X → Y is said to be one-one or injective, if the image of distinct elements of X under f

are distinct. In other words, if x1, x2 ∈ X and f (x1) = f (x2), then x1 = x2. If the function f is not one-
one, then f is called a many-one function.

The one-one and many-one functions can be illustrated by the following figures:

• A function f: X → Y can be defined as an onto (surjective) function, if ∀ y ∈ Y, there exists x ∈ X

such that f (x) = y.

The onto and many-one (not onto) functions can be illustrated by the following figures:
• A function f: X → Y is said to be bijective, if it is both one-one and onto. A bijective function can be
illustrated by the following figure:

Example: Show that the function f: R → N given by f (x) = x3 – 1 is bijective.

Solution:Let x1, x2 ∈ R
For f (x1) = f (x2), we have

Therefore, f is one-one.
Also, for any y in N, there exists in R such that

.
Therefore, f is onto.
Since f is both one-one and onto, f is bijective.

• A function f is invertible, if and only if f is bijective.

Example: Show that f: R+ ∪ {0} → N defined as f (x) = x3 + 1 is an invertible function. Also, find f–
1.

Solution:Let x1, x2 ∈ R+ ∪ {0} and f (x1) = f (x2)

Therefore, f is one-one.
Also, for any y in N, there exists R+ ∪ {0} such that = y.
∴ f is onto.
 Hence, f is bijective.
This shows that, f is invertible.
Let us consider a function g: N → R+ ∪ {0} such that Now,

Therefore, we have
and fog (y) = IN

• Relation: A relation R from a set A to a set B is a subset of the Cartesian product A × B, obtained
by describing a relationship between the first element x and the second element y of the ordered
pairs (x, y) in A × B.

• The image of an element x under a relation R is y, where (x, y) ∈ R

• Domain: The set of all the first elements of the ordered pairs in a relation R from a set A to a set
B is called the domain of the relation R.

• Range and Co-domain: The set of all the second elements in a relation R from a set A to a set B
is called the range of the relation R. The whole set B is called the co-domain of the relation R.
Range ⊆Co-domain

Example: In the relation X from W to R, given by X = {(x, y): y = 2x + 1; x ∈ W, y ∈ R}, we obtain

X = {(0, 1), (1, 3), (2, 5), (3, 7) …}. In this relation X, domain is the set of all whole numbers, i.e.,
domain = {0, 1, 2, 3 …}; range is the set of all positive odd integers, i.e., range = {1, 3, 5, 7 …};
and the co-domain is the set of all real numbers. In this relation, 1, 3, 5 and 7 are called the
images of 0, 1, 2 and 3 respectively.
• The total number of relations that can be defined from a set A to a set B is the number of possible
subsets of A × B.

1. If n(A) = p and n(B) = q, then n(A × B) = pq and the total number of relations is 2pq.
2. The number of reflexive relations on an n-element set is 2n(n-1)
3. The number of symmetric relations on a set with the ‘n’ number of elements is 2n(n+1)/2
 NO OF FUNCTIONS

• If a set A has m elements and set B has n elements, then the number of functions possible
from A to B is nm.
• If set A has n elements and set B has m elements, m≥n, then the number of injective
functions or one to one function is given by m!/(m-n)!.
• If a set A has m elements and set B has n elements, then the number of onto functions
from A to B = nm – nC1(n-1)m + nC2(n-2)m – nC3(n-3)m+….- nCn-1 (1)m.
“Note that this formula is used only if m is greater than or equal to n.”
• If there is a bijection between two sets, A and B, then both sets will have the same number
of elements. If n(A) = n(B) = m, then the number of bijective functions = m!.