src/HOLCF/Pcpo.ML
changeset 15563 9e125b675253
parent 14981 e73f8140af78
child 16922 2128ac2aa5db
equal deleted inserted replaced
15562:8455c9671494 15563:9e125b675253
     1 (*  Title:      HOLCF/Pcpo.ML
       
     2     ID:         $Id$
       
     3     Author:     Franz Regensburger
       
     4 
     1 
     5 introduction of the classes cpo and pcpo 
     2 (* legacy ML bindings *)
     6 *)
       
     7  
       
     8 
     3 
     9 (* ------------------------------------------------------------------------ *)
     4 val cpo = thm "cpo";
    10 (* derive the old rule minimal                                              *)
     5 val least = thm "least";
    11 (* ------------------------------------------------------------------------ *)
     6 val UU_def = thm "UU_def";
    12  
     7 val chfin = thm "chfin";
    13 Goalw [UU_def] "ALL z. UU << z";
     8 val ax_flat = thm "ax_flat";
    14 by (rtac (some_eq_ex RS iffD2) 1);
     9 val UU_least = thm "UU_least";
    15 by (rtac least 1);
    10 val minimal = thm "minimal";
    16 qed "UU_least";
    11 val thelubE = thm "thelubE";
       
    12 val is_ub_thelub = thm "is_ub_thelub";
       
    13 val is_lub_thelub = thm "is_lub_thelub";
       
    14 val lub_range_shift = thm "lub_range_shift";
       
    15 val maxinch_is_thelub = thm "maxinch_is_thelub";
       
    16 val lub_mono = thm "lub_mono";
       
    17 val lub_equal = thm "lub_equal";
       
    18 val lub_mono2 = thm "lub_mono2";
       
    19 val lub_equal2 = thm "lub_equal2";
       
    20 val lub_mono3 = thm "lub_mono3";
       
    21 val eq_UU_iff = thm "eq_UU_iff";
       
    22 val UU_I = thm "UU_I";
       
    23 val not_less2not_eq = thm "not_less2not_eq";
       
    24 val chain_UU_I = thm "chain_UU_I";
       
    25 val chain_UU_I_inverse = thm "chain_UU_I_inverse";
       
    26 val chain_UU_I_inverse2 = thm "chain_UU_I_inverse2";
       
    27 val notUU_I = thm "notUU_I";
       
    28 val chain_mono2 = thm "chain_mono2";
       
    29 val flat_imp_chfin = thm "flat_imp_chfin";
       
    30 val flat_eq = thm "flat_eq";
       
    31 val chfin2finch = thm "chfin2finch";
       
    32 val infinite_chain_adm_lemma = thm "infinite_chain_adm_lemma";
       
    33 val increasing_chain_adm_lemma = thm "increasing_chain_adm_lemma";
    17 
    34 
    18 bind_thm("minimal", UU_least RS spec);
    35 structure Pcpo =
    19 
    36 struct
    20 AddIffs [minimal];
    37   val thy = the_context ();
    21 
    38   val UU_def = UU_def;
    22 (* ------------------------------------------------------------------------ *)
    39 end;
    23 (* in cpo's everthing equal to THE lub has lub properties for every chain  *)
       
    24 (* ------------------------------------------------------------------------ *)
       
    25 
       
    26 Goal "[| chain(S); lub(range(S)) = (l::'a::cpo) |] ==> range(S) <<| l ";
       
    27 by (blast_tac (claset() addDs [cpo] addIs [lubI]) 1);
       
    28 qed "thelubE";
       
    29 
       
    30 (* ------------------------------------------------------------------------ *)
       
    31 (* Properties of the lub                                                    *)
       
    32 (* ------------------------------------------------------------------------ *)
       
    33 
       
    34 
       
    35 Goal "chain (S::nat => 'a::cpo) ==> S(x) << lub(range(S))";
       
    36 by (blast_tac (claset() addDs [cpo] addIs [lubI RS is_ub_lub]) 1);
       
    37 qed "is_ub_thelub";
       
    38 
       
    39 Goal "[| chain (S::nat => 'a::cpo); range(S) <| x |] ==> lub(range S) << x";
       
    40 by (blast_tac (claset() addDs [cpo] addIs [lubI RS is_lub_lub]) 1);
       
    41 qed "is_lub_thelub";
       
    42 
       
    43 Goal "[| range X <= range Y;  chain Y; chain (X::nat=>'a::cpo) |] ==> lub(range X) << lub(range Y)";
       
    44 by (etac is_lub_thelub 1);
       
    45 by (rtac ub_rangeI 1);
       
    46 by (subgoal_tac "? j. X i = Y j" 1);
       
    47 by  (Clarsimp_tac 1);
       
    48 by  (etac is_ub_thelub 1);
       
    49 by Auto_tac;
       
    50 qed "lub_range_mono";
       
    51 
       
    52 Goal "chain (Y::nat=>'a::cpo) ==> lub(range (%i. Y(i + j))) = lub(range Y)";
       
    53 by (rtac antisym_less 1);
       
    54 by (rtac lub_range_mono 1);
       
    55 by    (Fast_tac 1);
       
    56 by   (atac 1);
       
    57 by (etac chain_shift 1);
       
    58 by (rtac is_lub_thelub 1);
       
    59 by (assume_tac 1);
       
    60 by (rtac ub_rangeI 1);
       
    61 by (rtac trans_less 1);
       
    62 by (rtac is_ub_thelub 2);
       
    63 by (etac chain_shift 2);
       
    64 by (etac chain_mono3 1);
       
    65 by (rtac le_add1 1);
       
    66 qed "lub_range_shift";
       
    67 
       
    68 Goal "chain Y ==> max_in_chain i Y = (lub(range(Y)) = ((Y i)::'a::cpo))";
       
    69 by (rtac iffI 1);
       
    70 by (fast_tac (HOL_cs addSIs [thelubI,lub_finch1]) 1);
       
    71 by (rewtac max_in_chain_def);
       
    72 by (safe_tac (HOL_cs addSIs [antisym_less]));
       
    73 by (fast_tac (HOL_cs addSEs [chain_mono3]) 1);
       
    74 by (dtac sym 1);
       
    75 by (force_tac (HOL_cs addSEs [is_ub_thelub], simpset()) 1);
       
    76 qed "maxinch_is_thelub";
       
    77 
       
    78 
       
    79 (* ------------------------------------------------------------------------ *)
       
    80 (* the << relation between two chains is preserved by their lubs            *)
       
    81 (* ------------------------------------------------------------------------ *)
       
    82 
       
    83 Goal "[|chain(C1::(nat=>'a::cpo));chain(C2); ALL k. C1(k) << C2(k)|]\
       
    84 \     ==> lub(range(C1)) << lub(range(C2))";
       
    85 by (etac is_lub_thelub 1);
       
    86 by (rtac ub_rangeI 1);
       
    87 by (rtac trans_less 1);
       
    88 by (etac spec 1);
       
    89 by (etac is_ub_thelub 1);
       
    90 qed "lub_mono";
       
    91 
       
    92 (* ------------------------------------------------------------------------ *)
       
    93 (* the = relation between two chains is preserved by their lubs            *)
       
    94 (* ------------------------------------------------------------------------ *)
       
    95 
       
    96 Goal "[| chain(C1::(nat=>'a::cpo));chain(C2);ALL k. C1(k)=C2(k)|]\
       
    97 \     ==> lub(range(C1))=lub(range(C2))";
       
    98 by (rtac antisym_less 1);
       
    99 by (rtac lub_mono 1);
       
   100 by (atac 1);
       
   101 by (atac 1);
       
   102 by (strip_tac 1);
       
   103 by (rtac (antisym_less_inverse RS conjunct1) 1);
       
   104 by (etac spec 1);
       
   105 by (rtac lub_mono 1);
       
   106 by (atac 1);
       
   107 by (atac 1);
       
   108 by (strip_tac 1);
       
   109 by (rtac (antisym_less_inverse RS conjunct2) 1);
       
   110 by (etac spec 1);
       
   111 qed "lub_equal";
       
   112 
       
   113 (* ------------------------------------------------------------------------ *)
       
   114 (* more results about mono and = of lubs of chains                          *)
       
   115 (* ------------------------------------------------------------------------ *)
       
   116 
       
   117 Goal "[|EX j. ALL i. j<i --> X(i::nat)=Y(i);chain(X::nat=>'a::cpo);chain(Y)|]\
       
   118 \ ==> lub(range(X))<<lub(range(Y))";
       
   119 by (etac  exE 1);
       
   120 by (rtac is_lub_thelub 1);
       
   121 by (assume_tac 1);
       
   122 by (rtac ub_rangeI 1);
       
   123 by (strip_tac 1);
       
   124 by (case_tac "j<i" 1);
       
   125 by (res_inst_tac [("s","Y(i)"),("t","X(i)")] subst 1);
       
   126 by (rtac sym 1);
       
   127 by (Fast_tac 1);
       
   128 by (rtac is_ub_thelub 1);
       
   129 by (assume_tac 1);
       
   130 by (res_inst_tac [("y","X(Suc(j))")] trans_less 1);
       
   131 by (rtac chain_mono 1);
       
   132 by (assume_tac 1);
       
   133 by (rtac (not_less_eq RS subst) 1);
       
   134 by (atac 1);
       
   135 by (res_inst_tac [("s","Y(Suc(j))"),("t","X(Suc(j))")] subst 1);
       
   136 by (Asm_simp_tac 1);
       
   137 by (etac is_ub_thelub 1);
       
   138 qed "lub_mono2";
       
   139 
       
   140 Goal "[|EX j. ALL i. j<i --> X(i)=Y(i); chain(X::nat=>'a::cpo); chain(Y)|]\
       
   141 \     ==> lub(range(X))=lub(range(Y))";
       
   142 by (blast_tac (claset() addIs [antisym_less, lub_mono2, sym]) 1);
       
   143 qed "lub_equal2";
       
   144 
       
   145 Goal "[|chain(Y::nat=>'a::cpo);chain(X);\
       
   146 \ALL i. EX j. Y(i)<< X(j)|]==> lub(range(Y))<<lub(range(X))";
       
   147 by (rtac is_lub_thelub 1);
       
   148 by (atac 1);
       
   149 by (rtac ub_rangeI 1);
       
   150 by (strip_tac 1);
       
   151 by (etac allE 1);
       
   152 by (etac exE 1);
       
   153 by (rtac trans_less 1);
       
   154 by (rtac is_ub_thelub 2);
       
   155 by (atac 2);
       
   156 by (atac 1);
       
   157 qed "lub_mono3";
       
   158 
       
   159 (* ------------------------------------------------------------------------ *)
       
   160 (* usefull lemmas about UU                                                  *)
       
   161 (* ------------------------------------------------------------------------ *)
       
   162 
       
   163 Goal "(x=UU)=(x<<UU)";
       
   164 by (rtac iffI 1);
       
   165 by (hyp_subst_tac 1);
       
   166 by (rtac refl_less 1);
       
   167 by (rtac antisym_less 1);
       
   168 by (atac 1);
       
   169 by (rtac minimal 1);
       
   170 qed "eq_UU_iff";
       
   171 
       
   172 Goal "x << UU ==> x = UU";
       
   173 by (stac eq_UU_iff 1);
       
   174 by (assume_tac 1);
       
   175 qed "UU_I";
       
   176 
       
   177 Goal "~(x::'a::po)<<y ==> ~x=y";
       
   178 by Auto_tac;
       
   179 qed "not_less2not_eq";
       
   180 
       
   181 Goal "[|chain(Y);lub(range(Y))=UU|] ==> ALL i. Y(i)=UU";
       
   182 by (rtac allI 1);
       
   183 by (rtac antisym_less 1);
       
   184 by (rtac minimal 2);
       
   185 by (etac subst 1);
       
   186 by (etac is_ub_thelub 1);
       
   187 qed "chain_UU_I";
       
   188 
       
   189 
       
   190 Goal "ALL i. Y(i::nat)=UU ==> lub(range(Y::(nat=>'a::pcpo)))=UU";
       
   191 by (rtac lub_chain_maxelem 1);
       
   192 by (etac spec 1);
       
   193 by (rtac allI 1);
       
   194 by (rtac (antisym_less_inverse RS conjunct1) 1);
       
   195 by (etac spec 1);
       
   196 qed "chain_UU_I_inverse";
       
   197 
       
   198 Goal "~lub(range(Y::(nat=>'a::pcpo)))=UU ==> EX i.~ Y(i)=UU";
       
   199 by (blast_tac (claset() addIs [chain_UU_I_inverse]) 1);
       
   200 qed "chain_UU_I_inverse2";
       
   201 
       
   202 Goal "[| x<<y; ~x=UU |] ==> ~y=UU";
       
   203 by (blast_tac (claset() addIs [UU_I]) 1);
       
   204 qed "notUU_I";
       
   205 
       
   206 Goal 
       
   207  "[|EX j. ~Y(j)=UU;chain(Y::nat=>'a::pcpo)|] ==> EX j. ALL i. j<i-->~Y(i)=UU";
       
   208 by (blast_tac (claset() addDs [notUU_I, chain_mono]) 1);
       
   209 qed "chain_mono2";
       
   210 
       
   211 (**************************************)
       
   212 (* some properties for chfin and flat *)
       
   213 (**************************************)
       
   214 
       
   215 (* ------------------------------------------------------------------------ *)
       
   216 (* flat types are chfin                                              *)
       
   217 (* ------------------------------------------------------------------------ *)
       
   218 
       
   219 (*Used only in an "instance" declaration (Fun1.thy)*)
       
   220 Goalw [max_in_chain_def]
       
   221      "ALL Y::nat=>'a::flat. chain Y --> (EX n. max_in_chain n Y)";
       
   222 by (Clarify_tac 1);
       
   223 by (case_tac "ALL i. Y(i)=UU" 1);
       
   224 by (res_inst_tac [("x","0")] exI 1);
       
   225 by (Asm_simp_tac 1);
       
   226 by (Asm_full_simp_tac 1);
       
   227 by (etac exE 1);
       
   228 by (res_inst_tac [("x","i")] exI 1);
       
   229 by (strip_tac 1);
       
   230 by (etac (le_imp_less_or_eq RS disjE) 1);
       
   231 by Safe_tac;
       
   232 by (blast_tac (claset() addDs [chain_mono, ax_flat RS spec RS spec RS mp]) 1);
       
   233 qed "flat_imp_chfin";
       
   234 
       
   235 (* flat subclass of chfin --> adm_flat not needed *)
       
   236 
       
   237 Goal "(a::'a::flat) ~= UU ==> a << b = (a = b)";
       
   238 by (safe_tac (HOL_cs addSIs [refl_less]));
       
   239 by (dtac (ax_flat RS spec RS spec RS mp) 1);
       
   240 by (fast_tac (HOL_cs addSIs [refl_less,ax_flat RS spec RS spec RS mp]) 1);
       
   241 qed "flat_eq";
       
   242 
       
   243 Goal "chain (Y::nat=>'a::chfin) ==> finite_chain Y";
       
   244 by (force_tac (HOL_cs, simpset() addsimps [chfin,finite_chain_def]) 1);
       
   245 qed "chfin2finch";
       
   246 
       
   247 (* ------------------------------------------------------------------------ *)
       
   248 (* lemmata for improved admissibility introdution rule                      *)
       
   249 (* ------------------------------------------------------------------------ *)
       
   250 
       
   251 val prems = Goal
       
   252 "[|chain Y; ALL i. P (Y i); \
       
   253 \  (!!Y. [| chain Y; ALL i. P (Y i); ~ finite_chain Y |] ==> P (lub(range Y)))\
       
   254 \ |] ==> P (lub (range Y))";
       
   255 by (cut_facts_tac prems 1);
       
   256 by (case_tac "finite_chain Y" 1);
       
   257 by (eresolve_tac prems 2);
       
   258 by (atac 2);
       
   259 by (atac 2);
       
   260 by (rewtac finite_chain_def);
       
   261 by (safe_tac HOL_cs);
       
   262 by (etac (lub_finch1 RS thelubI RS ssubst) 1);
       
   263 by (atac 1);
       
   264 by (etac spec 1);
       
   265 qed "infinite_chain_adm_lemma";
       
   266 
       
   267 val prems = Goal
       
   268 "[|chain Y;  ALL i. P (Y i); \
       
   269 \  (!!Y. [| chain Y; ALL i. P (Y i);  \
       
   270 \           ALL i. EX j. i < j & Y i ~= Y j & Y i << Y j|]\
       
   271 \ ==> P (lub (range Y))) |] ==> P (lub (range Y))";
       
   272 by (cut_facts_tac prems 1);
       
   273 by (etac infinite_chain_adm_lemma 1);
       
   274 by (atac 1);
       
   275 by (etac thin_rl 1);
       
   276 by (rewtac finite_chain_def);
       
   277 by (rewtac max_in_chain_def);
       
   278 by (fast_tac (HOL_cs addIs prems
       
   279 		     addDs [le_imp_less_or_eq] addEs [chain_mono]) 1);
       
   280 qed "increasing_chain_adm_lemma";