src/HOLCF/Porder.ML
changeset 4721 c8a8482a8124
parent 4098 71e05eb27fb6
child 5068 fb28eaa07e01
equal deleted inserted replaced
4720:c1b83b42f65a 4721:c8a8482a8124
    26 
    26 
    27 (* ------------------------------------------------------------------------ *)
    27 (* ------------------------------------------------------------------------ *)
    28 (* chains are monotone functions                                            *)
    28 (* chains are monotone functions                                            *)
    29 (* ------------------------------------------------------------------------ *)
    29 (* ------------------------------------------------------------------------ *)
    30 
    30 
    31 qed_goalw "chain_mono" thy [is_chain] "is_chain F ==> x<y --> F x<<F y"
    31 qed_goalw "chain_mono" thy [chain] "chain F ==> x<y --> F x<<F y"
    32 ( fn prems =>
    32 ( fn prems =>
    33         [
    33         [
    34         (cut_facts_tac prems 1),
    34         (cut_facts_tac prems 1),
    35         (nat_ind_tac "y" 1),
    35         (nat_ind_tac "y" 1),
    36         (rtac impI 1),
    36         (rtac impI 1),
    45         (hyp_subst_tac 1),
    45         (hyp_subst_tac 1),
    46         (etac allE 1),
    46         (etac allE 1),
    47         (atac 1)
    47         (atac 1)
    48         ]);
    48         ]);
    49 
    49 
    50 qed_goal "chain_mono3" thy "[| is_chain F; x <= y |] ==> F x << F y"
    50 qed_goal "chain_mono3" thy "[| chain F; x <= y |] ==> F x << F y"
    51  (fn prems =>
    51  (fn prems =>
    52         [
    52         [
    53         (cut_facts_tac prems 1),
    53         (cut_facts_tac prems 1),
    54         (rtac (le_imp_less_or_eq RS disjE) 1),
    54         (rtac (le_imp_less_or_eq RS disjE) 1),
    55         (atac 1),
    55         (atac 1),
    62 
    62 
    63 (* ------------------------------------------------------------------------ *)
    63 (* ------------------------------------------------------------------------ *)
    64 (* The range of a chain is a totaly ordered     <<                           *)
    64 (* The range of a chain is a totaly ordered     <<                           *)
    65 (* ------------------------------------------------------------------------ *)
    65 (* ------------------------------------------------------------------------ *)
    66 
    66 
    67 qed_goalw "chain_is_tord" thy [is_tord] 
    67 qed_goalw "chain_tord" thy [tord] 
    68 "!!F. is_chain(F) ==> is_tord(range(F))"
    68 "!!F. chain(F) ==> tord(range(F))"
    69  (fn _ =>
    69  (fn _ =>
    70         [
    70         [
    71         Safe_tac,
    71         Safe_tac,
    72         (rtac nat_less_cases 1),
    72         (rtac nat_less_cases 1),
    73         (ALLGOALS (fast_tac (claset() addIs [refl_less, chain_mono RS mp])))]);
    73         (ALLGOALS (fast_tac (claset() addIs [refl_less, chain_mono RS mp])))]);
   136         [
   136         [
   137         (cut_facts_tac prems 1),
   137         (cut_facts_tac prems 1),
   138         (atac 1)
   138         (atac 1)
   139         ]);
   139         ]);
   140 
   140 
   141 qed_goalw "is_chainE" thy [is_chain] "is_chain F ==> !i. F(i) << F(Suc(i))"
   141 qed_goalw "chainE" thy [chain] "chain F ==> !i. F(i) << F(Suc(i))"
   142 (fn prems =>
   142 (fn prems =>
   143         [
   143         [
   144         (cut_facts_tac prems 1),
   144         (cut_facts_tac prems 1),
   145         (atac 1)]);
   145         (atac 1)]);
   146 
   146 
   147 qed_goalw "is_chainI" thy [is_chain] "!i. F i << F(Suc i) ==> is_chain F"
   147 qed_goalw "chainI" thy [chain] "!i. F i << F(Suc i) ==> chain F"
   148 (fn prems =>
   148 (fn prems =>
   149         [
   149         [
   150         (cut_facts_tac prems 1),
   150         (cut_facts_tac prems 1),
   151         (atac 1)]);
   151         (atac 1)]);
   152 
   152 
   183 (* ------------------------------------------------------------------------ *)
   183 (* ------------------------------------------------------------------------ *)
   184 (* results about finite chains                                              *)
   184 (* results about finite chains                                              *)
   185 (* ------------------------------------------------------------------------ *)
   185 (* ------------------------------------------------------------------------ *)
   186 
   186 
   187 qed_goalw "lub_finch1" thy [max_in_chain_def]
   187 qed_goalw "lub_finch1" thy [max_in_chain_def]
   188         "[| is_chain C; max_in_chain i C|] ==> range C <<| C i"
   188         "[| chain C; max_in_chain i C|] ==> range C <<| C i"
   189 (fn prems =>
   189 (fn prems =>
   190         [
   190         [
   191         (cut_facts_tac prems 1),
   191         (cut_facts_tac prems 1),
   192         (rtac is_lubI 1),
   192         (rtac is_lubI 1),
   193         (rtac conjI 1),
   193         (rtac conjI 1),
   216         (rtac (select_eq_Ex RS iffD2) 1),
   216         (rtac (select_eq_Ex RS iffD2) 1),
   217         (etac conjunct2 1)
   217         (etac conjunct2 1)
   218         ]);
   218         ]);
   219 
   219 
   220 
   220 
   221 qed_goal "bin_chain" thy "x<<y ==> is_chain (%i. if i=0 then x else y)"
   221 qed_goal "bin_chain" thy "x<<y ==> chain (%i. if i=0 then x else y)"
   222  (fn prems =>
   222  (fn prems =>
   223         [
   223         [
   224         (cut_facts_tac prems 1),
   224         (cut_facts_tac prems 1),
   225         (rtac is_chainI 1),
   225         (rtac chainI 1),
   226         (rtac allI 1),
   226         (rtac allI 1),
   227         (nat_ind_tac "i" 1),
   227         (nat_ind_tac "i" 1),
   228         (Asm_simp_tac 1),
   228         (Asm_simp_tac 1),
   229         (Asm_simp_tac 1)
   229         (Asm_simp_tac 1)
   230         ]);
   230         ]);