Inverse of Relations Presentation.pptx

presentation on inverse of relation

1. IRREFLEXIVE Partial Order Relation Hafiz Muhammad Shahzad

2. Fourth Type of relation: IRREFLEXIVE RELATION: Let R be a binary relation on a set A. R is irreflexive iff for all a∈A,(a,a) ∉R. That is, R is irreflexive if no element in A is related to itself by R.

3. EXAMPLE: Let A = {1,2,3,4} and define the following relations on A: R1 = {(1,3), (1,4), (2,3), (2,4), (3,1), (3,4)} R2 = {(1,1), (1,2), (2,1), (2,2), (3,3), (4,4)} it is actually reflexive not irrflexive. R3 = {(1,2), (2,3), (3,3), (3,4)} Then R1 is irreflexive since no element of A is related to itself in R1. i.e. (1,1)∉ R1 , (2,2) ∉ R1 , (3,3) ∉ R1 ,(4,4) ∉ R1 R2 is not irreflexive, since all elements of A are related to themselves in R2 R3 is not irreflexive since (3,3) ∈R3. Note that R3 is not reflexive.

4. DIRECTED GRAPH OF AN IRREFLEXIVE RELATION: Let R be an irreflexive relation on a set A. Then by definition, no element of A is related to itself by R. Accordingly, there is no loop at each point of A in the directed graph of R. EXAMPLE: Let A = {1,2,3} and R = {(1,3), (2,1), (2,3), (3,2)} be represented by the directed graph.

5. MATRIX REPRESENTATION OF AN IRREFLEXIVE RELATION its matrix representation the diagonal elements are all zero, if one of them is not zero the we will say that the relation is not irreflexive. EXAMPLE: Let A = {1,2,3} and R = {(1,3), (2,1), (2,3), (3,2)} be represented by the matrix. Then R is irreflexive, since all elements in the main diagonal are 0’s.

6. Fifth Type of relation ANTISYMMETRIC RELATION: If (a,b) then no (b,a) but each element can be related . Points If set (2,1) exist in R then (1,2) should not be in R then it is called Antisymmetric. (1,1), (2,2) sets in the relation can also be called antisymmetirc. Symmetric and antisymmetirc are not opposite. Important point .

7. Example Let A = {1,2,3,4} and define the following relations on A. R1 = {(1,1),(2,2),(3,3)} R2 = {(1,2),(2,2), (2,3), (3,4), (4,1)} R3={(1,3),(2,2), (2,4), (3,1), (4,2)} R4={(1,3),(2,4), (3,1), (4,3)} Solution R1 is anti-symmetric and symmetric . R2 is anti-symmetric but not symmetric because (1,2) ∈ R2but (2,1) ∉ R2. R3 is not anti-symmetric since (1,3) & (3,1) ∈ R3 but 1 ≠ 3. Note that R3 is symmetric. R4 is neither anti-symmetric because (1,3) & (3,1) ∈ R4 but 1 ≠ 3 nor symmetric because (2,4) ∈ R4 but (4,2) ∉R

8. DIRECTED GRAPH OF AN ANTISYMMETRIC RELATION: Let R be an anti-symmetric relation on a set A. Then by definition, no two distinct elements of A are related to each other. Accordingly, there is no pair of arrows between two distinct elements of A in the directed graph of R.

9. EXAMPLE: Let A = {1,2,3} And R be the relation defined on A is R ={(1,1), (1,2), (2,3), (3,1)}.Thus R is represented by the directed graph as R is anti-symmetric, since there is no pair of arrows between two distinct points in A.

10. MATRIX REPRESENTATION OF AN ANTISYMMETRIC RELATION: Point: Each first row and each first column must be different. EXAMPLE: Let A = {1,2,3} and a relation R = {(1,1), (1,2), (2,3), (3,1)}on A be represented by the matrix. Then R is anti-symmetric as clear by the form of matrix M

11. PARTIAL ORDER RELATION: Let R be a binary relation defined on a set A. R is a partial order relation,if and only if, R is reflexive, antisymmetric , and transitive . Please do not mix with EQUIVALENCE RELATION. Let A be a non-empty set and R a binary relation on A. R is an equivalence relation if, and only if, R is reflexive, symmetric , and transitive.

12. Example Let R be the set of real numbers and define the“less than or equal to” , on R as follows: for all real numbers x and y in R. x ≤y ⇔ x. Show that ≤ is a Let R be the set of real numbers and define the“less than or equal to” , on R as follows: for all real numbers x and y in R.x ≤y ⇔ x < y or x = y Show that ≤ is a partial order relation relation. Reflexive Real Numbers= {-3,-2,-1,0,1,2,3, 3.5, 7.1, 8,9,10,11...} (<=) R= { (0,0), (1,1), (2,2), (3.5,3.5) } This relation is Reflexive.

13. Example ...con for all real numbers x and y in R. x ≤y ⇔ x. This is the condition. Real Numbers= {-3,-2,-1,0,1,2,3, 3.5, 7.1, 8,9,10,11...} R<= { (0,0), (1,1), (2,2), (3.5,3.5) } This relation is Reflexive. Anti Symmetric If I take (1,2) then (2,1) is not exist due to the condition. It means this relation is anti symmetric. Transitive take (1,2) , (2,4) (1,4) It means all condition are successfully fullfilled. It is Transitive as well.

14. Example Let “R” be the relation defined on the set of integers Z as follows: for all a, b ∈Z, aRb iff b=a r for some positive integer r. Show that R is a partial order on Z. Solution: Z= {-2,-1,0, 1, 2 ,3 4} Reflexive: Take a=0 , r=1. => b=a r = (0) 1 =0 , b=0 hence , first order pair comes (0,0) Take a=1 , r=1 => b=a r = (1) 1 =1 , b= 1 hence second order pair comes (1,1) Take a=2 , r=1 => b=2 b=a r = (2) 1 =2 , b= 2 hence third order pair comes (2,2) Hence (0,0), (1,1) and (2,2) it is reflexive.

15. Example ...con Anti Symmetric: Take a=1, r=2 => b=a r = (1) 2 =1 ,b=1 hence , order pair comes (1,1) Take a=2, r=2 => b=a r = (2) 2 =4 ,b= 4 hence second order pair comes (2,4 ) , means (4,2) should not be exit is the subset Take a=4, r=2 b=a r = (4) 2 =16 ,b= 16 hence third order pair comes (4,16), hence (4,2) is not exist. Or a=4, r=1 b=a r = (4) 1 =4, b= 4, hence third order pair comes (4,4), hence (4,2) is also not exist. it is Anti Symmetric.

16. Example ...con Transitive: Take a=2, r=2 => b=a r = (2) 2 =4,b=4 hence , order pair comes (2,4) Take a=4, r=2 b=a r = (4) 2 =16 ,b= 16 hence second order pair comes (4,16). Take a=4, r=2 => b=a r = (2) 2 =4 ,b= 4 hence second order pair comes (2,4) Take a=2, r=4 b=a r = (2) 4 =16 ,b= 16 hence third order pair comes (2,16). R= {(2,4),(4,16),(2,16)} This relation is transitive as well. Hence, it is proved that this is partial order of the given conditon . b=a r

17. Inverse of Relations Composite Relation Complementry Relation

18. INVERSE OF A RELATION (R-1): the inverse relation R -1 of R is obtained by interchanging the elements of all the ordered pairs in R. E.g R ={ (2,2), (5,6), (2,7), (3,6),(4,8)} R -1 ={ (2,2), (6,5), (7,2), (6,3),(8,4)}

19. ARROW DIAGRAM OF AN INVERSE RELATION: The relation R = {(2,2), (2,6), (2,8), (3,6), (4,8)} is represented by the arrow diagram. Then inverse of the above relation can be obtained simply changing the directions of the arrows and hence the diagram is

20. MATRIX REPRESENTATION OF INVERSE RELATION: The relation R = {(2, 2), (2, 6), (2, 8), (3, 6), (4, 8)}from A = {2, 3,4} to B = {2, 6, 8} is defined by the matrix M below. The matrix representation of inverse relation R-1 is obtained by simply taking its transpose . (i.e., changing rows by columns and columns by rows). Hence R-1 is represented by Mt as shown.

21. COMPLEMENTRY RELATION: Let R be a relation from a set A to a set B. The complementry relation R of R is the set of all those ordered pairs in A×B that do not belong to R. Symbolically: R -1 = A×B - R

22. Example: Find Complementry Relation; Let A = {1,2,3} and B={1,2} R = {(1,1), (1,3), (2,2), (2,3), (3,1)} Solution A*B= { (1,1) , (1,2), (2,1), (2,2) , (3,1) ,(3,2)} R -1= A×B – R = { (1,2), (2,1),(3,2) }

23. Example Let R be a binary relation on a set A. Prove that (i) If R is reflexive, then R-1 is reflexive. (ii) If R is symmetrice, then R-1 is Symmetrice. (iii) If R is transirive , then R-1 is transitive (iv) if R is antisymmetrice, then R-1 is anti symmetric. Let A={(1,2,3} Reflexive R={ (1,1), (2,2),(3,3)} => R-1 is reflexive as well. Symmetrice R={ (1,2), (2,1)} => R-1= {(2,1), (1,2)} is Symmetric as well. Transtive R={ (1,2),(2,3), (1,3)}=> R-1 ={(2,1),(3,2),(3,1) } is transitive as well. AntiSymmetric R= { (1,2), (3,1)} => R-1 ={ (2,1),(1,3)} is antisymmetric

24. Example Let R be a relation on a set A. Prove that R is reflexive iff R-1 is irreflexive. Solution: Let A={1,2} A*A={(1,1), (1,2),(2,1),(2,2)} => Reflexive =(1,1), (2,2) R-1 =A×B – R= { (1,2), (2,1} it is irreflexive.

25. Example Suppose that R is a symmetric relation on a set A. Is R(Bar) also symmetric. Solve your own

26. Solution Let A={1,2} R= {(1,2), (2,1)} A*A ={ (1,1),(1,2),(2,1),(2,2)} R(bar)= A*A-R R(BAR)= {(1,1),(2,2)} Yes it is symmetric.

27. Composite Relation

28. Example R= {(a,1),(a,4),(b,3) ,(c,1),(c,4)} as a relation from A to B S={(1,x), (2,x), (3,y), (3,z) } Be a relation from B to C. Write Composite relation of R and S. SoR={ } find E.g Second element of R and first element of S Composite relation of R and S is SoR={(a,x), (b,y), (b,z),(c,x)}

29. Composite relation from Arrow Diagram Let A={ a,b,c} , B={ 1,2,3,4} and C={x,y,z}. Define relation R from A to B and S from B to C by the above diagram.

30. Solution You have to see set B , each element of set B that have arrow and head is pointing will be taken. Composite relation of R and S => ROS

31. Example Let X = {1,2,3},Y′={a, b, c, d}, Y={a, b, c, d, e} and Z ={x, y, z}. Define functions f:X→Y′ and g: X →Z by the arrow diagrams .

32. Solution

33. Matrix represenation in Composite relation

34. Matrix Find the matrix reresenting thereatliosn SoR and RoS where the matrices representing R and S are

35. Solution

36. Example Let R and S be reflexive relations on a set A. Prove SoR is reflexive.

37. Solultion Let A= {1,2} R={(1,1), (2,2)} S=((1,1), (2,2),(2,1)) SoR={ (1,1), (2,2), (2,1) } SoR is relexive.