6-Week 6 Matrices Relations and Functions.pptx

topics of matrices and relations and function

1. MATRICES & RELATIONS Part 2

2. Outline Composing Relation Equivalence Relation Partial Orderings Closure Relation

3. Composing Relation

4. Composition DEFINTION. Let R be a relation from a set A to a set B and S a relation from set B to a set C . The composite of R and S is the relation consisting of ordered pairs (a, c), where a ∈ A, c ∈ C , and for which there exists an element b ∈ B such that (a, b) ∈ R and (b, c) ∈ S . We denote the composite of R and S by S  R. What is R 2 o R 1 if R 1 is a relation from {1, 2, 3} to {1, 2, 3, 4} with R 1 = {(1,1), (1,3), (1,4), (2,3), (3,1), (3,4)} and R 2 is a relation from {1, 2, 3, 4} to {0,1, 2} where R 2 = {(1,0), (2,0), (3,1), (3,2), (4,1)} R 2 o R 1 =

5. Composition (practice) Suppose R = {(1, 2), (1, 6), (2, 4), (3, 4), (3, 6), (3, 8)} is a relation from the set {1, 2, 3} to the set {2, 4, 6, 8} and S = {(2, u ), (4, s ), (4, t ), (6, t ), (8, u )} is a relation from the set {2, 4, 6, 8} to the set {s , t , u }. What is the S o R? Then the composition of relations R and S is S o R = {(1, u ), (1, t ), (2, s ), (2, t ), (3, s ), (3, t ), (3, u )}

6. Composition (cont..) The composite relation R and S is more clear if demonstrated with an arrow diagram:

7. Composition (cont..) EXAMPLE2. What is the composite of the relations R and S , where R is the relation from {1, 2, 3} to {1, 2, 3, 4} with R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)} and S is the relation from {1, 2, 3, 4} to {0, 1, 2} with S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)}? SOLUTION : S o R is constructed using all ordered pairs in R and ordered pairs in S , where the second element of the ordered pair in R agrees with the first element of the ordered pair in S . For example, the ordered pairs (2, 3) in R and (3, 1) in S produce the ordered pair (2, 1) in S o R. Computing all the ordered pairs in the composite, we find S o R = {(1, 0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)}.

8. Composition (cont..) If the relations and are expressed by the matrices and , then the matrix expressing the composition of the two relations is . in which case the “ . ” operator is the same as in normal matrix multiplication , but by replacing the times sign with “ ” and the plus sign with “ ”.  

9. Composition (cont..) EXAMPLE3. Suppose that the relation and on set A is expressed by the matrix = and = then the matrix representing o is = =  

10. Equivalence Relations

11. Equivalence Relations DEFINITION 1 : A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive. DEFINITION 2 : Two elements a , and b that are related by an equivalence relation are called equivalent. The notation is often used to denote that are equivalent elements with respect to a particular equivalence relation.  

12. A relation R on a set A is called reflexive if (a, a) ∈ R for every element a ∈ A. 3 Properties of relation Which of these relations are reflexive?

13. A relation R on a set Ais called symmetric if (b, a) ∈ R whenever (a, b) ∈ R, for all a, b ∈ A. 3 Properties of relation Which of these relations are symmetric?

14. A relation R on a set A is called transitive if whenever (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R, for all a, b, c ∈ A. 3 Properties of relation Which of these relations are transitive?

15. Equivalence Relations behavior Because R is reflexive, Each element is equivalent to itself. Because R is symmetric, A is equivalent to b whenever b is equivalent to a. Because R is transitive, If A and B are equivalent and B and C are equivalent, then A and C are also equivalent.

16. Equivalence Relations behavior(cont..) EXAMPLE: Suppose A = set of students and R is a relation on A such that if a is in the same class as b . → R is reflexive : every student is in the same class as itself → R is symmetric : if a is in the same class as b , then b must be in the same class as a . → R transitive : if a is in the same class as b and b is in the same class as c , then a must be in the same class as c . So, R is an equivalence relation.  

17. Equivalence Relations behavior(cont..) EXAMPLE : Suppose that R is the relation on the set of strings of English letters such that a R b if and only if l ( a ) = l ( b ), where l ( x ) is the length of the string x . Is R an equivalence relation? Solution : Show that all of the properties of an equivalence relation hold. Reflexivity : Because l ( a ) = l ( a ), it follows that a R a for all strings a . Symmetry : Suppose that a R b. Since l ( a ) = l ( b ), l ( b ) = l ( a ) also holds and b R a . Transitivity : Suppose that a R b and b R c . Since l ( a ) = l ( b ),and l ( b ) = l ( c ), l ( a ) = l ( a ) also holds and a R c . So, R is an equivalent relation.

18. Partial Orderings

19. Partial Orderings Definition : A relation R on a set S is called a partial ordering, or partial order, if it is reflexive, antisymmetric, and transitive . A set together with a partial ordering R is called a partially ordered set , or poset , and is denoted by ( S , R ). Members of S are called elements of the poset .

20. Partial Orderings ( cont …) EXAMPLE : Show that the “greater than or equal” relation (≥) is a partial ordering on the set of integers. Solution Reflexivity : a ≥ a for every integer a . Antisymmetry : If a ≥ b and b ≥ a , then a = b. Transitivity : If a ≥ b and b ≥ c , then a ≥ c.

21. Partial Orderings ( cont …) EXAMPLE :The relation on the set of positive integers is a partial ordering relation. Solution The relation is reflexive, since a a for every integer a; The relation is anstisymmetric , since if a b and b a , then a = b; The relation is transitive, since if a b and b c then a c .  

22. Closure Relation

23. Closure of Relation A relation R on a set A is a subset of the Cartesian product A×A. It consists of ordered pairs of elements from A. The closure of a relation refers to the smallest relation that contains R and satisfies certain properties.