...

[helm.git] / helm / software / matita / contribs / ng_assembly / common / nat_lemmas.ma

diff --git a/helm/software/matita/contribs/ng_assembly/common/nat_lemmas.ma b/helm/software/matita/contribs/ng_assembly/common/nat_lemmas.ma
index 4bfc4c11832366232bf43595a755b02d06a98a5d..bbce188e521db6730749d2fb03bdeda18cb94175 100644 (file)
--- a/helm/software/matita/contribs/ng_assembly/common/nat_lemmas.ma
+++ b/helm/software/matita/contribs/ng_assembly/common/nat_lemmas.ma
@@ -88,7 +88,7 @@ nlemma eq_to_eqnat : ∀n1,n2:nat.n1 = n2 → eq_nat n1 n2 = true.
                    napply (H n4 (nat_destruct_S_S … H1))
           ##]
  ##]
-nqed. 
+nqed.
 
 nlemma eqnat_to_eq : ∀n1,n2:nat.(eq_nat n1 n2 = true → n1 = n2).
  #n1;
@@ -110,6 +110,56 @@ nlemma eqnat_to_eq : ∀n1,n2:nat.(eq_nat n1 n2 = true → n1 = n2).
  ##]
 nqed.
 
+nlemma decidable_nat : ∀x,y:nat.decidable (x = y).
+ #x; nelim x; nnormalize;
+ ##[ ##1: #y; ncases y;
+          ##[ ##1: napply (or2_intro1 (O = O) (O ≠ O) (refl_eq …))
+          ##| ##2: #n2; napply (or2_intro2 (O = (S n2)) (O ≠ (S n2)) ?);
+                   nnormalize; #H; napply (nat_destruct_0_S n2 H)
+          ##]
+ ##| ##2: #n1; #H; #y; ncases y;
+          ##[ ##1: napply (or2_intro2 ((S n1) = O) ((S n1) ≠ O) ?);
+                   nnormalize; #H1; napply (nat_destruct_S_0 n1 H1)
+          ##| ##2: #n2; napply (or2_elim (n1 = n2) (n1 ≠ n2) ? (H n2) …);
+                   ##[ ##1: #H1; napply (or2_intro1 (? = ?) (? ≠ ?) …);
+                            nrewrite > H1; napply refl_eq
+                   ##| ##2: #H1; napply (or2_intro2 (? = ?) (? ≠ ?) …);
+                            nnormalize; #H2; napply (H1 (nat_destruct_S_S … H2))
+                   ##]
+          ##]
+ ##]
+nqed.
+
+nlemma neq_to_neqnat : ∀n1,n2:nat.n1 ≠ n2 → eq_nat n1 n2 = false.
+ #n1; nelim n1;
+ ##[ ##1: #n2; ncases n2;
+          ##[ ##1: nnormalize; #H; nelim (H (refl_eq …))
+          ##| ##2: #nn2; #H; nnormalize; napply refl_eq
+          ##]
+ ##| ##2: #nn1; #H; #n2; ncases n2;
+          ##[ ##1: #H1; nnormalize; napply refl_eq
+          ##| ##2: #nn2; nnormalize; #H1;
+                   napply (H nn2 ?); nnormalize; #H2;
+                   nrewrite > H2 in H1:(%); #H1;
+                   napply (H1 (refl_eq …))
+          ##]
+ ##]
+nqed.
+
+nlemma neqnat_to_neq : ∀n1,n2:nat.(eq_nat n1 n2 = false → n1 ≠ n2).
+ #n1; nelim n1;
+ ##[ ##1: #n2; ncases n2;
+          ##[ ##1: nnormalize; #H; napply (bool_destruct … H)
+          ##| ##2: #nn2; nnormalize; #H; #H1; nelim (nat_destruct_0_S … H1)  
+          ##]
+ ##| ##2: #nn1; #H; #n2; ncases n2;
+          ##[ ##1: nnormalize; #H1; #H2; nelim (nat_destruct_S_0 … H2)
+          ##| ##2: #nn2; nnormalize; #H1; #H2; napply (H nn2 H1 ?);
+                   napply (nat_destruct_S_S … H2)
+          ##]
+ ##]
+nqed.
+
 nlemma Sn_p_n_to_S_npn : ∀n1,n2.(S n1) + n2 = S (n1 + n2).
  #n1;
  nelim n1;