starl

[helm.git] / matita / matita / lib / basics / star.ma

diff --git a/matita/matita/lib/basics/star.ma b/matita/matita/lib/basics/star.ma
index bff1aaeef80042a2ae2e838317d0c5ed5c858a58..04d2d7317e4416b7031d18f5125f2ce78eeb72bc 100644 (file)
--- a/matita/matita/lib/basics/star.ma
+++ b/matita/matita/lib/basics/star.ma
@@ -88,6 +88,56 @@ theorem star_inv: ∀A,R.
 #H (elim H) /2/ normalize #c #d #H1 #H2 #H3 @(trans_star … H3) /2/
 qed.
 
+lemma star_decomp_l : 
+  ∀A,R,x,y.star A R x y → x = y ∨ ∃z.R x z ∧ star A R z y.
+#A #R #x #y #Hstar elim Hstar
+[ #b #c #Hleft #Hright *
+  [ #H1 %2 @(ex_intro ?? c) % //
+  | * #x0 * #H1 #H2 %2 @(ex_intro ?? x0) % /2/ ]
+| /2/ ]
+qed.
+
+(* right associative version of star *)
+inductive starl (A:Type[0]) (R:relation A) : A → A → Prop ≝
+  |injl: ∀a,b,c.R a b → starl A R b c → starl A R a c
+  |refll: ∀a.starl A R a a.
+ 
+lemma starl_comp : ∀A,R,a,b,c.
+  starl A R a b → R b c → starl A R a c.
+#A #R #a #b #c #Hstar elim Hstar 
+  [#a1 #b1 #c1 #Rab #sbc #Hind #a1 @(injl … Rab) @Hind //
+  |#a1 #Rac @(injl … Rac) //
+  ]
+qed.
+
+lemma star_compl : ∀A,R,a,b,c.
+  R a b → star A R b c → star A R a c.
+#A #R #a #b #c #Rab #Hstar elim Hstar 
+  [#b1 #c1 #sbb1 #Rb1c1 #Hind @(inj … Rb1c1) @Hind
+  |@(inj … Rab) //
+  ]
+qed.
+
+lemma star_to_starl: ∀A,R,a,b.star A R a b → starl A R a b.
+#A #R #a #b #Hs elim Hs //
+#d #c #sad #Rdc #sad @(starl_comp … Rdc) //
+qed.
+
+lemma starl_to_star: ∀A,R,a,b.starl A R a b → star A R a b.
+#A #R #a #b #Hs elim Hs // -Hs -b -a
+#a #b #c #Rab #sbc #sbc @(star_compl … Rab) //
+qed.
+
+lemma star_ind_l : 
+  ∀A:Type[0].∀R:relation A.∀Q:A → A → Prop.
+  (∀a.Q a a) → 
+  (∀a,b,c.R a b → star A R b c → Q b c → Q a c) → 
+  ∀a,b.star A R a b → Q a b.
+#A #R #Q #H1 #H2 #a #b #H0 
+elim (star_to_starl ???? H0) // -H0 -b -a 
+#a #b #c #Rab #slbc @H2 // @starl_to_star //
+qed.  
+
 (* RC and star *)
 
 lemma TC_to_star: ∀A,R,a,b.TC A R a b → star A R a b.
@@ -192,9 +242,9 @@ lemma TC_star_ind_dx: ∀A,R. reflexive A R →
 @(TC_star_ind_dx_aux … HR … Ha2 H … Ha12) //
 qed-.
 
-definition Conf3: ∀A. relation A → relation A → Prop ≝ λA,S,R.
-                  ∀a,a1. S a1 a → ∀a2. R a1 a2 → S a2 a.
+definition Conf3: ∀A,B. relation2 A B → relation A → Prop ≝ λA,B,S,R.
+                  ∀b,a1. S a1 b → ∀a2. R a1 a2 → S a2 b.
 
-lemma TC_Conf3: ∀A,S,R. Conf3 A S R → Conf3 A S (TC … R).
-#A #S #R #HSR #a #a1 #Ha1 #a2 #H elim H -a2 /2 width=3/
+lemma TC_Conf3: ∀A,B,S,R. Conf3 A B S R → Conf3 A B S (TC … R).
+#A #B #S #R #HSR #b #a1 #Ha1 #a2 #H elim H -a2 /2 width=3/
 qed.