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 :
- Any subset of A x A is said to be a relation on A.
- 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}$
- 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.