author | wenzelm |
Tue, 27 Aug 2002 11:09:35 +0200 | |
changeset 13535 | 007559e981c7 |
parent 13241 | 0ffc4403f811 |
child 14046 | 6616e6c53d48 |
permissions | -rw-r--r-- |
12610 | 1 |
(* Title: ZF/Induct/FoldSet.thy |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
2 |
ID: $Id$ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
3 |
Author: Sidi O Ehmety, Cambridge University Computer Laboratory |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
4 |
Copyright 2001 University of Cambridge |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
5 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
6 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
7 |
A "fold" functional for finite sets. For n non-negative we have |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
8 |
fold f e {x1,...,xn} = f x1 (... (f xn e)) where f is at |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
9 |
least left-commutative. |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
10 |
*) |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
11 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
12 |
(** foldSet **) |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
13 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
14 |
bind_thm("empty_fold_setE", |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
15 |
fold_set.mk_cases "<0, x> : fold_set(A, B, f,e)"); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
16 |
bind_thm("cons_fold_setE", |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
17 |
fold_set.mk_cases "<cons(x,C), y> : fold_set(A, B, f,e)"); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
18 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
19 |
(* add-hoc lemmas *) |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
20 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
21 |
Goal "[| x~:C; x~:B |] ==> cons(x,B)=cons(x,C) <-> B = C"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
22 |
by (auto_tac (claset() addEs [equalityE], simpset())); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
23 |
qed "cons_lemma1"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
24 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
25 |
Goal "[| cons(x, B)=cons(y, C); x~=y; x~:B; y~:C |] \ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
26 |
\ ==> B - {y} = C-{x} & x:C & y:B"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
27 |
by (auto_tac (claset() addEs [equalityE], simpset())); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
28 |
qed "cons_lemma2"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
29 |
|
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
30 |
(* fold_set monotonicity *) |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
31 |
Goal "<C, x> : fold_set(A, B, f, e) \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
32 |
\ ==> ALL D. A<=D --> <C, x> : fold_set(D, B, f, e)"; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
33 |
by (etac fold_set.induct 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
34 |
by (auto_tac (claset() addIs fold_set.intrs, simpset())); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
35 |
qed "fold_set_mono_lemma"; |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
36 |
|
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
37 |
Goal " C<=A ==> fold_set(C, B, f, e) <= fold_set(A, B, f, e)"; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
38 |
by (Clarify_tac 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
39 |
by (forward_tac [impOfSubs fold_set.dom_subset] 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
40 |
by (Clarify_tac 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
41 |
by (auto_tac (claset() addDs [fold_set_mono_lemma], simpset())); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
42 |
qed "fold_set_mono"; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
43 |
|
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
44 |
Goal "<C, x>:fold_set(A, B, f, e) ==> <C, x>:fold_set(C, B, f, e) & C<=A"; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
45 |
by (etac fold_set.induct 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
46 |
by (auto_tac (claset() addSIs fold_set.intrs |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
47 |
addIs [fold_set_mono RS subsetD], simpset())); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
48 |
qed "fold_set_lemma"; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
49 |
|
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
50 |
(* Proving that fold_set is deterministic *) |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
51 |
Goal "[| <C-{x},y> : fold_set(A, B, f,e); x:C; x:A; f(x, y):B |] \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
52 |
\ ==> <C, f(x, y)> : fold_set(A, B, f, e)"; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
53 |
by (ftac (fold_set.dom_subset RS subsetD) 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
54 |
by (etac (cons_Diff RS subst) 1 THEN resolve_tac fold_set.intrs 1); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
55 |
by Auto_tac; |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
56 |
qed "Diff1_fold_set"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
57 |
|
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
58 |
Goal "[| C:Fin(A); e:B; ALL x:A. ALL y:B. f(x, y):B |] ==>\ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
59 |
\ (EX x. <C, x> : fold_set(A, B, f,e))"; |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
60 |
by (etac Fin_induct 1); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
61 |
by Auto_tac; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
62 |
by (ftac (fold_set.dom_subset RS subsetD) 2); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
63 |
by (auto_tac (claset() addDs [fold_set.dom_subset RS subsetD] |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
64 |
addIs fold_set.intrs, simpset())); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
65 |
qed_spec_mp "Fin_imp_fold_set"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
66 |
|
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
67 |
Goal |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
68 |
"[| n:nat; e:B; \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
69 |
\ ALL x:A. ALL y:B. f(x, y):B; \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
70 |
\ ALL x:A. ALL y:A. ALL z:B. f(x, f(y, z))=f(y, f(x, z)) |] \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
71 |
\ ==> ALL C. |C|<n --> \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
72 |
\ (ALL x. <C, x> : fold_set(A, B, f,e)-->\ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
73 |
\ (ALL y. <C, y> : fold_set(A, B, f,e) --> y=x))"; |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
74 |
by (etac nat_induct 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
75 |
by (auto_tac (claset(), simpset() addsimps [le_iff])); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
76 |
by (Blast_tac 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
77 |
by (etac fold_set.elim 1); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
78 |
by (force_tac (claset() addSEs [empty_fold_setE], simpset()) 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
79 |
by (etac fold_set.elim 1); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
80 |
by (force_tac (claset() addSEs [empty_fold_setE], simpset()) 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
81 |
by (Clarify_tac 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
82 |
(*force simplification of "|C| < |cons(...)|"*) |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
83 |
by (rotate_tac 4 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
84 |
by (etac rev_mp 1); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
85 |
by (forw_inst_tac [("a", "Ca")] |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
86 |
(fold_set.dom_subset RS subsetD RS SigmaD1) 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
87 |
by (forw_inst_tac [("a", "Cb")] |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
88 |
(fold_set.dom_subset RS subsetD RS SigmaD1) 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
89 |
by (asm_simp_tac (simpset() addsimps |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
90 |
[Fin_into_Finite RS Finite_imp_cardinal_cons]) 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
91 |
by (rtac impI 1); |
13241 | 92 |
(** LEVEL 14 **) |
93 |
by (case_tac "x=xb" 1 THEN Auto_tac); (*SLOW*) |
|
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
94 |
by (asm_full_simp_tac (simpset() addsimps [cons_lemma1]) 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
95 |
by (REPEAT(thin_tac "ALL x:A. ?u(x)" 1) THEN Blast_tac 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
96 |
(*case x ~= xb*) |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
97 |
by (dtac cons_lemma2 1 THEN ALLGOALS Clarify_tac); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
98 |
by (subgoal_tac "Ca = cons(xb, Cb) - {x}" 1); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
99 |
by (REPEAT(thin_tac "ALL C. ?P(C)" 2)); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
100 |
by (REPEAT(thin_tac "ALL x:?u. ?P(x)" 2)); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
101 |
by (blast_tac (claset() addEs [equalityE]) 2); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
102 |
(** LEVEL 22 **) |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
103 |
by (subgoal_tac "|Ca| le |Cb|" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
104 |
by (rtac succ_le_imp_le 2); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
105 |
by (hyp_subst_tac 2); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
106 |
by (subgoal_tac "Finite(cons(xb, Cb)) & x:cons(xb, Cb) " 2); |
13241 | 107 |
by (asm_full_simp_tac (simpset() addsimps [Finite_imp_succ_cardinal_Diff, |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
108 |
Fin_into_Finite RS Finite_imp_cardinal_cons]) 2); |
13241 | 109 |
by (asm_simp_tac (simpset() addsimps [Fin_into_Finite]) 2); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
110 |
by (res_inst_tac [("C1", "Ca-{xb}"), ("e1","e"), ("A1", "A"), ("f1", "f")] |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
111 |
(Fin_imp_fold_set RS exE) 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
112 |
by (blast_tac (claset() addIs [Diff_subset RS Fin_subset]) 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
113 |
by (Blast_tac 1); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
114 |
by (blast_tac (claset() addSDs [FinD]) 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
115 |
(** LEVEL 32 **) |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
116 |
by (ftac Diff1_fold_set 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
117 |
by (Blast_tac 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
118 |
by (Blast_tac 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
119 |
by (blast_tac (claset() addSDs [fold_set.dom_subset RS subsetD]) 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
120 |
by (subgoal_tac "ya = f(xb, xa)" 1); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
121 |
by (dres_inst_tac [("x", "Ca")] spec 2); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
122 |
by (blast_tac (claset() delrules [equalityCE]) 2); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
123 |
by (subgoal_tac "<Cb-{x}, xa>: fold_set(A, B, f, e)" 1); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
124 |
by (Asm_full_simp_tac 2); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
125 |
by (subgoal_tac "yb = f(x, xa)" 1); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
126 |
by (dres_inst_tac [("C", "Cb")] Diff1_fold_set 2); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
127 |
by (ALLGOALS(Asm_simp_tac)); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
128 |
by (force_tac (claset() addSDs [fold_set.dom_subset RS subsetD], simpset()) 2); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
129 |
by (force_tac (claset() addSDs [fold_set.dom_subset RS subsetD], simpset()) 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
130 |
by (dres_inst_tac [("x", "Cb")] spec 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
131 |
by Auto_tac; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
132 |
qed_spec_mp "fold_set_determ_lemma"; |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
133 |
|
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
134 |
Goal |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
135 |
"[| <C, x>:fold_set(A, B, f, e); \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
136 |
\ <C, y>:fold_set(A, B, f, e); e:B; \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
137 |
\ ALL x:A. ALL y:B. f(x, y):B; \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
138 |
\ ALL x:A. ALL y:A. ALL z:B. f(x,f(y, z))=f(y, f(x, z)) |]\ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
139 |
\ ==> y=x"; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
140 |
by (forward_tac [fold_set.dom_subset RS subsetD] 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
141 |
by (Clarify_tac 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
142 |
by (dtac Fin_into_Finite 1); |
12484 | 143 |
by (rewtac Finite_def); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
144 |
by (Clarify_tac 1); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
145 |
by (res_inst_tac [("n", "succ(n)"), ("e", "e"), ("A", "A"), |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
146 |
("f", "f"), ("B", "B")] fold_set_determ_lemma 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
147 |
by (auto_tac (claset() addIs [eqpoll_imp_lepoll RS |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
148 |
lepoll_cardinal_le], simpset())); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
149 |
qed "fold_set_determ"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
150 |
|
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
151 |
(** The fold function **) |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
152 |
|
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
153 |
Goalw [fold_def] |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
154 |
"[| <C, y>:fold_set(A, B, f, e); e:B; \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
155 |
\ ALL x:A. ALL y:B. f(x, y):B; \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
156 |
\ ALL x:A. ALL y:A. ALL z:B. f(x, f(y, z))=f(y, f(x, z)) |] \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
157 |
\ ==> fold[B](f, e, C) = y"; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
158 |
by (forward_tac [fold_set.dom_subset RS subsetD] 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
159 |
by (Clarify_tac 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
160 |
by (rtac the_equality 1); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
161 |
by (res_inst_tac [("f", "f"), ("e", "e"), ("B", "B")] fold_set_determ 2); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
162 |
by (auto_tac (claset() addDs [fold_set_lemma], simpset())); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
163 |
by (blast_tac (claset() addSDs [FinD]) 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
164 |
qed "fold_equality"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
165 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
166 |
Goalw [fold_def] "e:B ==> fold[B](f,e,0) = e"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
167 |
by (blast_tac (claset() addSEs [empty_fold_setE] |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
168 |
addIs fold_set.intrs) 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
169 |
qed "fold_0"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
170 |
Addsimps [fold_0]; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
171 |
|
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
172 |
Goal |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
173 |
"[| C:Fin(A); c:A; c~:C; e:B; ALL x:A. ALL y:B. f(x, y):B; \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
174 |
\ ALL x:A. ALL y:A. ALL z:B. f(x, f(y, z))=f(y, f(x,z)) |] \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
175 |
\ ==> <cons(c, C), v> : fold_set(cons(c, C), B, f, e) <-> \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
176 |
\ (EX y. <C, y> : fold_set(C, B, f, e) & v = f(c, y))"; |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
177 |
by Auto_tac; |
13194 | 178 |
by (forward_tac [inst "a" "c" (thm"Fin.consI") RS FinD RS fold_set_mono RS subsetD] 1); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
179 |
by (assume_tac 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
180 |
by (assume_tac 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
181 |
by (forward_tac [FinD RS fold_set_mono RS subsetD] 2); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
182 |
by (assume_tac 2); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
183 |
by (ALLGOALS(forward_tac [inst "A" "A" fold_set.dom_subset RS subsetD])); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
184 |
by (ALLGOALS(dresolve_tac [FinD])); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
185 |
by (res_inst_tac [("A1", "cons(c, C)"), ("f1", "f"), |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
186 |
("B1", "B"), ("C1", "C")] (Fin_imp_fold_set RS exE) 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
187 |
by (res_inst_tac [("b", "cons(c, C)")] Fin_subset 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
188 |
by (resolve_tac [Finite_into_Fin] 2); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
189 |
by (resolve_tac [Fin_into_Finite] 2); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
190 |
by (Blast_tac 2); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
191 |
by (res_inst_tac [("x", "x")] exI 4); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
192 |
by (auto_tac (claset() addIs fold_set.intrs, simpset())); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
193 |
by (dresolve_tac [inst "C" "C" fold_set_lemma] 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
194 |
by (Blast_tac 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
195 |
by (resolve_tac fold_set.intrs 2); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
196 |
by Auto_tac; |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
197 |
by (blast_tac (claset() addIs [fold_set_mono RS subsetD]) 2); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
198 |
by (resolve_tac [fold_set_determ] 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
199 |
by (assume_tac 5); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
200 |
by Auto_tac; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
201 |
by (resolve_tac fold_set.intrs 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
202 |
by Auto_tac; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
203 |
by (blast_tac (claset() addIs [fold_set_mono RS subsetD]) 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
204 |
by (blast_tac (claset() addDs [fold_set.dom_subset RS subsetD]) 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
205 |
qed_spec_mp "fold_cons_lemma"; |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
206 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
207 |
Goalw [fold_def] |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
208 |
"[| C:Fin(A); c:A; c~:C; e:B; \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
209 |
\ (ALL x:A. ALL y:B. f(x, y):B); \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
210 |
\ (ALL x:A. ALL y:A. ALL z:B. f(x, f(y, z))=f(y, f(x, z))) |]\ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
211 |
\ ==> fold[B](f, e, cons(c, C)) = f(c, fold[B](f, e, C))"; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
212 |
by (asm_simp_tac (simpset() addsimps [fold_cons_lemma]) 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
213 |
by (rtac the_equality 1); |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
214 |
by (dres_inst_tac [("e", "e"), ("f", "f")] Fin_imp_fold_set 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
215 |
by Auto_tac; |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
216 |
by (res_inst_tac [("x", "x")] exI 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
217 |
by Auto_tac; |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
218 |
by (blast_tac (claset() addDs [fold_set_lemma]) 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
219 |
by (ALLGOALS(dtac fold_equality)); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
220 |
by (auto_tac (claset(), simpset() addsimps [symmetric fold_def])); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
221 |
by (REPEAT(blast_tac (claset() addDs [FinD]) 1)); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
222 |
qed "fold_cons"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
223 |
|
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
224 |
Goal |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
225 |
"[| C:Fin(A); e:B; \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
226 |
\ (ALL x:A. ALL y:B. f(x, y):B); \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
227 |
\ (ALL x:A. ALL y:A. ALL z:B. f(x, f(y, z))=f(y, f(x, z))) |] ==> \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
228 |
\ fold[B](f, e,C):B"; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
229 |
by (etac Fin_induct 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
230 |
by (ALLGOALS(asm_simp_tac (simpset() addsimps [fold_cons]))); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
231 |
qed_spec_mp "fold_type"; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
232 |
AddTCs [fold_type]; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
233 |
Addsimps [fold_type]; |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
234 |
|
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
235 |
Goal |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
236 |
"[| C:Fin(A); c:A; \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
237 |
\ ALL x:A. ALL y:B. f(x, y):B; \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
238 |
\ ALL x:A. ALL y:A. ALL z:B. f(x, f(y, z))=f(y, f(x, z)) |] \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
239 |
\ ==> (ALL y:B. f(c, fold[B](f, y, C)) = fold[B](f, f(c, y), C))"; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
240 |
by (etac Fin_induct 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
241 |
by (ALLGOALS(asm_simp_tac (simpset() addsimps [fold_cons]))); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
242 |
qed_spec_mp "fold_commute"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
243 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
244 |
Goal "x:D ==> cons(x, C) Int D = cons(x, C Int D)"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
245 |
by Auto_tac; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
246 |
qed "cons_Int_right_lemma1"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
247 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
248 |
Goal "x~:D ==> cons(x, C) Int D = C Int D"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
249 |
by Auto_tac; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
250 |
qed "cons_Int_right_lemma2"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
251 |
|
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
252 |
Goal |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
253 |
"[| C:Fin(A); D:Fin(A); e:B; \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
254 |
\ ALL x:A. ALL y:B. f(x, y):B; \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
255 |
\ ALL x:A. ALL y:A. ALL z:B. f(x, f(y, z))=f(y, f(x, z)) |] \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
256 |
\ ==> \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
257 |
\ fold[B](f, fold[B](f, e, D), C) \ |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
258 |
\ = fold[B](f, fold[B](f, e, (C Int D)), C Un D)"; |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
259 |
by (etac Fin_induct 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
260 |
by Auto_tac; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
261 |
by (subgoal_tac "cons(x, y) Un D = cons(x, y Un D)" 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
262 |
by Auto_tac; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
263 |
by (subgoal_tac "y Int D:Fin(A) & y Un D:Fin(A)" 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
264 |
by (Clarify_tac 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
265 |
by (case_tac "x:D" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
266 |
by (ALLGOALS(asm_simp_tac (simpset() addsimps |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
267 |
[cons_Int_right_lemma1,cons_Int_right_lemma2, |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
268 |
fold_cons, fold_commute,cons_absorb]))); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
269 |
qed "fold_nest_Un_Int"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
270 |
|
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
271 |
Goal "[| C:Fin(A); D:Fin(A); C Int D = 0; e:B; \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
272 |
\ ALL x:A. ALL y:B. f(x, y):B; \ |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
273 |
\ ALL x:A. ALL y:A. ALL z:B. f(x, f(y, z))=f(y, f(x, z)) |] \ |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
274 |
\ ==> fold[B](f,e,C Un D) = fold[B](f, fold[B](f,e,D), C)"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
275 |
by (asm_simp_tac (simpset() addsimps [fold_nest_Un_Int]) 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
276 |
qed "fold_nest_Un_disjoint"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
277 |
|
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
278 |
Goal "Finite(C) ==> C:Fin(cons(c, C))"; |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
279 |
by (dtac Finite_into_Fin 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
280 |
by (blast_tac (claset() addIs [Fin_mono RS subsetD]) 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
281 |
qed "Finite_cons_lemma"; |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
282 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
283 |
(** setsum **) |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
284 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
285 |
Goalw [setsum_def] "setsum(g, 0) = #0"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
286 |
by (Simp_tac 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
287 |
qed "setsum_0"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
288 |
Addsimps [setsum_0]; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
289 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
290 |
Goalw [setsum_def] |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
291 |
"[| Finite(C); c~:C |] \ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
292 |
\ ==> setsum(g, cons(c, C)) = g(c) $+ setsum(g, C)"; |
12860
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
293 |
by (auto_tac (claset(), simpset() addsimps [Finite_cons])); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
294 |
by (res_inst_tac [("A", "cons(c, C)")] fold_cons 1); |
7fc3fbfed8ef
Multiset: added the translation Mult(A) => A-||>nat-{0}
paulson
parents:
12610
diff
changeset
|
295 |
by (auto_tac (claset() addIs [Finite_cons_lemma], simpset())); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
296 |
qed "setsum_cons"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
297 |
Addsimps [setsum_cons]; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
298 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
299 |
Goal "setsum((%i. #0), C) = #0"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
300 |
by (case_tac "Finite(C)" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
301 |
by (asm_simp_tac (simpset() addsimps [setsum_def]) 2); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
302 |
by (etac Finite_induct 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
303 |
by Auto_tac; |
13535 | 304 |
qed "setsum_K0"; |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
305 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
306 |
(*The reversed orientation looks more natural, but LOOPS as a simprule!*) |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
307 |
Goal "[| Finite(C); Finite(D) |] \ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
308 |
\ ==> setsum(g, C Un D) $+ setsum(g, C Int D) \ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
309 |
\ = setsum(g, C) $+ setsum(g, D)"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
310 |
by (etac Finite_induct 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
311 |
by (subgoal_tac "cons(x, B) Un D = cons(x, B Un D) & \ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
312 |
\ Finite(B Un D) & Finite(B Int D)" 2); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
313 |
by (auto_tac (claset() addIs [Finite_Un, Int_lower1 RS subset_Finite], |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
314 |
simpset())); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
315 |
by (case_tac "x:D" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
316 |
by (subgoal_tac "cons(x, B) Int D = B Int D" 2); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
317 |
by (subgoal_tac "cons(x, B) Int D = cons(x, B Int D)" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
318 |
by Auto_tac; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
319 |
by (subgoal_tac "cons(x, B Un D) = B Un D" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
320 |
by Auto_tac; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
321 |
qed "setsum_Un_Int"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
322 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
323 |
Goal "setsum(g, C):int"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
324 |
by (case_tac "Finite(C)" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
325 |
by (asm_simp_tac (simpset() addsimps [setsum_def]) 2); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
326 |
by (etac Finite_induct 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
327 |
by Auto_tac; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
328 |
qed "setsum_type"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
329 |
Addsimps [setsum_type]; AddTCs [setsum_type]; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
330 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
331 |
Goal "[| Finite(C); Finite(D); C Int D = 0 |] \ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
332 |
\ ==> setsum(g, C Un D) = setsum(g, C) $+ setsum(g,D)"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
333 |
by (stac (setsum_Un_Int RS sym) 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
334 |
by (subgoal_tac "Finite(C Un D)" 3); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
335 |
by (auto_tac (claset() addIs [Finite_Un], simpset())); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
336 |
qed "setsum_Un_disjoint"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
337 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
338 |
Goal "Finite(I) ==> (ALL i:I. Finite(C(i))) --> Finite(RepFun(I, C))"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
339 |
by (etac Finite_induct 1); |
13241 | 340 |
by Auto_tac; |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
341 |
qed_spec_mp "Finite_RepFun"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
342 |
|
13241 | 343 |
Goal "Finite(I) \ |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
344 |
\ ==> (ALL i:I. Finite(C(i))) --> \ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
345 |
\ (ALL i:I. ALL j:I. i~=j --> C(i) Int C(j) = 0) --> \ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
346 |
\ setsum(f, UN i:I. C(i)) = setsum (%i. setsum(f, C(i)), I)"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
347 |
by (etac Finite_induct 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
348 |
by (ALLGOALS(Clarify_tac)); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
349 |
by Auto_tac; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
350 |
by (subgoal_tac "ALL i:B. x ~= i" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
351 |
by (Blast_tac 2); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
352 |
by (subgoal_tac "C(x) Int (UN i:B. C(i)) = 0" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
353 |
by (Blast_tac 2); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
354 |
by (subgoal_tac "Finite(UN i:B. C(i)) & Finite(C(x)) & Finite(B)" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
355 |
by (asm_simp_tac (simpset() addsimps [setsum_Un_disjoint]) 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
356 |
by (auto_tac (claset() addIs [Finite_Union, Finite_RepFun], simpset())); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
357 |
qed_spec_mp "setsum_UN_disjoint"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
358 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
359 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
360 |
Goal "setsum(%x. f(x) $+ g(x),C) = setsum(f, C) $+ setsum(g, C)"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
361 |
by (case_tac "Finite(C)" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
362 |
by (asm_simp_tac (simpset() addsimps [setsum_def]) 2); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
363 |
by (etac Finite_induct 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
364 |
by Auto_tac; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
365 |
qed "setsum_addf"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
366 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
367 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
368 |
val major::prems = Goal |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
369 |
"[| A=B; !!x. x:B ==> f(x) = g(x) |] ==> \ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
370 |
\ setsum(f, A) = setsum(g, B)"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
371 |
by (case_tac "Finite(B)" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
372 |
by (asm_simp_tac (simpset() addsimps [setsum_def, major]) 2); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
373 |
by (subgoal_tac "ALL C. C <= B --> (ALL x:C. f(x) = g(x)) \ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
374 |
\ --> setsum(f,C) = setsum(g, C)" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
375 |
by (cut_facts_tac [major] 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
376 |
by (asm_full_simp_tac (simpset() addsimps [major]@prems) 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
377 |
by (etac Finite_induct 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
378 |
by (ALLGOALS(Clarify_tac)); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
379 |
by (subgoal_tac "C=0" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
380 |
by (Force_tac 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
381 |
by (Blast_tac 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
382 |
by (asm_full_simp_tac (simpset() addsimps [major,subset_cons_iff]@prems) 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
383 |
by Safe_tac; |
12484 | 384 |
by (ftac subset_Finite 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
385 |
by (assume_tac 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
386 |
by (Blast_tac 1); |
12484 | 387 |
by (ftac subset_Finite 1); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
388 |
by (assume_tac 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
389 |
by (subgoal_tac "C = cons(x, C - {x})" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
390 |
by (Blast_tac 2); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
391 |
by (etac ssubst 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
392 |
by (dtac spec 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
393 |
by (mp_tac 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
394 |
by (asm_full_simp_tac (simpset() addsimps [Ball_def, major]@prems) 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
395 |
qed_spec_mp "setsum_cong"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
396 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
397 |
Goal "[| Finite(A); Finite(B) |] \ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
398 |
\ ==> setsum(f, A Un B) = \ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
399 |
\ setsum(f, A) $+ setsum(f, B) $- setsum(f, A Int B)"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
400 |
by (stac (setsum_Un_Int RS sym) 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
401 |
by Auto_tac; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
402 |
qed "setsum_Un"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
403 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
404 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
405 |
Goal "Finite(A) ==> (ALL x:A. g(x) $<= #0) --> setsum(g, A) $<= #0"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
406 |
by (etac Finite_induct 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
407 |
by (auto_tac (claset() addIs [zneg_or_0_add_zneg_or_0_imp_zneg_or_0], simpset())); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
408 |
qed_spec_mp "setsum_zneg_or_0"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
409 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
410 |
Goal "Finite(A) \ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
411 |
\ ==> ALL n:nat. setsum(f,A) = $# succ(n) --> (EX a:A. #0 $< f(a))"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
412 |
by (etac Finite_induct 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
413 |
by (auto_tac (claset(), simpset() |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
414 |
delsimps [int_of_0, int_of_succ] |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
415 |
addsimps [not_zless_iff_zle, int_of_0 RS sym])); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
416 |
by (subgoal_tac "setsum(f, B) $<= #0" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
417 |
by (ALLGOALS(Asm_full_simp_tac)); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
418 |
by (blast_tac (claset() addIs [setsum_zneg_or_0]) 2); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
419 |
by (subgoal_tac "$# 1 $<= f(x) $+ setsum(f, B)" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
420 |
by (dtac (zdiff_zle_iff RS iffD2) 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
421 |
by (subgoal_tac "$# 1 $<= $# 1 $- setsum(f,B)" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
422 |
by (dres_inst_tac [("x", "$# 1")] zle_trans 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
423 |
by (res_inst_tac [("j", "#1")] zless_zle_trans 2); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
424 |
by Auto_tac; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
425 |
qed "setsum_succD_lemma"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
426 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
427 |
Goal "[| setsum(f, A) = $# succ(n); n:nat |]==> EX a:A. #0 $< f(a)"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
428 |
by (case_tac "Finite(A)" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
429 |
by (blast_tac (claset() |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
430 |
addIs [setsum_succD_lemma RS bspec RS mp]) 1); |
12484 | 431 |
by (rewtac setsum_def); |
12089
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
432 |
by (auto_tac (claset(), |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
433 |
simpset() delsimps [int_of_0, int_of_succ] |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
434 |
addsimps [int_succ_int_1 RS sym, int_of_0 RS sym])); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
435 |
qed "setsum_succD"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
436 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
437 |
Goal "Finite(A) ==> (ALL x:A. #0 $<= g(x)) --> #0 $<= setsum(g, A)"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
438 |
by (etac Finite_induct 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
439 |
by (Simp_tac 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
440 |
by (auto_tac (claset() addIs [zpos_add_zpos_imp_zpos], simpset())); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
441 |
qed_spec_mp "g_zpos_imp_setsum_zpos"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
442 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
443 |
Goal "[| Finite(A); ALL x. #0 $<= g(x) |] ==> #0 $<= setsum(g, A)"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
444 |
by (etac Finite_induct 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
445 |
by (auto_tac (claset() addIs [zpos_add_zpos_imp_zpos], simpset())); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
446 |
qed_spec_mp "g_zpos_imp_setsum_zpos2"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
447 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
448 |
Goal "Finite(A) \ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
449 |
\ ==> (ALL x:A. #0 $< g(x)) --> A ~= 0 --> (#0 $< setsum(g, A))"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
450 |
by (etac Finite_induct 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
451 |
by (auto_tac (claset() addIs [zspos_add_zspos_imp_zspos],simpset())); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
452 |
qed_spec_mp "g_zspos_imp_setsum_zspos"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
453 |
|
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
454 |
Goal "Finite(A) \ |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
455 |
\ ==> ALL a. M(a) = #0 --> setsum(M, A) = setsum(M, A-{a})"; |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
456 |
by (etac Finite_induct 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
457 |
by (ALLGOALS(Clarify_tac)); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
458 |
by (Simp_tac 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
459 |
by (case_tac "x=a" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
460 |
by (subgoal_tac "cons(x, B) - {a} = cons(x, B -{a}) & Finite(B - {a})" 2); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
461 |
by (subgoal_tac "cons(a, B) - {a} = B" 1); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
462 |
by (auto_tac (claset() addIs [Finite_Diff], simpset())); |
34e7693271a9
Sidi Ehmety's port of the fold_set operator and multisets to ZF.
paulson
parents:
diff
changeset
|
463 |
qed_spec_mp "setsum_Diff"; |