src/HOL/Nominal/nominal_package.ML
changeset 20046 9c8909fc5865
parent 19985 d39c554cf750
child 20071 8f3e1ddb50e6
equal deleted inserted replaced
20045:e66efbafbf1f 20046:9c8909fc5865
   253     val perm_fun_def = PureThy.get_thm thy2 (Name "perm_fun_def");
   253     val perm_fun_def = PureThy.get_thm thy2 (Name "perm_fun_def");
   254 
   254 
   255     val unfolded_perm_eq_thms =
   255     val unfolded_perm_eq_thms =
   256       if length descr = length new_type_names then []
   256       if length descr = length new_type_names then []
   257       else map standard (List.drop (split_conj_thm
   257       else map standard (List.drop (split_conj_thm
   258         (Goal.prove thy2 [] []
   258         (Goal.prove_global thy2 [] []
   259           (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   259           (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   260             (map (fn (c as (s, T), x) =>
   260             (map (fn (c as (s, T), x) =>
   261                let val [T1, T2] = binder_types T
   261                let val [T1, T2] = binder_types T
   262                in HOLogic.mk_eq (Const c $ pi $ Free (x, T2),
   262                in HOLogic.mk_eq (Const c $ pi $ Free (x, T2),
   263                  Const ("Nominal.perm", T) $ pi $ Free (x, T2))
   263                  Const ("Nominal.perm", T) $ pi $ Free (x, T2))
   273     val _ = warning "perm_empty_thms";
   273     val _ = warning "perm_empty_thms";
   274 
   274 
   275     val perm_empty_thms = List.concat (map (fn a =>
   275     val perm_empty_thms = List.concat (map (fn a =>
   276       let val permT = mk_permT (Type (a, []))
   276       let val permT = mk_permT (Type (a, []))
   277       in map standard (List.take (split_conj_thm
   277       in map standard (List.take (split_conj_thm
   278         (Goal.prove thy2 [] []
   278         (Goal.prove_global thy2 [] []
   279           (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   279           (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   280             (map (fn ((s, T), x) => HOLogic.mk_eq
   280             (map (fn ((s, T), x) => HOLogic.mk_eq
   281                 (Const (s, permT --> T --> T) $
   281                 (Const (s, permT --> T --> T) $
   282                    Const ("List.list.Nil", permT) $ Free (x, T),
   282                    Const ("List.list.Nil", permT) $ Free (x, T),
   283                  Free (x, T)))
   283                  Free (x, T)))
   305         val pt_inst = PureThy.get_thm thy2 (Name ("pt_" ^ Sign.base_name a ^ "_inst"));
   305         val pt_inst = PureThy.get_thm thy2 (Name ("pt_" ^ Sign.base_name a ^ "_inst"));
   306         val pt2' = pt_inst RS pt2;
   306         val pt2' = pt_inst RS pt2;
   307         val pt2_ax = PureThy.get_thm thy2
   307         val pt2_ax = PureThy.get_thm thy2
   308           (Name (NameSpace.map_base (fn s => "pt_" ^ s ^ "2") a));
   308           (Name (NameSpace.map_base (fn s => "pt_" ^ s ^ "2") a));
   309       in List.take (map standard (split_conj_thm
   309       in List.take (map standard (split_conj_thm
   310         (Goal.prove thy2 [] []
   310         (Goal.prove_global thy2 [] []
   311              (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   311              (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   312                 (map (fn ((s, T), x) =>
   312                 (map (fn ((s, T), x) =>
   313                     let val perm = Const (s, permT --> T --> T)
   313                     let val perm = Const (s, permT --> T --> T)
   314                     in HOLogic.mk_eq
   314                     in HOLogic.mk_eq
   315                       (perm $ (Const ("List.op @", permT --> permT --> permT) $
   315                       (perm $ (Const ("List.op @", permT --> permT --> permT) $
   341         val pt3' = pt_inst RS pt3;
   341         val pt3' = pt_inst RS pt3;
   342         val pt3_rev' = at_inst RS (pt_inst RS pt3_rev);
   342         val pt3_rev' = at_inst RS (pt_inst RS pt3_rev);
   343         val pt3_ax = PureThy.get_thm thy2
   343         val pt3_ax = PureThy.get_thm thy2
   344           (Name (NameSpace.map_base (fn s => "pt_" ^ s ^ "3") a));
   344           (Name (NameSpace.map_base (fn s => "pt_" ^ s ^ "3") a));
   345       in List.take (map standard (split_conj_thm
   345       in List.take (map standard (split_conj_thm
   346         (Goal.prove thy2 [] [] (Logic.mk_implies
   346         (Goal.prove_global thy2 [] [] (Logic.mk_implies
   347              (HOLogic.mk_Trueprop (Const ("Nominal.prm_eq",
   347              (HOLogic.mk_Trueprop (Const ("Nominal.prm_eq",
   348                 permT --> permT --> HOLogic.boolT) $ pi1 $ pi2),
   348                 permT --> permT --> HOLogic.boolT) $ pi1 $ pi2),
   349               HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   349               HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   350                 (map (fn ((s, T), x) =>
   350                 (map (fn ((s, T), x) =>
   351                     let val perm = Const (s, permT --> T --> T)
   351                     let val perm = Const (s, permT --> T --> T)
   391              in
   391              in
   392                [cp_inst RS cp1 RS sym,
   392                [cp_inst RS cp1 RS sym,
   393                 at_inst RS (pt_inst RS pt_perm_compose) RS sym,
   393                 at_inst RS (pt_inst RS pt_perm_compose) RS sym,
   394                 at_inst RS (pt_inst RS pt_perm_compose_rev) RS sym]
   394                 at_inst RS (pt_inst RS pt_perm_compose_rev) RS sym]
   395             end))
   395             end))
   396         val thms = split_conj_thm (standard (Goal.prove thy [] []
   396         val thms = split_conj_thm (Goal.prove_global thy [] []
   397             (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   397             (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   398               (map (fn ((s, T), x) =>
   398               (map (fn ((s, T), x) =>
   399                   let
   399                   let
   400                     val pi1 = Free ("pi1", permT1);
   400                     val pi1 = Free ("pi1", permT1);
   401                     val pi2 = Free ("pi2", permT2);
   401                     val pi2 = Free ("pi2", permT2);
   406                     (perm1 $ pi1 $ (perm2 $ pi2 $ Free (x, T)),
   406                     (perm1 $ pi1 $ (perm2 $ pi2 $ Free (x, T)),
   407                      perm2 $ (perm3 $ pi1 $ pi2) $ (perm1 $ pi1 $ Free (x, T)))
   407                      perm2 $ (perm3 $ pi1 $ pi2) $ (perm1 $ pi1 $ Free (x, T)))
   408                   end)
   408                   end)
   409                 (perm_names ~~ Ts ~~ perm_indnames))))
   409                 (perm_names ~~ Ts ~~ perm_indnames))))
   410           (fn _ => EVERY [indtac induction perm_indnames 1,
   410           (fn _ => EVERY [indtac induction perm_indnames 1,
   411              ALLGOALS (asm_full_simp_tac simps)])))
   411              ALLGOALS (asm_full_simp_tac simps)]))
   412       in
   412       in
   413         foldl (fn ((s, tvs), thy) => AxClass.prove_arity
   413         foldl (fn ((s, tvs), thy) => AxClass.prove_arity
   414             (s, replicate (length tvs) (cp_class :: classes), [cp_class])
   414             (s, replicate (length tvs) (cp_class :: classes), [cp_class])
   415             (ClassPackage.intro_classes_tac [] THEN ALLGOALS (resolve_tac thms)) thy)
   415             (ClassPackage.intro_classes_tac [] THEN ALLGOALS (resolve_tac thms)) thy)
   416           thy (full_new_type_names' ~~ tyvars)
   416           thy (full_new_type_names' ~~ tyvars)
   515     val perm_indnames' = List.mapPartial
   515     val perm_indnames' = List.mapPartial
   516       (fn (x, (_, ("Nominal.noption", _, _))) => NONE | (x, _) => SOME x)
   516       (fn (x, (_, ("Nominal.noption", _, _))) => NONE | (x, _) => SOME x)
   517       (perm_indnames ~~ descr);
   517       (perm_indnames ~~ descr);
   518 
   518 
   519     fun mk_perm_closed name = map (fn th => standard (th RS mp))
   519     fun mk_perm_closed name = map (fn th => standard (th RS mp))
   520       (List.take (split_conj_thm (Goal.prove thy4 [] []
   520       (List.take (split_conj_thm (Goal.prove_global thy4 [] []
   521         (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj (map
   521         (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj (map
   522            (fn (S, x) =>
   522            (fn (S, x) =>
   523               let
   523               let
   524                 val S = map_term_types (map_type_tfree
   524                 val S = map_term_types (map_type_tfree
   525                   (fn (s, cs) => TFree (s, cs union cp_classes))) S;
   525                   (fn (s, cs) => TFree (s, cs union cp_classes))) S;
   764     
   764     
   765     fun prove_constr_rep_thm eqn =
   765     fun prove_constr_rep_thm eqn =
   766       let
   766       let
   767         val inj_thms = map (fn r => r RS iffD1) abs_inject_thms;
   767         val inj_thms = map (fn r => r RS iffD1) abs_inject_thms;
   768         val rewrites = constr_defs @ map mk_meta_eq rep_inverse_thms
   768         val rewrites = constr_defs @ map mk_meta_eq rep_inverse_thms
   769       in standard (Goal.prove thy8 [] [] eqn (fn _ => EVERY
   769       in Goal.prove_global thy8 [] [] eqn (fn _ => EVERY
   770         [resolve_tac inj_thms 1,
   770         [resolve_tac inj_thms 1,
   771          rewrite_goals_tac rewrites,
   771          rewrite_goals_tac rewrites,
   772          rtac refl 3,
   772          rtac refl 3,
   773          resolve_tac rep_intrs 2,
   773          resolve_tac rep_intrs 2,
   774          REPEAT (resolve_tac rep_thms 1)]))
   774          REPEAT (resolve_tac rep_thms 1)])
   775       end;
   775       end;
   776 
   776 
   777     val constr_rep_thmss = map (map prove_constr_rep_thm) constr_rep_eqns;
   777     val constr_rep_thmss = map (map prove_constr_rep_thm) constr_rep_eqns;
   778 
   778 
   779     (* prove theorem  pi \<bullet> Rep_i x = Rep_i (pi \<bullet> x) *)
   779     (* prove theorem  pi \<bullet> Rep_i x = Rep_i (pi \<bullet> x) *)
   783         val _ $ (_ $ (Rep $ x) $ _) = Logic.unvarify (prop_of th);
   783         val _ $ (_ $ (Rep $ x) $ _) = Logic.unvarify (prop_of th);
   784         val Type ("fun", [T, U]) = fastype_of Rep;
   784         val Type ("fun", [T, U]) = fastype_of Rep;
   785         val permT = mk_permT (Type (atom, []));
   785         val permT = mk_permT (Type (atom, []));
   786         val pi = Free ("pi", permT);
   786         val pi = Free ("pi", permT);
   787       in
   787       in
   788         standard (Goal.prove thy8 [] [] (HOLogic.mk_Trueprop (HOLogic.mk_eq
   788         Goal.prove_global thy8 [] [] (HOLogic.mk_Trueprop (HOLogic.mk_eq
   789             (Const ("Nominal.perm", permT --> U --> U) $ pi $ (Rep $ x),
   789             (Const ("Nominal.perm", permT --> U --> U) $ pi $ (Rep $ x),
   790              Rep $ (Const ("Nominal.perm", permT --> T --> T) $ pi $ x))))
   790              Rep $ (Const ("Nominal.perm", permT --> T --> T) $ pi $ x))))
   791           (fn _ => simp_tac (HOL_basic_ss addsimps (perm_defs @ Abs_inverse_thms @
   791           (fn _ => simp_tac (HOL_basic_ss addsimps (perm_defs @ Abs_inverse_thms @
   792             perm_closed_thms @ Rep_thms)) 1))
   792             perm_closed_thms @ Rep_thms)) 1)
   793       end) Rep_thms;
   793       end) Rep_thms;
   794 
   794 
   795     val perm_rep_perm_thms = List.concat (map prove_perm_rep_perm
   795     val perm_rep_perm_thms = List.concat (map prove_perm_rep_perm
   796       (atoms ~~ perm_closed_thmss));
   796       (atoms ~~ perm_closed_thmss));
   797 
   797 
   805         (constr_rep_thmss ~~ dist_lemmas);
   805         (constr_rep_thmss ~~ dist_lemmas);
   806 
   806 
   807     fun prove_distinct_thms (_, []) = []
   807     fun prove_distinct_thms (_, []) = []
   808       | prove_distinct_thms (p as (rep_thms, dist_lemma), t::ts) =
   808       | prove_distinct_thms (p as (rep_thms, dist_lemma), t::ts) =
   809           let
   809           let
   810             val dist_thm = standard (Goal.prove thy8 [] [] t (fn _ =>
   810             val dist_thm = Goal.prove_global thy8 [] [] t (fn _ =>
   811               simp_tac (simpset_of thy8 addsimps (dist_lemma :: rep_thms)) 1))
   811               simp_tac (simpset_of thy8 addsimps (dist_lemma :: rep_thms)) 1)
   812           in dist_thm::(standard (dist_thm RS not_sym))::
   812           in dist_thm::(standard (dist_thm RS not_sym))::
   813             (prove_distinct_thms (p, ts))
   813             (prove_distinct_thms (p, ts))
   814           end;
   814           end;
   815 
   815 
   816     val distinct_thms = map prove_distinct_thms
   816     val distinct_thms = map prove_distinct_thms
   847             end
   847             end
   848 
   848 
   849           val (_, l_args, r_args) = foldr constr_arg (1, [], []) dts;
   849           val (_, l_args, r_args) = foldr constr_arg (1, [], []) dts;
   850           val c = Const (cname, map fastype_of l_args ---> T)
   850           val c = Const (cname, map fastype_of l_args ---> T)
   851         in
   851         in
   852           standard (Goal.prove thy8 [] []
   852           Goal.prove_global thy8 [] []
   853             (HOLogic.mk_Trueprop (HOLogic.mk_eq
   853             (HOLogic.mk_Trueprop (HOLogic.mk_eq
   854               (perm (list_comb (c, l_args)), list_comb (c, r_args))))
   854               (perm (list_comb (c, l_args)), list_comb (c, r_args))))
   855             (fn _ => EVERY
   855             (fn _ => EVERY
   856               [simp_tac (simpset_of thy8 addsimps (constr_rep_thm :: perm_defs)) 1,
   856               [simp_tac (simpset_of thy8 addsimps (constr_rep_thm :: perm_defs)) 1,
   857                simp_tac (HOL_basic_ss addsimps (Rep_thms @ Abs_inverse_thms @
   857                simp_tac (HOL_basic_ss addsimps (Rep_thms @ Abs_inverse_thms @
   858                  constr_defs @ perm_closed_thms)) 1,
   858                  constr_defs @ perm_closed_thms)) 1,
   859                TRY (simp_tac (HOL_basic_ss addsimps
   859                TRY (simp_tac (HOL_basic_ss addsimps
   860                  (symmetric perm_fun_def :: abs_perm)) 1),
   860                  (symmetric perm_fun_def :: abs_perm)) 1),
   861                TRY (simp_tac (HOL_basic_ss addsimps
   861                TRY (simp_tac (HOL_basic_ss addsimps
   862                  (perm_fun_def :: perm_defs @ Rep_thms @ Abs_inverse_thms @
   862                  (perm_fun_def :: perm_defs @ Rep_thms @ Abs_inverse_thms @
   863                     perm_closed_thms)) 1)]))
   863                     perm_closed_thms)) 1)])
   864         end) (constrs ~~ constr_rep_thms)) (atoms ~~ perm_closed_thmss))
   864         end) (constrs ~~ constr_rep_thms)) (atoms ~~ perm_closed_thmss))
   865       end) (List.take (pdescr, length new_type_names) ~~ new_type_names ~~ constr_rep_thmss);
   865       end) (List.take (pdescr, length new_type_names) ~~ new_type_names ~~ constr_rep_thmss);
   866 
   866 
   867     (** prove injectivity of constructors **)
   867     (** prove injectivity of constructors **)
   868 
   868 
   896 
   896 
   897           val (_, args1, args2, eqs) = foldr make_inj (1, [], [], []) dts;
   897           val (_, args1, args2, eqs) = foldr make_inj (1, [], [], []) dts;
   898           val Ts = map fastype_of args1;
   898           val Ts = map fastype_of args1;
   899           val c = Const (cname, Ts ---> T)
   899           val c = Const (cname, Ts ---> T)
   900         in
   900         in
   901           standard (Goal.prove thy8 [] [] (HOLogic.mk_Trueprop (HOLogic.mk_eq
   901           Goal.prove_global thy8 [] [] (HOLogic.mk_Trueprop (HOLogic.mk_eq
   902               (HOLogic.mk_eq (list_comb (c, args1), list_comb (c, args2)),
   902               (HOLogic.mk_eq (list_comb (c, args1), list_comb (c, args2)),
   903                foldr1 HOLogic.mk_conj eqs)))
   903                foldr1 HOLogic.mk_conj eqs)))
   904             (fn _ => EVERY
   904             (fn _ => EVERY
   905                [asm_full_simp_tac (simpset_of thy8 addsimps (constr_rep_thm ::
   905                [asm_full_simp_tac (simpset_of thy8 addsimps (constr_rep_thm ::
   906                   rep_inject_thms')) 1,
   906                   rep_inject_thms')) 1,
   907                 TRY (asm_full_simp_tac (HOL_basic_ss addsimps (fresh_def :: supp_def ::
   907                 TRY (asm_full_simp_tac (HOL_basic_ss addsimps (fresh_def :: supp_def ::
   908                   alpha @ abs_perm @ abs_fresh @ rep_inject_thms @
   908                   alpha @ abs_perm @ abs_fresh @ rep_inject_thms @
   909                   perm_rep_perm_thms)) 1),
   909                   perm_rep_perm_thms)) 1),
   910                 TRY (asm_full_simp_tac (HOL_basic_ss addsimps (perm_fun_def ::
   910                 TRY (asm_full_simp_tac (HOL_basic_ss addsimps (perm_fun_def ::
   911                   expand_fun_eq :: rep_inject_thms @ perm_rep_perm_thms)) 1)]))
   911                   expand_fun_eq :: rep_inject_thms @ perm_rep_perm_thms)) 1)])
   912         end) (constrs ~~ constr_rep_thms)
   912         end) (constrs ~~ constr_rep_thms)
   913       end) (List.take (pdescr, length new_type_names) ~~ new_type_names ~~ constr_rep_thmss);
   913       end) (List.take (pdescr, length new_type_names) ~~ new_type_names ~~ constr_rep_thmss);
   914 
   914 
   915     (** equations for support and freshness **)
   915     (** equations for support and freshness **)
   916 
   916 
   944           fun supp t =
   944           fun supp t =
   945             Const ("Nominal.supp", fastype_of t --> HOLogic.mk_setT atomT) $ t;
   945             Const ("Nominal.supp", fastype_of t --> HOLogic.mk_setT atomT) $ t;
   946           fun fresh t =
   946           fun fresh t =
   947             Const ("Nominal.fresh", atomT --> fastype_of t --> HOLogic.boolT) $
   947             Const ("Nominal.fresh", atomT --> fastype_of t --> HOLogic.boolT) $
   948               Free ("a", atomT) $ t;
   948               Free ("a", atomT) $ t;
   949           val supp_thm = standard (Goal.prove thy8 [] []
   949           val supp_thm = Goal.prove_global thy8 [] []
   950               (HOLogic.mk_Trueprop (HOLogic.mk_eq
   950               (HOLogic.mk_Trueprop (HOLogic.mk_eq
   951                 (supp c,
   951                 (supp c,
   952                  if null dts then Const ("{}", HOLogic.mk_setT atomT)
   952                  if null dts then Const ("{}", HOLogic.mk_setT atomT)
   953                  else foldr1 (HOLogic.mk_binop "op Un") (map supp args2))))
   953                  else foldr1 (HOLogic.mk_binop "op Un") (map supp args2))))
   954             (fn _ =>
   954             (fn _ =>
   955               simp_tac (HOL_basic_ss addsimps (supp_def ::
   955               simp_tac (HOL_basic_ss addsimps (supp_def ::
   956                  Un_assoc :: de_Morgan_conj :: Collect_disj_eq :: finite_Un ::
   956                  Un_assoc :: de_Morgan_conj :: Collect_disj_eq :: finite_Un ::
   957                  symmetric empty_def :: Finites.emptyI :: simp_thms @
   957                  symmetric empty_def :: Finites.emptyI :: simp_thms @
   958                  abs_perm @ abs_fresh @ inject_thms' @ perm_thms')) 1))
   958                  abs_perm @ abs_fresh @ inject_thms' @ perm_thms')) 1)
   959         in
   959         in
   960           (supp_thm,
   960           (supp_thm,
   961            standard (Goal.prove thy8 [] [] (HOLogic.mk_Trueprop (HOLogic.mk_eq
   961            Goal.prove_global thy8 [] [] (HOLogic.mk_Trueprop (HOLogic.mk_eq
   962               (fresh c,
   962               (fresh c,
   963                if null dts then HOLogic.true_const
   963                if null dts then HOLogic.true_const
   964                else foldr1 HOLogic.mk_conj (map fresh args2))))
   964                else foldr1 HOLogic.mk_conj (map fresh args2))))
   965              (fn _ =>
   965              (fn _ =>
   966                simp_tac (simpset_of thy8 addsimps [fresh_def, supp_thm]) 1)))
   966                simp_tac (simpset_of thy8 addsimps [fresh_def, supp_thm]) 1))
   967         end) atoms) constrs)
   967         end) atoms) constrs)
   968       end) (List.take (pdescr, length new_type_names) ~~ new_type_names ~~ inject_thms ~~ perm_simps')));
   968       end) (List.take (pdescr, length new_type_names) ~~ new_type_names ~~ inject_thms ~~ perm_simps')));
   969 
   969 
   970     (**** weak induction theorem ****)
   970     (**** weak induction theorem ****)
   971 
   971 
   983       end;
   983       end;
   984 
   984 
   985     val (indrule_lemma_prems, indrule_lemma_concls) =
   985     val (indrule_lemma_prems, indrule_lemma_concls) =
   986       Library.foldl mk_indrule_lemma (([], []), (descr'' ~~ recTs ~~ recTs'));
   986       Library.foldl mk_indrule_lemma (([], []), (descr'' ~~ recTs ~~ recTs'));
   987 
   987 
   988     val indrule_lemma = standard (Goal.prove thy8 [] []
   988     val indrule_lemma = Goal.prove_global thy8 [] []
   989       (Logic.mk_implies
   989       (Logic.mk_implies
   990         (HOLogic.mk_Trueprop (mk_conj indrule_lemma_prems),
   990         (HOLogic.mk_Trueprop (mk_conj indrule_lemma_prems),
   991          HOLogic.mk_Trueprop (mk_conj indrule_lemma_concls))) (fn _ => EVERY
   991          HOLogic.mk_Trueprop (mk_conj indrule_lemma_concls))) (fn _ => EVERY
   992            [REPEAT (etac conjE 1),
   992            [REPEAT (etac conjE 1),
   993             REPEAT (EVERY
   993             REPEAT (EVERY
   994               [TRY (rtac conjI 1), full_simp_tac (HOL_basic_ss addsimps Rep_inverse_thms) 1,
   994               [TRY (rtac conjI 1), full_simp_tac (HOL_basic_ss addsimps Rep_inverse_thms) 1,
   995                etac mp 1, resolve_tac Rep_thms 1])]));
   995                etac mp 1, resolve_tac Rep_thms 1])]);
   996 
   996 
   997     val Ps = map head_of (HOLogic.dest_conj (HOLogic.dest_Trueprop (concl_of indrule_lemma)));
   997     val Ps = map head_of (HOLogic.dest_conj (HOLogic.dest_Trueprop (concl_of indrule_lemma)));
   998     val frees = if length Ps = 1 then [Free ("P", snd (dest_Var (hd Ps)))] else
   998     val frees = if length Ps = 1 then [Free ("P", snd (dest_Var (hd Ps)))] else
   999       map (Free o apfst fst o dest_Var) Ps;
   999       map (Free o apfst fst o dest_Var) Ps;
  1000     val indrule_lemma' = cterm_instantiate
  1000     val indrule_lemma' = cterm_instantiate
  1001       (map (cterm_of thy8) Ps ~~ map (cterm_of thy8) frees) indrule_lemma;
  1001       (map (cterm_of thy8) Ps ~~ map (cterm_of thy8) frees) indrule_lemma;
  1002 
  1002 
  1003     val Abs_inverse_thms' = map (fn r => r RS subst) Abs_inverse_thms;
  1003     val Abs_inverse_thms' = map (fn r => r RS subst) Abs_inverse_thms;
  1004 
  1004 
  1005     val dt_induct_prop = DatatypeProp.make_ind descr' sorts';
  1005     val dt_induct_prop = DatatypeProp.make_ind descr' sorts';
  1006     val dt_induct = standard (Goal.prove thy8 []
  1006     val dt_induct = Goal.prove_global thy8 []
  1007       (Logic.strip_imp_prems dt_induct_prop) (Logic.strip_imp_concl dt_induct_prop)
  1007       (Logic.strip_imp_prems dt_induct_prop) (Logic.strip_imp_concl dt_induct_prop)
  1008       (fn prems => EVERY
  1008       (fn prems => EVERY
  1009         [rtac indrule_lemma' 1,
  1009         [rtac indrule_lemma' 1,
  1010          (DatatypeAux.indtac rep_induct THEN_ALL_NEW ObjectLogic.atomize_tac) 1,
  1010          (DatatypeAux.indtac rep_induct THEN_ALL_NEW ObjectLogic.atomize_tac) 1,
  1011          EVERY (map (fn (prem, r) => (EVERY
  1011          EVERY (map (fn (prem, r) => (EVERY
  1012            [REPEAT (eresolve_tac Abs_inverse_thms' 1),
  1012            [REPEAT (eresolve_tac Abs_inverse_thms' 1),
  1013             simp_tac (HOL_basic_ss addsimps [symmetric r]) 1,
  1013             simp_tac (HOL_basic_ss addsimps [symmetric r]) 1,
  1014             DEPTH_SOLVE_1 (ares_tac [prem] 1 ORELSE etac allE 1)]))
  1014             DEPTH_SOLVE_1 (ares_tac [prem] 1 ORELSE etac allE 1)]))
  1015                 (prems ~~ constr_defs))]));
  1015                 (prems ~~ constr_defs))]);
  1016 
  1016 
  1017     val case_names_induct = mk_case_names_induct descr'';
  1017     val case_names_induct = mk_case_names_induct descr'';
  1018 
  1018 
  1019     (**** prove that new datatypes have finite support ****)
  1019     (**** prove that new datatypes have finite support ****)
  1020 
  1020 
  1026     val supp_atm = PureThy.get_thms thy8 (Name "supp_atm");
  1026     val supp_atm = PureThy.get_thms thy8 (Name "supp_atm");
  1027 
  1027 
  1028     val finite_supp_thms = map (fn atom =>
  1028     val finite_supp_thms = map (fn atom =>
  1029       let val atomT = Type (atom, [])
  1029       let val atomT = Type (atom, [])
  1030       in map standard (List.take
  1030       in map standard (List.take
  1031         (split_conj_thm (Goal.prove thy8 [] [] (HOLogic.mk_Trueprop
  1031         (split_conj_thm (Goal.prove_global thy8 [] [] (HOLogic.mk_Trueprop
  1032            (foldr1 HOLogic.mk_conj (map (fn (s, T) => HOLogic.mk_mem
  1032            (foldr1 HOLogic.mk_conj (map (fn (s, T) => HOLogic.mk_mem
  1033              (Const ("Nominal.supp", T --> HOLogic.mk_setT atomT) $ Free (s, T),
  1033              (Const ("Nominal.supp", T --> HOLogic.mk_setT atomT) $ Free (s, T),
  1034               Const ("Finite_Set.Finites", HOLogic.mk_setT (HOLogic.mk_setT atomT))))
  1034               Const ("Finite_Set.Finites", HOLogic.mk_setT (HOLogic.mk_setT atomT))))
  1035                (indnames ~~ recTs))))
  1035                (indnames ~~ recTs))))
  1036            (fn _ => indtac dt_induct indnames 1 THEN
  1036            (fn _ => indtac dt_induct indnames 1 THEN
  1256         b_i : newly introduced names for binders (sufficiently fresh)
  1256         b_i : newly introduced names for binders (sufficiently fresh)
  1257     ***********************************************************************)
  1257     ***********************************************************************)
  1258 
  1258 
  1259     val _ = warning "proving strong induction theorem ...";
  1259     val _ = warning "proving strong induction theorem ...";
  1260 
  1260 
  1261     val induct_aux = standard (Goal.prove thy9 [] ind_prems' ind_concl'
  1261     val induct_aux = Goal.prove_global thy9 [] ind_prems' ind_concl'
  1262       (fn prems => EVERY
  1262       (fn prems => EVERY
  1263         ([mk_subgoal 1 (K (K (K aux_ind_concl))),
  1263         ([mk_subgoal 1 (K (K (K aux_ind_concl))),
  1264           indtac dt_induct tnames 1] @
  1264           indtac dt_induct tnames 1] @
  1265          List.concat (map (fn ((_, (_, _, constrs)), (_, constrs')) =>
  1265          List.concat (map (fn ((_, (_, _, constrs)), (_, constrs')) =>
  1266            List.concat (map (fn ((cname, cargs), is) =>
  1266            List.concat (map (fn ((cname, cargs), is) =>
  1308                         addsimps induct_aux_lemmas'
  1308                         addsimps induct_aux_lemmas'
  1309                         addsimprocs [perm_simproc]) i))) 1])
  1309                         addsimprocs [perm_simproc]) i))) 1])
  1310                (constrs ~~ constrs'))) (descr'' ~~ ndescr)) @
  1310                (constrs ~~ constrs'))) (descr'' ~~ ndescr)) @
  1311          [REPEAT (eresolve_tac [conjE, allE_Nil] 1),
  1311          [REPEAT (eresolve_tac [conjE, allE_Nil] 1),
  1312           REPEAT (etac allE 1),
  1312           REPEAT (etac allE 1),
  1313           REPEAT (TRY (rtac conjI 1) THEN asm_full_simp_tac (simpset_of thy9) 1)])));
  1313           REPEAT (TRY (rtac conjI 1) THEN asm_full_simp_tac (simpset_of thy9) 1)]));
  1314 
  1314 
  1315     val induct_aux' = Thm.instantiate ([],
  1315     val induct_aux' = Thm.instantiate ([],
  1316       map (fn (s, T) =>
  1316       map (fn (s, T) =>
  1317         let val pT = TVar (("'n", 0), HOLogic.typeS) --> T --> HOLogic.boolT
  1317         let val pT = TVar (("'n", 0), HOLogic.typeS) --> T --> HOLogic.boolT
  1318         in (cterm_of thy9 (Var ((s, 0), pT)), cterm_of thy9 (Free (s, pT))) end)
  1318         in (cterm_of thy9 (Var ((s, 0), pT)), cterm_of thy9 (Free (s, pT))) end)
  1321         let val f' = Logic.varify f
  1321         let val f' = Logic.varify f
  1322         in (cterm_of thy9 f',
  1322         in (cterm_of thy9 f',
  1323           cterm_of thy9 (Const ("Nominal.supp", fastype_of f')))
  1323           cterm_of thy9 (Const ("Nominal.supp", fastype_of f')))
  1324         end) fresh_fs) induct_aux;
  1324         end) fresh_fs) induct_aux;
  1325 
  1325 
  1326     val induct = standard (Goal.prove thy9 [] ind_prems ind_concl
  1326     val induct = Goal.prove_global thy9 [] ind_prems ind_concl
  1327       (fn prems => EVERY
  1327       (fn prems => EVERY
  1328          [rtac induct_aux' 1,
  1328          [rtac induct_aux' 1,
  1329           REPEAT (resolve_tac induct_aux_lemmas 1),
  1329           REPEAT (resolve_tac induct_aux_lemmas 1),
  1330           REPEAT ((resolve_tac prems THEN_ALL_NEW
  1330           REPEAT ((resolve_tac prems THEN_ALL_NEW
  1331             (etac meta_spec ORELSE' full_simp_tac (HOL_basic_ss addsimps [fresh_def]))) 1)]))
  1331             (etac meta_spec ORELSE' full_simp_tac (HOL_basic_ss addsimps [fresh_def]))) 1)])
  1332 
  1332 
  1333     val (_, thy10) = thy9 |>
  1333     val (_, thy10) = thy9 |>
  1334       Theory.add_path big_name |>
  1334       Theory.add_path big_name |>
  1335       PureThy.add_thms [(("induct'", induct_aux), [])] ||>>
  1335       PureThy.add_thms [(("induct'", induct_aux), [])] ||>>
  1336       PureThy.add_thms [(("induct", induct), [case_names_induct])] ||>>
  1336       PureThy.add_thms [(("induct", induct), [case_names_induct])] ||>>
  1428           in
  1428           in
  1429             (HOLogic.mk_mem (HOLogic.mk_prod (x, y), R),
  1429             (HOLogic.mk_mem (HOLogic.mk_prod (x, y), R),
  1430              HOLogic.mk_mem (HOLogic.mk_prod (mk_perm [] (pi, x), mk_perm [] (pi, y)), R'))
  1430              HOLogic.mk_mem (HOLogic.mk_prod (mk_perm [] (pi, x), mk_perm [] (pi, y)), R'))
  1431           end) (recTs ~~ rec_result_Ts ~~ rec_sets ~~ rec_sets_pi ~~ (1 upto length recTs));
  1431           end) (recTs ~~ rec_result_Ts ~~ rec_sets ~~ rec_sets_pi ~~ (1 upto length recTs));
  1432         val ths = map (fn th => standard (th RS mp)) (split_conj_thm
  1432         val ths = map (fn th => standard (th RS mp)) (split_conj_thm
  1433           (Goal.prove thy11 [] []
  1433           (Goal.prove_global thy11 [] []
  1434             (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj (map HOLogic.mk_imp ps)))
  1434             (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj (map HOLogic.mk_imp ps)))
  1435             (fn _ => rtac rec_induct 1 THEN REPEAT
  1435             (fn _ => rtac rec_induct 1 THEN REPEAT
  1436                (NominalPermeq.perm_simp_tac (simpset_of thy11) 1 THEN
  1436                (NominalPermeq.perm_simp_tac (simpset_of thy11) 1 THEN
  1437                 (resolve_tac rec_intrs THEN_ALL_NEW
  1437                 (resolve_tac rec_intrs THEN_ALL_NEW
  1438                  asm_simp_tac (HOL_ss addsimps (fresh_bij @ perm_bij))) 1))))
  1438                  asm_simp_tac (HOL_ss addsimps (fresh_bij @ perm_bij))) 1))))
  1439         val ths' = map (fn ((P, Q), th) => standard
  1439         val ths' = map (fn ((P, Q), th) =>
  1440           (Goal.prove thy11 [] []
  1440           Goal.prove_global thy11 [] []
  1441             (Logic.mk_implies (HOLogic.mk_Trueprop Q, HOLogic.mk_Trueprop P))
  1441             (Logic.mk_implies (HOLogic.mk_Trueprop Q, HOLogic.mk_Trueprop P))
  1442             (fn _ => dtac (Thm.instantiate ([],
  1442             (fn _ => dtac (Thm.instantiate ([],
  1443                  [(cterm_of thy11 (Var (("pi", 0), permT)),
  1443                  [(cterm_of thy11 (Var (("pi", 0), permT)),
  1444                    cterm_of thy11 (Const ("List.rev", permT --> permT) $ pi))]) th) 1 THEN
  1444                    cterm_of thy11 (Const ("List.rev", permT --> permT) $ pi))]) th) 1 THEN
  1445                NominalPermeq.perm_simp_tac HOL_ss 1))) (ps ~~ ths)
  1445                NominalPermeq.perm_simp_tac HOL_ss 1)) (ps ~~ ths)
  1446       in (ths, ths') end) dt_atomTs);
  1446       in (ths, ths') end) dt_atomTs);
  1447 
  1447 
  1448     (** finite support **)
  1448     (** finite support **)
  1449 
  1449 
  1450     val rec_fin_supp_thms = map (fn aT =>
  1450     val rec_fin_supp_thms = map (fn aT =>
  1456         val fins = map (fn (f, T) => HOLogic.mk_Trueprop (HOLogic.mk_mem
  1456         val fins = map (fn (f, T) => HOLogic.mk_Trueprop (HOLogic.mk_mem
  1457           (Const ("Nominal.supp", T --> aset) $ f, finites)))
  1457           (Const ("Nominal.supp", T --> aset) $ f, finites)))
  1458             (rec_fns ~~ rec_fn_Ts)
  1458             (rec_fns ~~ rec_fn_Ts)
  1459       in
  1459       in
  1460         map (fn th => standard (th RS mp)) (split_conj_thm
  1460         map (fn th => standard (th RS mp)) (split_conj_thm
  1461           (Goal.prove thy11 [] fins
  1461           (Goal.prove_global thy11 [] fins
  1462             (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
  1462             (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
  1463               (map (fn (((T, U), R), i) =>
  1463               (map (fn (((T, U), R), i) =>
  1464                  let
  1464                  let
  1465                    val x = Free ("x" ^ string_of_int i, T);
  1465                    val x = Free ("x" ^ string_of_int i, T);
  1466                    val y = Free ("y" ^ string_of_int i, U)
  1466                    val y = Free ("y" ^ string_of_int i, U)