9 1 Relations and Their Properties Def 1 Let A and B be sets A binary relation from A to B is a subset of A B Def 2 A relation on a set A is a relation from A to A Def 3 A relation R on a set A is called reflexive if a a R for every element a A Def 4 A relation R on a set A is called symmetric if b a R whenever a b R for all a b A A relation R on a set A such that for all a b A if a b R and b a R then a b is called antisymmetric Def 5 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 Def 6 Let R be a relation from a set A to a set B and S a relation from 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 Def 7 Let R be a relation on the set A The powers Rn n 1 2 3 are defined recursively by R1 R and Rn 1 Rn R Theorem 1 The relation R on a set A is transitive if and only if Rn R for n 1 2 3 9 2 n ary Relations and Their Applications Def 1 Let A1 A2 An be sets An n ary relation on these sets is a subset of A1 A2 An The sets A1 A2 An are called the domains of the relation and n is called its degree Def 2 Let R be an n ary relation and C a condition that elements in R may satisfy Then the selection operator sC maps the n ary relation R to the n ary relation of all n tuples from R that satisfy the condition C Def 3 The projection Pi1i2 im where i1 i2 im maps the n tuple a1 a2 an to the m tuple ai1 ai2 aim where m n Def 4 Let R be a relation of degree m and S a relation of degree n The join Jp R S where p m and p n is a relation of degree m n p that consists of all m n p tuples a1 a2 am p c1 c2 cp b1 b2 bn p where the m tuple a1 a2 am p c1 c2 cp belongs to R and the n tuple c1 c2 cp b1 b2 bn p belongs to S 9 3 Representing Relations Def 1 A directed graph or digraph consists of a set V of vertices or nodes together with a set E of ordered pairs of elements of V called edges or arcs The vertex a is called the initial vertex of the edge a b and the vertex b is called the terminal vertex of this edge 9 4 Closures of Relations Def 1 A path from a to b in the directed graph G is a sequence of edges x0 x1 x1 x2 x2 x3 xn 1 xn in G where n is a non negative integer and x0 a and xn b that is a sequence of edges where the terminal vertex of an edge is the same as the initial vertex in the next edge in the path This path is denoted by x0 x1 x2 xn 1 xn and has length n We view the empty set of edges as a path of length zero from a to a A path of length n 1 that begins and ends at the same vertex is called a circuit or cycle Theorem 1 Let R be a relation on a set A There is a path of length n where n is a positive integer from a to b if and only if a b Rn Def 2 Let R be a relation on a set A The connectivity relation R consists of the pairs a b such that there is a path of length at least one from a to b in R Theorem 2 The transitive closure of a relation R equals the connectivity relation R Lemma 1 Let A be a set with n elements and let R be a relation on A If there is a path of length at least one in R from a to b then there is such a path with length not exceeding n Moreover when a b if there is a path of length at least one in R from a to b then there is such a path with length not exceeding n 1 Theorem 3 Let MR be the zero one matrix of the relation R on a set with n elements Then the zero one matrix of the transitive closure R is MR MR MR 2 MR 3 Lemma 2 Let Wk wij k be the zero one matrix that has a 1 in its i j th position if and only if there is a path from vi to vj with interior vertices from the set v1 v2 vk Then wij k wij k 1 wik k 1 wkj k 1 whenever i j and k are positive integers not exceeding MR n n
View Full Document
Unlocking...