152 val gs = map inst pre_gs |
152 val gs = map inst pre_gs |
153 val lhs = inst pre_lhs |
153 val lhs = inst pre_lhs |
154 val rhs = inst pre_rhs |
154 val rhs = inst pre_rhs |
155 |
155 |
156 val cqs = map (cterm_of thy) qs |
156 val cqs = map (cterm_of thy) qs |
157 val ags = map (assume o cterm_of thy) gs |
157 val ags = map (Thm.assume o cterm_of thy) gs |
158 |
158 |
159 val case_hyp = assume (cterm_of thy (HOLogic.mk_Trueprop (mk_eq (x, lhs)))) |
159 val case_hyp = Thm.assume (cterm_of thy (HOLogic.mk_Trueprop (mk_eq (x, lhs)))) |
160 in |
160 in |
161 ClauseContext { ctxt = ctxt', qs = qs, gs = gs, lhs = lhs, rhs = rhs, |
161 ClauseContext { ctxt = ctxt', qs = qs, gs = gs, lhs = lhs, rhs = rhs, |
162 cqs = cqs, ags = ags, case_hyp = case_hyp } |
162 cqs = cqs, ags = ags, case_hyp = case_hyp } |
163 end |
163 end |
164 |
164 |
186 val ClauseContext { ctxt, qs, cqs, ags, ... } = cdata |
186 val ClauseContext { ctxt, qs, cqs, ags, ... } = cdata |
187 val cert = Thm.cterm_of (ProofContext.theory_of ctxt) |
187 val cert = Thm.cterm_of (ProofContext.theory_of ctxt) |
188 |
188 |
189 (* Instantiate the GIntro thm with "f" and import into the clause context. *) |
189 (* Instantiate the GIntro thm with "f" and import into the clause context. *) |
190 val lGI = GIntro_thm |
190 val lGI = GIntro_thm |
191 |> forall_elim (cert f) |
191 |> Thm.forall_elim (cert f) |
192 |> fold forall_elim cqs |
192 |> fold Thm.forall_elim cqs |
193 |> fold Thm.elim_implies ags |
193 |> fold Thm.elim_implies ags |
194 |
194 |
195 fun mk_call_info (rcfix, rcassm, rcarg) RI = |
195 fun mk_call_info (rcfix, rcassm, rcarg) RI = |
196 let |
196 let |
197 val llRI = RI |
197 val llRI = RI |
198 |> fold forall_elim cqs |
198 |> fold Thm.forall_elim cqs |
199 |> fold (forall_elim o cert o Free) rcfix |
199 |> fold (Thm.forall_elim o cert o Free) rcfix |
200 |> fold Thm.elim_implies ags |
200 |> fold Thm.elim_implies ags |
201 |> fold Thm.elim_implies rcassm |
201 |> fold Thm.elim_implies rcassm |
202 |
202 |
203 val h_assum = |
203 val h_assum = |
204 HOLogic.mk_Trueprop (G $ rcarg $ (h $ rcarg)) |
204 HOLogic.mk_Trueprop (G $ rcarg $ (h $ rcarg)) |
240 in if j < i then |
240 in if j < i then |
241 let |
241 let |
242 val compat = lookup_compat_thm j i cts |
242 val compat = lookup_compat_thm j i cts |
243 in |
243 in |
244 compat (* "!!qj qi. Gsj => Gsi => lhsj = lhsi ==> rhsj = rhsi" *) |
244 compat (* "!!qj qi. Gsj => Gsi => lhsj = lhsi ==> rhsj = rhsi" *) |
245 |> fold forall_elim (cqsj @ cqsi) (* "Gsj => Gsi => lhsj = lhsi ==> rhsj = rhsi" *) |
245 |> fold Thm.forall_elim (cqsj @ cqsi) (* "Gsj => Gsi => lhsj = lhsi ==> rhsj = rhsi" *) |
246 |> fold Thm.elim_implies agsj |
246 |> fold Thm.elim_implies agsj |
247 |> fold Thm.elim_implies agsi |
247 |> fold Thm.elim_implies agsi |
248 |> Thm.elim_implies ((assume lhsi_eq_lhsj) RS sym) (* "Gsj, Gsi, lhsi = lhsj |-- rhsj = rhsi" *) |
248 |> Thm.elim_implies ((Thm.assume lhsi_eq_lhsj) RS sym) (* "Gsj, Gsi, lhsi = lhsj |-- rhsj = rhsi" *) |
249 end |
249 end |
250 else |
250 else |
251 let |
251 let |
252 val compat = lookup_compat_thm i j cts |
252 val compat = lookup_compat_thm i j cts |
253 in |
253 in |
254 compat (* "!!qi qj. Gsi => Gsj => lhsi = lhsj ==> rhsi = rhsj" *) |
254 compat (* "!!qi qj. Gsi => Gsj => lhsi = lhsj ==> rhsi = rhsj" *) |
255 |> fold forall_elim (cqsi @ cqsj) (* "Gsi => Gsj => lhsi = lhsj ==> rhsi = rhsj" *) |
255 |> fold Thm.forall_elim (cqsi @ cqsj) (* "Gsi => Gsj => lhsi = lhsj ==> rhsi = rhsj" *) |
256 |> fold Thm.elim_implies agsi |
256 |> fold Thm.elim_implies agsi |
257 |> fold Thm.elim_implies agsj |
257 |> fold Thm.elim_implies agsj |
258 |> Thm.elim_implies (assume lhsi_eq_lhsj) |
258 |> Thm.elim_implies (Thm.assume lhsi_eq_lhsj) |
259 |> (fn thm => thm RS sym) (* "Gsi, Gsj, lhsi = lhsj |-- rhsj = rhsi" *) |
259 |> (fn thm => thm RS sym) (* "Gsi, Gsj, lhsi = lhsj |-- rhsj = rhsi" *) |
260 end |
260 end |
261 end |
261 end |
262 |
262 |
263 (* Generates the replacement lemma in fully quantified form. *) |
263 (* Generates the replacement lemma in fully quantified form. *) |
272 val ih_elim_case = |
272 val ih_elim_case = |
273 Conv.fconv_rule (ih_conv (K (case_hyp RS eq_reflection))) ih_elim |
273 Conv.fconv_rule (ih_conv (K (case_hyp RS eq_reflection))) ih_elim |
274 |
274 |
275 val Ris = map (fn RCInfo {llRI, ...} => llRI) RCs |
275 val Ris = map (fn RCInfo {llRI, ...} => llRI) RCs |
276 val h_assums = map (fn RCInfo {h_assum, ...} => |
276 val h_assums = map (fn RCInfo {h_assum, ...} => |
277 assume (cterm_of thy (subst_bounds (rev qs, h_assum)))) RCs |
277 Thm.assume (cterm_of thy (subst_bounds (rev qs, h_assum)))) RCs |
278 |
278 |
279 val (eql, _) = |
279 val (eql, _) = |
280 Function_Ctx_Tree.rewrite_by_tree thy h ih_elim_case (Ris ~~ h_assums) tree |
280 Function_Ctx_Tree.rewrite_by_tree thy h ih_elim_case (Ris ~~ h_assums) tree |
281 |
281 |
282 val replace_lemma = (eql RS meta_eq_to_obj_eq) |
282 val replace_lemma = (eql RS meta_eq_to_obj_eq) |
283 |> implies_intr (cprop_of case_hyp) |
283 |> Thm.implies_intr (cprop_of case_hyp) |
284 |> fold_rev (implies_intr o cprop_of) h_assums |
284 |> fold_rev (Thm.implies_intr o cprop_of) h_assums |
285 |> fold_rev (implies_intr o cprop_of) ags |
285 |> fold_rev (Thm.implies_intr o cprop_of) ags |
286 |> fold_rev forall_intr cqs |
286 |> fold_rev Thm.forall_intr cqs |
287 |> Thm.close_derivation |
287 |> Thm.close_derivation |
288 in |
288 in |
289 replace_lemma |
289 replace_lemma |
290 end |
290 end |
291 |
291 |
299 val cctxj as ClauseContext {ags = agsj', lhs = lhsj', rhs = rhsj', qs = qsj', cqs = cqsj', ...} = |
299 val cctxj as ClauseContext {ags = agsj', lhs = lhsj', rhs = rhsj', qs = qsj', cqs = cqsj', ...} = |
300 mk_clause_context x ctxti cdescj |
300 mk_clause_context x ctxti cdescj |
301 |
301 |
302 val rhsj'h = Pattern.rewrite_term thy [(fvar,h)] [] rhsj' |
302 val rhsj'h = Pattern.rewrite_term thy [(fvar,h)] [] rhsj' |
303 val compat = get_compat_thm thy compat_store i j cctxi cctxj |
303 val compat = get_compat_thm thy compat_store i j cctxi cctxj |
304 val Ghsj' = map (fn RCInfo {h_assum, ...} => assume (cterm_of thy (subst_bounds (rev qsj', h_assum)))) RCsj |
304 val Ghsj' = map (fn RCInfo {h_assum, ...} => Thm.assume (cterm_of thy (subst_bounds (rev qsj', h_assum)))) RCsj |
305 |
305 |
306 val RLj_import = RLj |
306 val RLj_import = RLj |
307 |> fold forall_elim cqsj' |
307 |> fold Thm.forall_elim cqsj' |
308 |> fold Thm.elim_implies agsj' |
308 |> fold Thm.elim_implies agsj' |
309 |> fold Thm.elim_implies Ghsj' |
309 |> fold Thm.elim_implies Ghsj' |
310 |
310 |
311 val y_eq_rhsj'h = assume (cterm_of thy (HOLogic.mk_Trueprop (mk_eq (y, rhsj'h)))) |
311 val y_eq_rhsj'h = Thm.assume (cterm_of thy (HOLogic.mk_Trueprop (mk_eq (y, rhsj'h)))) |
312 val lhsi_eq_lhsj' = assume (cterm_of thy (HOLogic.mk_Trueprop (mk_eq (lhsi, lhsj')))) |
312 val lhsi_eq_lhsj' = Thm.assume (cterm_of thy (HOLogic.mk_Trueprop (mk_eq (lhsi, lhsj')))) |
313 (* lhs_i = lhs_j' |-- lhs_i = lhs_j' *) |
313 (* lhs_i = lhs_j' |-- lhs_i = lhs_j' *) |
314 in |
314 in |
315 (trans OF [case_hyp, lhsi_eq_lhsj']) (* lhs_i = lhs_j' |-- x = lhs_j' *) |
315 (trans OF [case_hyp, lhsi_eq_lhsj']) (* lhs_i = lhs_j' |-- x = lhs_j' *) |
316 |> implies_elim RLj_import |
316 |> Thm.implies_elim RLj_import |
317 (* Rj1' ... Rjk', lhs_i = lhs_j' |-- rhs_j'_h = rhs_j'_f *) |
317 (* Rj1' ... Rjk', lhs_i = lhs_j' |-- rhs_j'_h = rhs_j'_f *) |
318 |> (fn it => trans OF [it, compat]) |
318 |> (fn it => trans OF [it, compat]) |
319 (* lhs_i = lhs_j', Gj', Rj1' ... Rjk' |-- rhs_j'_h = rhs_i_f *) |
319 (* lhs_i = lhs_j', Gj', Rj1' ... Rjk' |-- rhs_j'_h = rhs_i_f *) |
320 |> (fn it => trans OF [y_eq_rhsj'h, it]) |
320 |> (fn it => trans OF [y_eq_rhsj'h, it]) |
321 (* lhs_i = lhs_j', Gj', Rj1' ... Rjk', y = rhs_j_h' |-- y = rhs_i_f *) |
321 (* lhs_i = lhs_j', Gj', Rj1' ... Rjk', y = rhs_j_h' |-- y = rhs_i_f *) |
322 |> fold_rev (implies_intr o cprop_of) Ghsj' |
322 |> fold_rev (Thm.implies_intr o cprop_of) Ghsj' |
323 |> fold_rev (implies_intr o cprop_of) agsj' |
323 |> fold_rev (Thm.implies_intr o cprop_of) agsj' |
324 (* lhs_i = lhs_j' , y = rhs_j_h' |-- Gj', Rj1'...Rjk' ==> y = rhs_i_f *) |
324 (* lhs_i = lhs_j' , y = rhs_j_h' |-- Gj', Rj1'...Rjk' ==> y = rhs_i_f *) |
325 |> implies_intr (cprop_of y_eq_rhsj'h) |
325 |> Thm.implies_intr (cprop_of y_eq_rhsj'h) |
326 |> implies_intr (cprop_of lhsi_eq_lhsj') |
326 |> Thm.implies_intr (cprop_of lhsi_eq_lhsj') |
327 |> fold_rev forall_intr (cterm_of thy h :: cqsj') |
327 |> fold_rev Thm.forall_intr (cterm_of thy h :: cqsj') |
328 end |
328 end |
329 |
329 |
330 |
330 |
331 |
331 |
332 fun mk_uniqueness_case thy globals G f ihyp ih_intro G_cases compat_store clauses rep_lemmas clausei = |
332 fun mk_uniqueness_case thy globals G f ihyp ih_intro G_cases compat_store clauses rep_lemmas clausei = |
336 val rhsC = Pattern.rewrite_term thy [(fvar, f)] [] rhs |
336 val rhsC = Pattern.rewrite_term thy [(fvar, f)] [] rhs |
337 |
337 |
338 val ih_intro_case = full_simplify (HOL_basic_ss addsimps [case_hyp]) ih_intro |
338 val ih_intro_case = full_simplify (HOL_basic_ss addsimps [case_hyp]) ih_intro |
339 |
339 |
340 fun prep_RC (RCInfo {llRI, RIvs, CCas, ...}) = (llRI RS ih_intro_case) |
340 fun prep_RC (RCInfo {llRI, RIvs, CCas, ...}) = (llRI RS ih_intro_case) |
341 |> fold_rev (implies_intr o cprop_of) CCas |
341 |> fold_rev (Thm.implies_intr o cprop_of) CCas |
342 |> fold_rev (forall_intr o cterm_of thy o Free) RIvs |
342 |> fold_rev (Thm.forall_intr o cterm_of thy o Free) RIvs |
343 |
343 |
344 val existence = fold (curry op COMP o prep_RC) RCs lGI |
344 val existence = fold (curry op COMP o prep_RC) RCs lGI |
345 |
345 |
346 val P = cterm_of thy (mk_eq (y, rhsC)) |
346 val P = cterm_of thy (mk_eq (y, rhsC)) |
347 val G_lhs_y = assume (cterm_of thy (HOLogic.mk_Trueprop (G $ lhs $ y))) |
347 val G_lhs_y = Thm.assume (cterm_of thy (HOLogic.mk_Trueprop (G $ lhs $ y))) |
348 |
348 |
349 val unique_clauses = |
349 val unique_clauses = |
350 map2 (mk_uniqueness_clause thy globals compat_store clausei) clauses rep_lemmas |
350 map2 (mk_uniqueness_clause thy globals compat_store clausei) clauses rep_lemmas |
351 |
351 |
352 fun elim_implies_eta A AB = |
352 fun elim_implies_eta A AB = |
353 Thm.compose_no_flatten true (A, 0) 1 AB |> Seq.list_of |> the_single |
353 Thm.compose_no_flatten true (A, 0) 1 AB |> Seq.list_of |> the_single |
354 |
354 |
355 val uniqueness = G_cases |
355 val uniqueness = G_cases |
356 |> forall_elim (cterm_of thy lhs) |
356 |> Thm.forall_elim (cterm_of thy lhs) |
357 |> forall_elim (cterm_of thy y) |
357 |> Thm.forall_elim (cterm_of thy y) |
358 |> forall_elim P |
358 |> Thm.forall_elim P |
359 |> Thm.elim_implies G_lhs_y |
359 |> Thm.elim_implies G_lhs_y |
360 |> fold elim_implies_eta unique_clauses |
360 |> fold elim_implies_eta unique_clauses |
361 |> implies_intr (cprop_of G_lhs_y) |
361 |> Thm.implies_intr (cprop_of G_lhs_y) |
362 |> forall_intr (cterm_of thy y) |
362 |> Thm.forall_intr (cterm_of thy y) |
363 |
363 |
364 val P2 = cterm_of thy (lambda y (G $ lhs $ y)) (* P2 y := (lhs, y): G *) |
364 val P2 = cterm_of thy (lambda y (G $ lhs $ y)) (* P2 y := (lhs, y): G *) |
365 |
365 |
366 val exactly_one = |
366 val exactly_one = |
367 ex1I |> instantiate' [SOME (ctyp_of thy ranT)] [SOME P2, SOME (cterm_of thy rhsC)] |
367 ex1I |> instantiate' [SOME (ctyp_of thy ranT)] [SOME P2, SOME (cterm_of thy rhsC)] |
368 |> curry (op COMP) existence |
368 |> curry (op COMP) existence |
369 |> curry (op COMP) uniqueness |
369 |> curry (op COMP) uniqueness |
370 |> simplify (HOL_basic_ss addsimps [case_hyp RS sym]) |
370 |> simplify (HOL_basic_ss addsimps [case_hyp RS sym]) |
371 |> implies_intr (cprop_of case_hyp) |
371 |> Thm.implies_intr (cprop_of case_hyp) |
372 |> fold_rev (implies_intr o cprop_of) ags |
372 |> fold_rev (Thm.implies_intr o cprop_of) ags |
373 |> fold_rev forall_intr cqs |
373 |> fold_rev Thm.forall_intr cqs |
374 |
374 |
375 val function_value = |
375 val function_value = |
376 existence |
376 existence |
377 |> implies_intr ihyp |
377 |> Thm.implies_intr ihyp |
378 |> implies_intr (cprop_of case_hyp) |
378 |> Thm.implies_intr (cprop_of case_hyp) |
379 |> forall_intr (cterm_of thy x) |
379 |> Thm.forall_intr (cterm_of thy x) |
380 |> forall_elim (cterm_of thy lhs) |
380 |> Thm.forall_elim (cterm_of thy lhs) |
381 |> curry (op RS) refl |
381 |> curry (op RS) refl |
382 in |
382 in |
383 (exactly_one, function_value) |
383 (exactly_one, function_value) |
384 end |
384 end |
385 |
385 |
410 |
410 |
411 val _ = trace_msg (K "Proving: Graph is a function") |
411 val _ = trace_msg (K "Proving: Graph is a function") |
412 val graph_is_function = complete |
412 val graph_is_function = complete |
413 |> Thm.forall_elim_vars 0 |
413 |> Thm.forall_elim_vars 0 |
414 |> fold (curry op COMP) ex1s |
414 |> fold (curry op COMP) ex1s |
415 |> implies_intr (ihyp) |
415 |> Thm.implies_intr (ihyp) |
416 |> implies_intr (cterm_of thy (HOLogic.mk_Trueprop (mk_acc domT R $ x))) |
416 |> Thm.implies_intr (cterm_of thy (HOLogic.mk_Trueprop (mk_acc domT R $ x))) |
417 |> forall_intr (cterm_of thy x) |
417 |> Thm.forall_intr (cterm_of thy x) |
418 |> (fn it => Drule.compose_single (it, 2, acc_induct_rule)) (* "EX! y. (?x,y):G" *) |
418 |> (fn it => Drule.compose_single (it, 2, acc_induct_rule)) (* "EX! y. (?x,y):G" *) |
419 |> (fn it => fold (forall_intr o cterm_of thy o Var) (Term.add_vars (prop_of it) []) it) |
419 |> (fn it => fold (Thm.forall_intr o cterm_of thy o Var) (Term.add_vars (prop_of it) []) it) |
420 |
420 |
421 val goalstate = Conjunction.intr graph_is_function complete |
421 val goalstate = Conjunction.intr graph_is_function complete |
422 |> Thm.close_derivation |
422 |> Thm.close_derivation |
423 |> Goal.protect |
423 |> Goal.protect |
424 |> fold_rev (implies_intr o cprop_of) compat |
424 |> fold_rev (Thm.implies_intr o cprop_of) compat |
425 |> implies_intr (cprop_of complete) |
425 |> Thm.implies_intr (cprop_of complete) |
426 in |
426 in |
427 (goalstate, values) |
427 (goalstate, values) |
428 end |
428 end |
429 |
429 |
430 (* wrapper -- restores quantifiers in rule specifications *) |
430 (* wrapper -- restores quantifiers in rule specifications *) |
560 fun mk_psimp (ClauseInfo {qglr = (oqs, _, _, _), cdata = ClauseContext {cqs, lhs, ags, ...}, ...}) valthm = |
560 fun mk_psimp (ClauseInfo {qglr = (oqs, _, _, _), cdata = ClauseContext {cqs, lhs, ags, ...}, ...}) valthm = |
561 let |
561 let |
562 val lhs_acc = cterm_of thy (HOLogic.mk_Trueprop (mk_acc domT R $ lhs)) (* "acc R lhs" *) |
562 val lhs_acc = cterm_of thy (HOLogic.mk_Trueprop (mk_acc domT R $ lhs)) (* "acc R lhs" *) |
563 val z_smaller = cterm_of thy (HOLogic.mk_Trueprop (R $ z $ lhs)) (* "R z lhs" *) |
563 val z_smaller = cterm_of thy (HOLogic.mk_Trueprop (R $ z $ lhs)) (* "R z lhs" *) |
564 in |
564 in |
565 ((assume z_smaller) RS ((assume lhs_acc) RS acc_downward)) |
565 ((Thm.assume z_smaller) RS ((Thm.assume lhs_acc) RS acc_downward)) |
566 |> (fn it => it COMP graph_is_function) |
566 |> (fn it => it COMP graph_is_function) |
567 |> implies_intr z_smaller |
567 |> Thm.implies_intr z_smaller |
568 |> forall_intr (cterm_of thy z) |
568 |> Thm.forall_intr (cterm_of thy z) |
569 |> (fn it => it COMP valthm) |
569 |> (fn it => it COMP valthm) |
570 |> implies_intr lhs_acc |
570 |> Thm.implies_intr lhs_acc |
571 |> asm_simplify (HOL_basic_ss addsimps [f_iff]) |
571 |> asm_simplify (HOL_basic_ss addsimps [f_iff]) |
572 |> fold_rev (implies_intr o cprop_of) ags |
572 |> fold_rev (Thm.implies_intr o cprop_of) ags |
573 |> fold_rev forall_intr_rename (map fst oqs ~~ cqs) |
573 |> fold_rev forall_intr_rename (map fst oqs ~~ cqs) |
574 end |
574 end |
575 in |
575 in |
576 map2 mk_psimp clauses valthms |
576 map2 mk_psimp clauses valthms |
577 end |
577 end |
604 val ihyp = Term.all domT $ Abs ("z", domT, |
604 val ihyp = Term.all domT $ Abs ("z", domT, |
605 Logic.mk_implies (HOLogic.mk_Trueprop (R $ Bound 0 $ x), |
605 Logic.mk_implies (HOLogic.mk_Trueprop (R $ Bound 0 $ x), |
606 HOLogic.mk_Trueprop (P $ Bound 0))) |
606 HOLogic.mk_Trueprop (P $ Bound 0))) |
607 |> cterm_of thy |
607 |> cterm_of thy |
608 |
608 |
609 val aihyp = assume ihyp |
609 val aihyp = Thm.assume ihyp |
610 |
610 |
611 fun prove_case clause = |
611 fun prove_case clause = |
612 let |
612 let |
613 val ClauseInfo {cdata = ClauseContext {ctxt, qs, cqs, ags, gs, lhs, case_hyp, ...}, |
613 val ClauseInfo {cdata = ClauseContext {ctxt, qs, cqs, ags, gs, lhs, case_hyp, ...}, |
614 RCs, qglr = (oqs, _, _, _), ...} = clause |
614 RCs, qglr = (oqs, _, _, _), ...} = clause |
620 fconv_rule (Conv.binder_conv |
620 fconv_rule (Conv.binder_conv |
621 (K (arg1_conv (arg_conv (arg_conv case_hyp_conv)))) ctxt) aihyp |
621 (K (arg1_conv (arg_conv (arg_conv case_hyp_conv)))) ctxt) aihyp |
622 end |
622 end |
623 |
623 |
624 fun mk_Prec (RCInfo {llRI, RIvs, CCas, rcarg, ...}) = sih |
624 fun mk_Prec (RCInfo {llRI, RIvs, CCas, rcarg, ...}) = sih |
625 |> forall_elim (cterm_of thy rcarg) |
625 |> Thm.forall_elim (cterm_of thy rcarg) |
626 |> Thm.elim_implies llRI |
626 |> Thm.elim_implies llRI |
627 |> fold_rev (implies_intr o cprop_of) CCas |
627 |> fold_rev (Thm.implies_intr o cprop_of) CCas |
628 |> fold_rev (forall_intr o cterm_of thy o Free) RIvs |
628 |> fold_rev (Thm.forall_intr o cterm_of thy o Free) RIvs |
629 |
629 |
630 val P_recs = map mk_Prec RCs (* [P rec1, P rec2, ... ] *) |
630 val P_recs = map mk_Prec RCs (* [P rec1, P rec2, ... ] *) |
631 |
631 |
632 val step = HOLogic.mk_Trueprop (P $ lhs) |
632 val step = HOLogic.mk_Trueprop (P $ lhs) |
633 |> fold_rev (curry Logic.mk_implies o prop_of) P_recs |
633 |> fold_rev (curry Logic.mk_implies o prop_of) P_recs |
634 |> fold_rev (curry Logic.mk_implies) gs |
634 |> fold_rev (curry Logic.mk_implies) gs |
635 |> curry Logic.mk_implies (HOLogic.mk_Trueprop (D $ lhs)) |
635 |> curry Logic.mk_implies (HOLogic.mk_Trueprop (D $ lhs)) |
636 |> fold_rev mk_forall_rename (map fst oqs ~~ qs) |
636 |> fold_rev mk_forall_rename (map fst oqs ~~ qs) |
637 |> cterm_of thy |
637 |> cterm_of thy |
638 |
638 |
639 val P_lhs = assume step |
639 val P_lhs = Thm.assume step |
640 |> fold forall_elim cqs |
640 |> fold Thm.forall_elim cqs |
641 |> Thm.elim_implies lhs_D |
641 |> Thm.elim_implies lhs_D |
642 |> fold Thm.elim_implies ags |
642 |> fold Thm.elim_implies ags |
643 |> fold Thm.elim_implies P_recs |
643 |> fold Thm.elim_implies P_recs |
644 |
644 |
645 val res = cterm_of thy (HOLogic.mk_Trueprop (P $ x)) |
645 val res = cterm_of thy (HOLogic.mk_Trueprop (P $ x)) |
646 |> Conv.arg_conv (Conv.arg_conv case_hyp_conv) |
646 |> Conv.arg_conv (Conv.arg_conv case_hyp_conv) |
647 |> symmetric (* P lhs == P x *) |
647 |> Thm.symmetric (* P lhs == P x *) |
648 |> (fn eql => equal_elim eql P_lhs) (* "P x" *) |
648 |> (fn eql => Thm.equal_elim eql P_lhs) (* "P x" *) |
649 |> implies_intr (cprop_of case_hyp) |
649 |> Thm.implies_intr (cprop_of case_hyp) |
650 |> fold_rev (implies_intr o cprop_of) ags |
650 |> fold_rev (Thm.implies_intr o cprop_of) ags |
651 |> fold_rev forall_intr cqs |
651 |> fold_rev Thm.forall_intr cqs |
652 in |
652 in |
653 (res, step) |
653 (res, step) |
654 end |
654 end |
655 |
655 |
656 val (cases, steps) = split_list (map prove_case clauses) |
656 val (cases, steps) = split_list (map prove_case clauses) |
657 |
657 |
658 val istep = complete_thm |
658 val istep = complete_thm |
659 |> Thm.forall_elim_vars 0 |
659 |> Thm.forall_elim_vars 0 |
660 |> fold (curry op COMP) cases (* P x *) |
660 |> fold (curry op COMP) cases (* P x *) |
661 |> implies_intr ihyp |
661 |> Thm.implies_intr ihyp |
662 |> implies_intr (cprop_of x_D) |
662 |> Thm.implies_intr (cprop_of x_D) |
663 |> forall_intr (cterm_of thy x) |
663 |> Thm.forall_intr (cterm_of thy x) |
664 |
664 |
665 val subset_induct_rule = |
665 val subset_induct_rule = |
666 acc_subset_induct |
666 acc_subset_induct |
667 |> (curry op COMP) (assume D_subset) |
667 |> (curry op COMP) (Thm.assume D_subset) |
668 |> (curry op COMP) (assume D_dcl) |
668 |> (curry op COMP) (Thm.assume D_dcl) |
669 |> (curry op COMP) (assume a_D) |
669 |> (curry op COMP) (Thm.assume a_D) |
670 |> (curry op COMP) istep |
670 |> (curry op COMP) istep |
671 |> fold_rev implies_intr steps |
671 |> fold_rev Thm.implies_intr steps |
672 |> implies_intr a_D |
672 |> Thm.implies_intr a_D |
673 |> implies_intr D_dcl |
673 |> Thm.implies_intr D_dcl |
674 |> implies_intr D_subset |
674 |> Thm.implies_intr D_subset |
675 |
675 |
676 val simple_induct_rule = |
676 val simple_induct_rule = |
677 subset_induct_rule |
677 subset_induct_rule |
678 |> forall_intr (cterm_of thy D) |
678 |> Thm.forall_intr (cterm_of thy D) |
679 |> forall_elim (cterm_of thy acc_R) |
679 |> Thm.forall_elim (cterm_of thy acc_R) |
680 |> assume_tac 1 |> Seq.hd |
680 |> assume_tac 1 |> Seq.hd |
681 |> (curry op COMP) (acc_downward |
681 |> (curry op COMP) (acc_downward |
682 |> (instantiate' [SOME (ctyp_of thy domT)] |
682 |> (instantiate' [SOME (ctyp_of thy domT)] |
683 (map (SOME o cterm_of thy) [R, x, z])) |
683 (map (SOME o cterm_of thy) [R, x, z])) |
684 |> forall_intr (cterm_of thy z) |
684 |> Thm.forall_intr (cterm_of thy z) |
685 |> forall_intr (cterm_of thy x)) |
685 |> Thm.forall_intr (cterm_of thy x)) |
686 |> forall_intr (cterm_of thy a) |
686 |> Thm.forall_intr (cterm_of thy a) |
687 |> forall_intr (cterm_of thy P) |
687 |> Thm.forall_intr (cterm_of thy P) |
688 in |
688 in |
689 simple_induct_rule |
689 simple_induct_rule |
690 end |
690 end |
691 |
691 |
692 |
692 |
734 |> Function_Ctx_Tree.export_term (fixes, assumes) |
734 |> Function_Ctx_Tree.export_term (fixes, assumes) |
735 |> fold_rev (curry Logic.mk_implies o prop_of) ags |
735 |> fold_rev (curry Logic.mk_implies o prop_of) ags |
736 |> fold_rev mk_forall_rename (map fst oqs ~~ qs) |
736 |> fold_rev mk_forall_rename (map fst oqs ~~ qs) |
737 |> cterm_of thy |
737 |> cterm_of thy |
738 |
738 |
739 val thm = assume hyp |
739 val thm = Thm.assume hyp |
740 |> fold forall_elim cqs |
740 |> fold Thm.forall_elim cqs |
741 |> fold Thm.elim_implies ags |
741 |> fold Thm.elim_implies ags |
742 |> Function_Ctx_Tree.import_thm thy (fixes, assumes) |
742 |> Function_Ctx_Tree.import_thm thy (fixes, assumes) |
743 |> fold Thm.elim_implies used (* "(arg, lhs) : R'" *) |
743 |> fold Thm.elim_implies used (* "(arg, lhs) : R'" *) |
744 |
744 |
745 val z_eq_arg = HOLogic.mk_Trueprop (mk_eq (z, arg)) |
745 val z_eq_arg = HOLogic.mk_Trueprop (mk_eq (z, arg)) |
746 |> cterm_of thy |> assume |
746 |> cterm_of thy |> Thm.assume |
747 |
747 |
748 val acc = thm COMP ih_case |
748 val acc = thm COMP ih_case |
749 val z_acc_local = acc |
749 val z_acc_local = acc |
750 |> Conv.fconv_rule (Conv.arg_conv (Conv.arg_conv (K (symmetric (z_eq_arg RS eq_reflection))))) |
750 |> Conv.fconv_rule |
|
751 (Conv.arg_conv (Conv.arg_conv (K (Thm.symmetric (z_eq_arg RS eq_reflection))))) |
751 |
752 |
752 val ethm = z_acc_local |
753 val ethm = z_acc_local |
753 |> Function_Ctx_Tree.export_thm thy (fixes, |
754 |> Function_Ctx_Tree.export_thm thy (fixes, |
754 z_eq_arg :: case_hyp :: ags @ assumes) |
755 z_eq_arg :: case_hyp :: ags @ assumes) |
755 |> fold_rev forall_intr_rename (map fst oqs ~~ cqs) |
756 |> fold_rev forall_intr_rename (map fst oqs ~~ cqs) |
783 val ihyp = Term.all domT $ Abs ("z", domT, |
784 val ihyp = Term.all domT $ Abs ("z", domT, |
784 Logic.mk_implies (HOLogic.mk_Trueprop (R' $ Bound 0 $ x), |
785 Logic.mk_implies (HOLogic.mk_Trueprop (R' $ Bound 0 $ x), |
785 HOLogic.mk_Trueprop (acc_R $ Bound 0))) |
786 HOLogic.mk_Trueprop (acc_R $ Bound 0))) |
786 |> cterm_of thy |
787 |> cterm_of thy |
787 |
788 |
788 val ihyp_a = assume ihyp |> Thm.forall_elim_vars 0 |
789 val ihyp_a = Thm.assume ihyp |> Thm.forall_elim_vars 0 |
789 |
790 |
790 val R_z_x = cterm_of thy (HOLogic.mk_Trueprop (R $ z $ x)) |
791 val R_z_x = cterm_of thy (HOLogic.mk_Trueprop (R $ z $ x)) |
791 |
792 |
792 val (hyps, cases) = fold (mk_nest_term_case thy globals R' ihyp_a) clauses ([], []) |
793 val (hyps, cases) = fold (mk_nest_term_case thy globals R' ihyp_a) clauses ([], []) |
793 in |
794 in |
794 R_cases |
795 R_cases |
795 |> forall_elim (cterm_of thy z) |
796 |> Thm.forall_elim (cterm_of thy z) |
796 |> forall_elim (cterm_of thy x) |
797 |> Thm.forall_elim (cterm_of thy x) |
797 |> forall_elim (cterm_of thy (acc_R $ z)) |
798 |> Thm.forall_elim (cterm_of thy (acc_R $ z)) |
798 |> curry op COMP (assume R_z_x) |
799 |> curry op COMP (Thm.assume R_z_x) |
799 |> fold_rev (curry op COMP) cases |
800 |> fold_rev (curry op COMP) cases |
800 |> implies_intr R_z_x |
801 |> Thm.implies_intr R_z_x |
801 |> forall_intr (cterm_of thy z) |
802 |> Thm.forall_intr (cterm_of thy z) |
802 |> (fn it => it COMP accI) |
803 |> (fn it => it COMP accI) |
803 |> implies_intr ihyp |
804 |> Thm.implies_intr ihyp |
804 |> forall_intr (cterm_of thy x) |
805 |> Thm.forall_intr (cterm_of thy x) |
805 |> (fn it => Drule.compose_single(it,2,wf_induct_rule)) |
806 |> (fn it => Drule.compose_single(it,2,wf_induct_rule)) |
806 |> curry op RS (assume wfR') |
807 |> curry op RS (Thm.assume wfR') |
807 |> forall_intr_vars |
808 |> forall_intr_vars |
808 |> (fn it => it COMP allI) |
809 |> (fn it => it COMP allI) |
809 |> fold implies_intr hyps |
810 |> fold Thm.implies_intr hyps |
810 |> implies_intr wfR' |
811 |> Thm.implies_intr wfR' |
811 |> forall_intr (cterm_of thy R') |
812 |> Thm.forall_intr (cterm_of thy R') |
812 |> forall_elim (cterm_of thy (inrel_R)) |
813 |> Thm.forall_elim (cterm_of thy (inrel_R)) |
813 |> curry op RS wf_in_rel |
814 |> curry op RS wf_in_rel |
814 |> full_simplify (HOL_basic_ss addsimps [in_rel_def]) |
815 |> full_simplify (HOL_basic_ss addsimps [in_rel_def]) |
815 |> forall_intr (cterm_of thy Rrel) |
816 |> Thm.forall_intr (cterm_of thy Rrel) |
816 end |
817 end |
817 |
818 |
818 |
819 |
819 |
820 |
820 (* Tail recursion (probably very fragile) |
821 (* Tail recursion (probably very fragile) |