src/HOL/Tools/Function/induction_schema.ML
changeset 59621 291934bac95e
parent 59618 e6939796717e
child 59627 bb1e4a35d506
equal deleted inserted replaced
59620:92d7d8e4f1bf 59621:291934bac95e
    44 
    44 
    45 fun sum_prod_conv ctxt = Raw_Simplifier.rewrite ctxt true
    45 fun sum_prod_conv ctxt = Raw_Simplifier.rewrite ctxt true
    46   (map meta (@{thm split_conv} :: @{thms sum.case}))
    46   (map meta (@{thm split_conv} :: @{thms sum.case}))
    47 
    47 
    48 fun term_conv thy cv t =
    48 fun term_conv thy cv t =
    49   cv (Thm.cterm_of thy t)
    49   cv (Thm.global_cterm_of thy t)
    50   |> Thm.prop_of |> Logic.dest_equals |> snd
    50   |> Thm.prop_of |> Logic.dest_equals |> snd
    51 
    51 
    52 fun mk_relT T = HOLogic.mk_setT (HOLogic.mk_prodT (T, T))
    52 fun mk_relT T = HOLogic.mk_setT (HOLogic.mk_prodT (T, T))
    53 
    53 
    54 fun dest_hhf ctxt t =
    54 fun dest_hhf ctxt t =
   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'')