1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 set "baseuri" "cic:/matita/Fsub/util".
16 include "logic/equality.ma".
17 include "nat/compare.ma".
18 include "list/list.ma".
20 (*** useful definitions and lemmas not really related to Fsub ***)
25 |false \Rightarrow m].
27 inductive in_list (A:Type): A → (list A) → Prop ≝
28 | in_Base : ∀ x,l.(in_list A x (x::l))
29 | in_Skip : ∀ x,y,l.(in_list A x l) → (x ≠ y) → (in_list A x (y::l)).
31 notation > "hvbox(x ∈ l)"
32 non associative with precedence 30 for @{ 'inlist $x $l }.
33 notation < "hvbox(x \nbsp ∈ \nbsp l)"
34 non associative with precedence 30 for @{ 'inlist $x $l }.
35 interpretation "item in list" 'inlist x l =
36 (cic:/matita/Fsub/util/in_list.ind#xpointer(1/1) _ x l).
38 lemma in_Skip2 : ∀x,y,l.(in_list nat x l) → (in_list nat x (y::l)).
39 intros;elim (decidable_eq_nat x y)
40 [rewrite > H1;apply in_Base
41 |apply (in_Skip ? ? ? ? H H1)]
44 definition incl : \forall A.(list A) \to (list A) \to Prop \def
45 \lambda A,l,m.\forall x.(in_list A x l) \to (in_list A x m).
47 (* FIXME: use the map in library/list (when there will be one) *)
48 definition map : \forall A,B,f.((list A) \to (list B)) \def
49 \lambda A,B,f.let rec map (l : (list A)) : (list B) \def
50 match l in list return \lambda l0:(list A).(list B) with
51 [nil \Rightarrow (nil B)
52 |(cons (a:A) (t:(list A))) \Rightarrow
53 (cons B (f a) (map t))] in map.
55 lemma in_list_nil : \forall A,x.\lnot (in_list A x []).
56 intros.unfold.intro.inversion H
57 [intros;lapply (sym_eq ? ? ? H2);destruct Hletin
61 lemma in_cons_case : ∀A.∀x,h:A.∀t:list A.x ∈ h::t → x = h ∨ (x ≠ h ∧ (x ∈ t)).
62 intros;inversion H;intros
63 [destruct H2;left;symmetry;assumption
64 |destruct H5;right;split [rewrite > Hcut|rewrite > Hcut1] assumption ]
67 lemma max_case : \forall m,n.(max m n) = match (leb m n) with
69 | true \Rightarrow m ].
70 intros;elim m;simplify;reflexivity;