src/ZF/Tools/inductive_package.ML
changeset 17985 d5d576b72371
parent 17959 8db36a108213
child 18358 0a733e11021a
equal deleted inserted replaced
17984:bdac047db2a5 17985:d5d576b72371
   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