X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;f=matita%2Fmatita%2Flib%2Fbinding%2Fnames.ma;fp=matita%2Fmatita%2Flib%2Fbinding%2Fnames.ma;h=bc5f07d43ce3bf2559ba3935940025e36149b220;hb=4a41f041869956a6c98418e6d06b3a2521a1fb2a;hp=0000000000000000000000000000000000000000;hpb=ed93840d88912c92da47c4cec1713d9565f361d3;p=helm.git

diff --git a/matita/matita/lib/binding/names.ma b/matita/matita/lib/binding/names.ma
new file mode 100644
index 000000000..bc5f07d43
--- /dev/null
+++ b/matita/matita/lib/binding/names.ma
@@ -0,0 +1,78 @@
+(**************************************************************************)
+(*       ___                                                              *)
+(*      ||M||                                                             *)
+(*      ||A||       A project by Andrea Asperti                           *)
+(*      ||T||                                                             *)
+(*      ||I||       Developers:                                           *)
+(*      ||T||         The HELM team.                                      *)
+(*      ||A||         http://helm.cs.unibo.it                             *)
+(*      \   /                                                             *)
+(*       \ /        This file is distributed under the terms of the       *)
+(*        v         GNU General Public License Version 2                  *)
+(*                                                                        *)
+(**************************************************************************)
+
+include "basics/logic.ma".
+include "basics/lists/in.ma".
+include "basics/types.ma".
+
+(*interpretation "list membership" 'mem x l = (in_list ? x l).*)
+
+record Nset : Type[1] ≝
+{
+  (* carrier is specified as a coercion: when an object X of type Nset is
+     given, but something of type Type is expected, Matita will insert a
+     hidden coercion: the user sees "X", but really means "carrier X"     *)
+  carrier :> DeqSet;
+  N_fresh : list carrier → carrier;
+  p_fresh : ∀l.N_fresh l ∉ l
+}.
+
+definition maxlist ≝
+ λl.foldr ?? (λx,acc.max x acc) 0 l.
+
+definition natfresh ≝ λl.S (maxlist l).
+
+lemma le_max_1 : ∀x,y.x ≤ max x y. /2/
+qed.
+
+lemma le_max_2 : ∀x,y.y ≤ max x y. /2/
+qed.
+
+lemma le_maxlist : ∀l,x.x ∈ l → x ≤ maxlist l.
+#l elim l
+[#x #Hx @False_ind cases (not_in_list_nil ? x) #H1 /2/
+|#y #tl #IH #x #H1 change with (max ??) in ⊢ (??%);
+ cases (in_list_cons_case ???? H1);#H2;
+ [ >H2 @le_max_1
+ | whd in ⊢ (??%); lapply (refl ? (leb y (maxlist tl)));
+   cases (leb y (maxlist tl)) in ⊢ (???% → %);#H3
+   [ @IH //
+   | lapply (IH ? H2) #H4
+     lapply (leb_false_to_not_le … H3) #H5
+     lapply (not_le_to_lt … H5) #H6
+     @(transitive_le … H4)
+     @(transitive_le … H6) %2 %
+   ]
+ ]
+]
+qed.
+
+(* prove freshness for nat *)
+lemma lt_l_natfresh_l : ∀l,x.x ∈ l → x < natfresh l.
+#l #x #H1 @le_S_S /2/
+qed.
+
+(*naxiom p_Xfresh : ∀l.∀x:Xcarr.x ∈ l → x ≠ ntm (Xfresh l) ∧ x ≠ ntp (Xfresh l).*)
+lemma p_natfresh : ∀l.natfresh l ∉ l.
+#l % #H1 lapply (lt_l_natfresh_l … H1) #H2
+cases (lt_to_not_eq … H2) #H3 @H3 %
+qed.
+
+include "basics/finset.ma".
+
+definition X : Nset ≝ mk_Nset DeqNat ….
+[ @natfresh
+| @p_natfresh
+]
+qed.
\ No newline at end of file