Relations and Functions

Relations and Functions.

Relations

A Relation/Relations between two non empty set is the subset of cartesian product of two sets. i.e let R be the relation from non empty set A to non empty set B then $R  \subseteq  A\times B$. 

$R\subseteq ${(a, b) : $a\in A$, and $b\in B$}

Now if (a,b)$\in$ R then we say a is related to b by Relation R and also written as aRb.

Points to remember :

  1. Any subset of A x A is said to be a relation on A.
  2. If A has m elements and B has n elements then AxB has mn elements, Hence total number of all posible relations of A x B will be all possible subsets of A x B  i.e $2^{mn}$
  3. If R=A x B, then the first set A is called as Domain of R and Set B is called as Range of R. We can also write B=R{A}. 

Points to remember :

(1)  Any subset of A x A is said to be a relation on A.

(2)  If A has m elements and B has n elements then AxB has mn elements, Hence total number of all posible relations of A x B will be all possible subsets of A x B  i.e $2^{mn}$

(3)  If R=A x B, then the first set A is called as Domain of R and Set B is called as Range of R. We can also write B=R{A}. 

Some Particular Relations

1. Void Relation ( Or Empty Relation )

An Empty or Void relation is, if no element of A is related to the element of set B

i.e  R = $\emptyset \in $AxB

Illustration ::  Let Set A ={1, 2, 3, 4 } and Set B = { 5, 6, 7, 8} and Let R be defined as R={(a, b) : a$\in$ A , b$\in$ B and |a – b|$\gt$10}

Since there doesn’t exist any a$\in$ A and b$\in$ B that satisfy the condition that |a – b|$\gt$10.

Hence R is an Empty Relation. 

2. Universal Relation

An R is a universal Relation if R=A x B

Illustration :: Let Set A = {a, b, c} and Set B = {x , y, z}  Then R = A x B = {(a , x), (a, y), (a, z), (b, x), (b, y), (b, z), (c, x), (c, y), (c, z) }  is a Universal Relation between Set A and Set B.

3. Identity Relation

Identity Relation on set A to Set A is denoted as $I_A$ and is defined as

$I_A$={(a, a) : $a\in A$}

i.e Let A={x, y, z} then Identity Relation $I_A$ is

$I_A$={(x, x) , (y, y) , (z, z)} 

Various types of Relations

Assuming A to be a non empty set then the Relation R on A is

1. Reflexive Relation

The R is Reflexive , if (a,a)$\in$ R for every a$\in$ A. That is aRa for each a$\in$ A.

Let Set A = { 1, 2, 3, 4, 5}

(1) Let R={(a, b): a – b is divisible by 2} defined on set A.

Let a$\in$ A and a – a =0 is divisible by 2

Hence (a, a)$\in$ R , Hence R is a Reflexive Relation

(2) Let R = {(a, b) : a<b} on set A.

Since a$\not \lt$ a, Hence (a, a)$\not \in$ R

Therefore R is not Reflexive.

2. Symmetric Relation.

The Symmetric Relation R is , if (a, b)$\in$ R $\Rightarrow$ (b, a)$\in$ R for all a, b $\in$ A.

i.e  if aRb $\Rightarrow$ bRa $\forall $ a, b $\in$ A

Let Set A = { 1, 2, 3, 4, 5}

(1) Let R={(a, b): a – b is divisible by 2} where a, b$\in$ A

Let a, b$\in$ A and  a – b is divisible by 2

$\Rightarrow$   -(b-a) is divisible by 2.

Thus b – a is also divisible by 2

Hence (b, a)$\in$ R ,

$\therefore$   (a, b)$\in$ R $\Rightarrow$ (b, a)$\in$ R

Hence R is a Symmetric Relation.

(2) Let R = {(a, b) : a<b} where a, b$\in$ A

Let (a, b)$\in$ R $\Rightarrow$  a< b

$\therefore$  b>a Hence (b, a)$\not \in$ R

Therefore R is not Symmetric.

3. Transitive Relation

If (a, b)$\in$R , (b, c)$\in$ R $\Rightarrow $ (a, c)$\in$ R $\forall$ a, b, c $\in$ A.

i.e aRb , bRc $\Rightarrow $ aRc $\forall$ a, b, c$\in$ A.  

Let Set A = { 1, 2, 3, 4, 5}

(1) Let R={(a, b): a – b is divisible by 2} where a, b$\in$ A

Let a, b, c$\in$ A and (a – b) and (b – c)  is divisible by 2 

Hence (a, b)$\in$ R , and (b, c)$\in$ R,

Now (a – c) = (a – b + b – c)  is also divisible by 2

Hence (a, c)$\in$ R

$\therefore$   aRb and bRc $\Rightarrow$ aRc

Hence R is a Transitive Relation

(2) Let R = {(a, b) : a<b} where a, b$\in$ A

Let a<b, and b<c

Therefore a<b

Hence  (a, c)$\in$ R

Therefore R is Transitive Relation.

4. Equivalence Relation

A relation R is said to be Equivalence when R is (i) Reflexive (ii) Symmetric and (iii) transitive relation. 

Let Set A = { 1, 2, 3, 4, 5}

(1) Let R={(a, b): a – b is divisible by 2} where a, b$\in$ A

Since R is Reflexive , Symmetric and Transitive.

Hence Relation R is Equivalence Relation.

(2) Let R = {(a, b) : a<b} where a, b$\in$ A

Since R is Not Reflexive, Not Symmetric but Transitive .

Hence Relation R is Not Equivalence Relation.

Example 1 ::  Let A be the set of all real numbers and R be a relation in A defined by R={(a, b) : ( 1 + ab)>0 }

Prove that R is reflexive and symmetric but not transitive.

Solution 1 ::  Let a$\in$ A, Then (1+ab)=(1+$a^2$) >0 Implies that (a, a)$\in$R  $\forall \,a\in A$

$\Rightarrow$ R is reflexive

Now Let (a, b)$\in$ R \Rightarrow$  ( 1 +ab ) > 0

$\Rightarrow$   ( 1 + ba ) > 0

$\Rightarrow $   (b, a)$\in$ R.

$\therefore $ R is symmetric.

Let a=-1 , b= 0.5 , c = 20 Now,  Since (1 + ab)=(1 + (-1)(0.5))=0.5 > 0 Hence (a, b)=(-1, 0.5)$\in$ R

Also  ( 1 + bc ) = (1 + (0.5)(20))=11 > 0 Hence (b, c) = ( 0.5, 20)$\in$ R

But ( 1 + ac) = ( 1 + (-1)(20)) = -19 < 0

Hence (a, c) = (-1, 20)$\not \in $ R

Hence R is not transitive. 

Therefore R is reflexive and symmetric but not transitive. 

Example 2 ::  Let N be the set of all natural number and let R be a relation on N x N defined by  (a, b)R(c, d) $\iff $ ad = bc .

Prove that R is equivalence. 

Solution 2 ::  We know that  ab=ba Hence (a, b)R(a, b)

Hence R is reflexive.

Now, Let (a, b)R(c, d) $\Rightarrow $ ad=bc

$\Rightarrow $  bc=ad

$\Rightarrow $   cb=da

$\Rightarrow $  (c, d)R(a,b)

$\therefore $ relation R is symmetric.

Let (a, b)R(c, d) and (c, d)R(e, f)

$\Rightarrow $  ad=bc  and cf=de

$\Rightarrow $ (ad)(cf)=(bc)(de)

$\Rightarrow \; (af)\cancel{(dc)} = (be) \cancel{(dc)}$

$\Rightarrow $ af=be

$\Rightarrow $  (a, b)R(e, f)

Hence R is transitive.

Since R is reflexive, symmetric and transitive, thus R is equivalence relation.   

Example 3 ::  Let R and S be two equivalence relation on a set A. Then prove that

(a) R$\cap$S is equivalence.

(b) R$\cup$S is reflexive, symmetric but not transitive.  

Solution 3 ::  Given R and S are two equivalence relation on set A.

(a)  Since R and S are reflexive on set A, i.e for every a$\in$A (a,a)$\in$R and (a,a)$\in S \Rightarrow (a,a)\in R\cap S$

Hence R$\cap$S is reflexive on set A.

Let (a,b)$\in R\cap S$ Hence (a,b)$\in$R and (a,b)$\in$S.

Since R and S are symmetric hence For every (a,b)$\in R\Rightarrow (b,a)\in R$ also  For every (a,b)$\in S\Rightarrow (b,a)\in S$

Hence (b,a)$\in R\cap S$

$\Rightarrow$  (a,b), (b,a)$\in R\cap$S

Hence R$\cap$S is symmetric.

Let (a,b), (b,c)$\in R\cap S$

$\Rightarrow$ (a,b), (b,c)$\in$R and  (a,b), (b,c)$\in$S

Since R and S is transitive Hence

(a,c)$\in$R and (a,c)$\in$S

Hence for (a,b), (b,c)$\in R\cap S$ $\Rightarrow$ (a,c)$\in R\cap S$

Hence $R\cap S$ is reflexive, symmetric and transitive.

Hence $R\cap S$ is EQUIVALENCE RELATION IF R AND S ARE EQUIVALENCE ON SET A.


(b) Let A={1,2,3}

Let one of relation R on set A is R={(1,1), (2,2), (3,3), (1,2), (2,1)}. Hence R is equivalence.

And second relation S on set A is  S={(1,1), (2,2), (3,3), (2,3), (3,2)}. Hence S is equivalence relation.

Where as relation R$\cup$S={(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)}

Now we can see R$\cup$S is reflexive and symmetric but for (1,2), (2,3)$\in R\cup$S  where as (1,3)$\not \in R\cup S$

Hence $R\cup S$ is REFLEXIVE, SYMMETRIC BUT NOT TRANSITIVE.