RELATION

What is Relation
A relation is defined from a set A to set B as a subset of A X B, i.e. the Cartesian product of set A and set B.
Example: Suppose A={1,2,3} and B={5,8,12,15}, then A X B ={(1,5), (1,8), (1,12), (1,15), (2,5), (2,8), (2,12), (2,15), (3,5), (3,8), (3,12), (3,15)}
Now take R as a subset of A X B
R={(1,8), (1,12), (2,8), (2,12), (3,8), (3,12), (3,15)}
This set R is a relation from A to B.

A Problem on this topic:

Let A be a set of first n natural numbers. How many relations on A can be defined?

Obviously, there are n elements in A so AxA will have n^2 ordered pairs. Therefore total number of subsets of AxA will be 2^( n^2). Hence total number of relations that can be defined on A are 2^( n^2). .
Another question is how many of them are Reflexive relations?
A={1,2,3,…, n}
AxA={(1,1),(1,2),…,(1,n),(2,1),(2,2),(2,3),…,(2,n), …, (n,n)}
Let us have the following partition of AxA:

S1={(1,1), (2, 2), (3, 3), …, (n, n)}
S2=AxA – S1={(1,2), (1, 3), (1, 4), …, (1, n), (2, 1), (2, 3), (2, 4), …, (2, n), …,(n, n-1)}
Now every Reflexive relation will have the elements of S1 and besides these elements the Reflexive relation may have one or 2 or 3 or 4 or …or all or no elements of S2.
Thus,
(S1)U (Any subset of S2) [U stands for union of two sets]
is a reflexive relation.
Therefore number of subsets of S2 =number of all Reflexive relations on A.
= 2^(n^2 -n )=
One more question is how many of them are Symmetric relations?
Consider the following partition of AxA:
S1={(1,1), (2, 2), (3, 3), …, (n, n)}
S2={(1,2), (1, 3), (1, 4), …, (1, n), (2, 3), (2, 4), …, (2, n), (3,4),(3,5),…,(3,n), (4,5),
(4,6),…,(4,n), …,(n, n-1)}
S3= {(2,1), ( 3,1), ( 4,1), …, (n,1), (3,2), (4, 2), …, (n, 2), (4,3),(5,3),…,(n,3), (5,4),
(6,4),…,(n,4), …,(n-1, n)}
n(S1)= n;
n(S2) = n(S3) = n(n-1)/2.[i.e. (n^2 –n )/2]
n(S1) +n(S2)+n(S3)= n+n(n-1)/2+n(n-1)/2 = n^2
To form a symmetric relation we can choose 0, 1, 2, 3, … or n elements from S1 and we can choose 0, 1, 2, 3, … or n(n-1) elements from S2 and we can elements from S3 only in one way as to bring the symmetry there corresponds to each pair of S2 a unique pair in S3. Thus the total number of ways to form a symmetric relation is:
(2^n).(2^(n(n-1)/2)) = 2^(n(n+1)/2)