From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU  Wed Apr 16 10:42:06 2008
Date:         Wed, 16 Apr 2008 10:33:20 -0400
From: "William J. Rapaport" <rapaport@cse.Buffalo.EDU>
Subject: 191:  Proof that R* is the transitive closure of R
To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU

------------------------------------------------------------------------
Subject: 191:  Proof that R* is the transitive closure of R
------------------------------------------------------------------------

Reminder: Let R be a binary relation on set A.
          Then R* =def {(a,b) \in AxA | there exists a path from a to b}
 
Theorem:  Let R be a binary relation on set A.
	  Then R* = the transitive closure of R.

proof:

We need to show that the 3 parts of the definition of transitive closure
are satisfied by R*:

	1)	R is a subset of R* (i.e., R* "extends" R)

	2)	R* is transitive

	3)	R* is the "smallest" transitive extension of R
		i.e., for all S:    (R is a subset of S
		                  ^  S is transitive)
		       
		                     ->

		                     R* is a subset of S

(1)  R is a subset of R* by the definition of R* (after all, if R(a,b),
     then there is a path from a to b, namely, the edge connecting a to b)

(2)  Suppose R*(a,b) ^ R*(b,c).
     Show R*(a,c):

	i.e., show that there's a path from a to c:

	R*(a,b) implies that there's a path from a to b.
	R*(b,c) implies that there's a path from b to c.

	So, to find a path from a to c, just take the path from a to b
	and then follow the path from b to c.

(3)  Suppose S is such that: (R is a subset of S) ^ (S is transitive)
     Show that R* is a subset of S:

	Fact 1:
	S is transitive implies S^n is transitive.

	(Why?  Well, that requires a lemma, which is proved in the text!
	But it should be plausible.  Remember that S^2 =def SoS, which
	creates an "S-path" from a to c if there's already an S-path
	from a to b and another from b to c.  So, if S is already
	transitive, then "surely" S^n will also be transitive.)

	Fact 2:
	For all n: S^n is a subset of S (see Thm 8.1.1 in the text)

	Fact 3:
	S* = UkS^k	(see text)

	Facts 2 and 3 imply that S* is a subset of S.

	Fact 4:
	R is a subset of S implies R* is a subset of S*
	(because any path in R* is also a path in S*)

	Therefore, R* is a subset of S*, which is a subset of S.

	QED.