Counting the Relations (3)

4. Antisymmetric Relations:-

Here Diagonal elements have 2 choices but 

for non-diagonal pairs have three choices:

  • 1st   element of pair is present or 
  • 2nd element of pair is present or
  • Both are absent.

let |A| =n then and R is a relation from A to A, so 

Total number of elements in R = n2 

Total number of Diagonal pair = n

Total number of Non- Diagonal pair = (n^{2}-n)/2 and each have 3 choices

So Total number of  Antisymmetric Relations = 3^{(n^{2}-n)/2}. 2^{n}


5. Asymmetric Relations:

Diagonal pairs have only one choice as they are not allowed here.

Non-Diagonal pairs have three choices:

  • 1st   element of pair is present or 
  • 2nd element of pair is present or
  • Both are absent.
  • So total number of Asymmetric Relation3^{(n^{2}-n)/2}. 1^{n} =3^{(n^{2}-n)/2} 







Non Diagonal Pair and Couting the Relations(2)

3. Symmetric relation:-

Diagonal elements have two choices either they want to be the part or they don't. But for remaining elements, if (a,b) is present then (b, a) must be present.

So  Non - Diagonal elements are chosen in this way to participate in a relation.

the total number of Non-Diagonal element are : n^{2} -n 

 and the total number of Non-Diagonal Pairs are:-  (n^{2}-n)/2

 each pair have two choices: either they want to be part of relation or they don't.

Why we are making pairs:  By making pair we are assuring either both (a,b) and (b, a) is present or both are absent.  Two elements of type (a,b) and (b,a) forms a non-diagonal pair.


So total number of Symmetric relations is:-  2^{(n^{2}-n)/2}. 2^{^{n}}



let us say A={1,2,3} then 

and A relation R from A to A  is shown below:

R= {(1,1) ,(1,2) , (1,3)

        (2,1) ,(2,2) , (2,3)

        (3,1) ,(3,2) ,  (3,3) }

Now If you see ,clearly the bold letters represent a diagonal and and

Total number of diagonal elements is               3

Total number of Non - Diagonal element is :-  6 

Total number of Non - Diagonal pairs :-    6/2=3 and they are like this:-

1^{st} pair ={(1,2)(2,1)}

2^{nd} pair ={(1,3)(3,1)}

3^{rd} pair ={(2,3)(3,2)}


 So total number of Symmetric relations  = 2^{3}. 2^{3} = 64



Couting the Relations

let A  and B are set such that |A| =n  and |B| = m

then  |A*B| = m*n

Relation: It is a subset of cartesian product.

Since already we know |A*B| = m*n and each element in the cartesian product have two choices: either they want to be the part of the relation of they don't want. 

2 choices for m*n elements so total no. relations possible = 2m*n


we have already discussed the types of relations. So let's know some more details:

1. Number of Reflexive relations:-

let |A| = n

Reflexive relations are always defined on the same set :

|A*A| = n2 

if there are n elements in the set then there will be n reflexive pairs like (1,1), (2,2) ... (n,n)

So all these pairs must be present in  reflexive pairs so out of n2 elements n has one choice as they must be the part of relation but remaining  n2 -n has two choice 

So total number of reflexive relations= 1^{n}.2^{n^{2}-n} = 2^{n^{2}-n}


2. The number of Ir-Reflexive relations:

Again those reflexive pairs have only one choice they must not be present so: one choice for 'n' elements and two choices for n2 -n elements.

total number of Ir- reflexive relations= 1^{n}.2^{n^{2}-n} = 2^{n^{2}-n}

Basics of Functions | Function | Types of function

Function:  A relation 'f' from a set 'A' to a set 'B' is called a function if to each element a∈A, we can assign an unique element of 'B'.
It is denoted as f: A→B. A is called domain and B is called co domain.

Range: Range of the function f: A→B is {y | y∈B and (x,y)∈ f}
Types of function:
Injective function (One to One mapping): A function f: A→B is said to be one to one if no two elements in  'A' are mapped to same element of 'B'.
Surjective function (Onto function): A function f: A→B is said to be onto if each element of B is mapped by atleast one element of A, i.e, range of f=B.
Bijective function: 
A function f: A→B is said to be bijective if it is one to one as well as onto.
Note: Let a function f: A→B having cadinality of A and B as m and n respectively.
Total number of functions =  nm
Total number of Injective functions = nPm
Total number of Surjective functions = nm - nC1(n-1)mnC2(n-2)m - nC3(n-3)m +............... + (-1)n-1 nCn-1(1)m
Total number of Bijective functions (when m =n) = n!

Basics of relation | Types of relation | Reflexive | Irreflexive | Symmetric | AntiSymmetric | Asymmetric | Transitive | Equivalence

Relation: A binary relation from set A to set B is a subset of AxB (cartesian product of A and B).
A = {1, 2, 3, 4}
Find R = {(a, b) | a divides b} ?
Answer: R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}
Types of relation

Relation  Definition Example
Reflexive A relation R on a set A is called reflexive if (a, a) ∈ R for every element a ∈ A A = {1, 2, 3}
R = {(1,1), (2,2), (3,3), (1,3), (1,4)}
Irreflexive A relation R on set A is called Irreflexive if no a∈A is related to a (aRa does not hold). A = {1, 2, 3}
R = {(1,3), (1,4)}
Symmetric A relation R on set A is called Symmetric if aRb implies bRa, ∀a∈Aand ∀b∈A. A = {1, 2, 3}
R = {(1,1), (2,2), (3,3), (1,3), (3,1)}
AntiSymmetric A relation R on set A is called Anti-Symmetric if aRb and bRa implies a=b, ∀a∈A and ∀b∈A. A = {1, 2, 3}
R = {(1,1), (2,2), (3,3), (1,3), (2,3}
Asymmetric A relation R on set A is called Asymmetric if for all a, b in A, if (a,b) is in R, then (b,a) is not in R. A = {1, 2, 3}
R = {(1,3), (2,3}
Transitive A relation R on set A is called Transitive if aRb and bRc implies aRc, ∀a,b,c ∈A A = {1, 2, 3}
R = {(1,2), (2,3), (1,3)}
Equivalence A relation is an Equivalence Relation if it is reflexive, symmetric, and transitive. A = {1, 2, 3}
R = {(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)}