219 (HOLogic.mk_Trueprop ( |
219 (HOLogic.mk_Trueprop ( |
220 Const (@{const_name Set.member}, HOLogic.mk_prodT (T, T) --> mk_relT T --> HOLogic.boolT) |
220 Const (@{const_name Set.member}, HOLogic.mk_prodT (T, T) --> mk_relT T --> HOLogic.boolT) |
221 $ (HOLogic.pair_const T T $ Bound 0 $ x) |
221 $ (HOLogic.pair_const T T $ Bound 0 $ x) |
222 $ R), |
222 $ R), |
223 HOLogic.mk_Trueprop (P_comp $ Bound 0))) |
223 HOLogic.mk_Trueprop (P_comp $ Bound 0))) |
224 |> Proof_Context.cterm_of ctxt |
224 |> Thm.cterm_of ctxt |
225 |
225 |
226 val aihyp = Thm.assume ihyp |
226 val aihyp = Thm.assume ihyp |
227 |
227 |
228 (* Rule for case splitting along the sum types *) |
228 (* Rule for case splitting along the sum types *) |
229 val xss = map (fn (SchemeBranch { xs, ... }) => map Free xs) branches |
229 val xss = map (fn (SchemeBranch { xs, ... }) => map Free xs) branches |
233 |
233 |
234 fun prove_branch (bidx, (SchemeBranch { P, xs, ws, Cs, ... }, (complete_thm, pat))) = |
234 fun prove_branch (bidx, (SchemeBranch { P, xs, ws, Cs, ... }, (complete_thm, pat))) = |
235 let |
235 let |
236 val fxs = map Free xs |
236 val fxs = map Free xs |
237 val branch_hyp = |
237 val branch_hyp = |
238 Thm.assume (Proof_Context.cterm_of ctxt (HOLogic.mk_Trueprop (HOLogic.mk_eq (x, pat)))) |
238 Thm.assume (Thm.cterm_of ctxt (HOLogic.mk_Trueprop (HOLogic.mk_eq (x, pat)))) |
239 |
239 |
240 val C_hyps = map (Proof_Context.cterm_of ctxt #> Thm.assume) Cs |
240 val C_hyps = map (Thm.cterm_of ctxt #> Thm.assume) Cs |
241 |
241 |
242 val (relevant_cases, ineqss') = |
242 val (relevant_cases, ineqss') = |
243 (scases_idx ~~ ineqss) |
243 (scases_idx ~~ ineqss) |
244 |> filter (fn ((_, SchemeCase {bidx=bidx', ...}), _) => bidx' = bidx) |
244 |> filter (fn ((_, SchemeCase {bidx=bidx', ...}), _) => bidx' = bidx) |
245 |> split_list |
245 |> split_list |
246 |
246 |
247 fun prove_case (cidx, SchemeCase {qs, gs, lhs, rs, ...}) ineq_press = |
247 fun prove_case (cidx, SchemeCase {qs, gs, lhs, rs, ...}) ineq_press = |
248 let |
248 let |
249 val case_hyps = |
249 val case_hyps = |
250 map (Thm.assume o Proof_Context.cterm_of ctxt o HOLogic.mk_Trueprop o HOLogic.mk_eq) |
250 map (Thm.assume o Thm.cterm_of ctxt o HOLogic.mk_Trueprop o HOLogic.mk_eq) |
251 (fxs ~~ lhs) |
251 (fxs ~~ lhs) |
252 |
252 |
253 val cqs = map (Proof_Context.cterm_of ctxt o Free) qs |
253 val cqs = map (Thm.cterm_of ctxt o Free) qs |
254 val ags = map (Thm.assume o Proof_Context.cterm_of ctxt) gs |
254 val ags = map (Thm.assume o Thm.cterm_of ctxt) gs |
255 |
255 |
256 val replace_x_simpset = |
256 val replace_x_simpset = |
257 put_simpset HOL_basic_ss ctxt addsimps (branch_hyp :: case_hyps) |
257 put_simpset HOL_basic_ss ctxt addsimps (branch_hyp :: case_hyps) |
258 val sih = full_simplify replace_x_simpset aihyp |
258 val sih = full_simplify replace_x_simpset aihyp |
259 |
259 |
260 fun mk_Prec (idx, Gvs, Gas, rcargs) (ineq, pres) = |
260 fun mk_Prec (idx, Gvs, Gas, rcargs) (ineq, pres) = |
261 let |
261 let |
262 val cGas = map (Thm.assume o Proof_Context.cterm_of ctxt) Gas |
262 val cGas = map (Thm.assume o Thm.cterm_of ctxt) Gas |
263 val cGvs = map (Proof_Context.cterm_of ctxt o Free) Gvs |
263 val cGvs = map (Thm.cterm_of ctxt o Free) Gvs |
264 val import = fold Thm.forall_elim (cqs @ cGvs) |
264 val import = fold Thm.forall_elim (cqs @ cGvs) |
265 #> fold Thm.elim_implies (ags @ cGas) |
265 #> fold Thm.elim_implies (ags @ cGas) |
266 val ipres = pres |
266 val ipres = pres |
267 |> Thm.forall_elim (Proof_Context.cterm_of ctxt (list_comb (P_of idx, rcargs))) |
267 |> Thm.forall_elim (Thm.cterm_of ctxt (list_comb (P_of idx, rcargs))) |
268 |> import |
268 |> import |
269 in |
269 in |
270 sih |
270 sih |
271 |> Thm.forall_elim (Proof_Context.cterm_of ctxt (inject idx rcargs)) |
271 |> Thm.forall_elim (Thm.cterm_of ctxt (inject idx rcargs)) |
272 |> Thm.elim_implies (import ineq) (* Psum rcargs *) |
272 |> Thm.elim_implies (import ineq) (* Psum rcargs *) |
273 |> Conv.fconv_rule (sum_prod_conv ctxt) |
273 |> Conv.fconv_rule (sum_prod_conv ctxt) |
274 |> Conv.fconv_rule (ind_rulify ctxt) |
274 |> Conv.fconv_rule (ind_rulify ctxt) |
275 |> (fn th => th COMP ipres) (* P rs *) |
275 |> (fn th => th COMP ipres) (* P rs *) |
276 |> fold_rev (Thm.implies_intr o Thm.cprop_of) cGas |
276 |> fold_rev (Thm.implies_intr o Thm.cprop_of) cGas |
281 |
281 |
282 val step = HOLogic.mk_Trueprop (list_comb (P, lhs)) |
282 val step = HOLogic.mk_Trueprop (list_comb (P, lhs)) |
283 |> fold_rev (curry Logic.mk_implies o Thm.prop_of) P_recs |
283 |> fold_rev (curry Logic.mk_implies o Thm.prop_of) P_recs |
284 |> fold_rev (curry Logic.mk_implies) gs |
284 |> fold_rev (curry Logic.mk_implies) gs |
285 |> fold_rev (Logic.all o Free) qs |
285 |> fold_rev (Logic.all o Free) qs |
286 |> Proof_Context.cterm_of ctxt |
286 |> Thm.cterm_of ctxt |
287 |
287 |
288 val Plhs_to_Pxs_conv = |
288 val Plhs_to_Pxs_conv = |
289 foldl1 (uncurry Conv.combination_conv) |
289 foldl1 (uncurry Conv.combination_conv) |
290 (Conv.all_conv :: map (fn ch => K (Thm.symmetric (ch RS eq_reflection))) case_hyps) |
290 (Conv.all_conv :: map (fn ch => K (Thm.symmetric (ch RS eq_reflection))) case_hyps) |
291 |
291 |
301 end |
301 end |
302 |
302 |
303 val (cases, steps) = split_list (map2 prove_case relevant_cases ineqss') |
303 val (cases, steps) = split_list (map2 prove_case relevant_cases ineqss') |
304 |
304 |
305 val bstep = complete_thm |
305 val bstep = complete_thm |
306 |> Thm.forall_elim (Proof_Context.cterm_of ctxt (list_comb (P, fxs))) |
306 |> Thm.forall_elim (Thm.cterm_of ctxt (list_comb (P, fxs))) |
307 |> fold (Thm.forall_elim o Proof_Context.cterm_of ctxt) (fxs @ map Free ws) |
307 |> fold (Thm.forall_elim o Thm.cterm_of ctxt) (fxs @ map Free ws) |
308 |> fold Thm.elim_implies C_hyps |
308 |> fold Thm.elim_implies C_hyps |
309 |> fold Thm.elim_implies cases (* P xs *) |
309 |> fold Thm.elim_implies cases (* P xs *) |
310 |> fold_rev (Thm.implies_intr o Thm.cprop_of) C_hyps |
310 |> fold_rev (Thm.implies_intr o Thm.cprop_of) C_hyps |
311 |> fold_rev (Thm.forall_intr o Proof_Context.cterm_of ctxt o Free) ws |
311 |> fold_rev (Thm.forall_intr o Thm.cterm_of ctxt o Free) ws |
312 |
312 |
313 val Pxs = |
313 val Pxs = |
314 Proof_Context.cterm_of ctxt (HOLogic.mk_Trueprop (P_comp $ x)) |
314 Thm.cterm_of ctxt (HOLogic.mk_Trueprop (P_comp $ x)) |
315 |> Goal.init |
315 |> Goal.init |
316 |> (Simplifier.rewrite_goals_tac ctxt |
316 |> (Simplifier.rewrite_goals_tac ctxt |
317 (map meta (branch_hyp :: @{thm split_conv} :: @{thms sum.case})) |
317 (map meta (branch_hyp :: @{thm split_conv} :: @{thms sum.case})) |
318 THEN CONVERSION (ind_rulify ctxt) 1) |
318 THEN CONVERSION (ind_rulify ctxt) 1) |
319 |> Seq.hd |
319 |> Seq.hd |
320 |> Thm.elim_implies (Conv.fconv_rule Drule.beta_eta_conversion bstep) |
320 |> Thm.elim_implies (Conv.fconv_rule Drule.beta_eta_conversion bstep) |
321 |> Goal.finish ctxt |
321 |> Goal.finish ctxt |
322 |> Thm.implies_intr (Thm.cprop_of branch_hyp) |
322 |> Thm.implies_intr (Thm.cprop_of branch_hyp) |
323 |> fold_rev (Thm.forall_intr o Proof_Context.cterm_of ctxt) fxs |
323 |> fold_rev (Thm.forall_intr o Thm.cterm_of ctxt) fxs |
324 in |
324 in |
325 (Pxs, steps) |
325 (Pxs, steps) |
326 end |
326 end |
327 |
327 |
328 val (branches, steps) = |
328 val (branches, steps) = |
330 |> split_list |> apsnd flat |
330 |> split_list |> apsnd flat |
331 |
331 |
332 val istep = sum_split_rule |
332 val istep = sum_split_rule |
333 |> fold (fn b => fn th => Drule.compose (b, 1, th)) branches |
333 |> fold (fn b => fn th => Drule.compose (b, 1, th)) branches |
334 |> Thm.implies_intr ihyp |
334 |> Thm.implies_intr ihyp |
335 |> Thm.forall_intr (Proof_Context.cterm_of ctxt x) (* "!!x. (!!y<x. P y) ==> P x" *) |
335 |> Thm.forall_intr (Thm.cterm_of ctxt x) (* "!!x. (!!y<x. P y) ==> P x" *) |
336 |
336 |
337 val induct_rule = |
337 val induct_rule = |
338 @{thm "wf_induct_rule"} |
338 @{thm "wf_induct_rule"} |
339 |> (curry op COMP) wf_thm |
339 |> (curry op COMP) wf_thm |
340 |> (curry op COMP) istep |
340 |> (curry op COMP) istep |
355 val R = Free (Rn, mk_relT ST) |
355 val R = Free (Rn, mk_relT ST) |
356 val x = Free (xn, ST) |
356 val x = Free (xn, ST) |
357 |
357 |
358 val ineqss = |
358 val ineqss = |
359 mk_ineqs R scheme |
359 mk_ineqs R scheme |
360 |> map (map (apply2 (Thm.assume o Proof_Context.cterm_of ctxt''))) |
360 |> map (map (apply2 (Thm.assume o Thm.cterm_of ctxt''))) |
361 val complete = |
361 val complete = |
362 map_range (mk_completeness ctxt'' scheme #> Proof_Context.cterm_of ctxt'' #> Thm.assume) |
362 map_range (mk_completeness ctxt'' scheme #> Thm.cterm_of ctxt'' #> Thm.assume) |
363 (length branches) |
363 (length branches) |
364 val wf_thm = mk_wf R scheme |> Proof_Context.cterm_of ctxt'' |> Thm.assume |
364 val wf_thm = mk_wf R scheme |> Thm.cterm_of ctxt'' |> Thm.assume |
365 |
365 |
366 val (descent, pres) = split_list (flat ineqss) |
366 val (descent, pres) = split_list (flat ineqss) |
367 val newgoals = complete @ pres @ wf_thm :: descent |
367 val newgoals = complete @ pres @ wf_thm :: descent |
368 |
368 |
369 val (steps, indthm) = |
369 val (steps, indthm) = |
371 |
371 |
372 fun project (i, SchemeBranch {xs, ...}) = |
372 fun project (i, SchemeBranch {xs, ...}) = |
373 let |
373 let |
374 val inst = (foldr1 HOLogic.mk_prod (map Free xs)) |
374 val inst = (foldr1 HOLogic.mk_prod (map Free xs)) |
375 |> Sum_Tree.mk_inj ST (length branches) (i + 1) |
375 |> Sum_Tree.mk_inj ST (length branches) (i + 1) |
376 |> Proof_Context.cterm_of ctxt'' |
376 |> Thm.cterm_of ctxt'' |
377 in |
377 in |
378 indthm |
378 indthm |
379 |> Drule.instantiate' [] [SOME inst] |
379 |> Drule.instantiate' [] [SOME inst] |
380 |> simplify (put_simpset Sum_Tree.sumcase_split_ss ctxt'') |
380 |> simplify (put_simpset Sum_Tree.sumcase_split_ss ctxt'') |
381 |> Conv.fconv_rule (ind_rulify ctxt'') |
381 |> Conv.fconv_rule (ind_rulify ctxt'') |