Page 1 :
identity relation I is an Equivalence Relation., , Example: A= {1, 2, 3} = ((1, 1), (2, 2), G, 33}, 8. Void Relation: It is given by R: A ~B such that k= 2 (© AxB) isa null relation. Void, Relation R = @ is symmetric and transitive but not reflexive., , elation: A relation R: AB such that R= A x B(S A xB) isa universal, , ee id symmetric and transitive. So this is an, , relation. Universal Relation from A >B is reflexive,, equivalence relation., , Operations on relations, , iously defined, a binary relation between two nonempty sets A and B (in that order) is, nothing more than a subset of the Cartesian product of A and B (n that order). Since relations are, , Y sets they are sus ce the ordinary set operations. For example, given two relations Rl and, , ; : difference of these two relations. The previously, , As we previ, , , , , , , , Concatenation, , Let R bea relation be:, tween the sets a i, concatenate these relations Wiehe ie, RS := . ; ', £(@,c) | (a,b) in R and (b,c) in $ for some b out of B}, , Diagonal ofa Set, , Let A be a set, the e ‘, , x er a set, sted we define the diagonal (D) of A by, , (A) = {(a,a) | ain A}, Shorter Notations, Usi iti, nae above definitions, one can Say (lets assume R is a relation between A and B):, , R is transitive if and only if R « R is a subset of R., , R is reflexive if and only if D(A) is a subset of R., , R is symmetric if R" is a subset of R., , R is antisymmetric if and only if the intersection of R and R" is D(A)., , R is asymmetric if and only if the intersection of D(A) and R is empty., , R is a function if and only if R' + R is a subset of D(B)., , In this case it is a function A — B. Let's assume R meets the condition of being a function, then, R is injective if R * R™ is a subset of D(A)., R is surjective if {b | (a,b) in R} =B., , , , , , Warshall’s algorithm is an efficient method of finding the adjacency matrix of the, transitive closure of relation R on a finite set S from the adjacency matrix of R. It uses, erties of the digraph D, in particular, walks of various lengths in D., walk, transitive closure, relation, and digraph are all found in Epp., y the adjacency matrix of R and Tbe the adjacency matrix of, salled the n of digraph’D due to the, be reached from 7 v in D by a sequence of arcs