36 by (etac (cons_absorb RS ssubst) 3 THEN assume_tac 3); (*backtracking!*) |
36 by (etac (cons_absorb RS ssubst) 3 THEN assume_tac 3); (*backtracking!*) |
37 by (REPEAT (ares_tac prems 1)); |
37 by (REPEAT (ares_tac prems 1)); |
38 qed "Fin_induct"; |
38 qed "Fin_induct"; |
39 |
39 |
40 (** Simplification for Fin **) |
40 (** Simplification for Fin **) |
41 val Fin_ss = arith_ss addsimps Fin.intrs; |
41 Addsimps Fin.intrs; |
42 |
42 |
43 (*The union of two finite sets is finite.*) |
43 (*The union of two finite sets is finite.*) |
44 val major::prems = goal Finite.thy |
44 goal Finite.thy |
45 "[| b: Fin(A); c: Fin(A) |] ==> b Un c : Fin(A)"; |
45 "!!b c. [| b: Fin(A); c: Fin(A) |] ==> b Un c : Fin(A)"; |
46 by (rtac (major RS Fin_induct) 1); |
46 by (etac Fin_induct 1); |
47 by (ALLGOALS (asm_simp_tac (Fin_ss addsimps (prems@[Un_0, Un_cons])))); |
47 by (ALLGOALS (asm_simp_tac (!simpset addsimps [Un_cons]))); |
48 qed "Fin_UnI"; |
48 qed "Fin_UnI"; |
|
49 |
|
50 Addsimps [Fin_UnI]; |
49 |
51 |
50 (*The union of a set of finite sets is finite.*) |
52 (*The union of a set of finite sets is finite.*) |
51 val [major] = goal Finite.thy "C : Fin(Fin(A)) ==> Union(C) : Fin(A)"; |
53 val [major] = goal Finite.thy "C : Fin(Fin(A)) ==> Union(C) : Fin(A)"; |
52 by (rtac (major RS Fin_induct) 1); |
54 by (rtac (major RS Fin_induct) 1); |
53 by (ALLGOALS (asm_simp_tac (Fin_ss addsimps [Union_0, Union_cons, Fin_UnI]))); |
55 by (ALLGOALS Asm_simp_tac); |
54 qed "Fin_UnionI"; |
56 qed "Fin_UnionI"; |
55 |
57 |
56 (*Every subset of a finite set is finite.*) |
58 (*Every subset of a finite set is finite.*) |
57 goal Finite.thy "!!b A. b: Fin(A) ==> ALL z. z<=b --> z: Fin(A)"; |
59 goal Finite.thy "!!b A. b: Fin(A) ==> ALL z. z<=b --> z: Fin(A)"; |
58 by (etac Fin_induct 1); |
60 by (etac Fin_induct 1); |
59 by (simp_tac (Fin_ss addsimps [subset_empty_iff]) 1); |
61 by (simp_tac (!simpset addsimps [subset_empty_iff]) 1); |
60 by (asm_simp_tac (ZF_ss addsimps subset_cons_iff::distrib_simps) 1); |
62 by (asm_simp_tac (!simpset addsimps subset_cons_iff::distrib_simps) 1); |
61 by (safe_tac ZF_cs); |
63 by (safe_tac (!claset)); |
62 by (eres_inst_tac [("b","z")] (cons_Diff RS subst) 1); |
64 by (eres_inst_tac [("b","z")] (cons_Diff RS subst) 1); |
63 by (asm_simp_tac Fin_ss 1); |
65 by (Asm_simp_tac 1); |
64 qed "Fin_subset_lemma"; |
66 qed "Fin_subset_lemma"; |
65 |
67 |
66 goal Finite.thy "!!c b A. [| c<=b; b: Fin(A) |] ==> c: Fin(A)"; |
68 goal Finite.thy "!!c b A. [| c<=b; b: Fin(A) |] ==> c: Fin(A)"; |
67 by (REPEAT (ares_tac [Fin_subset_lemma RS spec RS mp] 1)); |
69 by (REPEAT (ares_tac [Fin_subset_lemma RS spec RS mp] 1)); |
68 qed "Fin_subset"; |
70 qed "Fin_subset"; |
72 \ P(b); \ |
74 \ P(b); \ |
73 \ !!x y. [| x: A; y: Fin(A); x:y; P(y) |] ==> P(y-{x}) \ |
75 \ !!x y. [| x: A; y: Fin(A); x:y; P(y) |] ==> P(y-{x}) \ |
74 \ |] ==> c<=b --> P(b-c)"; |
76 \ |] ==> c<=b --> P(b-c)"; |
75 by (rtac (major RS Fin_induct) 1); |
77 by (rtac (major RS Fin_induct) 1); |
76 by (stac Diff_cons 2); |
78 by (stac Diff_cons 2); |
77 by (ALLGOALS (asm_simp_tac (Fin_ss addsimps (prems@[Diff_0, cons_subset_iff, |
79 by (ALLGOALS (asm_simp_tac (!simpset addsimps (prems@[cons_subset_iff, |
78 Diff_subset RS Fin_subset])))); |
80 Diff_subset RS Fin_subset])))); |
79 qed "Fin_0_induct_lemma"; |
81 qed "Fin_0_induct_lemma"; |
80 |
82 |
81 val prems = goal Finite.thy |
83 val prems = goal Finite.thy |
82 "[| b: Fin(A); \ |
84 "[| b: Fin(A); \ |
89 qed "Fin_0_induct"; |
91 qed "Fin_0_induct"; |
90 |
92 |
91 (*Functions from a finite ordinal*) |
93 (*Functions from a finite ordinal*) |
92 val prems = goal Finite.thy "n: nat ==> n->A <= Fin(nat*A)"; |
94 val prems = goal Finite.thy "n: nat ==> n->A <= Fin(nat*A)"; |
93 by (nat_ind_tac "n" prems 1); |
95 by (nat_ind_tac "n" prems 1); |
94 by (simp_tac (ZF_ss addsimps [Pi_empty1, Fin.emptyI, subset_iff, cons_iff]) 1); |
96 by (simp_tac (!simpset addsimps [Pi_empty1, subset_iff, cons_iff]) 1); |
95 by (asm_simp_tac (ZF_ss addsimps [succ_def, mem_not_refl RS cons_fun_eq]) 1); |
97 by (asm_simp_tac (!simpset addsimps [succ_def, mem_not_refl RS cons_fun_eq]) 1); |
96 by (fast_tac (ZF_cs addSIs [Fin.consI]) 1); |
98 by (fast_tac (!claset addSIs [Fin.consI]) 1); |
97 qed "nat_fun_subset_Fin"; |
99 qed "nat_fun_subset_Fin"; |
98 |
100 |
99 |
101 |
100 (*** Finite function space ***) |
102 (*** Finite function space ***) |
101 |
103 |
110 by (REPEAT (ares_tac [FiniteFun_mono] 1)); |
112 by (REPEAT (ares_tac [FiniteFun_mono] 1)); |
111 qed "FiniteFun_mono1"; |
113 qed "FiniteFun_mono1"; |
112 |
114 |
113 goal Finite.thy "!!h. h: A -||>B ==> h: domain(h) -> B"; |
115 goal Finite.thy "!!h. h: A -||>B ==> h: domain(h) -> B"; |
114 by (etac FiniteFun.induct 1); |
116 by (etac FiniteFun.induct 1); |
115 by (simp_tac (ZF_ss addsimps [empty_fun, domain_0]) 1); |
117 by (simp_tac (!simpset addsimps [empty_fun, domain_0]) 1); |
116 by (asm_simp_tac (ZF_ss addsimps [fun_extend3, domain_cons]) 1); |
118 by (asm_simp_tac (!simpset addsimps [fun_extend3, domain_cons]) 1); |
117 qed "FiniteFun_is_fun"; |
119 qed "FiniteFun_is_fun"; |
118 |
120 |
119 goal Finite.thy "!!h. h: A -||>B ==> domain(h) : Fin(A)"; |
121 goal Finite.thy "!!h. h: A -||>B ==> domain(h) : Fin(A)"; |
120 by (etac FiniteFun.induct 1); |
122 by (etac FiniteFun.induct 1); |
121 by (simp_tac (Fin_ss addsimps [domain_0]) 1); |
123 by (simp_tac (!simpset addsimps [domain_0]) 1); |
122 by (asm_simp_tac (Fin_ss addsimps [domain_cons]) 1); |
124 by (asm_simp_tac (!simpset addsimps [domain_cons]) 1); |
123 qed "FiniteFun_domain_Fin"; |
125 qed "FiniteFun_domain_Fin"; |
124 |
126 |
125 bind_thm ("FiniteFun_apply_type", FiniteFun_is_fun RS apply_type); |
127 bind_thm ("FiniteFun_apply_type", FiniteFun_is_fun RS apply_type); |
126 |
128 |
127 (*Every subset of a finite function is a finite function.*) |
129 (*Every subset of a finite function is a finite function.*) |
128 goal Finite.thy "!!b A. b: A-||>B ==> ALL z. z<=b --> z: A-||>B"; |
130 goal Finite.thy "!!b A. b: A-||>B ==> ALL z. z<=b --> z: A-||>B"; |
129 by (etac FiniteFun.induct 1); |
131 by (etac FiniteFun.induct 1); |
130 by (simp_tac (ZF_ss addsimps subset_empty_iff::FiniteFun.intrs) 1); |
132 by (simp_tac (!simpset addsimps subset_empty_iff::FiniteFun.intrs) 1); |
131 by (asm_simp_tac (ZF_ss addsimps subset_cons_iff::distrib_simps) 1); |
133 by (asm_simp_tac (!simpset addsimps subset_cons_iff::distrib_simps) 1); |
132 by (safe_tac ZF_cs); |
134 by (safe_tac (!claset)); |
133 by (eres_inst_tac [("b","z")] (cons_Diff RS subst) 1); |
135 by (eres_inst_tac [("b","z")] (cons_Diff RS subst) 1); |
134 by (dtac (spec RS mp) 1 THEN assume_tac 1); |
136 by (dtac (spec RS mp) 1 THEN assume_tac 1); |
135 by (fast_tac (ZF_cs addSIs FiniteFun.intrs) 1); |
137 by (fast_tac (!claset addSIs FiniteFun.intrs) 1); |
136 qed "FiniteFun_subset_lemma"; |
138 qed "FiniteFun_subset_lemma"; |
137 |
139 |
138 goal Finite.thy "!!c b A. [| c<=b; b: A-||>B |] ==> c: A-||>B"; |
140 goal Finite.thy "!!c b A. [| c<=b; b: A-||>B |] ==> c: A-||>B"; |
139 by (REPEAT (ares_tac [FiniteFun_subset_lemma RS spec RS mp] 1)); |
141 by (REPEAT (ares_tac [FiniteFun_subset_lemma RS spec RS mp] 1)); |
140 qed "FiniteFun_subset"; |
142 qed "FiniteFun_subset"; |