190 |
190 |
191 (********) |
191 (********) |
192 val dummy = writeln " Proving monotonicity..."; |
192 val dummy = writeln " Proving monotonicity..."; |
193 |
193 |
194 val bnd_mono = |
194 val bnd_mono = |
195 OldGoals.prove_goalw_cterm [] |
195 standard (Goal.prove sign1 [] [] (FOLogic.mk_Trueprop (Fp.bnd_mono $ dom_sum $ fp_abs)) |
196 (cterm_of sign1 |
196 (fn _ => EVERY |
197 (FOLogic.mk_Trueprop (Fp.bnd_mono $ dom_sum $ fp_abs))) |
197 [rtac (Collect_subset RS bnd_monoI) 1, |
198 (fn _ => |
198 REPEAT (ares_tac (basic_monos @ monos) 1)])); |
199 [rtac (Collect_subset RS bnd_monoI) 1, |
|
200 REPEAT (ares_tac (basic_monos @ monos) 1)]); |
|
201 |
199 |
202 val dom_subset = standard (big_rec_def RS Fp.subs); |
200 val dom_subset = standard (big_rec_def RS Fp.subs); |
203 |
201 |
204 val unfold = standard ([big_rec_def, bnd_mono] MRS Fp.Tarski); |
202 val unfold = standard ([big_rec_def, bnd_mono] MRS Fp.Tarski); |
205 |
203 |
219 [dom_subset] RL (asm_rl :: ([Part_trans] RL monos)) |
217 [dom_subset] RL (asm_rl :: ([Part_trans] RL monos)) |
220 RL [subsetD]; |
218 RL [subsetD]; |
221 |
219 |
222 (*Type-checking is hardest aspect of proof; |
220 (*Type-checking is hardest aspect of proof; |
223 disjIn selects the correct disjunct after unfolding*) |
221 disjIn selects the correct disjunct after unfolding*) |
224 fun intro_tacsf disjIn prems = |
222 fun intro_tacsf disjIn = |
225 [(*insert prems and underlying sets*) |
223 [DETERM (stac unfold 1), |
226 cut_facts_tac prems 1, |
|
227 DETERM (stac unfold 1), |
|
228 REPEAT (resolve_tac [Part_eqI,CollectI] 1), |
224 REPEAT (resolve_tac [Part_eqI,CollectI] 1), |
229 (*Now 2-3 subgoals: typechecking, the disjunction, perhaps equality.*) |
225 (*Now 2-3 subgoals: typechecking, the disjunction, perhaps equality.*) |
230 rtac disjIn 2, |
226 rtac disjIn 2, |
231 (*Not ares_tac, since refl must be tried before equality assumptions; |
227 (*Not ares_tac, since refl must be tried before equality assumptions; |
232 backtracking may occur if the premises have extra variables!*) |
228 backtracking may occur if the premises have extra variables!*) |
249 val mk_disj_rls = |
245 val mk_disj_rls = |
250 let fun f rl = rl RS disjI1 |
246 let fun f rl = rl RS disjI1 |
251 and g rl = rl RS disjI2 |
247 and g rl = rl RS disjI2 |
252 in accesses_bal(f, g, asm_rl) end; |
248 in accesses_bal(f, g, asm_rl) end; |
253 |
249 |
254 fun prove_intr (ct, tacsf) = OldGoals.prove_goalw_cterm part_rec_defs ct tacsf; |
250 val intrs = |
255 |
251 (intr_tms, map intro_tacsf (mk_disj_rls (length intr_tms))) |
256 val intrs = ListPair.map prove_intr |
252 |> ListPair.map (fn (t, tacs) => |
257 (map (cterm_of sign1) intr_tms, |
253 standard (Goal.prove sign1 [] [] t |
258 map intro_tacsf (mk_disj_rls(length intr_tms))) |
254 (fn _ => EVERY (rewrite_goals_tac part_rec_defs :: tacs)))) |
259 handle MetaSimplifier.SIMPLIFIER (msg,thm) => (print_thm thm; error msg); |
255 handle MetaSimplifier.SIMPLIFIER (msg, thm) => (print_thm thm; error msg); |
260 |
256 |
261 (********) |
257 (********) |
262 val dummy = writeln " Proving the elimination rule..."; |
258 val dummy = writeln " Proving the elimination rule..."; |
263 |
259 |
264 (*Breaks down logical connectives in the monotonic function*) |
260 (*Breaks down logical connectives in the monotonic function*) |
343 (fn prems => resolve_tac (triv_rls@prems) |
339 (fn prems => resolve_tac (triv_rls@prems) |
344 ORELSE' assume_tac |
340 ORELSE' assume_tac |
345 ORELSE' etac FalseE)); |
341 ORELSE' etac FalseE)); |
346 |
342 |
347 val quant_induct = |
343 val quant_induct = |
348 OldGoals.prove_goalw_cterm part_rec_defs |
344 standard (Goal.prove sign1 [] ind_prems |
349 (cterm_of sign1 |
345 (FOLogic.mk_Trueprop (Ind_Syntax.mk_all_imp (big_rec_tm, pred))) |
350 (Logic.list_implies |
346 (fn prems => EVERY |
351 (ind_prems, |
347 [rewrite_goals_tac part_rec_defs, |
352 FOLogic.mk_Trueprop (Ind_Syntax.mk_all_imp(big_rec_tm,pred))))) |
348 rtac (impI RS allI) 1, |
353 (fn prems => |
349 DETERM (etac raw_induct 1), |
354 [rtac (impI RS allI) 1, |
350 (*Push Part inside Collect*) |
355 DETERM (etac raw_induct 1), |
351 full_simp_tac (min_ss addsimps [Part_Collect]) 1, |
356 (*Push Part inside Collect*) |
352 (*This CollectE and disjE separates out the introduction rules*) |
357 full_simp_tac (min_ss addsimps [Part_Collect]) 1, |
353 REPEAT (FIRSTGOAL (eresolve_tac [CollectE, disjE])), |
358 (*This CollectE and disjE separates out the introduction rules*) |
354 (*Now break down the individual cases. No disjE here in case |
359 REPEAT (FIRSTGOAL (eresolve_tac [CollectE, disjE])), |
355 some premise involves disjunction.*) |
360 (*Now break down the individual cases. No disjE here in case |
356 REPEAT (FIRSTGOAL (eresolve_tac [CollectE, exE, conjE] |
361 some premise involves disjunction.*) |
357 ORELSE' bound_hyp_subst_tac)), |
362 REPEAT (FIRSTGOAL (eresolve_tac [CollectE, exE, conjE] |
358 ind_tac (rev (map (rewrite_rule part_rec_defs) prems)) (length prems)])); |
363 ORELSE' bound_hyp_subst_tac)), |
|
364 ind_tac (rev prems) (length prems) ]); |
|
365 |
359 |
366 val dummy = if !Ind_Syntax.trace then |
360 val dummy = if !Ind_Syntax.trace then |
367 (writeln "quant_induct = "; print_thm quant_induct) |
361 (writeln "quant_induct = "; print_thm quant_induct) |
368 else (); |
362 else (); |
369 |
363 |
429 val need_mutual = length rec_names > 1; |
423 val need_mutual = length rec_names > 1; |
430 |
424 |
431 val lemma = (*makes the link between the two induction rules*) |
425 val lemma = (*makes the link between the two induction rules*) |
432 if need_mutual then |
426 if need_mutual then |
433 (writeln " Proving the mutual induction rule..."; |
427 (writeln " Proving the mutual induction rule..."; |
434 OldGoals.prove_goalw_cterm part_rec_defs |
428 standard (Goal.prove sign1 [] [] |
435 (cterm_of sign1 (Logic.mk_implies (induct_concl, |
429 (Logic.mk_implies (induct_concl, mutual_induct_concl)) |
436 mutual_induct_concl))) |
430 (fn _ => EVERY |
437 (fn prems => |
431 [rewrite_goals_tac part_rec_defs, |
438 [cut_facts_tac prems 1, |
432 REPEAT (rewrite_goals_tac [Pr.split_eq] THEN lemma_tac 1)]))) |
439 REPEAT (rewrite_goals_tac [Pr.split_eq] THEN |
433 else (writeln " [ No mutual induction rule needed ]"; TrueI); |
440 lemma_tac 1)])) |
|
441 else (writeln " [ No mutual induction rule needed ]"; |
|
442 TrueI); |
|
443 |
434 |
444 val dummy = if !Ind_Syntax.trace then |
435 val dummy = if !Ind_Syntax.trace then |
445 (writeln "lemma = "; print_thm lemma) |
436 (writeln "lemma = "; print_thm lemma) |
446 else (); |
437 else (); |
447 |
438 |
491 ) i) |
482 ) i) |
492 THEN mutual_ind_tac prems (i-1); |
483 THEN mutual_ind_tac prems (i-1); |
493 |
484 |
494 val mutual_induct_fsplit = |
485 val mutual_induct_fsplit = |
495 if need_mutual then |
486 if need_mutual then |
496 OldGoals.prove_goalw_cterm [] |
487 standard (Goal.prove sign1 [] (map (induct_prem (rec_tms~~preds)) intr_tms) |
497 (cterm_of sign1 |
488 mutual_induct_concl |
498 (Logic.list_implies |
489 (fn prems => EVERY |
499 (map (induct_prem (rec_tms~~preds)) intr_tms, |
490 [rtac (quant_induct RS lemma) 1, |
500 mutual_induct_concl))) |
491 mutual_ind_tac (rev prems) (length prems)])) |
501 (fn prems => |
|
502 [rtac (quant_induct RS lemma) 1, |
|
503 mutual_ind_tac (rev prems) (length prems)]) |
|
504 else TrueI; |
492 else TrueI; |
505 |
493 |
506 (** Uncurrying the predicate in the ordinary induction rule **) |
494 (** Uncurrying the predicate in the ordinary induction rule **) |
507 |
495 |
508 (*instantiate the variable to a tuple, if it is non-trivial, in order to |
496 (*instantiate the variable to a tuple, if it is non-trivial, in order to |