8.4 Closures of Relations Intro Consider the following example (telephone line, bus route,) a b c d Is R, defined above on the set A={a, b, c, d}, transitive? If not, is there a (possibly indirect) link between each of the cities?

To answer, we want to find the Transitive Closure Closures, in general Def: Let R be a relation on a set A that may or may not have some property P. (Ex: Reflexive, ) If there is a relation S with property P containing R such that S is a subset of every relation with property P containing R, then S is called the closure of R with respect to P.

Note: the closure may or may not exist Reflexive Closures- Idea, Example Reflexive Closure of Rthe smallest reflexive relation that contains R Consider R={(1,2),(2,3),(3,2)} on A={1,2,3} 1 2 3 Using both ordered pairs and digraphs, find the reflexive

closure. Reflexive Closures Reflexive Closure of Rthe smallest reflexive relation that contains R Reflexive Closure = R Where on A.

={(a,a)| a A} is the diagonal relation More examples Find the reflexive closures for: R={(a,b)|a

Symmetric Example Find the symmetric closure of R={(1,1), (1,2),(2,2),(2,3),(3,1),(3,2)} on A={1,2,3} 1 2 3 Symmetric Closures Symmetric Closure of R = R R-1 Where R-1= {(b,a) | (a,b) R}

Example: R={(a,b)|a>b} on the integers Z Symmetric closure: Transitive Theory- example 1 2 4 3 Add all (a,c) such that (a,b), (b,c) R.

Keep going. (Why?) Transitive Closure Theory, and Def of Path Def: A path from a to b in a directed graph G is a sequence of edges (x0,x1), (x1,x2) (xn-1, xn) in G where x0=a and xn=b. It is denoted x1, x2,xn and has length n. When a=b, the path is called a circuit or cycle.

Find Transitive Closure- see worksheet Do Worksheet 12 43 Find the transitive closure Find circuits and paths of length 2, 3, 4

Example- in matrices Using the idea that R n+1 = RnR and MSR = MR MS , Find the matrices for R R2 R3

R4 The find paths of length 2, 3, 4 Example = Next step

In order to come up with a theory for the transitive closure, we will first study paths. Theorem 1 Theorem 1: Let R be a relation on a set A. There is a path of length n from a to b iff (a,b)Rn Proof method?

Proof of Thm. 1 By induction: N=1: true by definition (path from a to b of l=1 iff (a,b) R). Induction step: Assume: There exists a path of length __ from ___iff ______ Show: There exists a path of length __ from ___iff ______ Assuming the IH (Inductive Hypothesis), There is a path of length __ from ___

Iff There exists an element c with a path from a to c in R and a path of length n from c to b in ___ Iff There exists an element c with (a,c) ___ and (c,b) ___ Iff (a,b) ____ = _______ Def 2: Connectivity relation Def. 2: Let R be a relation on set A. The connectivity relation R* consists of the pairs (a,b) such that there is a path between a and b

in R. R* = Examples R={(a,b)| a has met b} 6 degrees Erdos number R* include (you,__)

R={(a,b)| it is possible to travel from stop a to b directly} on set A of all subway stops R*= R={(a,b)|state a and b have a common border on the set A of states. R*= Thm. 2: Transitive closure is the connectivity

relation Theorem 2: The transitive closure of a relation R equals the connectivity relation R* = Elements of the Proof: Note that R R* To show R* is the transitive closure of R, show: 1) R* is ________

2) Whenever S is a transitive relation that contains R, then R* ______ Proof of Thm 2 1) Assume (a,b) R* and (b,c) R* So (a,b) ___ and (b,c) ___ By Thm. 1, there exists paths 2 paths: In conclusion ________

Thm 2 proof 2) Suppose S is a transitive relation containing R It can be shown by induction that Sn is transitive. By a previous theorem in sec. 8.1, S n ___ S. Since S* = S k and S k __ S , the S* ___ S. Since R ___S, the R* ____ S*. Therefore R* ___ S* ___ S.