src/ZF/AC/recfunAC16.ML
changeset 3731 71366483323b
parent 2469 b50b8c0eec01
child 4091 771b1f6422a8
equal deleted inserted replaced
3730:6933d20f335f 3731:71366483323b
    11 (* Basic properties of recfunAC16                                         *)
    11 (* Basic properties of recfunAC16                                         *)
    12 (* ********************************************************************** *)
    12 (* ********************************************************************** *)
    13 
    13 
    14 goalw thy [recfunAC16_def] "recfunAC16(f,fa,0,a) = 0";
    14 goalw thy [recfunAC16_def] "recfunAC16(f,fa,0,a) = 0";
    15 by (rtac transrec2_0 1);
    15 by (rtac transrec2_0 1);
    16 val recfunAC16_0 = result();
    16 qed "recfunAC16_0";
    17 
    17 
    18 goalw thy [recfunAC16_def] "recfunAC16(f,fa,succ(i),a) =  \
    18 goalw thy [recfunAC16_def] "recfunAC16(f,fa,succ(i),a) =  \
    19 \       if (EX y:recfunAC16(f,fa,i,a). fa ` i <= y, recfunAC16(f,fa,i,a), \
    19 \       if (EX y:recfunAC16(f,fa,i,a). fa ` i <= y, recfunAC16(f,fa,i,a), \
    20 \       recfunAC16(f,fa,i,a) Un {f ` (LEAST j. fa ` i <= f ` j &  \
    20 \       recfunAC16(f,fa,i,a) Un {f ` (LEAST j. fa ` i <= f ` j &  \
    21 \       (ALL b<a. (fa`b <= f`j  \
    21 \       (ALL b<a. (fa`b <= f`j  \
    22 \       --> (ALL t:recfunAC16(f,fa,i,a). ~ fa`b <= t))))})";
    22 \       --> (ALL t:recfunAC16(f,fa,i,a). ~ fa`b <= t))))})";
    23 by (rtac transrec2_succ 1);
    23 by (rtac transrec2_succ 1);
    24 val recfunAC16_succ = result();
    24 qed "recfunAC16_succ";
    25 
    25 
    26 goalw thy [recfunAC16_def] "!!i. Limit(i)  \
    26 goalw thy [recfunAC16_def] "!!i. Limit(i)  \
    27 \       ==> recfunAC16(f,fa,i,a) = (UN j<i. recfunAC16(f,fa,j,a))";
    27 \       ==> recfunAC16(f,fa,i,a) = (UN j<i. recfunAC16(f,fa,j,a))";
    28 by (etac transrec2_Limit 1);
    28 by (etac transrec2_Limit 1);
    29 val recfunAC16_Limit = result();
    29 qed "recfunAC16_Limit";
    30 
    30 
    31 (* ********************************************************************** *)
    31 (* ********************************************************************** *)
    32 (* Monotonicity of transrec2                                              *)
    32 (* Monotonicity of transrec2                                              *)
    33 (* ********************************************************************** *)
    33 (* ********************************************************************** *)
    34 
    34 
    42 by (fast_tac (FOL_cs addSIs [succI1, prem1]
    42 by (fast_tac (FOL_cs addSIs [succI1, prem1]
    43         addSEs [ballE, leE, prem1 RSN (2, subset_trans)]) 1);
    43         addSEs [ballE, leE, prem1 RSN (2, subset_trans)]) 1);
    44 by (fast_tac (!claset addIs [OUN_I, ltI]
    44 by (fast_tac (!claset addIs [OUN_I, ltI]
    45         addSEs [Limit_has_succ RS ltE, succI1 RSN (2, Ord_in_Ord) RS le_refl,
    45         addSEs [Limit_has_succ RS ltE, succI1 RSN (2, Ord_in_Ord) RS le_refl,
    46                 transrec2_Limit RS ssubst]) 1);
    46                 transrec2_Limit RS ssubst]) 1);
    47 val transrec2_mono_lemma = result();
    47 qed "transrec2_mono_lemma";
    48 
    48 
    49 val [prem1, prem2] = goal thy "[| !!g r. r <= B(g,r); j le i |]  \
    49 val [prem1, prem2] = goal thy "[| !!g r. r <= B(g,r); j le i |]  \
    50 \       ==> transrec2(j, 0, B) <= transrec2(i, 0, B)";
    50 \       ==> transrec2(j, 0, B) <= transrec2(i, 0, B)";
    51 by (resolve_tac [prem2 RS leE] 1);
    51 by (resolve_tac [prem2 RS leE] 1);
    52 by (resolve_tac [transrec2_mono_lemma RS impE] 1);
    52 by (resolve_tac [transrec2_mono_lemma RS impE] 1);
    53 by (TRYALL (fast_tac (!claset addSIs [prem1, prem2, lt_Ord2])));
    53 by (TRYALL (fast_tac (!claset addSIs [prem1, prem2, lt_Ord2])));
    54 val transrec2_mono = result();
    54 qed "transrec2_mono";
    55 
    55 
    56 (* ********************************************************************** *)
    56 (* ********************************************************************** *)
    57 (* Monotonicity of recfunAC16                                             *)
    57 (* Monotonicity of recfunAC16                                             *)
    58 (* ********************************************************************** *)
    58 (* ********************************************************************** *)
    59 
    59 
    60 goalw thy [recfunAC16_def]
    60 goalw thy [recfunAC16_def]
    61         "!!i. i le j ==> recfunAC16(f, g, i, a) <= recfunAC16(f, g, j, a)";
    61         "!!i. i le j ==> recfunAC16(f, g, i, a) <= recfunAC16(f, g, j, a)";
    62 by (rtac transrec2_mono 1);
    62 by (rtac transrec2_mono 1);
    63 by (REPEAT (fast_tac (!claset addIs [expand_if RS iffD2]) 1));
    63 by (REPEAT (fast_tac (!claset addIs [expand_if RS iffD2]) 1));
    64 val recfunAC16_mono = result();
    64 qed "recfunAC16_mono";
    65 
    65