(**************************************************************************)
include "basics/star.ma".
-include "Ground-2/xoa_props.ma".
+include "Ground_2/xoa_props.ma".
(* PROPERTIES of RELATIONS **************************************************)
+definition predicate: Type[0] → Type[0] ≝ λA. A → Prop.
+
+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.
lemma TC_reflexive: ∀A,R. reflexive A R → reflexive A (TC … R).
/2/ qed.
-lemma TC_star_ind: ∀A,R. reflexive A R → ∀a1. ∀P:A→Prop.
+lemma TC_star_ind: ∀A,R. reflexive A R → ∀a1. ∀P:predicate A.
P a1 → (∀a,a2. TC … R a1 a → R a a2 → P a → P a2) →
∀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 → predicate A ≝
+ λA,R,S,a1. ∀a2. R a1 a2 → S a1 a2.
+
+inductive SN (A) (R,S:relation A): predicate A ≝
+| 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.