src/ZF/WF.ML
changeset 437 435875e4b21d
parent 435 ca5356bd315a
child 443 10884e64c241
equal deleted inserted replaced
436:0cdc840297bb 437:435875e4b21d
    60   !!B. ALL x:A. (ALL y. <y,x>: r --> y:B) --> x:B ==> A<=B  *)
    60   !!B. ALL x:A. (ALL y. <y,x>: r --> y:B) --> x:B ==> A<=B  *)
    61 val [prem] = goal WF.thy
    61 val [prem] = goal WF.thy
    62     "[| !!y B. [| ALL x:A. (ALL y:A. <y,x>:r --> y:B) --> x:B;   y:A  \
    62     "[| !!y B. [| ALL x:A. (ALL y:A. <y,x>:r --> y:B) --> x:B;   y:A  \
    63 \              |] ==> y:B |] \
    63 \              |] ==> y:B |] \
    64 \    ==>  wf[A](r)";
    64 \    ==>  wf[A](r)";
    65 br wf_onI 1;
    65 by (rtac wf_onI 1);
    66 by (res_inst_tac [ ("c", "u") ] (prem RS DiffE) 1);
    66 by (res_inst_tac [ ("c", "u") ] (prem RS DiffE) 1);
    67 by (contr_tac 3);
    67 by (contr_tac 3);
    68 by (fast_tac ZF_cs 2);
    68 by (fast_tac ZF_cs 2);
    69 by (fast_tac ZF_cs 1);
    69 by (fast_tac ZF_cs 1);
    70 val wf_onI2 = result();
    70 val wf_onI2 = result();
   129 val [subs,indhyp] = goal WF.thy
   129 val [subs,indhyp] = goal WF.thy
   130     "[| field(r)<=A;  \
   130     "[| field(r)<=A;  \
   131 \       !!y B. [| ALL x:A. (ALL y:A. <y,x>:r --> y:B) --> x:B;   y:A  \
   131 \       !!y B. [| ALL x:A. (ALL y:A. <y,x>:r --> y:B) --> x:B;   y:A  \
   132 \              |] ==> y:B |] \
   132 \              |] ==> y:B |] \
   133 \    ==>  wf(r)";
   133 \    ==>  wf(r)";
   134 br ([wf_onI2, subs] MRS (wf_on_subset_A RS wf_on_field_imp_wf)) 1;
   134 by (rtac ([wf_onI2, subs] MRS (wf_on_subset_A RS wf_on_field_imp_wf)) 1);
   135 by (REPEAT (ares_tac [indhyp] 1));
   135 by (REPEAT (ares_tac [indhyp] 1));
   136 val wfI2 = result();
   136 val wfI2 = result();
   137 
   137 
   138 
   138 
   139 (*** Properties of well-founded relations ***)
   139 (*** Properties of well-founded relations ***)
   146 goal WF.thy "!!r. [| wf(r);  <a,x>:r;  <x,a>:r |] ==> P";
   146 goal WF.thy "!!r. [| wf(r);  <a,x>:r;  <x,a>:r |] ==> P";
   147 by (subgoal_tac "ALL x. <a,x>:r --> <x,a>:r --> P" 1);
   147 by (subgoal_tac "ALL x. <a,x>:r --> <x,a>:r --> P" 1);
   148 by (wf_ind_tac "a" [] 2);
   148 by (wf_ind_tac "a" [] 2);
   149 by (fast_tac ZF_cs 2);
   149 by (fast_tac ZF_cs 2);
   150 by (fast_tac FOL_cs 1);
   150 by (fast_tac FOL_cs 1);
   151 val wf_anti_sym = result();
   151 val wf_asym = result();
   152 
   152 
   153 goal WF.thy "!!r. [| wf[A](r); a: A |] ==> <a,a> ~: r";
   153 goal WF.thy "!!r. [| wf[A](r); a: A |] ==> <a,a> ~: r";
   154 by (wf_on_ind_tac "a" [] 1);
   154 by (wf_on_ind_tac "a" [] 1);
   155 by (fast_tac ZF_cs 1);
   155 by (fast_tac ZF_cs 1);
   156 val wf_on_not_refl = result();
   156 val wf_on_not_refl = result();
   158 goal WF.thy "!!r. [| wf[A](r);  <a,b>:r;  <b,a>:r;  a:A;  b:A |] ==> P";
   158 goal WF.thy "!!r. [| wf[A](r);  <a,b>:r;  <b,a>:r;  a:A;  b:A |] ==> P";
   159 by (subgoal_tac "ALL y:A. <a,y>:r --> <y,a>:r --> P" 1);
   159 by (subgoal_tac "ALL y:A. <a,y>:r --> <y,a>:r --> P" 1);
   160 by (wf_on_ind_tac "a" [] 2);
   160 by (wf_on_ind_tac "a" [] 2);
   161 by (fast_tac ZF_cs 2);
   161 by (fast_tac ZF_cs 2);
   162 by (fast_tac ZF_cs 1);
   162 by (fast_tac ZF_cs 1);
   163 val wf_on_anti_sym = result();
   163 val wf_on_asym = result();
   164 
   164 
   165 (*Needed to prove well_ordI.  Could also reason that wf[A](r) means
   165 (*Needed to prove well_ordI.  Could also reason that wf[A](r) means
   166   wf(r Int A*A);  thus wf( (r Int A*A)^+ ) and use wf_not_refl *)
   166   wf(r Int A*A);  thus wf( (r Int A*A)^+ ) and use wf_not_refl *)
   167 goal WF.thy
   167 goal WF.thy
   168     "!!r. [| wf[A](r); <a,b>:r; <b,c>:r; <c,a>:r; a:A; b:A; c:A |] ==> P";
   168     "!!r. [| wf[A](r); <a,b>:r; <b,c>:r; <c,a>:r; a:A; b:A; c:A |] ==> P";
   178 val bchain_tac = EVERY' [rtac (bspec RS mp), assume_tac, assume_tac ];
   178 val bchain_tac = EVERY' [rtac (bspec RS mp), assume_tac, assume_tac ];
   179 
   179 
   180 (*transitive closure of a WF relation is WF provided A is downwards closed*)
   180 (*transitive closure of a WF relation is WF provided A is downwards closed*)
   181 val [wfr,subs] = goal WF.thy
   181 val [wfr,subs] = goal WF.thy
   182     "[| wf[A](r);  r-``A <= A |] ==> wf[A](r^+)";
   182     "[| wf[A](r);  r-``A <= A |] ==> wf[A](r^+)";
   183 br wf_onI2 1;
   183 by (rtac wf_onI2 1);
   184 by (bchain_tac 1);
   184 by (bchain_tac 1);
   185 by (eres_inst_tac [("a","y")] (wfr RS wf_on_induct) 1);
   185 by (eres_inst_tac [("a","y")] (wfr RS wf_on_induct) 1);
   186 by (rtac (impI RS ballI) 1);
   186 by (rtac (impI RS ballI) 1);
   187 by (etac tranclE 1);
   187 by (etac tranclE 1);
   188 by (etac (bspec RS mp) 1 THEN assume_tac 1);
   188 by (etac (bspec RS mp) 1 THEN assume_tac 1);
   192 by (best_tac ZF_cs 1);
   192 by (best_tac ZF_cs 1);
   193 val wf_on_trancl = result();
   193 val wf_on_trancl = result();
   194 
   194 
   195 goal WF.thy "!!r. wf(r) ==> wf(r^+)";
   195 goal WF.thy "!!r. wf(r) ==> wf(r^+)";
   196 by (asm_full_simp_tac (ZF_ss addsimps [wf_iff_wf_on_field]) 1);
   196 by (asm_full_simp_tac (ZF_ss addsimps [wf_iff_wf_on_field]) 1);
   197 br (trancl_type RS field_rel_subset RSN (2, wf_on_subset_A)) 1;
   197 by (rtac (trancl_type RS field_rel_subset RSN (2, wf_on_subset_A)) 1);
   198 be wf_on_trancl 1;
   198 by (etac wf_on_trancl 1);
   199 by (fast_tac ZF_cs 1);
   199 by (fast_tac ZF_cs 1);
   200 val wf_trancl = result();
   200 val wf_trancl = result();
   201 
   201 
   202 
   202 
   203 
   203 
   340 
   340 
   341 
   341 
   342 goalw WF.thy [wf_on_def, wfrec_on_def]
   342 goalw WF.thy [wf_on_def, wfrec_on_def]
   343  "!!A r. [| wf[A](r);  a: A |] ==> \
   343  "!!A r. [| wf[A](r);  a: A |] ==> \
   344 \        wfrec[A](r,a,H) = H(a, lam x: (r-``{a}) Int A. wfrec[A](r,x,H))";
   344 \        wfrec[A](r,a,H) = H(a, lam x: (r-``{a}) Int A. wfrec[A](r,x,H))";
   345 be (wfrec RS trans) 1;
   345 by (etac (wfrec RS trans) 1);
   346 by (asm_simp_tac (ZF_ss addsimps [vimage_Int_square, cons_subset_iff]) 1);
   346 by (asm_simp_tac (ZF_ss addsimps [vimage_Int_square, cons_subset_iff]) 1);
   347 val wfrec_on = result();
   347 val wfrec_on = result();
   348 
   348