src/HOLCF/Cfun2.ML
changeset 892 d0dc8d057929
parent 297 5ef75ff3baeb
child 1168 74be52691d62
equal deleted inserted replaced
891:a5ad535a241a 892:d0dc8d057929
    10 
    10 
    11 (* ------------------------------------------------------------------------ *)
    11 (* ------------------------------------------------------------------------ *)
    12 (* access to less_cfun in class po                                          *)
    12 (* access to less_cfun in class po                                          *)
    13 (* ------------------------------------------------------------------------ *)
    13 (* ------------------------------------------------------------------------ *)
    14 
    14 
    15 val less_cfun = prove_goal Cfun2.thy "( f1 << f2 ) = (fapp(f1) << fapp(f2))"
    15 qed_goal "less_cfun" Cfun2.thy "( f1 << f2 ) = (fapp(f1) << fapp(f2))"
    16 (fn prems =>
    16 (fn prems =>
    17 	[
    17 	[
    18 	(rtac (inst_cfun_po RS ssubst) 1),
    18 	(rtac (inst_cfun_po RS ssubst) 1),
    19 	(fold_goals_tac [less_cfun_def]),
    19 	(fold_goals_tac [less_cfun_def]),
    20 	(rtac refl 1)
    20 	(rtac refl 1)
    22 
    22 
    23 (* ------------------------------------------------------------------------ *)
    23 (* ------------------------------------------------------------------------ *)
    24 (* Type 'a ->'b  is pointed                                                 *)
    24 (* Type 'a ->'b  is pointed                                                 *)
    25 (* ------------------------------------------------------------------------ *)
    25 (* ------------------------------------------------------------------------ *)
    26 
    26 
    27 val minimal_cfun = prove_goalw Cfun2.thy [UU_cfun_def] "UU_cfun << f"
    27 qed_goalw "minimal_cfun" Cfun2.thy [UU_cfun_def] "UU_cfun << f"
    28 (fn prems =>
    28 (fn prems =>
    29 	[
    29 	[
    30 	(rtac (less_cfun RS ssubst) 1),
    30 	(rtac (less_cfun RS ssubst) 1),
    31 	(rtac (Abs_Cfun_inverse2 RS ssubst) 1),
    31 	(rtac (Abs_Cfun_inverse2 RS ssubst) 1),
    32 	(rtac contX_const 1),
    32 	(rtac contX_const 1),
    38 (* fapp yields continuous functions in 'a => 'b                             *)
    38 (* fapp yields continuous functions in 'a => 'b                             *)
    39 (* this is continuity of fapp in its 'second' argument                      *)
    39 (* this is continuity of fapp in its 'second' argument                      *)
    40 (* contX_fapp2 ==> monofun_fapp2 & contlub_fapp2                            *)
    40 (* contX_fapp2 ==> monofun_fapp2 & contlub_fapp2                            *)
    41 (* ------------------------------------------------------------------------ *)
    41 (* ------------------------------------------------------------------------ *)
    42 
    42 
    43 val contX_fapp2 = prove_goal Cfun2.thy "contX(fapp(fo))"
    43 qed_goal "contX_fapp2" Cfun2.thy "contX(fapp(fo))"
    44 (fn prems =>
    44 (fn prems =>
    45 	[
    45 	[
    46 	(res_inst_tac [("P","contX")] CollectD 1),
    46 	(res_inst_tac [("P","contX")] CollectD 1),
    47 	(fold_goals_tac [Cfun_def]),
    47 	(fold_goals_tac [Cfun_def]),
    48 	(rtac Rep_Cfun 1)
    48 	(rtac Rep_Cfun 1)
    70 
    70 
    71 (* ------------------------------------------------------------------------ *)
    71 (* ------------------------------------------------------------------------ *)
    72 (* fapp is monotone in its 'first' argument                                 *)
    72 (* fapp is monotone in its 'first' argument                                 *)
    73 (* ------------------------------------------------------------------------ *)
    73 (* ------------------------------------------------------------------------ *)
    74 
    74 
    75 val monofun_fapp1 = prove_goalw Cfun2.thy [monofun] "monofun(fapp)"
    75 qed_goalw "monofun_fapp1" Cfun2.thy [monofun] "monofun(fapp)"
    76 (fn prems =>
    76 (fn prems =>
    77 	[
    77 	[
    78 	(strip_tac 1),
    78 	(strip_tac 1),
    79 	(etac (less_cfun RS subst) 1)
    79 	(etac (less_cfun RS subst) 1)
    80 	]);
    80 	]);
    82 
    82 
    83 (* ------------------------------------------------------------------------ *)
    83 (* ------------------------------------------------------------------------ *)
    84 (* monotonicity of application fapp in mixfix syntax [_]_                   *)
    84 (* monotonicity of application fapp in mixfix syntax [_]_                   *)
    85 (* ------------------------------------------------------------------------ *)
    85 (* ------------------------------------------------------------------------ *)
    86 
    86 
    87 val monofun_cfun_fun = prove_goal Cfun2.thy  "f1 << f2 ==> f1[x] << f2[x]"
    87 qed_goal "monofun_cfun_fun" Cfun2.thy  "f1 << f2 ==> f1[x] << f2[x]"
    88 (fn prems =>
    88 (fn prems =>
    89 	[
    89 	[
    90 	(cut_facts_tac prems 1),
    90 	(cut_facts_tac prems 1),
    91 	(res_inst_tac [("x","x")] spec 1),
    91 	(res_inst_tac [("x","x")] spec 1),
    92 	(rtac (less_fun RS subst) 1),
    92 	(rtac (less_fun RS subst) 1),
    99 
    99 
   100 (* ------------------------------------------------------------------------ *)
   100 (* ------------------------------------------------------------------------ *)
   101 (* monotonicity of fapp in both arguments in mixfix syntax [_]_             *)
   101 (* monotonicity of fapp in both arguments in mixfix syntax [_]_             *)
   102 (* ------------------------------------------------------------------------ *)
   102 (* ------------------------------------------------------------------------ *)
   103 
   103 
   104 val monofun_cfun = prove_goal Cfun2.thy
   104 qed_goal "monofun_cfun" Cfun2.thy
   105 	"[|f1<<f2;x1<<x2|] ==> f1[x1] << f2[x2]"
   105 	"[|f1<<f2;x1<<x2|] ==> f1[x1] << f2[x2]"
   106 (fn prems =>
   106 (fn prems =>
   107 	[
   107 	[
   108 	(cut_facts_tac prems 1),
   108 	(cut_facts_tac prems 1),
   109 	(rtac trans_less 1),
   109 	(rtac trans_less 1),
   115 (* ------------------------------------------------------------------------ *)
   115 (* ------------------------------------------------------------------------ *)
   116 (* ch2ch - rules for the type 'a -> 'b                                      *)
   116 (* ch2ch - rules for the type 'a -> 'b                                      *)
   117 (* use MF2 lemmas from Cont.ML                                              *)
   117 (* use MF2 lemmas from Cont.ML                                              *)
   118 (* ------------------------------------------------------------------------ *)
   118 (* ------------------------------------------------------------------------ *)
   119 
   119 
   120 val ch2ch_fappR = prove_goal Cfun2.thy 
   120 qed_goal "ch2ch_fappR" Cfun2.thy 
   121  "is_chain(Y) ==> is_chain(%i. f[Y(i)])"
   121  "is_chain(Y) ==> is_chain(%i. f[Y(i)])"
   122 (fn prems =>
   122 (fn prems =>
   123 	[
   123 	[
   124 	(cut_facts_tac prems 1),
   124 	(cut_facts_tac prems 1),
   125 	(etac (monofun_fapp2 RS ch2ch_MF2R) 1)
   125 	(etac (monofun_fapp2 RS ch2ch_MF2R) 1)
   133 (* ------------------------------------------------------------------------ *)
   133 (* ------------------------------------------------------------------------ *)
   134 (*  the lub of a chain of continous functions is monotone                   *)
   134 (*  the lub of a chain of continous functions is monotone                   *)
   135 (* use MF2 lemmas from Cont.ML                                              *)
   135 (* use MF2 lemmas from Cont.ML                                              *)
   136 (* ------------------------------------------------------------------------ *)
   136 (* ------------------------------------------------------------------------ *)
   137 
   137 
   138 val lub_cfun_mono = prove_goal Cfun2.thy 
   138 qed_goal "lub_cfun_mono" Cfun2.thy 
   139 	"is_chain(F) ==> monofun(% x.lub(range(% j.F(j)[x])))"
   139 	"is_chain(F) ==> monofun(% x.lub(range(% j.F(j)[x])))"
   140 (fn prems =>
   140 (fn prems =>
   141 	[
   141 	[
   142 	(cut_facts_tac prems 1),
   142 	(cut_facts_tac prems 1),
   143 	(rtac lub_MF2_mono 1),
   143 	(rtac lub_MF2_mono 1),
   149 (* ------------------------------------------------------------------------ *)
   149 (* ------------------------------------------------------------------------ *)
   150 (* a lemma about the exchange of lubs for type 'a -> 'b                     *)
   150 (* a lemma about the exchange of lubs for type 'a -> 'b                     *)
   151 (* use MF2 lemmas from Cont.ML                                              *)
   151 (* use MF2 lemmas from Cont.ML                                              *)
   152 (* ------------------------------------------------------------------------ *)
   152 (* ------------------------------------------------------------------------ *)
   153 
   153 
   154 val ex_lubcfun = prove_goal Cfun2.thy
   154 qed_goal "ex_lubcfun" Cfun2.thy
   155 	"[| is_chain(F); is_chain(Y) |] ==>\
   155 	"[| is_chain(F); is_chain(Y) |] ==>\
   156 \		lub(range(%j. lub(range(%i. F(j)[Y(i)])))) =\
   156 \		lub(range(%j. lub(range(%i. F(j)[Y(i)])))) =\
   157 \		lub(range(%i. lub(range(%j. F(j)[Y(i)]))))"
   157 \		lub(range(%i. lub(range(%j. F(j)[Y(i)]))))"
   158 (fn prems =>
   158 (fn prems =>
   159 	[
   159 	[
   167 
   167 
   168 (* ------------------------------------------------------------------------ *)
   168 (* ------------------------------------------------------------------------ *)
   169 (* the lub of a chain of cont. functions is continuous                      *)
   169 (* the lub of a chain of cont. functions is continuous                      *)
   170 (* ------------------------------------------------------------------------ *)
   170 (* ------------------------------------------------------------------------ *)
   171 
   171 
   172 val contX_lubcfun = prove_goal Cfun2.thy 
   172 qed_goal "contX_lubcfun" Cfun2.thy 
   173 	"is_chain(F) ==> contX(% x.lub(range(% j.F(j)[x])))"
   173 	"is_chain(F) ==> contX(% x.lub(range(% j.F(j)[x])))"
   174 (fn prems =>
   174 (fn prems =>
   175 	[
   175 	[
   176 	(cut_facts_tac prems 1),
   176 	(cut_facts_tac prems 1),
   177 	(rtac monocontlub2contX 1),
   177 	(rtac monocontlub2contX 1),
   186 
   186 
   187 (* ------------------------------------------------------------------------ *)
   187 (* ------------------------------------------------------------------------ *)
   188 (* type 'a -> 'b is chain complete                                          *)
   188 (* type 'a -> 'b is chain complete                                          *)
   189 (* ------------------------------------------------------------------------ *)
   189 (* ------------------------------------------------------------------------ *)
   190 
   190 
   191 val lub_cfun = prove_goal Cfun2.thy 
   191 qed_goal "lub_cfun" Cfun2.thy 
   192   "is_chain(CCF) ==> range(CCF) <<| fabs(% x.lub(range(% i.CCF(i)[x])))"
   192   "is_chain(CCF) ==> range(CCF) <<| fabs(% x.lub(range(% i.CCF(i)[x])))"
   193 (fn prems =>
   193 (fn prems =>
   194 	[
   194 	[
   195 	(cut_facts_tac prems 1),
   195 	(cut_facts_tac prems 1),
   196 	(rtac is_lubI 1),
   196 	(rtac is_lubI 1),
   214 val thelub_cfun = (lub_cfun RS thelubI);
   214 val thelub_cfun = (lub_cfun RS thelubI);
   215 (* 
   215 (* 
   216 is_chain(?CCF1) ==> lub(range(?CCF1)) = fabs(%x. lub(range(%i. ?CCF1(i)[x])))
   216 is_chain(?CCF1) ==> lub(range(?CCF1)) = fabs(%x. lub(range(%i. ?CCF1(i)[x])))
   217 *)
   217 *)
   218 
   218 
   219 val cpo_cfun = prove_goal Cfun2.thy 
   219 qed_goal "cpo_cfun" Cfun2.thy 
   220   "is_chain(CCF::nat=>('a::pcpo->'b::pcpo)) ==> ? x. range(CCF) <<| x"
   220   "is_chain(CCF::nat=>('a::pcpo->'b::pcpo)) ==> ? x. range(CCF) <<| x"
   221 (fn prems =>
   221 (fn prems =>
   222 	[
   222 	[
   223 	(cut_facts_tac prems 1),
   223 	(cut_facts_tac prems 1),
   224 	(rtac exI 1),
   224 	(rtac exI 1),
   228 
   228 
   229 (* ------------------------------------------------------------------------ *)
   229 (* ------------------------------------------------------------------------ *)
   230 (* Extensionality in 'a -> 'b                                               *)
   230 (* Extensionality in 'a -> 'b                                               *)
   231 (* ------------------------------------------------------------------------ *)
   231 (* ------------------------------------------------------------------------ *)
   232 
   232 
   233 val ext_cfun = prove_goal Cfun1.thy "(!!x. f[x] = g[x]) ==> f = g"
   233 qed_goal "ext_cfun" Cfun1.thy "(!!x. f[x] = g[x]) ==> f = g"
   234  (fn prems =>
   234  (fn prems =>
   235 	[
   235 	[
   236 	(res_inst_tac [("t","f")] (Rep_Cfun_inverse RS subst) 1),
   236 	(res_inst_tac [("t","f")] (Rep_Cfun_inverse RS subst) 1),
   237 	(res_inst_tac [("t","g")] (Rep_Cfun_inverse RS subst) 1),
   237 	(res_inst_tac [("t","g")] (Rep_Cfun_inverse RS subst) 1),
   238 	(res_inst_tac [("f","fabs")] arg_cong 1),
   238 	(res_inst_tac [("f","fabs")] arg_cong 1),
   242 
   242 
   243 (* ------------------------------------------------------------------------ *)
   243 (* ------------------------------------------------------------------------ *)
   244 (* Monotonicity of fabs                                                     *)
   244 (* Monotonicity of fabs                                                     *)
   245 (* ------------------------------------------------------------------------ *)
   245 (* ------------------------------------------------------------------------ *)
   246 
   246 
   247 val semi_monofun_fabs = prove_goal Cfun2.thy 
   247 qed_goal "semi_monofun_fabs" Cfun2.thy 
   248 	"[|contX(f);contX(g);f<<g|]==>fabs(f)<<fabs(g)"
   248 	"[|contX(f);contX(g);f<<g|]==>fabs(f)<<fabs(g)"
   249  (fn prems =>
   249  (fn prems =>
   250 	[
   250 	[
   251 	(rtac (less_cfun RS iffD2) 1),
   251 	(rtac (less_cfun RS iffD2) 1),
   252 	(rtac (Abs_Cfun_inverse2 RS ssubst) 1),
   252 	(rtac (Abs_Cfun_inverse2 RS ssubst) 1),
   258 
   258 
   259 (* ------------------------------------------------------------------------ *)
   259 (* ------------------------------------------------------------------------ *)
   260 (* Extenionality wrt. << in 'a -> 'b                                        *)
   260 (* Extenionality wrt. << in 'a -> 'b                                        *)
   261 (* ------------------------------------------------------------------------ *)
   261 (* ------------------------------------------------------------------------ *)
   262 
   262 
   263 val less_cfun2 = prove_goal Cfun2.thy "(!!x. f[x] << g[x]) ==> f << g"
   263 qed_goal "less_cfun2" Cfun2.thy "(!!x. f[x] << g[x]) ==> f << g"
   264  (fn prems =>
   264  (fn prems =>
   265 	[
   265 	[
   266 	(res_inst_tac [("t","f")] (Rep_Cfun_inverse RS subst) 1),
   266 	(res_inst_tac [("t","f")] (Rep_Cfun_inverse RS subst) 1),
   267 	(res_inst_tac [("t","g")] (Rep_Cfun_inverse RS subst) 1),
   267 	(res_inst_tac [("t","g")] (Rep_Cfun_inverse RS subst) 1),
   268 	(rtac semi_monofun_fabs 1),
   268 	(rtac semi_monofun_fabs 1),