src/ZF/WF.ML
changeset 6 8ce8c4d13d4d
parent 0 a5a9c433f639
child 435 ca5356bd315a
equal deleted inserted replaced
5:75e163863e16 6:8ce8c4d13d4d
    16 epsilon.ML.  Expanding out the definition of wftrec in wfrec would yield
    16 epsilon.ML.  Expanding out the definition of wftrec in wfrec would yield
    17 a mess.
    17 a mess.
    18 *)
    18 *)
    19 
    19 
    20 open WF;
    20 open WF;
    21 
       
    22 val [H_cong] = mk_typed_congs WF.thy[("H","[i,i]=>i")];
       
    23 
       
    24 val wf_ss = ZF_ss addcongs [H_cong];
       
    25 
    21 
    26 
    22 
    27 (*** Well-founded relations ***)
    23 (*** Well-founded relations ***)
    28 
    24 
    29 (*Are these two theorems at all useful??*)
    25 (*Are these two theorems at all useful??*)
   136 val apply_recfun = result();
   132 val apply_recfun = result();
   137 
   133 
   138 (*eresolve_tac transD solves <a,b>:r using transitivity AT MOST ONCE
   134 (*eresolve_tac transD solves <a,b>:r using transitivity AT MOST ONCE
   139   spec RS mp  instantiates induction hypotheses*)
   135   spec RS mp  instantiates induction hypotheses*)
   140 fun indhyp_tac hyps =
   136 fun indhyp_tac hyps =
   141     ares_tac (TrueI::hyps) ORELSE' 
   137     resolve_tac (TrueI::refl::hyps) ORELSE' 
   142     (cut_facts_tac hyps THEN'
   138     (cut_facts_tac hyps THEN'
   143        DEPTH_SOLVE_1 o (ares_tac [TrueI, ballI] ORELSE'
   139        DEPTH_SOLVE_1 o (ares_tac [TrueI, ballI] ORELSE'
   144 		        eresolve_tac [underD, transD, spec RS mp]));
   140 		        eresolve_tac [underD, transD, spec RS mp]));
   145 
   141 
   146 (*** NOTE! some simplifications need a different auto_tac!! ***)
   142 (*** NOTE! some simplifications need a different solver!! ***)
   147 val wf_super_ss = wf_ss setauto indhyp_tac;
   143 val wf_super_ss = ZF_ss setsolver indhyp_tac;
   148 
   144 
   149 val prems = goalw WF.thy [is_recfun_def]
   145 val prems = goalw WF.thy [is_recfun_def]
   150     "[| wf(r);  trans(r);  is_recfun(r,a,H,f);  is_recfun(r,b,H,g) |] ==> \
   146     "[| wf(r);  trans(r);  is_recfun(r,a,H,f);  is_recfun(r,b,H,g) |] ==> \
   151 \    <x,a>:r --> <x,b>:r --> f`x=g`x";
   147 \    <x,a>:r --> <x,b>:r --> f`x=g`x";
   152 by (cut_facts_tac prems 1);
   148 by (cut_facts_tac prems 1);
   153 by (wf_ind_tac "x" prems 1);
   149 by (wf_ind_tac "x" prems 1);
   154 by (REPEAT (rtac impI 1 ORELSE etac ssubst 1));
   150 by (REPEAT (rtac impI 1 ORELSE etac ssubst 1));
   155 by (rewtac restrict_def);
   151 by (rewtac restrict_def);
   156 by (ASM_SIMP_TAC (wf_super_ss addrews [vimage_singleton_iff]) 1);
   152 by (asm_simp_tac (wf_super_ss addsimps [vimage_singleton_iff]) 1);
   157 val is_recfun_equal_lemma = result();
   153 val is_recfun_equal_lemma = result();
   158 val is_recfun_equal = standard (is_recfun_equal_lemma RS mp RS mp);
   154 val is_recfun_equal = standard (is_recfun_equal_lemma RS mp RS mp);
   159 
   155 
   160 val prems as [wfr,transr,recf,recg,_] = goal WF.thy
   156 val prems as [wfr,transr,recf,recg,_] = goal WF.thy
   161     "[| wf(r);  trans(r);       \
   157     "[| wf(r);  trans(r);       \
   163 \    restrict(f, r-``{b}) = g";
   159 \    restrict(f, r-``{b}) = g";
   164 by (cut_facts_tac prems 1);
   160 by (cut_facts_tac prems 1);
   165 by (rtac (consI1 RS restrict_type RS fun_extension) 1);
   161 by (rtac (consI1 RS restrict_type RS fun_extension) 1);
   166 by (etac is_recfun_type 1);
   162 by (etac is_recfun_type 1);
   167 by (ALLGOALS
   163 by (ALLGOALS
   168     (ASM_SIMP_TAC (wf_super_ss addrews
   164     (asm_simp_tac (wf_super_ss addsimps
   169 		   [ [wfr,transr,recf,recg] MRS is_recfun_equal ])));
   165 		   [ [wfr,transr,recf,recg] MRS is_recfun_equal ])));
   170 val is_recfun_cut = result();
   166 val is_recfun_cut = result();
   171 
   167 
   172 (*** Main Existence Lemma ***)
   168 (*** Main Existence Lemma ***)
   173 
   169 
   193 by (wf_ind_tac "a" prems 1);
   189 by (wf_ind_tac "a" prems 1);
   194 by (res_inst_tac [("f", "lam y: r-``{a1}. wftrec(r,y,H)")] is_the_recfun 1);
   190 by (res_inst_tac [("f", "lam y: r-``{a1}. wftrec(r,y,H)")] is_the_recfun 1);
   195 by (REPEAT (assume_tac 2));
   191 by (REPEAT (assume_tac 2));
   196 by (rewrite_goals_tac [is_recfun_def, wftrec_def]);
   192 by (rewrite_goals_tac [is_recfun_def, wftrec_def]);
   197 (*Applying the substitution: must keep the quantified assumption!!*)
   193 (*Applying the substitution: must keep the quantified assumption!!*)
   198 by (REPEAT (dtac underD 1 ORELSE resolve_tac [refl, lam_cong, H_cong] 1));
   194 by (REPEAT (dtac underD 1 ORELSE resolve_tac [refl, lam_cong] 1));
   199 by (fold_tac [is_recfun_def]);
   195 by (fold_tac [is_recfun_def]);
   200 by (rtac (consI1 RS restrict_type RSN (2,fun_extension)) 1);
   196 by (rtac (consI1 RS restrict_type RSN (2,fun_extension) RS subst_context) 1);
   201 by (rtac is_recfun_type 1);
   197 by (rtac is_recfun_type 1);
   202 by (ALLGOALS
   198 by (ALLGOALS
   203     (ASM_SIMP_TAC
   199     (asm_simp_tac
   204      (wf_super_ss addrews [underI RS beta, apply_recfun, is_recfun_cut])));
   200      (wf_super_ss addsimps [underI RS beta, apply_recfun, is_recfun_cut])));
   205 val unfold_the_recfun = result();
   201 val unfold_the_recfun = result();
   206 
   202 
   207 
   203 
   208 (*** Unfolding wftrec ***)
   204 (*** Unfolding wftrec ***)
   209 
   205 
   212 \    restrict(the_recfun(r,a,H), r-``{b}) = the_recfun(r,b,H)";
   208 \    restrict(the_recfun(r,a,H), r-``{b}) = the_recfun(r,b,H)";
   213 by (REPEAT (ares_tac (prems @ [is_recfun_cut, unfold_the_recfun]) 1));
   209 by (REPEAT (ares_tac (prems @ [is_recfun_cut, unfold_the_recfun]) 1));
   214 val the_recfun_cut = result();
   210 val the_recfun_cut = result();
   215 
   211 
   216 (*NOT SUITABLE FOR REWRITING since it is recursive!*)
   212 (*NOT SUITABLE FOR REWRITING since it is recursive!*)
   217 val prems = goalw WF.thy [wftrec_def]
   213 goalw WF.thy [wftrec_def]
   218     "[| wf(r);  trans(r) |] ==> \
   214     "!!r. [| wf(r);  trans(r) |] ==> \
   219 \    wftrec(r,a,H) = H(a, lam x: r-``{a}. wftrec(r,x,H))";
   215 \         wftrec(r,a,H) = H(a, lam x: r-``{a}. wftrec(r,x,H))";
   220 by (rtac (rewrite_rule [is_recfun_def] unfold_the_recfun RS ssubst) 1);
   216 by (rtac (rewrite_rule [is_recfun_def] unfold_the_recfun RS ssubst) 1);
   221 by (ALLGOALS (ASM_SIMP_TAC
   217 by (ALLGOALS (asm_simp_tac
   222 	      (wf_ss addrews (prems@[vimage_singleton_iff RS iff_sym, 
   218 	(ZF_ss addsimps [vimage_singleton_iff RS iff_sym, the_recfun_cut])));
   223 				     the_recfun_cut]))));
       
   224 val wftrec = result();
   219 val wftrec = result();
   225 
   220 
   226 (** Removal of the premise trans(r) **)
   221 (** Removal of the premise trans(r) **)
   227 
   222 
   228 (*NOT SUITABLE FOR REWRITING since it is recursive!*)
   223 (*NOT SUITABLE FOR REWRITING since it is recursive!*)
   229 val [wfr] = goalw WF.thy [wfrec_def]
   224 val [wfr] = goalw WF.thy [wfrec_def]
   230     "wf(r) ==> wfrec(r,a,H) = H(a, lam x:r-``{a}. wfrec(r,x,H))";
   225     "wf(r) ==> wfrec(r,a,H) = H(a, lam x:r-``{a}. wfrec(r,x,H))";
   231 by (rtac (wfr RS wf_trancl RS wftrec RS ssubst) 1);
   226 by (rtac (wfr RS wf_trancl RS wftrec RS ssubst) 1);
   232 by (rtac trans_trancl 1);
   227 by (rtac trans_trancl 1);
   233 by (rtac (refl RS H_cong) 1);
   228 by (rtac (vimage_pair_mono RS restrict_lam_eq RS subst_context) 1);
   234 by (rtac (vimage_pair_mono RS restrict_lam_eq) 1);
       
   235 by (etac r_into_trancl 1);
   229 by (etac r_into_trancl 1);
   236 by (rtac subset_refl 1);
   230 by (rtac subset_refl 1);
   237 val wfrec = result();
   231 val wfrec = result();
   238 
   232 
   239 (*This form avoids giant explosions in proofs.  NOTE USE OF == *)
   233 (*This form avoids giant explosions in proofs.  NOTE USE OF == *)
   251 by (res_inst_tac [("a","a")] wf_induct2 1);
   245 by (res_inst_tac [("a","a")] wf_induct2 1);
   252 by (rtac (wfrec RS ssubst) 4);
   246 by (rtac (wfrec RS ssubst) 4);
   253 by (REPEAT (ares_tac (prems@[lam_type]) 1
   247 by (REPEAT (ares_tac (prems@[lam_type]) 1
   254      ORELSE eresolve_tac [spec RS mp, underD] 1));
   248      ORELSE eresolve_tac [spec RS mp, underD] 1));
   255 val wfrec_type = result();
   249 val wfrec_type = result();
   256 
       
   257 val prems = goalw WF.thy [wfrec_def,wftrec_def,the_recfun_def,is_recfun_def]
       
   258     "[| r=r';  !!x u. H(x,u)=H'(x,u);  a=a' |] \
       
   259 \    ==> wfrec(r,a,H)=wfrec(r',a',H')";
       
   260 by (EVERY1 (map rtac (prems RL [subst])));
       
   261 by (SIMP_TAC (wf_ss addrews (prems RL [sym])) 1);
       
   262 val wfrec_cong = result();