X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;f=matita%2Fmatita%2Fcontribs%2Flambda_delta%2FGround_2%2Fstar.ma;h=e438b44f0c6bea578f1b243f7985aa68a8f51ec6;hb=d38087520d6ce1d696b28da40f3811291fc8a311;hp=ffc5ab1ac48d464d78da03e5e0dd3f96717b66ca;hpb=78f21d7d9014e5c7655f58239e4f1a128ea2c558;p=helm.git

diff --git a/matita/matita/contribs/lambda_delta/Ground_2/star.ma b/matita/matita/contribs/lambda_delta/Ground_2/star.ma
index ffc5ab1ac..e438b44f0 100644
--- a/matita/matita/contribs/lambda_delta/Ground_2/star.ma
+++ b/matita/matita/contribs/lambda_delta/Ground_2/star.ma
@@ -17,6 +17,9 @@ include "Ground_2/xoa_props.ma".
 
 (* PROPERTIES of RELATIONS **************************************************)
 
+definition Decidable: Prop → Prop ≝
+   λR. R ∨ (R → False). 
+
 definition confluent: ∀A. ∀R1,R2: relation A. Prop ≝ λA,R1,R2.
                       ∀a0,a1. R1 a0 a1 → ∀a2. R2 a0 a2 →
                       ∃∃a. R2 a1 a & R1 a2 a.
@@ -107,3 +110,16 @@ lemma TC_star_ind: ∀A,R. reflexive A R → ∀a1. ∀P:A→Prop.
                    ∀a2. TC … R a1 a2 → P a2.
 #A #R #H #a1 #P #Ha1 #IHa1 #a2 #Ha12 elim Ha12 -Ha12 a2 /3/
 qed.
+
+definition NF: ∀A. relation A → relation A → A → Prop ≝
+   λA,R,S,a1. ∀a2. R a1 a2 → S a1 a2.
+
+inductive SN (A) (R,S:relation A): A → Prop ≝
+| SN_intro: ∀a1. (∀a2. R a1 a2 → (S a1 a2 → False) → SN A R S a2) → SN A R S a1
+.
+
+lemma NF_to_SN: ∀A,R,S,a. NF A R S a → SN A R S a.
+#A #R #S #a1 #Ha1
+@SN_intro #a2 #HRa12 #HSa12
+elim (HSa12 ?) -HSa12 /2/
+qed.