src/HOL/Lfp.ML
changeset 3842 b55686a7b22c
parent 1873 b07ee188f061
child 5098 48e70d9fe05f
equal deleted inserted replaced
3841:22bbc1676768 3842:b55686a7b22c
    39 
    39 
    40 (*** General induction rule for least fixed points ***)
    40 (*** General induction rule for least fixed points ***)
    41 
    41 
    42 val [lfp,mono,indhyp] = goal Lfp.thy
    42 val [lfp,mono,indhyp] = goal Lfp.thy
    43     "[| a: lfp(f);  mono(f);                            \
    43     "[| a: lfp(f);  mono(f);                            \
    44 \       !!x. [| x: f(lfp(f) Int {x.P(x)}) |] ==> P(x)   \
    44 \       !!x. [| x: f(lfp(f) Int {x. P(x)}) |] ==> P(x)   \
    45 \    |] ==> P(a)";
    45 \    |] ==> P(a)";
    46 by (res_inst_tac [("a","a")] (Int_lower2 RS subsetD RS CollectD) 1);
    46 by (res_inst_tac [("a","a")] (Int_lower2 RS subsetD RS CollectD) 1);
    47 by (rtac (lfp RSN (2, lfp_lowerbound RS subsetD)) 1);
    47 by (rtac (lfp RSN (2, lfp_lowerbound RS subsetD)) 1);
    48 by (EVERY1 [rtac Int_greatest, rtac subset_trans, 
    48 by (EVERY1 [rtac Int_greatest, rtac subset_trans, 
    49             rtac (Int_lower1 RS (mono RS monoD)),
    49             rtac (Int_lower1 RS (mono RS monoD)),
    64 by (rtac (mono RS lfp_Tarski) 1);
    64 by (rtac (mono RS lfp_Tarski) 1);
    65 qed "def_lfp_Tarski";
    65 qed "def_lfp_Tarski";
    66 
    66 
    67 val rew::prems = goal Lfp.thy
    67 val rew::prems = goal Lfp.thy
    68     "[| A == lfp(f);  mono(f);   a:A;                   \
    68     "[| A == lfp(f);  mono(f);   a:A;                   \
    69 \       !!x. [| x: f(A Int {x.P(x)}) |] ==> P(x)        \
    69 \       !!x. [| x: f(A Int {x. P(x)}) |] ==> P(x)        \
    70 \    |] ==> P(a)";
    70 \    |] ==> P(a)";
    71 by (EVERY1 [rtac induct,        (*backtracking to force correct induction*)
    71 by (EVERY1 [rtac induct,        (*backtracking to force correct induction*)
    72             REPEAT1 o (ares_tac (map (rewrite_rule [rew]) prems))]);
    72             REPEAT1 o (ares_tac (map (rewrite_rule [rew]) prems))]);
    73 qed "def_induct";
    73 qed "def_induct";
    74 
    74