src/ZF/ex/Limit.ML
changeset 4091 771b1f6422a8
parent 3840 e0baea4d485a
child 4152 451104c223e2
equal deleted inserted replaced
4090:9f1eaab75e8c 4091:771b1f6422a8
    68     "[| !!x. x:set(D) ==> rel(D,x,x);   \
    68     "[| !!x. x:set(D) ==> rel(D,x,x);   \
    69 \       !!x y z. [| rel(D,x,y); rel(D,y,z); x:set(D); y:set(D); z:set(D)|] ==> \
    69 \       !!x y z. [| rel(D,x,y); rel(D,y,z); x:set(D); y:set(D); z:set(D)|] ==> \
    70 \                rel(D,x,z);  \
    70 \                rel(D,x,z);  \
    71 \       !!x y. [| rel(D,x,y); rel(D,y,x); x:set(D); y:set(D)|] ==> x=y |] ==> \
    71 \       !!x y. [| rel(D,x,y); rel(D,y,x); x:set(D); y:set(D)|] ==> x=y |] ==> \
    72 \    po(D)";
    72 \    po(D)";
    73 by (safe_tac (!claset));
    73 by (safe_tac (claset()));
    74 brr prems 1;
    74 brr prems 1;
    75 qed "poI";
    75 qed "poI";
    76 
    76 
    77 val prems = goalw Limit.thy [cpo_def]
    77 val prems = goalw Limit.thy [cpo_def]
    78     "[| po(D); !!X. chain(D,X) ==> islub(D,X,x(D,X))|] ==> cpo(D)";
    78     "[| po(D); !!X. chain(D,X) ==> islub(D,X,x(D,X))|] ==> cpo(D)";
    79 by (safe_tac (!claset addSIs [exI]));
    79 by (safe_tac (claset() addSIs [exI]));
    80 brr prems 1;
    80 brr prems 1;
    81 qed "cpoI";
    81 qed "cpoI";
    82 
    82 
    83 val [cpo] = goalw Limit.thy [cpo_def] "cpo(D) ==> po(D)";
    83 val [cpo] = goalw Limit.thy [cpo_def] "cpo(D) ==> po(D)";
    84 by (rtac (cpo RS conjunct1) 1);
    84 by (rtac (cpo RS conjunct1) 1);
   114 (* Theorems about isub and islub.                                       *)
   114 (* Theorems about isub and islub.                                       *)
   115 (*----------------------------------------------------------------------*)
   115 (*----------------------------------------------------------------------*)
   116 
   116 
   117 val prems = goalw Limit.thy [islub_def]  (* islub_isub *)
   117 val prems = goalw Limit.thy [islub_def]  (* islub_isub *)
   118     "islub(D,X,x) ==> isub(D,X,x)";
   118     "islub(D,X,x) ==> isub(D,X,x)";
   119 by (simp_tac (!simpset addsimps prems) 1);
   119 by (simp_tac (simpset() addsimps prems) 1);
   120 qed "islub_isub";
   120 qed "islub_isub";
   121 
   121 
   122 val prems = goal Limit.thy
   122 val prems = goal Limit.thy
   123     "islub(D,X,x) ==> x:set(D)";
   123     "islub(D,X,x) ==> x:set(D)";
   124 by (rtac (rewrite_rule[islub_def,isub_def](hd prems) RS conjunct1 RS conjunct1) 1);
   124 by (rtac (rewrite_rule[islub_def,isub_def](hd prems) RS conjunct1 RS conjunct1) 1);
   137 by (resolve_tac prems 1);
   137 by (resolve_tac prems 1);
   138 qed "islub_least";
   138 qed "islub_least";
   139 
   139 
   140 val prems = goalw Limit.thy [islub_def]  (* islubI *)
   140 val prems = goalw Limit.thy [islub_def]  (* islubI *)
   141     "[|isub(D,X,x); !!y. isub(D,X,y) ==> rel(D,x,y)|] ==> islub(D,X,x)";
   141     "[|isub(D,X,x); !!y. isub(D,X,y) ==> rel(D,x,y)|] ==> islub(D,X,x)";
   142 by (safe_tac (!claset));
   142 by (safe_tac (claset()));
   143 by (REPEAT(ares_tac prems 1));
   143 by (REPEAT(ares_tac prems 1));
   144 qed "islubI";
   144 qed "islubI";
   145 
   145 
   146 val prems = goalw Limit.thy [isub_def]  (* isubI *)
   146 val prems = goalw Limit.thy [isub_def]  (* isubI *)
   147     "[|x:set(D);  !!n. n:nat ==> rel(D,X`n,x)|] ==> isub(D,X,x)";
   147     "[|x:set(D);  !!n. n:nat ==> rel(D,X`n,x)|] ==> isub(D,X,x)";
   148 by (safe_tac (!claset));
   148 by (safe_tac (claset()));
   149 by (REPEAT(ares_tac prems 1));
   149 by (REPEAT(ares_tac prems 1));
   150 qed "isubI";
   150 qed "isubI";
   151 
   151 
   152 val prems = goalw Limit.thy [isub_def]  (* isubE *)
   152 val prems = goalw Limit.thy [isub_def]  (* isubE *)
   153     "!!z.[|isub(D,X,x);[|x:set(D);  !!n. n:nat==>rel(D,X`n,x)|] ==> P|] ==> P";
   153     "!!z.[|isub(D,X,x);[|x:set(D);  !!n. n:nat==>rel(D,X`n,x)|] ==> P|] ==> P";
   154 by (safe_tac (!claset));
   154 by (safe_tac (claset()));
   155 by (Asm_simp_tac 1);
   155 by (Asm_simp_tac 1);
   156 qed "isubE";
   156 qed "isubE";
   157 
   157 
   158 val prems = goalw Limit.thy [isub_def]  (* isubD1 *)
   158 val prems = goalw Limit.thy [isub_def]  (* isubD1 *)
   159     "isub(D,X,x) ==> x:set(D)";
   159     "isub(D,X,x) ==> x:set(D)";
   160 by (simp_tac (!simpset addsimps prems) 1);
   160 by (simp_tac (simpset() addsimps prems) 1);
   161 qed "isubD1";
   161 qed "isubD1";
   162 
   162 
   163 val prems = goalw Limit.thy [isub_def]  (* isubD2 *)
   163 val prems = goalw Limit.thy [isub_def]  (* isubD2 *)
   164     "[|isub(D,X,x); n:nat|]==>rel(D,X`n,x)";
   164     "[|isub(D,X,x); n:nat|]==>rel(D,X`n,x)";
   165 by (simp_tac (!simpset addsimps prems) 1);
   165 by (simp_tac (simpset() addsimps prems) 1);
   166 qed "isubD2";
   166 qed "isubD2";
   167 
   167 
   168 val prems = goal Limit.thy
   168 val prems = goal Limit.thy
   169     "!!z. [|islub(D,X,x); islub(D,X,y); cpo(D)|] ==> x = y";
   169     "!!z. [|islub(D,X,x); islub(D,X,y); cpo(D)|] ==> x = y";
   170 by (etac cpo_antisym 1);
   170 by (etac cpo_antisym 1);
   196  "!!z.[|X:nat->set(D);  !!n. n:nat ==> rel(D,X`n,X`succ(n))|] ==> chain(D,X)"
   196  "!!z.[|X:nat->set(D);  !!n. n:nat ==> rel(D,X`n,X`succ(n))|] ==> chain(D,X)"
   197  (fn prems => [Asm_simp_tac 1]);
   197  (fn prems => [Asm_simp_tac 1]);
   198 
   198 
   199 val prems = goalw Limit.thy [chain_def]
   199 val prems = goalw Limit.thy [chain_def]
   200     "chain(D,X) ==> X : nat -> set(D)";
   200     "chain(D,X) ==> X : nat -> set(D)";
   201 by (asm_simp_tac (!simpset addsimps prems) 1);
   201 by (asm_simp_tac (simpset() addsimps prems) 1);
   202 qed "chain_fun";
   202 qed "chain_fun";
   203     
   203     
   204 val prems = goalw Limit.thy [chain_def]
   204 val prems = goalw Limit.thy [chain_def]
   205     "[|chain(D,X); n:nat|] ==> X`n : set(D)";
   205     "[|chain(D,X); n:nat|] ==> X`n : set(D)";
   206 by (rtac ((hd prems)RS conjunct1 RS apply_type) 1);
   206 by (rtac ((hd prems)RS conjunct1 RS apply_type) 1);
   234     "[|n le m; chain(D,X); cpo(D); n:nat; m:nat|] ==> rel(D,X`n,X`m)";
   234     "[|n le m; chain(D,X); cpo(D); n:nat; m:nat|] ==> rel(D,X`n,X`m)";
   235 by (rtac impE 1);  (* The first three steps prepare for the induction proof *)
   235 by (rtac impE 1);  (* The first three steps prepare for the induction proof *)
   236 by (assume_tac 3);
   236 by (assume_tac 3);
   237 by (rtac (hd prems) 2);
   237 by (rtac (hd prems) 2);
   238 by (res_inst_tac [("n","m")] nat_induct 1);
   238 by (res_inst_tac [("n","m")] nat_induct 1);
   239 by (safe_tac (!claset));
   239 by (safe_tac (claset()));
   240 by (asm_full_simp_tac (!simpset addsimps prems) 2);
   240 by (asm_full_simp_tac (simpset() addsimps prems) 2);
   241 by (rtac cpo_trans 4);
   241 by (rtac cpo_trans 4);
   242 by (rtac (le_succ_eq RS subst) 3);
   242 by (rtac (le_succ_eq RS subst) 3);
   243 brr(cpo_refl::chain_in::chain_rel::nat_0I::nat_succI::prems) 1;
   243 brr(cpo_refl::chain_in::chain_rel::nat_0I::nat_succI::prems) 1;
   244 qed "chain_rel_gen";
   244 qed "chain_rel_gen";
   245 
   245 
   262 
   262 
   263 val prems = goalw Limit.thy [pcpo_def] (* pcpo_bot_ex1 *)
   263 val prems = goalw Limit.thy [pcpo_def] (* pcpo_bot_ex1 *)
   264     "pcpo(D) ==> EX! x. x:set(D) & (ALL y:set(D). rel(D,x,y))";
   264     "pcpo(D) ==> EX! x. x:set(D) & (ALL y:set(D). rel(D,x,y))";
   265 by (rtac (hd prems RS conjunct2 RS bexE) 1);
   265 by (rtac (hd prems RS conjunct2 RS bexE) 1);
   266 by (rtac ex1I 1);
   266 by (rtac ex1I 1);
   267 by (safe_tac (!claset));
   267 by (safe_tac (claset()));
   268 by (assume_tac 1);
   268 by (assume_tac 1);
   269 by (etac bspec 1);
   269 by (etac bspec 1);
   270 by (assume_tac 1);
   270 by (assume_tac 1);
   271 by (rtac cpo_antisym 1);
   271 by (rtac cpo_antisym 1);
   272 by (rtac (hd prems RS conjunct1) 1);
   272 by (rtac (hd prems RS conjunct1) 1);
   309     "[|x:set(D); cpo(D)|] ==> chain(D,(lam n:nat. x))";
   309     "[|x:set(D); cpo(D)|] ==> chain(D,(lam n:nat. x))";
   310 by (rtac conjI 1);
   310 by (rtac conjI 1);
   311 by (rtac lam_type 1);
   311 by (rtac lam_type 1);
   312 by (resolve_tac prems 1);
   312 by (resolve_tac prems 1);
   313 by (rtac ballI 1);
   313 by (rtac ballI 1);
   314 by (asm_simp_tac (!simpset addsimps [nat_succI]) 1);
   314 by (asm_simp_tac (simpset() addsimps [nat_succI]) 1);
   315 brr(cpo_refl::prems) 1;
   315 brr(cpo_refl::prems) 1;
   316 qed "chain_const";
   316 qed "chain_const";
   317 
   317 
   318 goalw Limit.thy [islub_def,isub_def] (* islub_const *)
   318 goalw Limit.thy [islub_def,isub_def] (* islub_const *)
   319     "!!x D. [|x:set(D); cpo(D)|] ==> islub(D,(lam n:nat. x),x)";
   319     "!!x D. [|x:set(D); cpo(D)|] ==> islub(D,(lam n:nat. x),x)";
   335 (* Taking the suffix of chains has no effect on ub's.                   *) 
   335 (* Taking the suffix of chains has no effect on ub's.                   *) 
   336 (*----------------------------------------------------------------------*)
   336 (*----------------------------------------------------------------------*)
   337 
   337 
   338 val prems = goalw Limit.thy [isub_def,suffix_def]  (* isub_suffix *)
   338 val prems = goalw Limit.thy [isub_def,suffix_def]  (* isub_suffix *)
   339     "[|chain(D,X); cpo(D); n:nat|] ==> isub(D,suffix(X,n),x) <-> isub(D,X,x)";
   339     "[|chain(D,X); cpo(D); n:nat|] ==> isub(D,suffix(X,n),x) <-> isub(D,X,x)";
   340 by (simp_tac (!simpset addsimps prems) 1);
   340 by (simp_tac (simpset() addsimps prems) 1);
   341 by (safe_tac (!claset));
   341 by (safe_tac (claset()));
   342 by (dtac bspec 2);
   342 by (dtac bspec 2);
   343 by (assume_tac 3);      (* to instantiate unknowns properly *)
   343 by (assume_tac 3);      (* to instantiate unknowns properly *)
   344 by (rtac cpo_trans 1);
   344 by (rtac cpo_trans 1);
   345 by (rtac chain_rel_gen_add 2);
   345 by (rtac chain_rel_gen_add 2);
   346 by (dtac bspec 6);
   346 by (dtac bspec 6);
   348 brr(chain_in::add_type::prems) 1;
   348 brr(chain_in::add_type::prems) 1;
   349 qed "isub_suffix";
   349 qed "isub_suffix";
   350 
   350 
   351 val prems = goalw Limit.thy [islub_def]  (* islub_suffix *)
   351 val prems = goalw Limit.thy [islub_def]  (* islub_suffix *)
   352     "[|chain(D,X); cpo(D); n:nat|] ==> islub(D,suffix(X,n),x) <-> islub(D,X,x)";
   352     "[|chain(D,X); cpo(D); n:nat|] ==> islub(D,suffix(X,n),x) <-> islub(D,X,x)";
   353 by (asm_simp_tac (!simpset addsimps isub_suffix::prems) 1);
   353 by (asm_simp_tac (simpset() addsimps isub_suffix::prems) 1);
   354 qed "islub_suffix";
   354 qed "islub_suffix";
   355 
   355 
   356 val prems = goalw Limit.thy [lub_def]  (* lub_suffix *)
   356 val prems = goalw Limit.thy [lub_def]  (* lub_suffix *)
   357     "[|chain(D,X); cpo(D); n:nat|] ==> lub(D,suffix(X,n)) = lub(D,X)";
   357     "[|chain(D,X); cpo(D); n:nat|] ==> lub(D,suffix(X,n)) = lub(D,X)";
   358 by (asm_simp_tac (!simpset addsimps islub_suffix::prems) 1);
   358 by (asm_simp_tac (simpset() addsimps islub_suffix::prems) 1);
   359 qed "lub_suffix";
   359 qed "lub_suffix";
   360 
   360 
   361 (*----------------------------------------------------------------------*)
   361 (*----------------------------------------------------------------------*)
   362 (* Dominate and subchain.                                               *) 
   362 (* Dominate and subchain.                                               *) 
   363 (*----------------------------------------------------------------------*)
   363 (*----------------------------------------------------------------------*)
   436 (* Matrix.                                                              *) 
   436 (* Matrix.                                                              *) 
   437 (*----------------------------------------------------------------------*)
   437 (*----------------------------------------------------------------------*)
   438 
   438 
   439 val prems = goalw Limit.thy [matrix_def]  (* matrix_fun *)
   439 val prems = goalw Limit.thy [matrix_def]  (* matrix_fun *)
   440     "matrix(D,M) ==> M : nat -> (nat -> set(D))";
   440     "matrix(D,M) ==> M : nat -> (nat -> set(D))";
   441 by (simp_tac (!simpset addsimps prems) 1);
   441 by (simp_tac (simpset() addsimps prems) 1);
   442 qed "matrix_fun";
   442 qed "matrix_fun";
   443 
   443 
   444 val prems = goalw Limit.thy []  (* matrix_in_fun *)
   444 val prems = goalw Limit.thy []  (* matrix_in_fun *)
   445     "[|matrix(D,M); n:nat|] ==> M`n : nat -> set(D)";
   445     "[|matrix(D,M); n:nat|] ==> M`n : nat -> set(D)";
   446 by (rtac apply_type 1);
   446 by (rtac apply_type 1);
   453 by (REPEAT(resolve_tac(matrix_in_fun::prems) 1));
   453 by (REPEAT(resolve_tac(matrix_in_fun::prems) 1));
   454 qed "matrix_in";
   454 qed "matrix_in";
   455 
   455 
   456 val prems = goalw Limit.thy [matrix_def]  (* matrix_rel_1_0 *)
   456 val prems = goalw Limit.thy [matrix_def]  (* matrix_rel_1_0 *)
   457     "[|matrix(D,M); n:nat; m:nat|] ==> rel(D,M`n`m,M`succ(n)`m)";
   457     "[|matrix(D,M); n:nat; m:nat|] ==> rel(D,M`n`m,M`succ(n)`m)";
   458 by (simp_tac (!simpset addsimps prems) 1);
   458 by (simp_tac (simpset() addsimps prems) 1);
   459 qed "matrix_rel_1_0";
   459 qed "matrix_rel_1_0";
   460 
   460 
   461 val prems = goalw Limit.thy [matrix_def]  (* matrix_rel_0_1 *)
   461 val prems = goalw Limit.thy [matrix_def]  (* matrix_rel_0_1 *)
   462     "[|matrix(D,M); n:nat; m:nat|] ==> rel(D,M`n`m,M`n`succ(m))";
   462     "[|matrix(D,M); n:nat; m:nat|] ==> rel(D,M`n`m,M`n`succ(m))";
   463 by (simp_tac (!simpset addsimps prems) 1);
   463 by (simp_tac (simpset() addsimps prems) 1);
   464 qed "matrix_rel_0_1";
   464 qed "matrix_rel_0_1";
   465 
   465 
   466 val prems = goalw Limit.thy [matrix_def]  (* matrix_rel_1_1 *)
   466 val prems = goalw Limit.thy [matrix_def]  (* matrix_rel_1_1 *)
   467     "[|matrix(D,M); n:nat; m:nat|] ==> rel(D,M`n`m,M`succ(n)`succ(m))";
   467     "[|matrix(D,M); n:nat; m:nat|] ==> rel(D,M`n`m,M`succ(n)`succ(m))";
   468 by (simp_tac (!simpset addsimps prems) 1);
   468 by (simp_tac (simpset() addsimps prems) 1);
   469 qed "matrix_rel_1_1";
   469 qed "matrix_rel_1_1";
   470 
   470 
   471 val prems = goal Limit.thy  (* fun_swap *)
   471 val prems = goal Limit.thy  (* fun_swap *)
   472     "f:X->Y->Z ==> (lam y:Y. lam x:X. f`x`y):Y->X->Z";
   472     "f:X->Y->Z ==> (lam y:Y. lam x:X. f`x`y):Y->X->Z";
   473 by (rtac lam_type 1);
   473 by (rtac lam_type 1);
   477 by (REPEAT(ares_tac prems 1));
   477 by (REPEAT(ares_tac prems 1));
   478 qed "fun_swap";
   478 qed "fun_swap";
   479 
   479 
   480 val prems = goalw Limit.thy [matrix_def]  (* matrix_sym_axis *)
   480 val prems = goalw Limit.thy [matrix_def]  (* matrix_sym_axis *)
   481     "!!z. matrix(D,M) ==> matrix(D,lam m:nat. lam n:nat. M`n`m)";
   481     "!!z. matrix(D,M) ==> matrix(D,lam m:nat. lam n:nat. M`n`m)";
   482 by (Simp_tac 1 THEN safe_tac (!claset) THEN 
   482 by (Simp_tac 1 THEN safe_tac (claset()) THEN 
   483 REPEAT(asm_simp_tac (!simpset addsimps [fun_swap]) 1));
   483 REPEAT(asm_simp_tac (simpset() addsimps [fun_swap]) 1));
   484 qed "matrix_sym_axis";
   484 qed "matrix_sym_axis";
   485 
   485 
   486 val prems = goalw Limit.thy [chain_def]  (* matrix_chain_diag *)
   486 val prems = goalw Limit.thy [chain_def]  (* matrix_chain_diag *)
   487     "matrix(D,M) ==> chain(D,lam n:nat. M`n`n)";
   487     "matrix(D,M) ==> chain(D,lam n:nat. M`n`n)";
   488 by (safe_tac (!claset));
   488 by (safe_tac (claset()));
   489 by (rtac lam_type 1);
   489 by (rtac lam_type 1);
   490 by (rtac matrix_in 1);
   490 by (rtac matrix_in 1);
   491 by (REPEAT(ares_tac prems 1));
   491 by (REPEAT(ares_tac prems 1));
   492 by (Asm_simp_tac 1);
   492 by (Asm_simp_tac 1);
   493 by (rtac matrix_rel_1_1 1);
   493 by (rtac matrix_rel_1_1 1);
   494 by (REPEAT(ares_tac prems 1));
   494 by (REPEAT(ares_tac prems 1));
   495 qed "matrix_chain_diag";
   495 qed "matrix_chain_diag";
   496 
   496 
   497 val prems = goalw Limit.thy [chain_def]  (* matrix_chain_left *)
   497 val prems = goalw Limit.thy [chain_def]  (* matrix_chain_left *)
   498     "[|matrix(D,M); n:nat|] ==> chain(D,M`n)";
   498     "[|matrix(D,M); n:nat|] ==> chain(D,M`n)";
   499 by (safe_tac (!claset));
   499 by (safe_tac (claset()));
   500 by (rtac apply_type 1);
   500 by (rtac apply_type 1);
   501 by (rtac matrix_fun 1);
   501 by (rtac matrix_fun 1);
   502 by (REPEAT(ares_tac prems 1));
   502 by (REPEAT(ares_tac prems 1));
   503 by (rtac matrix_rel_0_1 1);
   503 by (rtac matrix_rel_0_1 1);
   504 by (REPEAT(ares_tac prems 1));
   504 by (REPEAT(ares_tac prems 1));
   505 qed "matrix_chain_left";
   505 qed "matrix_chain_left";
   506 
   506 
   507 val prems = goalw Limit.thy [chain_def]  (* matrix_chain_right *)
   507 val prems = goalw Limit.thy [chain_def]  (* matrix_chain_right *)
   508     "[|matrix(D,M); m:nat|] ==> chain(D,lam n:nat. M`n`m)";
   508     "[|matrix(D,M); m:nat|] ==> chain(D,lam n:nat. M`n`m)";
   509 by (safe_tac (!claset));
   509 by (safe_tac (claset()));
   510 by (asm_simp_tac(!simpset addsimps prems) 2);
   510 by (asm_simp_tac(simpset() addsimps prems) 2);
   511 brr(lam_type::matrix_in::matrix_rel_1_0::prems) 1;
   511 brr(lam_type::matrix_in::matrix_rel_1_0::prems) 1;
   512 qed "matrix_chain_right";
   512 qed "matrix_chain_right";
   513 
   513 
   514 val prems = goalw Limit.thy [matrix_def]  (* matrix_chainI *)
   514 val prems = goalw Limit.thy [matrix_def]  (* matrix_chainI *)
   515     "[|!!x. x:nat==>chain(D,M`x);  !!y. y:nat==>chain(D,lam x:nat. M`x`y);   \
   515     "[|!!x. x:nat==>chain(D,M`x);  !!y. y:nat==>chain(D,lam x:nat. M`x`y);   \
   516 \      M:nat->nat->set(D); cpo(D)|] ==> matrix(D,M)";
   516 \      M:nat->nat->set(D); cpo(D)|] ==> matrix(D,M)";
   517 by (safe_tac (!claset addSIs [ballI]));
   517 by (safe_tac (claset() addSIs [ballI]));
   518 by (cut_inst_tac[("y1","m"),("n","n")](hd(tl prems) RS chain_rel) 2);
   518 by (cut_inst_tac[("y1","m"),("n","n")](hd(tl prems) RS chain_rel) 2);
   519 by (Asm_full_simp_tac 4);
   519 by (Asm_full_simp_tac 4);
   520 by (rtac cpo_trans 5);
   520 by (rtac cpo_trans 5);
   521 by (cut_inst_tac[("y1","m"),("n","n")](hd(tl prems) RS chain_rel) 6);
   521 by (cut_inst_tac[("y1","m"),("n","n")](hd(tl prems) RS chain_rel) 6);
   522 by (Asm_full_simp_tac 8);
   522 by (Asm_full_simp_tac 8);
   535 
   535 
   536 val prems = goalw Limit.thy []  (* isub_lemma *)
   536 val prems = goalw Limit.thy []  (* isub_lemma *)
   537     "[|isub(D,(lam n:nat. M`n`n),y); matrix(D,M); cpo(D)|] ==>  \
   537     "[|isub(D,(lam n:nat. M`n`n),y); matrix(D,M); cpo(D)|] ==>  \
   538 \    isub(D,(lam n:nat. lub(D,lam m:nat. M`n`m)),y)";
   538 \    isub(D,(lam n:nat. lub(D,lam m:nat. M`n`m)),y)";
   539 by (rewtac isub_def);
   539 by (rewtac isub_def);
   540 by (safe_tac (!claset));
   540 by (safe_tac (claset()));
   541 by (rtac isubD1 1);
   541 by (rtac isubD1 1);
   542 by (resolve_tac prems 1);
   542 by (resolve_tac prems 1);
   543 by (Asm_simp_tac 1);
   543 by (Asm_simp_tac 1);
   544 by (cut_inst_tac[("a","n")](hd(tl prems) RS matrix_fun RS apply_type) 1);
   544 by (cut_inst_tac[("a","n")](hd(tl prems) RS matrix_fun RS apply_type) 1);
   545 by (assume_tac 1);
   545 by (assume_tac 1);
   549 by (rtac matrix_chain_left 1);
   549 by (rtac matrix_chain_left 1);
   550 by (resolve_tac prems 1);
   550 by (resolve_tac prems 1);
   551 by (assume_tac 1);
   551 by (assume_tac 1);
   552 by (resolve_tac prems 1);
   552 by (resolve_tac prems 1);
   553 by (rewtac isub_def);
   553 by (rewtac isub_def);
   554 by (safe_tac (!claset));
   554 by (safe_tac (claset()));
   555 by (rtac isubD1 1);
   555 by (rtac isubD1 1);
   556 by (resolve_tac prems 1);
   556 by (resolve_tac prems 1);
   557 by (cut_inst_tac[("P","n le na")]excluded_middle 1);
   557 by (cut_inst_tac[("P","n le na")]excluded_middle 1);
   558 by (safe_tac (!claset));
   558 by (safe_tac (claset()));
   559 by (rtac cpo_trans 1);
   559 by (rtac cpo_trans 1);
   560 by (resolve_tac prems 1);
   560 by (resolve_tac prems 1);
   561 by (rtac (not_le_iff_lt RS iffD1 RS leI RS chain_rel_gen) 1);
   561 by (rtac (not_le_iff_lt RS iffD1 RS leI RS chain_rel_gen) 1);
   562 by (assume_tac 3);
   562 by (assume_tac 3);
   563 by (REPEAT(ares_tac (nat_into_Ord::matrix_chain_left::prems) 1));
   563 by (REPEAT(ares_tac (nat_into_Ord::matrix_chain_left::prems) 1));
   573   ([chain_rel_gen,matrix_chain_right,matrix_in,isubD1]@prems) 1));
   573   ([chain_rel_gen,matrix_chain_right,matrix_in,isubD1]@prems) 1));
   574 qed "isub_lemma";
   574 qed "isub_lemma";
   575 
   575 
   576 val prems = goalw Limit.thy [chain_def]  (* matrix_chain_lub *)
   576 val prems = goalw Limit.thy [chain_def]  (* matrix_chain_lub *)
   577     "[|matrix(D,M); cpo(D)|] ==> chain(D,lam n:nat. lub(D,lam m:nat. M`n`m))";
   577     "[|matrix(D,M); cpo(D)|] ==> chain(D,lam n:nat. lub(D,lam m:nat. M`n`m))";
   578 by (safe_tac (!claset));
   578 by (safe_tac (claset()));
   579 by (rtac lam_type 1);
   579 by (rtac lam_type 1);
   580 by (rtac islub_in 1);
   580 by (rtac islub_in 1);
   581 by (rtac cpo_lub 1);
   581 by (rtac cpo_lub 1);
   582 by (resolve_tac prems 2);
   582 by (resolve_tac prems 2);
   583 by (Asm_simp_tac 2);
   583 by (Asm_simp_tac 2);
   585 by (rtac lam_type 1);
   585 by (rtac lam_type 1);
   586 by (REPEAT(ares_tac (matrix_in::prems) 1));
   586 by (REPEAT(ares_tac (matrix_in::prems) 1));
   587 by (Asm_simp_tac 1);
   587 by (Asm_simp_tac 1);
   588 by (rtac matrix_rel_0_1 1);
   588 by (rtac matrix_rel_0_1 1);
   589 by (REPEAT(ares_tac prems 1));
   589 by (REPEAT(ares_tac prems 1));
   590 by (asm_simp_tac (!simpset addsimps 
   590 by (asm_simp_tac (simpset() addsimps 
   591     [hd prems RS matrix_chain_left RS chain_fun RS eta]) 1);
   591     [hd prems RS matrix_chain_left RS chain_fun RS eta]) 1);
   592 by (rtac dominate_islub 1);
   592 by (rtac dominate_islub 1);
   593 by (rtac cpo_lub 3);
   593 by (rtac cpo_lub 3);
   594 by (rtac cpo_lub 2);
   594 by (rtac cpo_lub 2);
   595 by (rewtac dominate_def);
   595 by (rewtac dominate_def);
   611 by (rewtac dominate_def);
   611 by (rewtac dominate_def);
   612 by (rtac ballI 1);
   612 by (rtac ballI 1);
   613 by (rtac bexI 1);
   613 by (rtac bexI 1);
   614 by (assume_tac 2);
   614 by (assume_tac 2);
   615 by (Asm_simp_tac 1);
   615 by (Asm_simp_tac 1);
   616 by (asm_simp_tac (!simpset addsimps 
   616 by (asm_simp_tac (simpset() addsimps 
   617     [hd prems RS matrix_chain_left RS chain_fun RS eta]) 1);
   617     [hd prems RS matrix_chain_left RS chain_fun RS eta]) 1);
   618 by (rtac islub_ub 1);
   618 by (rtac islub_ub 1);
   619 by (rtac cpo_lub 1);
   619 by (rtac cpo_lub 1);
   620 by (REPEAT(ares_tac 
   620 by (REPEAT(ares_tac 
   621 (matrix_chain_left::matrix_chain_diag::chain_fun::matrix_chain_lub::prems) 1));
   621 (matrix_chain_left::matrix_chain_diag::chain_fun::matrix_chain_lub::prems) 1));
   635 
   635 
   636 val prems = goalw Limit.thy []  (* lub_matrix_diag *)
   636 val prems = goalw Limit.thy []  (* lub_matrix_diag *)
   637     "[|matrix(D,M); cpo(D)|] ==>  \
   637     "[|matrix(D,M); cpo(D)|] ==>  \
   638 \    lub(D,(lam n:nat. lub(D,lam m:nat. M`n`m))) =  \
   638 \    lub(D,(lam n:nat. lub(D,lam m:nat. M`n`m))) =  \
   639 \    lub(D,(lam n:nat. M`n`n))";
   639 \    lub(D,(lam n:nat. M`n`n))";
   640 by (simp_tac (!simpset addsimps [lemma1,lemma2]) 1);
   640 by (simp_tac (simpset() addsimps [lemma1,lemma2]) 1);
   641 by (rewtac islub_def);
   641 by (rewtac islub_def);
   642 by (simp_tac (!simpset addsimps [hd(tl prems) RS (hd prems RS isub_eq)]) 1);
   642 by (simp_tac (simpset() addsimps [hd(tl prems) RS (hd prems RS isub_eq)]) 1);
   643 qed "lub_matrix_diag";
   643 qed "lub_matrix_diag";
   644 
   644 
   645 val [matrix,cpo] = goalw Limit.thy []  (* lub_matrix_diag_sym *)
   645 val [matrix,cpo] = goalw Limit.thy []  (* lub_matrix_diag_sym *)
   646     "[|matrix(D,M); cpo(D)|] ==>  \
   646     "[|matrix(D,M); cpo(D)|] ==>  \
   647 \    lub(D,(lam m:nat. lub(D,lam n:nat. M`n`m))) =  \
   647 \    lub(D,(lam m:nat. lub(D,lam n:nat. M`n`m))) =  \
   656 
   656 
   657 val prems = goalw Limit.thy [mono_def]  (* monoI *)
   657 val prems = goalw Limit.thy [mono_def]  (* monoI *)
   658     "[|f:set(D)->set(E);   \
   658     "[|f:set(D)->set(E);   \
   659 \      !!x y. [|rel(D,x,y); x:set(D); y:set(D)|] ==> rel(E,f`x,f`y)|] ==>   \
   659 \      !!x y. [|rel(D,x,y); x:set(D); y:set(D)|] ==> rel(E,f`x,f`y)|] ==>   \
   660 \     f:mono(D,E)";
   660 \     f:mono(D,E)";
   661 by (fast_tac(!claset addSIs prems) 1);
   661 by (fast_tac(claset() addSIs prems) 1);
   662 qed "monoI";
   662 qed "monoI";
   663 
   663 
   664 val prems = goal Limit.thy
   664 val prems = goal Limit.thy
   665     "f:mono(D,E) ==> f:set(D)->set(E)";
   665     "f:mono(D,E) ==> f:set(D)->set(E)";
   666 by (rtac (rewrite_rule[mono_def](hd prems) RS CollectD1) 1);
   666 by (rtac (rewrite_rule[mono_def](hd prems) RS CollectD1) 1);
   681 val prems = goalw Limit.thy [cont_def,mono_def]  (* contI *)
   681 val prems = goalw Limit.thy [cont_def,mono_def]  (* contI *)
   682     "[|f:set(D)->set(E);   \
   682     "[|f:set(D)->set(E);   \
   683 \      !!x y. [|rel(D,x,y); x:set(D); y:set(D)|] ==> rel(E,f`x,f`y);   \
   683 \      !!x y. [|rel(D,x,y); x:set(D); y:set(D)|] ==> rel(E,f`x,f`y);   \
   684 \      !!X. chain(D,X) ==> f`lub(D,X) = lub(E,lam n:nat. f`(X`n))|] ==>   \
   684 \      !!X. chain(D,X) ==> f`lub(D,X) = lub(E,lam n:nat. f`(X`n))|] ==>   \
   685 \     f:cont(D,E)";
   685 \     f:cont(D,E)";
   686 by (fast_tac(!claset addSIs prems) 1);
   686 by (fast_tac(claset() addSIs prems) 1);
   687 qed "contI";
   687 qed "contI";
   688 
   688 
   689 val prems = goal Limit.thy 
   689 val prems = goal Limit.thy 
   690     "f:cont(D,E) ==> f:mono(D,E)";
   690     "f:cont(D,E) ==> f:mono(D,E)";
   691 by (rtac (rewrite_rule[cont_def](hd prems) RS CollectD1) 1);
   691 by (rtac (rewrite_rule[cont_def](hd prems) RS CollectD1) 1);
   720 
   720 
   721 val prems = goalw Limit.thy []  (* mono_chain *)
   721 val prems = goalw Limit.thy []  (* mono_chain *)
   722     "[|f:mono(D,E); chain(D,X)|] ==> chain(E,lam n:nat. f`(X`n))";
   722     "[|f:mono(D,E); chain(D,X)|] ==> chain(E,lam n:nat. f`(X`n))";
   723 by (rewtac chain_def);
   723 by (rewtac chain_def);
   724 by (Simp_tac 1);
   724 by (Simp_tac 1);
   725 by (safe_tac (!claset));
   725 by (safe_tac (claset()));
   726 by (rtac lam_type 1);
   726 by (rtac lam_type 1);
   727 by (rtac mono_map 1);
   727 by (rtac mono_map 1);
   728 by (resolve_tac prems 1);
   728 by (resolve_tac prems 1);
   729 by (rtac chain_in 1);
   729 by (rtac chain_in 1);
   730 by (REPEAT(ares_tac prems 1));
   730 by (REPEAT(ares_tac prems 1));
   765 
   765 
   766 val prems = goal Limit.thy
   766 val prems = goal Limit.thy
   767     "[|!!x. x:set(D) ==> rel(E,f`x,g`x); f:cont(D,E); g:cont(D,E)|] ==> \
   767     "[|!!x. x:set(D) ==> rel(E,f`x,g`x); f:cont(D,E); g:cont(D,E)|] ==> \
   768 \    rel(cf(D,E),f,g)";
   768 \    rel(cf(D,E),f,g)";
   769 by (rtac rel_I 1);
   769 by (rtac rel_I 1);
   770 by (simp_tac (!simpset addsimps [cf_def]) 1);
   770 by (simp_tac (simpset() addsimps [cf_def]) 1);
   771 by (safe_tac (!claset));
   771 by (safe_tac (claset()));
   772 brr prems 1;
   772 brr prems 1;
   773 qed "rel_cfI";
   773 qed "rel_cfI";
   774 
   774 
   775 val prems = goalw Limit.thy [rel_def,cf_def]
   775 val prems = goalw Limit.thy [rel_def,cf_def]
   776     "!!z. [|rel(cf(D,E),f,g); x:set(D)|] ==> rel(E,f`x,g`x)";
   776     "!!z. [|rel(cf(D,E),f,g); x:set(D)|] ==> rel(E,f`x,g`x)";
   843 by (Asm_simp_tac 1);
   843 by (Asm_simp_tac 1);
   844 by (REPEAT(ares_tac ((chain_in RS cf_cont RS cont_mono)::prems) 1));
   844 by (REPEAT(ares_tac ((chain_in RS cf_cont RS cont_mono)::prems) 1));
   845 by (REPEAT(ares_tac ((chain_cf RS chain_fun)::prems) 1));
   845 by (REPEAT(ares_tac ((chain_cf RS chain_fun)::prems) 1));
   846 by (stac beta 1);
   846 by (stac beta 1);
   847 by (REPEAT(ares_tac((cpo_lub RS islub_in)::prems) 1));
   847 by (REPEAT(ares_tac((cpo_lub RS islub_in)::prems) 1));
   848 by (asm_simp_tac(!simpset addsimps[hd prems RS chain_in RS cf_cont RS cont_lub]) 1);
   848 by (asm_simp_tac(simpset() addsimps[hd prems RS chain_in RS cf_cont RS cont_lub]) 1);
   849 by (forward_tac[hd prems RS matrix_lemma RS lub_matrix_diag]1);
   849 by (forward_tac[hd prems RS matrix_lemma RS lub_matrix_diag]1);
   850 brr prems 1;
   850 brr prems 1;
   851 by (Asm_full_simp_tac 1);
   851 by (Asm_full_simp_tac 1);
   852 by (asm_simp_tac(!simpset addsimps[chain_in RS beta]) 1);
   852 by (asm_simp_tac(simpset() addsimps[chain_in RS beta]) 1);
   853 by (dtac (hd prems RS matrix_lemma RS lub_matrix_diag_sym) 1);
   853 by (dtac (hd prems RS matrix_lemma RS lub_matrix_diag_sym) 1);
   854 brr prems 1;
   854 brr prems 1;
   855 by (Asm_full_simp_tac 1);
   855 by (Asm_full_simp_tac 1);
   856 qed "chain_cf_lub_cont";
   856 qed "chain_cf_lub_cont";
   857 
   857 
   918 val prems = goal Limit.thy  (* const_cont *)
   918 val prems = goal Limit.thy  (* const_cont *)
   919     "[|y:set(E); cpo(D); cpo(E)|] ==> (lam x:set(D).y) : cont(D,E)";
   919     "[|y:set(E); cpo(D); cpo(E)|] ==> (lam x:set(D).y) : cont(D,E)";
   920 by (rtac contI 1);
   920 by (rtac contI 1);
   921 by (Asm_simp_tac 2);
   921 by (Asm_simp_tac 2);
   922 brr(lam_type::cpo_refl::prems) 1;
   922 brr(lam_type::cpo_refl::prems) 1;
   923 by (asm_simp_tac(!simpset addsimps(chain_in::(cpo_lub RS islub_in)::
   923 by (asm_simp_tac(simpset() addsimps(chain_in::(cpo_lub RS islub_in)::
   924     lub_const::prems)) 1);
   924     lub_const::prems)) 1);
   925 qed "const_cont";
   925 qed "const_cont";
   926 
   926 
   927 val prems = goal Limit.thy  (* cf_least *)
   927 val prems = goal Limit.thy  (* cf_least *)
   928     "[|cpo(D); pcpo(E); y:cont(D,E)|]==>rel(cf(D,E),(lam x:set(D).bot(E)),y)";
   928     "[|cpo(D); pcpo(E); y:cont(D,E)|]==>rel(cf(D,E),(lam x:set(D).bot(E)),y)";
   949 (*----------------------------------------------------------------------*)
   949 (*----------------------------------------------------------------------*)
   950 (* Identity and composition.                                            *)
   950 (* Identity and composition.                                            *)
   951 (*----------------------------------------------------------------------*)
   951 (*----------------------------------------------------------------------*)
   952 
   952 
   953 val id_thm = prove_goalw Perm.thy [id_def] "x:X ==> (id(X)`x) = x"
   953 val id_thm = prove_goalw Perm.thy [id_def] "x:X ==> (id(X)`x) = x"
   954   (fn prems => [simp_tac(!simpset addsimps prems) 1]);
   954   (fn prems => [simp_tac(simpset() addsimps prems) 1]);
   955 
   955 
   956 val prems = goal Limit.thy  (* id_cont *)
   956 val prems = goal Limit.thy  (* id_cont *)
   957     "cpo(D) ==> id(set(D)):cont(D,D)";
   957     "cpo(D) ==> id(set(D)):cont(D,D)";
   958 by (rtac contI 1);
   958 by (rtac contI 1);
   959 by (rtac id_type 1);
   959 by (rtac id_type 1);
   960 by (asm_simp_tac (!simpset addsimps[id_thm]) 1);
   960 by (asm_simp_tac (simpset() addsimps[id_thm]) 1);
   961 by (asm_simp_tac(!simpset addsimps(id_thm::(cpo_lub RS islub_in)::
   961 by (asm_simp_tac(simpset() addsimps(id_thm::(cpo_lub RS islub_in)::
   962     chain_in::(chain_fun RS eta)::prems)) 1);
   962     chain_in::(chain_fun RS eta)::prems)) 1);
   963 qed "id_cont";
   963 qed "id_cont";
   964 
   964 
   965 val comp_cont_apply = cont_fun RSN(2,cont_fun RS comp_fun_apply);
   965 val comp_cont_apply = cont_fun RSN(2,cont_fun RS comp_fun_apply);
   966 
   966 
   973 by (rtac cont_mono 9); (* 15 subgoals *)
   973 by (rtac cont_mono 9); (* 15 subgoals *)
   974 brr(comp_fun::cont_fun::cont_map::prems) 1; (* proves all but the lub case *)
   974 brr(comp_fun::cont_fun::cont_map::prems) 1; (* proves all but the lub case *)
   975 by (stac comp_cont_apply 1);
   975 by (stac comp_cont_apply 1);
   976 by (stac cont_lub 4);
   976 by (stac cont_lub 4);
   977 by (stac cont_lub 6);
   977 by (stac cont_lub 6);
   978 by (asm_full_simp_tac(!simpset addsimps (* RS: new subgoals contain unknowns *)
   978 by (asm_full_simp_tac(simpset() addsimps (* RS: new subgoals contain unknowns *)
   979     [hd prems RS (hd(tl prems) RS comp_cont_apply),chain_in]) 8);
   979     [hd prems RS (hd(tl prems) RS comp_cont_apply),chain_in]) 8);
   980 brr((cpo_lub RS islub_in)::cont_chain::prems) 1;
   980 brr((cpo_lub RS islub_in)::cont_chain::prems) 1;
   981 qed "comp_pres_cont";
   981 qed "comp_pres_cont";
   982 
   982 
   983 val prems = goal Limit.thy  (* comp_mono *)
   983 val prems = goal Limit.thy  (* comp_mono *)
  1012 by (rtac fun_extension 1);
  1012 by (rtac fun_extension 1);
  1013 by (stac lub_cf 3);
  1013 by (stac lub_cf 3);
  1014 brr(comp_fun::(cf_cont RS cont_fun)::(cpo_lub RS islub_in)::cpo_cf::
  1014 brr(comp_fun::(cf_cont RS cont_fun)::(cpo_lub RS islub_in)::cpo_cf::
  1015     chain_cf_comp::prems) 1;
  1015     chain_cf_comp::prems) 1;
  1016 by (cut_facts_tac[hd prems,hd(tl prems)]1);
  1016 by (cut_facts_tac[hd prems,hd(tl prems)]1);
  1017 by (asm_simp_tac(!simpset addsimps((chain_in RS cf_cont RSN(3,chain_in RS 
  1017 by (asm_simp_tac(simpset() addsimps((chain_in RS cf_cont RSN(3,chain_in RS 
  1018     cf_cont RS comp_cont_apply))::(tl(tl prems)))) 1);
  1018     cf_cont RS comp_cont_apply))::(tl(tl prems)))) 1);
  1019 by (stac comp_cont_apply 1);
  1019 by (stac comp_cont_apply 1);
  1020 brr((cpo_lub RS islub_in RS cf_cont)::cpo_cf::prems) 1;
  1020 brr((cpo_lub RS islub_in RS cf_cont)::cpo_cf::prems) 1;
  1021 by (asm_simp_tac(!simpset addsimps(lub_cf::
  1021 by (asm_simp_tac(simpset() addsimps(lub_cf::
  1022  (hd(tl prems)RS chain_cf RSN(2,hd prems RS chain_in RS cf_cont RS cont_lub))::
  1022  (hd(tl prems)RS chain_cf RSN(2,hd prems RS chain_in RS cf_cont RS cont_lub))::
  1023  (hd(tl prems) RS chain_cf RS cpo_lub RS islub_in)::prems)) 1);
  1023  (hd(tl prems) RS chain_cf RS cpo_lub RS islub_in)::prems)) 1);
  1024 by (cut_inst_tac[("M","lam xa:nat. lam xb:nat. X`xa`(Y`xb`x)")]
  1024 by (cut_inst_tac[("M","lam xa:nat. lam xb:nat. X`xa`(Y`xb`x)")]
  1025    lub_matrix_diag 1);
  1025    lub_matrix_diag 1);
  1026 by (Asm_full_simp_tac 3);
  1026 by (Asm_full_simp_tac 3);
  1048 val prems = goalw Limit.thy [projpair_def]  (* projpairE *)
  1048 val prems = goalw Limit.thy [projpair_def]  (* projpairE *)
  1049     "[| projpair(D,E,e,p);   \
  1049     "[| projpair(D,E,e,p);   \
  1050 \       [| e:cont(D,E); p:cont(E,D); p O e = id(set(D));   \
  1050 \       [| e:cont(D,E); p:cont(E,D); p O e = id(set(D));   \
  1051 \          rel(cf(E,E))(e O p)(id(set(E)))|] ==> Q |] ==> Q";
  1051 \          rel(cf(E,E))(e O p)(id(set(E)))|] ==> Q |] ==> Q";
  1052 by (rtac (hd(tl prems)) 1);
  1052 by (rtac (hd(tl prems)) 1);
  1053 by (REPEAT(asm_simp_tac(!simpset addsimps[hd prems]) 1));
  1053 by (REPEAT(asm_simp_tac(simpset() addsimps[hd prems]) 1));
  1054 qed "projpairE";
  1054 qed "projpairE";
  1055 
  1055 
  1056 val prems = goal Limit.thy  (* projpair_e_cont *)
  1056 val prems = goal Limit.thy  (* projpair_e_cont *)
  1057     "projpair(D,E,e,p) ==> e:cont(D,E)";
  1057     "projpair(D,E,e,p) ==> e:cont(D,E)";
  1058 by (rtac projpairE 1);
  1058 by (rtac projpairE 1);
  1216 (* The identity embedding.                                              *)
  1216 (* The identity embedding.                                              *)
  1217 (*----------------------------------------------------------------------*)
  1217 (*----------------------------------------------------------------------*)
  1218 
  1218 
  1219 val prems = goalw Limit.thy [projpair_def]  (* projpair_id *)
  1219 val prems = goalw Limit.thy [projpair_def]  (* projpair_id *)
  1220     "cpo(D) ==> projpair(D,D,id(set(D)),id(set(D)))";
  1220     "cpo(D) ==> projpair(D,D,id(set(D)),id(set(D)))";
  1221 by (safe_tac (!claset));
  1221 by (safe_tac (claset()));
  1222 brr(id_cont::id_comp::id_type::prems) 1;
  1222 brr(id_cont::id_comp::id_type::prems) 1;
  1223 by (stac id_comp 1); (* Matches almost anything *)
  1223 by (stac id_comp 1); (* Matches almost anything *)
  1224 brr(id_cont::id_type::cpo_refl::cpo_cf::cont_cf::prems) 1;
  1224 brr(id_cont::id_type::cpo_refl::cpo_cf::cont_cf::prems) 1;
  1225 qed "projpair_id";
  1225 qed "projpair_id";
  1226 
  1226 
  1243 (* Proof in Isa/ZF: 23 lines (compared to 56: 60% reduction). *)
  1243 (* Proof in Isa/ZF: 23 lines (compared to 56: 60% reduction). *)
  1244 
  1244 
  1245 val prems = goalw Limit.thy [projpair_def]  (* lemma *)
  1245 val prems = goalw Limit.thy [projpair_def]  (* lemma *)
  1246     "[|emb(D,D',e); emb(D',E,e'); cpo(D); cpo(D'); cpo(E)|] ==>  \
  1246     "[|emb(D,D',e); emb(D',E,e'); cpo(D); cpo(D'); cpo(E)|] ==>  \
  1247 \    projpair(D,E,e' O e,(Rp(D,D',e)) O (Rp(D',E,e')))";
  1247 \    projpair(D,E,e' O e,(Rp(D,D',e)) O (Rp(D',E,e')))";
  1248 by (safe_tac (!claset));
  1248 by (safe_tac (claset()));
  1249 brr(comp_pres_cont::Rp_cont::emb_cont::prems) 1;
  1249 brr(comp_pres_cont::Rp_cont::emb_cont::prems) 1;
  1250 by (rtac (comp_assoc RS subst) 1);
  1250 by (rtac (comp_assoc RS subst) 1);
  1251 by (res_inst_tac[("t1","e'")](comp_assoc RS ssubst) 1);
  1251 by (res_inst_tac[("t1","e'")](comp_assoc RS ssubst) 1);
  1252 by (stac embRp_eq 1); (* Matches everything due to subst/ssubst. *)
  1252 by (stac embRp_eq 1); (* Matches everything due to subst/ssubst. *)
  1253 brr prems 1;
  1253 brr prems 1;
  1286 
  1286 
  1287 (* Proof with non-reflexive relation approach:
  1287 (* Proof with non-reflexive relation approach:
  1288 by (rtac CollectI 1);
  1288 by (rtac CollectI 1);
  1289 by (rtac domainI 1);
  1289 by (rtac domainI 1);
  1290 by (rtac CollectI 1);
  1290 by (rtac CollectI 1);
  1291 by (simp_tac(!simpset addsimps prems) 1);
  1291 by (simp_tac(simpset() addsimps prems) 1);
  1292 by (rtac (hd prems) 1);
  1292 by (rtac (hd prems) 1);
  1293 by (Simp_tac 1);
  1293 by (Simp_tac 1);
  1294 by (rtac ballI 1);
  1294 by (rtac ballI 1);
  1295 by (dtac ((hd prems) RS apply_type) 1);
  1295 by (dtac ((hd prems) RS apply_type) 1);
  1296 by (etac CollectE 1);
  1296 by (etac CollectE 1);
  1297 by (assume_tac 1);
  1297 by (assume_tac 1);
  1298 by (rtac rel_I 1);
  1298 by (rtac rel_I 1);
  1299 by (rtac CollectI 1);
  1299 by (rtac CollectI 1);
  1300 by (fast_tac(!claset addSIs prems) 1);
  1300 by (fast_tac(claset() addSIs prems) 1);
  1301 by (rtac ballI 1);
  1301 by (rtac ballI 1);
  1302 by (Simp_tac 1);
  1302 by (Simp_tac 1);
  1303 by (dtac ((hd prems) RS apply_type) 1);
  1303 by (dtac ((hd prems) RS apply_type) 1);
  1304 by (etac CollectE 1);
  1304 by (etac CollectE 1);
  1305 by (assume_tac 1);
  1305 by (assume_tac 1);
  1315 val prems = goalw Limit.thy [iprod_def] (* rel_iprodI *)
  1315 val prems = goalw Limit.thy [iprod_def] (* rel_iprodI *)
  1316     "[|!!n. n:nat ==> rel(DD`n,f`n,g`n); f:(PROD n:nat. set(DD`n));  \
  1316     "[|!!n. n:nat ==> rel(DD`n,f`n,g`n); f:(PROD n:nat. set(DD`n));  \
  1317 \      g:(PROD n:nat. set(DD`n))|] ==> rel(iprod(DD),f,g)";
  1317 \      g:(PROD n:nat. set(DD`n))|] ==> rel(iprod(DD),f,g)";
  1318 by (rtac rel_I 1);
  1318 by (rtac rel_I 1);
  1319 by (Simp_tac 1);
  1319 by (Simp_tac 1);
  1320 by (safe_tac (!claset));
  1320 by (safe_tac (claset()));
  1321 brr prems 1;
  1321 brr prems 1;
  1322 qed "rel_iprodI";
  1322 qed "rel_iprodI";
  1323 
  1323 
  1324 val prems = goalw Limit.thy [iprod_def] (* rel_iprodE *)
  1324 val prems = goalw Limit.thy [iprod_def] (* rel_iprodE *)
  1325     "[|rel(iprod(DD),f,g); n:nat|] ==> rel(DD`n,f`n,g`n)";
  1325     "[|rel(iprod(DD),f,g); n:nat|] ==> rel(DD`n,f`n,g`n)";
  1326 by (cut_facts_tac[hd prems RS rel_E]1);
  1326 by (cut_facts_tac[hd prems RS rel_E]1);
  1327 by (Asm_full_simp_tac 1);
  1327 by (Asm_full_simp_tac 1);
  1328 by (safe_tac (!claset));
  1328 by (safe_tac (claset()));
  1329 by (etac bspec 1);
  1329 by (etac bspec 1);
  1330 by (resolve_tac prems 1);
  1330 by (resolve_tac prems 1);
  1331 qed "rel_iprodE";
  1331 qed "rel_iprodE";
  1332 
  1332 
  1333 (* Some special theorems like dProdApIn_cpo and other `_cpo' 
  1333 (* Some special theorems like dProdApIn_cpo and other `_cpo' 
  1334    probably not needed in Isabelle, wait and see. *)
  1334    probably not needed in Isabelle, wait and see. *)
  1335 
  1335 
  1336 val prems = goalw Limit.thy [chain_def]  (* chain_iprod *)
  1336 val prems = goalw Limit.thy [chain_def]  (* chain_iprod *)
  1337     "[|chain(iprod(DD),X);  !!n. n:nat ==> cpo(DD`n); n:nat|] ==>  \
  1337     "[|chain(iprod(DD),X);  !!n. n:nat ==> cpo(DD`n); n:nat|] ==>  \
  1338 \    chain(DD`n,lam m:nat. X`m`n)";
  1338 \    chain(DD`n,lam m:nat. X`m`n)";
  1339 by (safe_tac (!claset));
  1339 by (safe_tac (claset()));
  1340 by (rtac lam_type 1);
  1340 by (rtac lam_type 1);
  1341 by (rtac apply_type 1);
  1341 by (rtac apply_type 1);
  1342 by (rtac iprodE 1);
  1342 by (rtac iprodE 1);
  1343 by (etac (hd prems RS conjunct1 RS apply_type) 1);
  1343 by (etac (hd prems RS conjunct1 RS apply_type) 1);
  1344 by (resolve_tac prems 1);
  1344 by (resolve_tac prems 1);
  1345 by (asm_simp_tac(!simpset addsimps prems) 1);
  1345 by (asm_simp_tac(simpset() addsimps prems) 1);
  1346 by (rtac rel_iprodE 1);
  1346 by (rtac rel_iprodE 1);
  1347 by (asm_simp_tac (!simpset addsimps prems) 1);
  1347 by (asm_simp_tac (simpset() addsimps prems) 1);
  1348 by (resolve_tac prems 1);
  1348 by (resolve_tac prems 1);
  1349 qed "chain_iprod";
  1349 qed "chain_iprod";
  1350 
  1350 
  1351 val prems = goalw Limit.thy [islub_def,isub_def]  (* islub_iprod *)
  1351 val prems = goalw Limit.thy [islub_def,isub_def]  (* islub_iprod *)
  1352     "[|chain(iprod(DD),X);  !!n. n:nat ==> cpo(DD`n)|] ==>   \
  1352     "[|chain(iprod(DD),X);  !!n. n:nat ==> cpo(DD`n)|] ==>   \
  1353 \    islub(iprod(DD),X,lam n:nat. lub(DD`n,lam m:nat. X`m`n))";
  1353 \    islub(iprod(DD),X,lam n:nat. lub(DD`n,lam m:nat. X`m`n))";
  1354 by (safe_tac (!claset));
  1354 by (safe_tac (claset()));
  1355 by (rtac iprodI 1);
  1355 by (rtac iprodI 1);
  1356 by (rtac lam_type 1); 
  1356 by (rtac lam_type 1); 
  1357 brr((chain_iprod RS cpo_lub RS islub_in)::prems) 1;
  1357 brr((chain_iprod RS cpo_lub RS islub_in)::prems) 1;
  1358 by (rtac rel_iprodI 1);
  1358 by (rtac rel_iprodI 1);
  1359 by (Asm_simp_tac 1);
  1359 by (Asm_simp_tac 1);
  1364 brr(iprodI::lam_type::(chain_iprod RS cpo_lub RS islub_in)::prems) 1;
  1364 brr(iprodI::lam_type::(chain_iprod RS cpo_lub RS islub_in)::prems) 1;
  1365 by (rtac rel_iprodI 1);
  1365 by (rtac rel_iprodI 1);
  1366 by (Asm_simp_tac 1);
  1366 by (Asm_simp_tac 1);
  1367 brr(islub_least::(chain_iprod RS cpo_lub)::prems) 1;
  1367 brr(islub_least::(chain_iprod RS cpo_lub)::prems) 1;
  1368 by (rewtac isub_def);
  1368 by (rewtac isub_def);
  1369 by (safe_tac (!claset));
  1369 by (safe_tac (claset()));
  1370 by (etac (iprodE RS apply_type) 1);
  1370 by (etac (iprodE RS apply_type) 1);
  1371 by (assume_tac 1);
  1371 by (assume_tac 1);
  1372 by (Asm_simp_tac 1);
  1372 by (Asm_simp_tac 1);
  1373 by (dtac bspec 1);
  1373 by (dtac bspec 1);
  1374 by (etac rel_iprodE 2);
  1374 by (etac rel_iprodE 2);
  1401 
  1401 
  1402 val prems = goalw Limit.thy [subcpo_def]  (* subcpoI *)
  1402 val prems = goalw Limit.thy [subcpo_def]  (* subcpoI *)
  1403     "[|set(D)<=set(E);  \
  1403     "[|set(D)<=set(E);  \
  1404 \      !!x y. [|x:set(D); y:set(D)|] ==> rel(D,x,y)<->rel(E,x,y);  \
  1404 \      !!x y. [|x:set(D); y:set(D)|] ==> rel(D,x,y)<->rel(E,x,y);  \
  1405 \      !!X. chain(D,X) ==> lub(E,X) : set(D)|] ==> subcpo(D,E)";
  1405 \      !!X. chain(D,X) ==> lub(E,X) : set(D)|] ==> subcpo(D,E)";
  1406 by (safe_tac (!claset));
  1406 by (safe_tac (claset()));
  1407 by (asm_full_simp_tac(!simpset addsimps prems) 2);
  1407 by (asm_full_simp_tac(simpset() addsimps prems) 2);
  1408 by (asm_simp_tac(!simpset addsimps prems) 2);
  1408 by (asm_simp_tac(simpset() addsimps prems) 2);
  1409 brr(prems@[subsetD]) 1;
  1409 brr(prems@[subsetD]) 1;
  1410 qed "subcpoI";
  1410 qed "subcpoI";
  1411 
  1411 
  1412 val subcpo_subset = prove_goalw Limit.thy [subcpo_def]  
  1412 val subcpo_subset = prove_goalw Limit.thy [subcpo_def]  
  1413     "!!x. subcpo(D,E) ==> set(D)<=set(E)"
  1413     "!!x. subcpo(D,E) ==> set(D)<=set(E)"
  1457 
  1457 
  1458 val prems = goal Limit.thy  (* subcpo_cpo *)
  1458 val prems = goal Limit.thy  (* subcpo_cpo *)
  1459     "[|subcpo(D,E); cpo(E)|] ==> cpo(D)";
  1459     "[|subcpo(D,E); cpo(E)|] ==> cpo(D)";
  1460 brr[cpoI,poI]1;
  1460 brr[cpoI,poI]1;
  1461 (* Changing the order of the assumptions, otherwise full_simp doesn't work. *)
  1461 (* Changing the order of the assumptions, otherwise full_simp doesn't work. *)
  1462 by (asm_full_simp_tac(!simpset addsimps[hd prems RS subcpo_rel_eq]) 1);
  1462 by (asm_full_simp_tac(simpset() addsimps[hd prems RS subcpo_rel_eq]) 1);
  1463 brr(cpo_refl::(hd prems RS subcpo_subset RS subsetD)::prems) 1;
  1463 brr(cpo_refl::(hd prems RS subcpo_subset RS subsetD)::prems) 1;
  1464 by (dtac (imp_refl RS mp) 1);
  1464 by (dtac (imp_refl RS mp) 1);
  1465 by (dtac (imp_refl RS mp) 1);
  1465 by (dtac (imp_refl RS mp) 1);
  1466 by (asm_full_simp_tac(!simpset addsimps[hd prems RS subcpo_rel_eq]) 1);
  1466 by (asm_full_simp_tac(simpset() addsimps[hd prems RS subcpo_rel_eq]) 1);
  1467 brr(cpo_trans::(hd prems RS subcpo_subset RS subsetD)::prems) 1;
  1467 brr(cpo_trans::(hd prems RS subcpo_subset RS subsetD)::prems) 1;
  1468 (* Changing the order of the assumptions, otherwise full_simp doesn't work. *)
  1468 (* Changing the order of the assumptions, otherwise full_simp doesn't work. *)
  1469 by (dtac (imp_refl RS mp) 1);
  1469 by (dtac (imp_refl RS mp) 1);
  1470 by (dtac (imp_refl RS mp) 1);
  1470 by (dtac (imp_refl RS mp) 1);
  1471 by (asm_full_simp_tac(!simpset addsimps[hd prems RS subcpo_rel_eq]) 1);
  1471 by (asm_full_simp_tac(simpset() addsimps[hd prems RS subcpo_rel_eq]) 1);
  1472 brr(cpo_antisym::(hd prems RS subcpo_subset RS subsetD)::prems) 1;
  1472 brr(cpo_antisym::(hd prems RS subcpo_subset RS subsetD)::prems) 1;
  1473 brr(islub_subcpo::prems) 1;
  1473 brr(islub_subcpo::prems) 1;
  1474 qed "subcpo_cpo";
  1474 qed "subcpo_cpo";
  1475 
  1475 
  1476 val prems = goal Limit.thy  (* lub_subcpo *)
  1476 val prems = goal Limit.thy  (* lub_subcpo *)
  1496 (* Now, work on subgoal 2 (and 3) to instantiate unknown. *)
  1496 (* Now, work on subgoal 2 (and 3) to instantiate unknown. *)
  1497 by (Simp_tac 2);
  1497 by (Simp_tac 2);
  1498 by (rtac conjI 2);
  1498 by (rtac conjI 2);
  1499 by (rtac conjI 3);
  1499 by (rtac conjI 3);
  1500 by (resolve_tac prems 3);
  1500 by (resolve_tac prems 3);
  1501 by (simp_tac(!simpset addsimps [rewrite_rule[set_def](hd prems)]) 1);
  1501 by (simp_tac(simpset() addsimps [rewrite_rule[set_def](hd prems)]) 1);
  1502 by (resolve_tac prems 1);
  1502 by (resolve_tac prems 1);
  1503 by (rtac cpo_refl 1);
  1503 by (rtac cpo_refl 1);
  1504 by (resolve_tac prems 1);
  1504 by (resolve_tac prems 1);
  1505 by (rtac rel_I 1);
  1505 by (rtac rel_I 1);
  1506 by (rtac CollectI 1);
  1506 by (rtac CollectI 1);
  1507 by (fast_tac(!claset addSIs [rewrite_rule[set_def](hd prems)]) 1);
  1507 by (fast_tac(claset() addSIs [rewrite_rule[set_def](hd prems)]) 1);
  1508 by (Simp_tac 1);
  1508 by (Simp_tac 1);
  1509 brr(conjI::cpo_refl::prems) 1;
  1509 brr(conjI::cpo_refl::prems) 1;
  1510 *)
  1510 *)
  1511 
  1511 
  1512 val prems = goalw Limit.thy [set_def,mkcpo_def]  (* mkcpoD1 *)
  1512 val prems = goalw Limit.thy [set_def,mkcpo_def]  (* mkcpoD1 *)
  1562 (*----------------------------------------------------------------------*)
  1562 (*----------------------------------------------------------------------*)
  1563 
  1563 
  1564 val prems = goalw Limit.thy [emb_chain_def]  (* emb_chainI *)
  1564 val prems = goalw Limit.thy [emb_chain_def]  (* emb_chainI *)
  1565     "[|!!n. n:nat ==> cpo(DD`n);   \
  1565     "[|!!n. n:nat ==> cpo(DD`n);   \
  1566 \      !!n. n:nat ==> emb(DD`n,DD`succ(n),ee`n)|] ==> emb_chain(DD,ee)";
  1566 \      !!n. n:nat ==> emb(DD`n,DD`succ(n),ee`n)|] ==> emb_chain(DD,ee)";
  1567 by (safe_tac (!claset));
  1567 by (safe_tac (claset()));
  1568 brr prems 1;
  1568 brr prems 1;
  1569 qed "emb_chainI";
  1569 qed "emb_chainI";
  1570 
  1570 
  1571 val emb_chain_cpo = prove_goalw Limit.thy [emb_chain_def] 
  1571 val emb_chain_cpo = prove_goalw Limit.thy [emb_chain_def] 
  1572     "!!x. [|emb_chain(DD,ee); n:nat|] ==> cpo(DD`n)"
  1572     "!!x. [|emb_chain(DD,ee); n:nat|] ==> cpo(DD`n)"
  1596 val Dinf_prod = DinfD1;
  1596 val Dinf_prod = DinfD1;
  1597 
  1597 
  1598 val prems = goalw Limit.thy [Dinf_def]  (* DinfD2 *)
  1598 val prems = goalw Limit.thy [Dinf_def]  (* DinfD2 *)
  1599     "[|x:set(Dinf(DD,ee)); n:nat|] ==>   \
  1599     "[|x:set(Dinf(DD,ee)); n:nat|] ==>   \
  1600 \    Rp(DD`n,DD`succ(n),ee`n)`(x`succ(n)) = x`n";
  1600 \    Rp(DD`n,DD`succ(n),ee`n)`(x`succ(n)) = x`n";
  1601 by (asm_simp_tac(!simpset addsimps[(hd prems RS mkcpoD2),hd(tl prems)]) 1);
  1601 by (asm_simp_tac(simpset() addsimps[(hd prems RS mkcpoD2),hd(tl prems)]) 1);
  1602 qed "DinfD2";
  1602 qed "DinfD2";
  1603 val Dinf_eq = DinfD2;
  1603 val Dinf_eq = DinfD2;
  1604 
  1604 
  1605 (* At first, rel_DinfI was stated too strongly, because rel_mkcpo was too:
  1605 (* At first, rel_DinfI was stated too strongly, because rel_mkcpo was too:
  1606 val prems = goalw Limit.thy [Dinf_def]  (* rel_DinfI *)
  1606 val prems = goalw Limit.thy [Dinf_def]  (* rel_DinfI *)
  1639 brr(chain_Dinf::(hd prems RS emb_chain_cpo)::[]) 1;
  1639 brr(chain_Dinf::(hd prems RS emb_chain_cpo)::[]) 1;
  1640 by (Asm_simp_tac 1);
  1640 by (Asm_simp_tac 1);
  1641 by (stac (Rp_cont RS cont_lub) 1);
  1641 by (stac (Rp_cont RS cont_lub) 1);
  1642 brr(emb_chain_cpo::emb_chain_emb::nat_succI::chain_iprod::chain_Dinf::prems) 1;
  1642 brr(emb_chain_cpo::emb_chain_emb::nat_succI::chain_iprod::chain_Dinf::prems) 1;
  1643 (* Useful simplification, ugly in HOL. *)
  1643 (* Useful simplification, ugly in HOL. *)
  1644 by (asm_simp_tac(!simpset addsimps(DinfD2::chain_in::[])) 1);
  1644 by (asm_simp_tac(simpset() addsimps(DinfD2::chain_in::[])) 1);
  1645 brr(cpo_iprod::emb_chain_cpo::prems) 1;
  1645 brr(cpo_iprod::emb_chain_cpo::prems) 1;
  1646 qed "subcpo_Dinf";
  1646 qed "subcpo_Dinf";
  1647 
  1647 
  1648 (* Simple example of existential reasoning in Isabelle versus HOL. *)
  1648 (* Simple example of existential reasoning in Isabelle versus HOL. *)
  1649 
  1649 
  1668 (* defined as eps(DD,ee,m,n), via e_less and e_gr.                      *)
  1668 (* defined as eps(DD,ee,m,n), via e_less and e_gr.                      *)
  1669 (*----------------------------------------------------------------------*)
  1669 (*----------------------------------------------------------------------*)
  1670 
  1670 
  1671 val prems = goalw Limit.thy [e_less_def]  (* e_less_eq *)
  1671 val prems = goalw Limit.thy [e_less_def]  (* e_less_eq *)
  1672     "!!x. m:nat ==> e_less(DD,ee,m,m) = id(set(DD`m))";
  1672     "!!x. m:nat ==> e_less(DD,ee,m,m) = id(set(DD`m))";
  1673 by (asm_simp_tac (!simpset addsimps[diff_self_eq_0]) 1);
  1673 by (asm_simp_tac (simpset() addsimps[diff_self_eq_0]) 1);
  1674 qed "e_less_eq";
  1674 qed "e_less_eq";
  1675  
  1675  
  1676 (* ARITH_CONV proves the following in HOL. Would like something similar 
  1676 (* ARITH_CONV proves the following in HOL. Would like something similar 
  1677    in Isabelle/ZF. *)
  1677    in Isabelle/ZF. *)
  1678 
  1678 
  1679 goal Arith.thy  (* lemma_succ_sub *)
  1679 goal Arith.thy  (* lemma_succ_sub *)
  1680     "!!z. [|n:nat; m:nat|] ==> succ(m#+n)#-m = succ(n)";
  1680     "!!z. [|n:nat; m:nat|] ==> succ(m#+n)#-m = succ(n)";
  1681 (*Uses add_succ_right the wrong way round!*)
  1681 (*Uses add_succ_right the wrong way round!*)
  1682 by (asm_simp_tac
  1682 by (asm_simp_tac
  1683     (simpset_of"Nat" addsimps [add_succ_right RS sym, diff_add_inverse]) 1);
  1683     (simpset_of Nat.thy addsimps [add_succ_right RS sym, diff_add_inverse]) 1);
  1684 val lemma_succ_sub = result();
  1684 val lemma_succ_sub = result();
  1685 
  1685 
  1686 val prems = goalw Limit.thy [e_less_def] (* e_less_add *)
  1686 val prems = goalw Limit.thy [e_less_def] (* e_less_add *)
  1687     "!!x. [|m:nat; k:nat|] ==>    \
  1687     "!!x. [|m:nat; k:nat|] ==>    \
  1688 \         e_less(DD,ee,m,succ(m#+k)) = (ee`(m#+k))O(e_less(DD,ee,m,m#+k))";
  1688 \         e_less(DD,ee,m,succ(m#+k)) = (ee`(m#+k))O(e_less(DD,ee,m,m#+k))";
  1689 by (asm_simp_tac (!simpset addsimps [lemma_succ_sub,diff_add_inverse]) 1);
  1689 by (asm_simp_tac (simpset() addsimps [lemma_succ_sub,diff_add_inverse]) 1);
  1690 qed "e_less_add";
  1690 qed "e_less_add";
  1691 
  1691 
  1692 (* Again, would like more theorems about arithmetic. *)
  1692 (* Again, would like more theorems about arithmetic. *)
  1693 (* Well, HOL has much better support and automation of natural numbers. *)
  1693 (* Well, HOL has much better support and automation of natural numbers. *)
  1694 
  1694 
  1695 val add1 = prove_goal Limit.thy
  1695 val add1 = prove_goal Limit.thy
  1696     "!!x. n:nat ==> succ(n) = n #+ 1"
  1696     "!!x. n:nat ==> succ(n) = n #+ 1"
  1697   (fn prems => 
  1697   (fn prems => 
  1698       [asm_simp_tac (!simpset addsimps[add_succ_right,add_0_right]) 1]);
  1698       [asm_simp_tac (simpset() addsimps[add_succ_right,add_0_right]) 1]);
  1699 
  1699 
  1700 val prems = goal Limit.thy  (* succ_sub1 *)
  1700 val prems = goal Limit.thy  (* succ_sub1 *)
  1701     "x:nat ==> 0 < x --> succ(x#-1)=x";
  1701     "x:nat ==> 0 < x --> succ(x#-1)=x";
  1702 by (res_inst_tac[("n","x")]nat_induct 1);
  1702 by (res_inst_tac[("n","x")]nat_induct 1);
  1703 by (resolve_tac prems 1);
  1703 by (resolve_tac prems 1);
  1704 by (Fast_tac 1);
  1704 by (Fast_tac 1);
  1705 by (safe_tac (!claset));
  1705 by (safe_tac (claset()));
  1706 by (Asm_simp_tac 1);
  1706 by (Asm_simp_tac 1);
  1707 by (Asm_simp_tac 1);
  1707 by (Asm_simp_tac 1);
  1708 qed "succ_sub1";
  1708 qed "succ_sub1";
  1709 
  1709 
  1710 val prems = goal Limit.thy (* succ_le_pos *)
  1710 val prems = goal Limit.thy (* succ_le_pos *)
  1711     "[|m:nat; k:nat|] ==> succ(m) le m #+ k --> 0 < k";
  1711     "[|m:nat; k:nat|] ==> succ(m) le m #+ k --> 0 < k";
  1712 by (res_inst_tac[("n","m")]nat_induct 1);
  1712 by (res_inst_tac[("n","m")]nat_induct 1);
  1713 by (resolve_tac prems 1);
  1713 by (resolve_tac prems 1);
  1714 by (rtac impI 1);
  1714 by (rtac impI 1);
  1715 by (asm_full_simp_tac(!simpset addsimps prems) 1);
  1715 by (asm_full_simp_tac(simpset() addsimps prems) 1);
  1716 by (safe_tac (!claset));
  1716 by (safe_tac (claset()));
  1717 by (asm_full_simp_tac(!simpset addsimps prems) 1); (* Surprise, surprise. *)
  1717 by (asm_full_simp_tac(simpset() addsimps prems) 1); (* Surprise, surprise. *)
  1718 qed "succ_le_pos";
  1718 qed "succ_le_pos";
  1719 
  1719 
  1720 goal Limit.thy  (* lemma_le_exists *)
  1720 goal Limit.thy  (* lemma_le_exists *)
  1721     "!!z. [|n:nat; m:nat|] ==> m le n --> (EX k:nat. n = m #+ k)";
  1721     "!!z. [|n:nat; m:nat|] ==> m le n --> (EX k:nat. n = m #+ k)";
  1722 by (res_inst_tac[("n","m")]nat_induct 1);
  1722 by (res_inst_tac[("n","m")]nat_induct 1);
  1723 by (assume_tac 1);
  1723 by (assume_tac 1);
  1724 by (safe_tac (!claset));
  1724 by (safe_tac (claset()));
  1725 by (rtac bexI 1);
  1725 by (rtac bexI 1);
  1726 by (rtac (add_0 RS sym) 1);
  1726 by (rtac (add_0 RS sym) 1);
  1727 by (assume_tac 1);
  1727 by (assume_tac 1);
  1728 by (Asm_full_simp_tac 1);
  1728 by (Asm_full_simp_tac 1);
  1729 (* Great, by luck I found le_cs. Such cs's and ss's should be documented. *)
  1729 (* Great, by luck I found le_cs. Such cs's and ss's should be documented. *)
  1730 by (fast_tac le_cs 1); 
  1730 by (fast_tac le_cs 1); 
  1731 by (asm_simp_tac
  1731 by (asm_simp_tac
  1732     (simpset_of"Nat" addsimps[add_succ, add_succ_right RS sym]) 1);
  1732     (simpset_of Nat.thy addsimps[add_succ, add_succ_right RS sym]) 1);
  1733 by (rtac bexI 1);
  1733 by (rtac bexI 1);
  1734 by (stac (succ_sub1 RS mp) 1);
  1734 by (stac (succ_sub1 RS mp) 1);
  1735 (* Instantiation. *)
  1735 (* Instantiation. *)
  1736 by (rtac refl 3);
  1736 by (rtac refl 3);
  1737 by (assume_tac 1);
  1737 by (assume_tac 1);
  1752 val prems = goal Limit.thy  (* e_less_le *)
  1752 val prems = goal Limit.thy  (* e_less_le *)
  1753     "[|m le n; m:nat; n:nat|] ==>   \
  1753     "[|m le n; m:nat; n:nat|] ==>   \
  1754 \    e_less(DD,ee,m,succ(n)) = ee`n O e_less(DD,ee,m,n)";
  1754 \    e_less(DD,ee,m,succ(n)) = ee`n O e_less(DD,ee,m,n)";
  1755 by (rtac le_exists 1);
  1755 by (rtac le_exists 1);
  1756 by (resolve_tac prems 1);
  1756 by (resolve_tac prems 1);
  1757 by (asm_simp_tac(!simpset addsimps(e_less_add::prems)) 1);
  1757 by (asm_simp_tac(simpset() addsimps(e_less_add::prems)) 1);
  1758 brr prems 1;
  1758 brr prems 1;
  1759 qed "e_less_le";
  1759 qed "e_less_le";
  1760 
  1760 
  1761 (* All theorems assume variables m and n are natural numbers. *)
  1761 (* All theorems assume variables m and n are natural numbers. *)
  1762 
  1762 
  1763 val prems = goal Limit.thy  (* e_less_succ *)
  1763 val prems = goal Limit.thy  (* e_less_succ *)
  1764     "m:nat ==> e_less(DD,ee,m,succ(m)) = ee`m O id(set(DD`m))";
  1764     "m:nat ==> e_less(DD,ee,m,succ(m)) = ee`m O id(set(DD`m))";
  1765 by (asm_simp_tac(!simpset addsimps(e_less_le::e_less_eq::prems)) 1);
  1765 by (asm_simp_tac(simpset() addsimps(e_less_le::e_less_eq::prems)) 1);
  1766 qed "e_less_succ";
  1766 qed "e_less_succ";
  1767 
  1767 
  1768 val prems = goal Limit.thy  (* e_less_succ_emb *)
  1768 val prems = goal Limit.thy  (* e_less_succ_emb *)
  1769     "[|!!n. n:nat ==> emb(DD`n,DD`succ(n),ee`n); m:nat|] ==>   \
  1769     "[|!!n. n:nat ==> emb(DD`n,DD`succ(n),ee`n); m:nat|] ==>   \
  1770 \    e_less(DD,ee,m,succ(m)) = ee`m";
  1770 \    e_less(DD,ee,m,succ(m)) = ee`m";
  1771 by (asm_simp_tac(!simpset addsimps(e_less_succ::prems)) 1);
  1771 by (asm_simp_tac(simpset() addsimps(e_less_succ::prems)) 1);
  1772 by (stac comp_id 1);
  1772 by (stac comp_id 1);
  1773 brr(emb_cont::cont_fun::refl::prems) 1;
  1773 brr(emb_cont::cont_fun::refl::prems) 1;
  1774 qed "e_less_succ_emb";
  1774 qed "e_less_succ_emb";
  1775 
  1775 
  1776 (* Compare this proof with the HOL one, here we do type checking. *)
  1776 (* Compare this proof with the HOL one, here we do type checking. *)
  1779 val prems = goal Limit.thy  (* emb_e_less_add *)
  1779 val prems = goal Limit.thy  (* emb_e_less_add *)
  1780     "[|emb_chain(DD,ee); m:nat; k:nat|] ==>   \
  1780     "[|emb_chain(DD,ee); m:nat; k:nat|] ==>   \
  1781 \    emb(DD`m,DD`(m#+k),e_less(DD,ee,m,m#+k))";
  1781 \    emb(DD`m,DD`(m#+k),e_less(DD,ee,m,m#+k))";
  1782 by (res_inst_tac[("n","k")]nat_induct 1);
  1782 by (res_inst_tac[("n","k")]nat_induct 1);
  1783 by (resolve_tac prems 1);
  1783 by (resolve_tac prems 1);
  1784 by (asm_simp_tac(!simpset addsimps(add_0_right::e_less_eq::prems)) 1);
  1784 by (asm_simp_tac(simpset() addsimps(add_0_right::e_less_eq::prems)) 1);
  1785 brr(emb_id::emb_chain_cpo::prems) 1;
  1785 brr(emb_id::emb_chain_cpo::prems) 1;
  1786 by (asm_simp_tac(!simpset addsimps(add_succ_right::e_less_add::prems)) 1);
  1786 by (asm_simp_tac(simpset() addsimps(add_succ_right::e_less_add::prems)) 1);
  1787 brr(emb_comp::emb_chain_emb::emb_chain_cpo::add_type::nat_succI::prems) 1;
  1787 brr(emb_comp::emb_chain_emb::emb_chain_cpo::add_type::nat_succI::prems) 1;
  1788 qed "emb_e_less_add";
  1788 qed "emb_e_less_add";
  1789 
  1789 
  1790 val prems = goal Limit.thy  (* emb_e_less *)
  1790 val prems = goal Limit.thy  (* emb_e_less *)
  1791     "[|m le n; emb_chain(DD,ee); m:nat; n:nat|] ==>   \
  1791     "[|m le n; emb_chain(DD,ee); m:nat; n:nat|] ==>   \
  1792 \    emb(DD`m,DD`n,e_less(DD,ee,m,n))";
  1792 \    emb(DD`m,DD`n,e_less(DD,ee,m,n))";
  1793 (* same proof as e_less_le *)
  1793 (* same proof as e_less_le *)
  1794 by (rtac le_exists 1);
  1794 by (rtac le_exists 1);
  1795 by (resolve_tac prems 1);
  1795 by (resolve_tac prems 1);
  1796 by (asm_simp_tac(!simpset addsimps(emb_e_less_add::prems)) 1);
  1796 by (asm_simp_tac(simpset() addsimps(emb_e_less_add::prems)) 1);
  1797 brr prems 1;
  1797 brr prems 1;
  1798 qed "emb_e_less";
  1798 qed "emb_e_less";
  1799 
  1799 
  1800 val comp_mono_eq = prove_goal Limit.thy
  1800 val comp_mono_eq = prove_goal Limit.thy
  1801     "!!z.[|f=f'; g=g'|] ==> f O g = f' O g'"
  1801     "!!z.[|f=f'; g=g'|] ==> f O g = f' O g'"
  1839 \    e_less(DD,ee,m,m#+k) = e_less(DD,ee,m#+n,m#+k) O e_less(DD,ee,m,m#+n)"
  1839 \    e_less(DD,ee,m,m#+k) = e_less(DD,ee,m#+n,m#+k) O e_less(DD,ee,m,m#+n)"
  1840   (fn prems => [trr((e_less_split_add_lemma RS mp)::prems) 1]);
  1840   (fn prems => [trr((e_less_split_add_lemma RS mp)::prems) 1]);
  1841 
  1841 
  1842 val prems = goalw Limit.thy [e_gr_def]  (* e_gr_eq *)
  1842 val prems = goalw Limit.thy [e_gr_def]  (* e_gr_eq *)
  1843     "!!x. m:nat ==> e_gr(DD,ee,m,m) = id(set(DD`m))";
  1843     "!!x. m:nat ==> e_gr(DD,ee,m,m) = id(set(DD`m))";
  1844 by (asm_simp_tac (!simpset addsimps[diff_self_eq_0]) 1);
  1844 by (asm_simp_tac (simpset() addsimps[diff_self_eq_0]) 1);
  1845 qed "e_gr_eq";
  1845 qed "e_gr_eq";
  1846 
  1846 
  1847 val prems = goalw Limit.thy [e_gr_def] (* e_gr_add *)
  1847 val prems = goalw Limit.thy [e_gr_def] (* e_gr_add *)
  1848     "!!x. [|n:nat; k:nat|] ==>    \
  1848     "!!x. [|n:nat; k:nat|] ==>    \
  1849 \         e_gr(DD,ee,succ(n#+k),n) =   \
  1849 \         e_gr(DD,ee,succ(n#+k),n) =   \
  1850 \         e_gr(DD,ee,n#+k,n) O Rp(DD`(n#+k),DD`succ(n#+k),ee`(n#+k))";
  1850 \         e_gr(DD,ee,n#+k,n) O Rp(DD`(n#+k),DD`succ(n#+k),ee`(n#+k))";
  1851 by (asm_simp_tac (!simpset addsimps [lemma_succ_sub,diff_add_inverse]) 1);
  1851 by (asm_simp_tac (simpset() addsimps [lemma_succ_sub,diff_add_inverse]) 1);
  1852 qed "e_gr_add";
  1852 qed "e_gr_add";
  1853 
  1853 
  1854 val prems = goal Limit.thy  (* e_gr_le *)
  1854 val prems = goal Limit.thy  (* e_gr_le *)
  1855     "[|n le m; m:nat; n:nat|] ==>   \
  1855     "[|n le m; m:nat; n:nat|] ==>   \
  1856 \    e_gr(DD,ee,succ(m),n) = e_gr(DD,ee,m,n) O Rp(DD`m,DD`succ(m),ee`m)";
  1856 \    e_gr(DD,ee,succ(m),n) = e_gr(DD,ee,m,n) O Rp(DD`m,DD`succ(m),ee`m)";
  1857 by (rtac le_exists 1);
  1857 by (rtac le_exists 1);
  1858 by (resolve_tac prems 1);
  1858 by (resolve_tac prems 1);
  1859 by (asm_simp_tac(!simpset addsimps(e_gr_add::prems)) 1);
  1859 by (asm_simp_tac(simpset() addsimps(e_gr_add::prems)) 1);
  1860 brr prems 1;
  1860 brr prems 1;
  1861 qed "e_gr_le";
  1861 qed "e_gr_le";
  1862 
  1862 
  1863 val prems = goal Limit.thy  (* e_gr_succ *)
  1863 val prems = goal Limit.thy  (* e_gr_succ *)
  1864     "m:nat ==>   \
  1864     "m:nat ==>   \
  1865 \    e_gr(DD,ee,succ(m),m) = id(set(DD`m)) O Rp(DD`m,DD`succ(m),ee`m)";
  1865 \    e_gr(DD,ee,succ(m),m) = id(set(DD`m)) O Rp(DD`m,DD`succ(m),ee`m)";
  1866 by (asm_simp_tac(!simpset addsimps(e_gr_le::e_gr_eq::prems)) 1);
  1866 by (asm_simp_tac(simpset() addsimps(e_gr_le::e_gr_eq::prems)) 1);
  1867 qed "e_gr_succ";
  1867 qed "e_gr_succ";
  1868 
  1868 
  1869 (* Cpo asm's due to THE uniqueness. *)
  1869 (* Cpo asm's due to THE uniqueness. *)
  1870 
  1870 
  1871 val prems = goal Limit.thy  (* e_gr_succ_emb *)
  1871 val prems = goal Limit.thy  (* e_gr_succ_emb *)
  1872     "[|emb_chain(DD,ee); m:nat|] ==>   \
  1872     "[|emb_chain(DD,ee); m:nat|] ==>   \
  1873 \    e_gr(DD,ee,succ(m),m) = Rp(DD`m,DD`succ(m),ee`m)";
  1873 \    e_gr(DD,ee,succ(m),m) = Rp(DD`m,DD`succ(m),ee`m)";
  1874 by (asm_simp_tac(!simpset addsimps(e_gr_succ::prems)) 1);
  1874 by (asm_simp_tac(simpset() addsimps(e_gr_succ::prems)) 1);
  1875 by (stac id_comp 1);
  1875 by (stac id_comp 1);
  1876 brr(Rp_cont::cont_fun::refl::emb_chain_cpo::emb_chain_emb::nat_succI::prems) 1;
  1876 brr(Rp_cont::cont_fun::refl::emb_chain_cpo::emb_chain_emb::nat_succI::prems) 1;
  1877 qed "e_gr_succ_emb";
  1877 qed "e_gr_succ_emb";
  1878 
  1878 
  1879 val prems = goal Limit.thy  (* e_gr_fun_add *)
  1879 val prems = goal Limit.thy  (* e_gr_fun_add *)
  1880     "[|emb_chain(DD,ee); n:nat; k:nat|] ==>   \
  1880     "[|emb_chain(DD,ee); n:nat; k:nat|] ==>   \
  1881 \    e_gr(DD,ee,n#+k,n): set(DD`(n#+k))->set(DD`n)";
  1881 \    e_gr(DD,ee,n#+k,n): set(DD`(n#+k))->set(DD`n)";
  1882 by (res_inst_tac[("n","k")]nat_induct 1);
  1882 by (res_inst_tac[("n","k")]nat_induct 1);
  1883 by (resolve_tac prems 1);
  1883 by (resolve_tac prems 1);
  1884 by (asm_simp_tac(!simpset addsimps(add_0_right::e_gr_eq::id_type::prems)) 1);
  1884 by (asm_simp_tac(simpset() addsimps(add_0_right::e_gr_eq::id_type::prems)) 1);
  1885 by (asm_simp_tac(!simpset addsimps(add_succ_right::e_gr_add::prems)) 1);
  1885 by (asm_simp_tac(simpset() addsimps(add_succ_right::e_gr_add::prems)) 1);
  1886 brr(comp_fun::Rp_cont::cont_fun::emb_chain_emb::emb_chain_cpo::add_type::
  1886 brr(comp_fun::Rp_cont::cont_fun::emb_chain_emb::emb_chain_cpo::add_type::
  1887     nat_succI::prems) 1;
  1887     nat_succI::prems) 1;
  1888 qed "e_gr_fun_add";
  1888 qed "e_gr_fun_add";
  1889 
  1889 
  1890 val prems = goal Limit.thy  (* e_gr_fun *)
  1890 val prems = goal Limit.thy  (* e_gr_fun *)
  1891     "[|n le m; emb_chain(DD,ee); m:nat; n:nat|] ==>   \
  1891     "[|n le m; emb_chain(DD,ee); m:nat; n:nat|] ==>   \
  1892 \    e_gr(DD,ee,m,n): set(DD`m)->set(DD`n)";
  1892 \    e_gr(DD,ee,m,n): set(DD`m)->set(DD`n)";
  1893 by (rtac le_exists 1);
  1893 by (rtac le_exists 1);
  1894 by (resolve_tac prems 1);
  1894 by (resolve_tac prems 1);
  1895 by (asm_simp_tac(!simpset addsimps(e_gr_fun_add::prems)) 1);
  1895 by (asm_simp_tac(simpset() addsimps(e_gr_fun_add::prems)) 1);
  1896 brr prems 1;
  1896 brr prems 1;
  1897 qed "e_gr_fun";
  1897 qed "e_gr_fun";
  1898 
  1898 
  1899 val prems = goal Limit.thy  (* e_gr_split_add_lemma *)
  1899 val prems = goal Limit.thy  (* e_gr_split_add_lemma *)
  1900     "[| emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==>  \
  1900     "[| emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==>  \
  1936 val prems = goal Limit.thy  (* e_gr_cont_lemma *)
  1936 val prems = goal Limit.thy  (* e_gr_cont_lemma *)
  1937     "[|emb_chain(DD,ee); m:nat; n:nat|] ==>   \
  1937     "[|emb_chain(DD,ee); m:nat; n:nat|] ==>   \
  1938 \    n le m --> e_gr(DD,ee,m,n):cont(DD`m,DD`n)";
  1938 \    n le m --> e_gr(DD,ee,m,n):cont(DD`m,DD`n)";
  1939 by (res_inst_tac[("n","m")]nat_induct 1);
  1939 by (res_inst_tac[("n","m")]nat_induct 1);
  1940 by (resolve_tac prems 1);
  1940 by (resolve_tac prems 1);
  1941 by (asm_full_simp_tac(!simpset addsimps
  1941 by (asm_full_simp_tac(simpset() addsimps
  1942     (le0_iff::e_gr_eq::nat_0I::prems)) 1);
  1942     (le0_iff::e_gr_eq::nat_0I::prems)) 1);
  1943 brr(impI::id_cont::emb_chain_cpo::nat_0I::prems) 1;
  1943 brr(impI::id_cont::emb_chain_cpo::nat_0I::prems) 1;
  1944 by (asm_full_simp_tac(!simpset addsimps[le_succ_iff]) 1);
  1944 by (asm_full_simp_tac(simpset() addsimps[le_succ_iff]) 1);
  1945 by (etac disjE 1);
  1945 by (etac disjE 1);
  1946 by (etac impE 1);
  1946 by (etac impE 1);
  1947 by (assume_tac 1);
  1947 by (assume_tac 1);
  1948 by (asm_simp_tac(!simpset addsimps(e_gr_le::prems)) 1);
  1948 by (asm_simp_tac(simpset() addsimps(e_gr_le::prems)) 1);
  1949 brr(comp_pres_cont::Rp_cont::emb_chain_cpo::emb_chain_emb::nat_succI::prems) 1;
  1949 brr(comp_pres_cont::Rp_cont::emb_chain_cpo::emb_chain_emb::nat_succI::prems) 1;
  1950 by (asm_simp_tac(!simpset addsimps(e_gr_eq::nat_succI::prems)) 1);
  1950 by (asm_simp_tac(simpset() addsimps(e_gr_eq::nat_succI::prems)) 1);
  1951 brr(id_cont::emb_chain_cpo::nat_succI::prems) 1;
  1951 brr(id_cont::emb_chain_cpo::nat_succI::prems) 1;
  1952 qed "e_gr_cont_lemma";
  1952 qed "e_gr_cont_lemma";
  1953 
  1953 
  1954 val prems = goal Limit.thy  (* e_gr_cont *)
  1954 val prems = goal Limit.thy  (* e_gr_cont *)
  1955     "[|n le m; emb_chain(DD,ee); m:nat; n:nat|] ==>   \
  1955     "[|n le m; emb_chain(DD,ee); m:nat; n:nat|] ==>   \
  1994 (* Use mp to prepare for induction. *)
  1994 (* Use mp to prepare for induction. *)
  1995 by (rtac mp 1);
  1995 by (rtac mp 1);
  1996 by (resolve_tac prems 2);
  1996 by (resolve_tac prems 2);
  1997 by (res_inst_tac[("n","k")]nat_induct 1);
  1997 by (res_inst_tac[("n","k")]nat_induct 1);
  1998 by (resolve_tac prems 1);
  1998 by (resolve_tac prems 1);
  1999 by (asm_full_simp_tac(!simpset addsimps
  1999 by (asm_full_simp_tac(simpset() addsimps
  2000     (add_0_right::e_gr_eq::e_less_eq::(id_type RS id_comp)::prems)) 1);
  2000     (add_0_right::e_gr_eq::e_less_eq::(id_type RS id_comp)::prems)) 1);
  2001 by (simp_tac(ZF_ss addsimps[le_succ_iff]) 1);
  2001 by (simp_tac(ZF_ss addsimps[le_succ_iff]) 1);
  2002 by (rtac impI 1);
  2002 by (rtac impI 1);
  2003 by (etac disjE 1);
  2003 by (etac disjE 1);
  2004 by (etac impE 1);
  2004 by (etac impE 1);
  2019 
  2019 
  2020 
  2020 
  2021 val prems = goalw Limit.thy [eps_def]  (* emb_eps *)
  2021 val prems = goalw Limit.thy [eps_def]  (* emb_eps *)
  2022     "[|m le n; emb_chain(DD,ee); m:nat; n:nat|] ==>   \
  2022     "[|m le n; emb_chain(DD,ee); m:nat; n:nat|] ==>   \
  2023 \    emb(DD`m,DD`n,eps(DD,ee,m,n))";
  2023 \    emb(DD`m,DD`n,eps(DD,ee,m,n))";
  2024 by (asm_simp_tac(!simpset addsimps prems) 1);
  2024 by (asm_simp_tac(simpset() addsimps prems) 1);
  2025 brr(emb_e_less::prems) 1;
  2025 brr(emb_e_less::prems) 1;
  2026 qed "emb_eps";
  2026 qed "emb_eps";
  2027 
  2027 
  2028 val prems = goalw Limit.thy [eps_def]  (* eps_fun *)
  2028 val prems = goalw Limit.thy [eps_def]  (* eps_fun *)
  2029     "[|emb_chain(DD,ee); m:nat; n:nat|] ==>   \
  2029     "[|emb_chain(DD,ee); m:nat; n:nat|] ==>   \
  2030 \    eps(DD,ee,m,n): set(DD`m)->set(DD`n)";
  2030 \    eps(DD,ee,m,n): set(DD`m)->set(DD`n)";
  2031 by (rtac (expand_if RS iffD2) 1);
  2031 by (rtac (expand_if RS iffD2) 1);
  2032 by (safe_tac (!claset));
  2032 by (safe_tac (claset()));
  2033 brr((e_less_cont RS cont_fun)::prems) 1;
  2033 brr((e_less_cont RS cont_fun)::prems) 1;
  2034 brr((not_le_iff_lt RS iffD1 RS leI)::e_gr_fun::nat_into_Ord::prems) 1;
  2034 brr((not_le_iff_lt RS iffD1 RS leI)::e_gr_fun::nat_into_Ord::prems) 1;
  2035 qed "eps_fun";
  2035 qed "eps_fun";
  2036 
  2036 
  2037 val eps_id = prove_goalw Limit.thy [eps_def]  
  2037 val eps_id = prove_goalw Limit.thy [eps_def]  
  2038     "n:nat ==> eps(DD,ee,n,n) = id(set(DD`n))"
  2038     "n:nat ==> eps(DD,ee,n,n) = id(set(DD`n))"
  2039   (fn prems => [simp_tac(!simpset addsimps(e_less_eq::nat_le_refl::prems)) 1]);
  2039   (fn prems => [simp_tac(simpset() addsimps(e_less_eq::nat_le_refl::prems)) 1]);
  2040 
  2040 
  2041 val eps_e_less_add = prove_goalw Limit.thy [eps_def]
  2041 val eps_e_less_add = prove_goalw Limit.thy [eps_def]
  2042     "[|m:nat; n:nat|] ==> eps(DD,ee,m,m#+n) = e_less(DD,ee,m,m#+n)"
  2042     "[|m:nat; n:nat|] ==> eps(DD,ee,m,m#+n) = e_less(DD,ee,m,m#+n)"
  2043   (fn prems => [simp_tac(!simpset addsimps(add_le_self::prems)) 1]);
  2043   (fn prems => [simp_tac(simpset() addsimps(add_le_self::prems)) 1]);
  2044 
  2044 
  2045 val eps_e_less = prove_goalw Limit.thy [eps_def]
  2045 val eps_e_less = prove_goalw Limit.thy [eps_def]
  2046     "[|m le n; m:nat; n:nat|] ==> eps(DD,ee,m,n) = e_less(DD,ee,m,n)"
  2046     "[|m le n; m:nat; n:nat|] ==> eps(DD,ee,m,n) = e_less(DD,ee,m,n)"
  2047   (fn prems => [simp_tac(!simpset addsimps prems) 1]);
  2047   (fn prems => [simp_tac(simpset() addsimps prems) 1]);
  2048 
  2048 
  2049 val shift_asm = imp_refl RS mp;
  2049 val shift_asm = imp_refl RS mp;
  2050 
  2050 
  2051 val prems = goalw Limit.thy [eps_def]  (* eps_e_gr_add *)
  2051 val prems = goalw Limit.thy [eps_def]  (* eps_e_gr_add *)
  2052     "[|n:nat; k:nat|] ==> eps(DD,ee,n#+k,n) = e_gr(DD,ee,n#+k,n)";
  2052     "[|n:nat; k:nat|] ==> eps(DD,ee,n#+k,n) = e_gr(DD,ee,n#+k,n)";
  2053 by (rtac (expand_if RS iffD2) 1);
  2053 by (rtac (expand_if RS iffD2) 1);
  2054 by (safe_tac (!claset));
  2054 by (safe_tac (claset()));
  2055 by (etac leE 1);
  2055 by (etac leE 1);
  2056 (* Must control rewriting by instantiating a variable. *)
  2056 (* Must control rewriting by instantiating a variable. *)
  2057 by (asm_full_simp_tac(!simpset addsimps
  2057 by (asm_full_simp_tac(simpset() addsimps
  2058      ((hd prems RS nat_into_Ord RS not_le_iff_lt RS iff_sym)::nat_into_Ord::
  2058      ((hd prems RS nat_into_Ord RS not_le_iff_lt RS iff_sym)::nat_into_Ord::
  2059       add_le_self::prems)) 1);
  2059       add_le_self::prems)) 1);
  2060 by (asm_simp_tac(!simpset addsimps(e_less_eq::e_gr_eq::prems)) 1);
  2060 by (asm_simp_tac(simpset() addsimps(e_less_eq::e_gr_eq::prems)) 1);
  2061 qed "eps_e_gr_add";
  2061 qed "eps_e_gr_add";
  2062 
  2062 
  2063 val prems = goalw Limit.thy []  (* eps_e_gr *)
  2063 val prems = goalw Limit.thy []  (* eps_e_gr *)
  2064     "[|n le m; m:nat; n:nat|] ==> eps(DD,ee,m,n) = e_gr(DD,ee,m,n)";
  2064     "[|n le m; m:nat; n:nat|] ==> eps(DD,ee,m,n) = e_gr(DD,ee,m,n)";
  2065 by (rtac le_exists 1);
  2065 by (rtac le_exists 1);
  2066 by (resolve_tac prems 1);
  2066 by (resolve_tac prems 1);
  2067 by (asm_simp_tac(!simpset addsimps(eps_e_gr_add::prems)) 1);
  2067 by (asm_simp_tac(simpset() addsimps(eps_e_gr_add::prems)) 1);
  2068 brr prems 1;
  2068 brr prems 1;
  2069 qed "eps_e_gr";
  2069 qed "eps_e_gr";
  2070 
  2070 
  2071 val prems = goal Limit.thy  (* eps_succ_ee *)
  2071 val prems = goal Limit.thy  (* eps_succ_ee *)
  2072     "[|!!n. n:nat ==> emb(DD`n,DD`succ(n),ee`n); m:nat|] ==>  \
  2072     "[|!!n. n:nat ==> emb(DD`n,DD`succ(n),ee`n); m:nat|] ==>  \
  2073 \    eps(DD,ee,m,succ(m)) = ee`m";
  2073 \    eps(DD,ee,m,succ(m)) = ee`m";
  2074 by (asm_simp_tac(!simpset addsimps(eps_e_less::le_succ_iff::e_less_succ_emb::
  2074 by (asm_simp_tac(simpset() addsimps(eps_e_less::le_succ_iff::e_less_succ_emb::
  2075    prems)) 1);
  2075    prems)) 1);
  2076 qed "eps_succ_ee";
  2076 qed "eps_succ_ee";
  2077 
  2077 
  2078 val prems = goal Limit.thy  (* eps_succ_Rp *)
  2078 val prems = goal Limit.thy  (* eps_succ_Rp *)
  2079     "[|emb_chain(DD,ee); m:nat|] ==>  \
  2079     "[|emb_chain(DD,ee); m:nat|] ==>  \
  2080 \    eps(DD,ee,succ(m),m) = Rp(DD`m,DD`succ(m),ee`m)";
  2080 \    eps(DD,ee,succ(m),m) = Rp(DD`m,DD`succ(m),ee`m)";
  2081 by (asm_simp_tac(!simpset addsimps(eps_e_gr::le_succ_iff::e_gr_succ_emb::
  2081 by (asm_simp_tac(simpset() addsimps(eps_e_gr::le_succ_iff::e_gr_succ_emb::
  2082    prems)) 1);
  2082    prems)) 1);
  2083 qed "eps_succ_Rp";
  2083 qed "eps_succ_Rp";
  2084 
  2084 
  2085 val prems = goal Limit.thy  (* eps_cont *)
  2085 val prems = goal Limit.thy  (* eps_cont *)
  2086     "[|emb_chain(DD,ee); m:nat; n:nat|] ==> eps(DD,ee,m,n): cont(DD`m,DD`n)";
  2086     "[|emb_chain(DD,ee); m:nat; n:nat|] ==> eps(DD,ee,m,n): cont(DD`m,DD`n)";
  2087 by (rtac nat_linear_le 1);
  2087 by (rtac nat_linear_le 1);
  2088 by (resolve_tac prems 1);
  2088 by (resolve_tac prems 1);
  2089 by (rtac (hd(rev prems)) 1);
  2089 by (rtac (hd(rev prems)) 1);
  2090 by (asm_simp_tac(!simpset addsimps(eps_e_less::e_less_cont::prems)) 1);
  2090 by (asm_simp_tac(simpset() addsimps(eps_e_less::e_less_cont::prems)) 1);
  2091 by (asm_simp_tac(!simpset addsimps(eps_e_gr::e_gr_cont::prems)) 1);
  2091 by (asm_simp_tac(simpset() addsimps(eps_e_gr::e_gr_cont::prems)) 1);
  2092 qed "eps_cont";
  2092 qed "eps_cont";
  2093 
  2093 
  2094 (* Theorems about splitting. *)
  2094 (* Theorems about splitting. *)
  2095 
  2095 
  2096 val prems = goal Limit.thy  (* eps_split_add_left *)
  2096 val prems = goal Limit.thy  (* eps_split_add_left *)
  2097     "[|n le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==>  \
  2097     "[|n le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==>  \
  2098 \    eps(DD,ee,m,m#+k) = eps(DD,ee,m#+n,m#+k) O eps(DD,ee,m,m#+n)";
  2098 \    eps(DD,ee,m,m#+k) = eps(DD,ee,m#+n,m#+k) O eps(DD,ee,m,m#+n)";
  2099 by (asm_simp_tac(!simpset addsimps 
  2099 by (asm_simp_tac(simpset() addsimps 
  2100     (eps_e_less::add_le_self::add_le_mono::prems)) 1);
  2100     (eps_e_less::add_le_self::add_le_mono::prems)) 1);
  2101 brr(e_less_split_add::prems) 1;
  2101 brr(e_less_split_add::prems) 1;
  2102 qed "eps_split_add_left";
  2102 qed "eps_split_add_left";
  2103 
  2103 
  2104 val prems = goal Limit.thy  (* eps_split_add_left_rev *)
  2104 val prems = goal Limit.thy  (* eps_split_add_left_rev *)
  2105     "[|n le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==>  \
  2105     "[|n le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==>  \
  2106 \    eps(DD,ee,m,m#+n) = eps(DD,ee,m#+k,m#+n) O eps(DD,ee,m,m#+k)";
  2106 \    eps(DD,ee,m,m#+n) = eps(DD,ee,m#+k,m#+n) O eps(DD,ee,m,m#+k)";
  2107 by (asm_simp_tac(!simpset addsimps 
  2107 by (asm_simp_tac(simpset() addsimps 
  2108     (eps_e_less_add::eps_e_gr::add_le_self::add_le_mono::prems)) 1);
  2108     (eps_e_less_add::eps_e_gr::add_le_self::add_le_mono::prems)) 1);
  2109 brr(e_less_e_gr_split_add::prems) 1;
  2109 brr(e_less_e_gr_split_add::prems) 1;
  2110 qed "eps_split_add_left_rev";
  2110 qed "eps_split_add_left_rev";
  2111 
  2111 
  2112 val prems = goal Limit.thy  (* eps_split_add_right *)
  2112 val prems = goal Limit.thy  (* eps_split_add_right *)
  2113     "[|m le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==>  \
  2113     "[|m le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==>  \
  2114 \    eps(DD,ee,n#+k,n) = eps(DD,ee,n#+m,n) O eps(DD,ee,n#+k,n#+m)";
  2114 \    eps(DD,ee,n#+k,n) = eps(DD,ee,n#+m,n) O eps(DD,ee,n#+k,n#+m)";
  2115 by (asm_simp_tac(!simpset addsimps 
  2115 by (asm_simp_tac(simpset() addsimps 
  2116     (eps_e_gr::add_le_self::add_le_mono::prems)) 1);
  2116     (eps_e_gr::add_le_self::add_le_mono::prems)) 1);
  2117 brr(e_gr_split_add::prems) 1;
  2117 brr(e_gr_split_add::prems) 1;
  2118 qed "eps_split_add_right";
  2118 qed "eps_split_add_right";
  2119 
  2119 
  2120 val prems = goal Limit.thy  (* eps_split_add_right_rev *)
  2120 val prems = goal Limit.thy  (* eps_split_add_right_rev *)
  2121     "[|m le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==>  \
  2121     "[|m le k; emb_chain(DD,ee); m:nat; n:nat; k:nat|] ==>  \
  2122 \    eps(DD,ee,n#+m,n) = eps(DD,ee,n#+k,n) O eps(DD,ee,n#+m,n#+k)";
  2122 \    eps(DD,ee,n#+m,n) = eps(DD,ee,n#+k,n) O eps(DD,ee,n#+m,n#+k)";
  2123 by (asm_simp_tac(!simpset addsimps 
  2123 by (asm_simp_tac(simpset() addsimps 
  2124     (eps_e_gr_add::eps_e_less::add_le_self::add_le_mono::prems)) 1);
  2124     (eps_e_gr_add::eps_e_less::add_le_self::add_le_mono::prems)) 1);
  2125 brr(e_gr_e_less_split_add::prems) 1;
  2125 brr(e_gr_e_less_split_add::prems) 1;
  2126 qed "eps_split_add_right_rev";
  2126 qed "eps_split_add_right_rev";
  2127 
  2127 
  2128 (* Arithmetic, little support in Isabelle/ZF. *)
  2128 (* Arithmetic, little support in Isabelle/ZF. *)
  2229    but since x le y is x<succ(y) simplification does too much with this thm. *)
  2229    but since x le y is x<succ(y) simplification does too much with this thm. *)
  2230 by (stac eps_split_right_le 1);
  2230 by (stac eps_split_right_le 1);
  2231 by (assume_tac 2);
  2231 by (assume_tac 2);
  2232 by (asm_simp_tac(ZF_ss addsimps [add1]) 1);
  2232 by (asm_simp_tac(ZF_ss addsimps [add1]) 1);
  2233 brr(add_le_self::nat_0I::nat_succI::prems) 1;
  2233 brr(add_le_self::nat_0I::nat_succI::prems) 1;
  2234 by (asm_simp_tac(!simpset addsimps(eps_succ_Rp::prems)) 1);
  2234 by (asm_simp_tac(simpset() addsimps(eps_succ_Rp::prems)) 1);
  2235 by (stac comp_fun_apply 1);
  2235 by (stac comp_fun_apply 1);
  2236 brr(eps_fun::nat_succI::(Rp_cont RS cont_fun)::emb_chain_emb::
  2236 brr(eps_fun::nat_succI::(Rp_cont RS cont_fun)::emb_chain_emb::
  2237     emb_chain_cpo::refl::prems) 1;
  2237     emb_chain_cpo::refl::prems) 1;
  2238 (* Now the second part of the proof. Slightly different than HOL. *)
  2238 (* Now the second part of the proof. Slightly different than HOL. *)
  2239 by (asm_simp_tac(!simpset addsimps(eps_e_less::nat_succI::prems)) 1);
  2239 by (asm_simp_tac(simpset() addsimps(eps_e_less::nat_succI::prems)) 1);
  2240 by (etac (le_iff RS iffD1 RS disjE) 1);
  2240 by (etac (le_iff RS iffD1 RS disjE) 1);
  2241 by (asm_simp_tac(!simpset addsimps(e_less_le::prems)) 1);
  2241 by (asm_simp_tac(simpset() addsimps(e_less_le::prems)) 1);
  2242 by (stac comp_fun_apply 1);
  2242 by (stac comp_fun_apply 1);
  2243 brr(e_less_cont::cont_fun::emb_chain_emb::emb_cont::prems) 1;
  2243 brr(e_less_cont::cont_fun::emb_chain_emb::emb_cont::prems) 1;
  2244 by (stac embRp_eq_thm 1);
  2244 by (stac embRp_eq_thm 1);
  2245 brr(emb_chain_emb::(e_less_cont RS cont_fun RS apply_type)::emb_chain_cpo::
  2245 brr(emb_chain_emb::(e_less_cont RS cont_fun RS apply_type)::emb_chain_cpo::
  2246     nat_succI::prems) 1;
  2246     nat_succI::prems) 1;
  2247 by (asm_simp_tac(!simpset addsimps(eps_e_less::prems)) 1);
  2247 by (asm_simp_tac(simpset() addsimps(eps_e_less::prems)) 1);
  2248 by (dtac shift_asm 1);
  2248 by (dtac shift_asm 1);
  2249 by (asm_full_simp_tac(!simpset addsimps(eps_succ_Rp::e_less_eq::id_apply::
  2249 by (asm_full_simp_tac(simpset() addsimps(eps_succ_Rp::e_less_eq::id_apply::
  2250    nat_succI::prems)) 1);
  2250    nat_succI::prems)) 1);
  2251 qed "rho_emb_fun";
  2251 qed "rho_emb_fun";
  2252 
  2252 
  2253 val rho_emb_apply1 = prove_goalw Limit.thy [rho_emb_def]
  2253 val rho_emb_apply1 = prove_goalw Limit.thy [rho_emb_def]
  2254     "!!z. x:set(DD`n) ==> rho_emb(DD,ee,n)`x = (lam m:nat. eps(DD,ee,n,m)`x)"
  2254     "!!z. x:set(DD`n) ==> rho_emb(DD,ee,n)`x = (lam m:nat. eps(DD,ee,n,m)`x)"
  2258     "!!z. [|x:set(DD`n); m:nat|] ==> rho_emb(DD,ee,n)`x`m = eps(DD,ee,n,m)`x"
  2258     "!!z. [|x:set(DD`n); m:nat|] ==> rho_emb(DD,ee,n)`x`m = eps(DD,ee,n,m)`x"
  2259   (fn prems => [Asm_simp_tac 1]);
  2259   (fn prems => [Asm_simp_tac 1]);
  2260 
  2260 
  2261 val rho_emb_id = prove_goal Limit.thy 
  2261 val rho_emb_id = prove_goal Limit.thy 
  2262   "!!z. [| x:set(DD`n); n:nat|] ==> rho_emb(DD,ee,n)`x`n = x"
  2262   "!!z. [| x:set(DD`n); n:nat|] ==> rho_emb(DD,ee,n)`x`n = x"
  2263   (fn prems => [asm_simp_tac(!simpset addsimps[rho_emb_apply2,eps_id,id_thm]) 1]);
  2263   (fn prems => [asm_simp_tac(simpset() addsimps[rho_emb_apply2,eps_id,id_thm]) 1]);
  2264 
  2264 
  2265 (* Shorter proof, 23 against 62. *)
  2265 (* Shorter proof, 23 against 62. *)
  2266 
  2266 
  2267 val prems = goalw Limit.thy [] (* rho_emb_cont *)
  2267 val prems = goalw Limit.thy [] (* rho_emb_cont *)
  2268     "[|emb_chain(DD,ee); n:nat|] ==>   \
  2268     "[|emb_chain(DD,ee); n:nat|] ==>   \
  2277 by (stac lub_Dinf 1);
  2277 by (stac lub_Dinf 1);
  2278 by (rtac chainI 1);
  2278 by (rtac chainI 1);
  2279 brr(lam_type::(rho_emb_fun RS apply_type)::chain_in::prems) 1;
  2279 brr(lam_type::(rho_emb_fun RS apply_type)::chain_in::prems) 1;
  2280 by (Asm_simp_tac 1);
  2280 by (Asm_simp_tac 1);
  2281 by (rtac rel_DinfI 1);
  2281 by (rtac rel_DinfI 1);
  2282 by (asm_simp_tac(!simpset addsimps (rho_emb_apply2::chain_in::[])) 1);
  2282 by (asm_simp_tac(simpset() addsimps (rho_emb_apply2::chain_in::[])) 1);
  2283 brr((eps_cont RS cont_mono)::chain_rel::Dinf_prod::
  2283 brr((eps_cont RS cont_mono)::chain_rel::Dinf_prod::
  2284     (rho_emb_fun RS apply_type)::chain_in::nat_succI::prems) 1;
  2284     (rho_emb_fun RS apply_type)::chain_in::nat_succI::prems) 1;
  2285 (* Now, back to the result of applying lub_Dinf *)
  2285 (* Now, back to the result of applying lub_Dinf *)
  2286 by (asm_simp_tac(!simpset addsimps (rho_emb_apply2::chain_in::[])) 1);
  2286 by (asm_simp_tac(simpset() addsimps (rho_emb_apply2::chain_in::[])) 1);
  2287 by (stac rho_emb_apply1 1);
  2287 by (stac rho_emb_apply1 1);
  2288 brr((cpo_lub RS islub_in)::emb_chain_cpo::prems) 1;
  2288 brr((cpo_lub RS islub_in)::emb_chain_cpo::prems) 1;
  2289 by (rtac fun_extension 1);
  2289 by (rtac fun_extension 1);
  2290 brr(lam_type::(eps_cont RS cont_fun RS apply_type)::(cpo_lub RS islub_in)::
  2290 brr(lam_type::(eps_cont RS cont_fun RS apply_type)::(cpo_lub RS islub_in)::
  2291     emb_chain_cpo::prems) 1;
  2291     emb_chain_cpo::prems) 1;
  2292 brr(cont_chain::eps_cont::emb_chain_cpo::prems) 1;
  2292 brr(cont_chain::eps_cont::emb_chain_cpo::prems) 1;
  2293 by (Asm_simp_tac 1);
  2293 by (Asm_simp_tac 1);
  2294 by (asm_simp_tac(!simpset addsimps((eps_cont RS cont_lub)::prems)) 1);
  2294 by (asm_simp_tac(simpset() addsimps((eps_cont RS cont_lub)::prems)) 1);
  2295 qed "rho_emb_cont";
  2295 qed "rho_emb_cont";
  2296 
  2296 
  2297 (* 32 vs 61, using safe_tac with imp in asm would be unfortunate (5steps) *)
  2297 (* 32 vs 61, using safe_tac with imp in asm would be unfortunate (5steps) *)
  2298 
  2298 
  2299 val prems = goalw Limit.thy [] (* lemma1 *)
  2299 val prems = goalw Limit.thy [] (* lemma1 *)
  2300     "[|m le n; emb_chain(DD,ee); x:set(Dinf(DD,ee)); m:nat; n:nat|] ==>   \
  2300     "[|m le n; emb_chain(DD,ee); x:set(Dinf(DD,ee)); m:nat; n:nat|] ==>   \
  2301 \    rel(DD`n,e_less(DD,ee,m,n)`(x`m),x`n)";
  2301 \    rel(DD`n,e_less(DD,ee,m,n)`(x`m),x`n)";
  2302 by (rtac impE 1 THEN atac 3 THEN rtac(hd prems) 2);  (* For induction proof *)
  2302 by (rtac impE 1 THEN atac 3 THEN rtac(hd prems) 2);  (* For induction proof *)
  2303 by (res_inst_tac[("n","n")]nat_induct 1);
  2303 by (res_inst_tac[("n","n")]nat_induct 1);
  2304 by (rtac impI 2);
  2304 by (rtac impI 2);
  2305 by (asm_full_simp_tac (!simpset addsimps (e_less_eq::prems)) 2);
  2305 by (asm_full_simp_tac (simpset() addsimps (e_less_eq::prems)) 2);
  2306 by (stac id_thm 2);
  2306 by (stac id_thm 2);
  2307 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_0I::prems) 1;
  2307 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_0I::prems) 1;
  2308 by (asm_full_simp_tac (!simpset addsimps [le_succ_iff]) 1);
  2308 by (asm_full_simp_tac (simpset() addsimps [le_succ_iff]) 1);
  2309 by (rtac impI 1);
  2309 by (rtac impI 1);
  2310 by (etac disjE 1);
  2310 by (etac disjE 1);
  2311 by (dtac mp 1 THEN atac 1);
  2311 by (dtac mp 1 THEN atac 1);
  2312 by (rtac cpo_trans 1);
  2312 by (rtac cpo_trans 1);
  2313 by (stac e_less_le 2);
  2313 by (stac e_less_le 2);
  2328 (* Dinf and cont_fun doesn't go well together, both Pi(_,%x._). *)
  2328 (* Dinf and cont_fun doesn't go well together, both Pi(_,%x._). *)
  2329 (* brr solves 11 of 12 subgoals *)
  2329 (* brr solves 11 of 12 subgoals *)
  2330 brr((hd(tl(tl prems)) RS Dinf_prod RS apply_type)::cont_fun::Rp_cont::
  2330 brr((hd(tl(tl prems)) RS Dinf_prod RS apply_type)::cont_fun::Rp_cont::
  2331     e_less_cont::emb_cont::emb_chain_emb::emb_chain_cpo::apply_type::
  2331     e_less_cont::emb_cont::emb_chain_emb::emb_chain_cpo::apply_type::
  2332     embRp_rel::(disjI1 RS (le_succ_iff RS iffD2))::nat_succI::prems) 1;
  2332     embRp_rel::(disjI1 RS (le_succ_iff RS iffD2))::nat_succI::prems) 1;
  2333 by (asm_full_simp_tac (!simpset addsimps (e_less_eq::prems)) 1);
  2333 by (asm_full_simp_tac (simpset() addsimps (e_less_eq::prems)) 1);
  2334 by (stac id_thm 1);
  2334 by (stac id_thm 1);
  2335 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_succI::prems) 1;
  2335 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_succI::prems) 1;
  2336 val lemma1 = result();
  2336 val lemma1 = result();
  2337 
  2337 
  2338 (* 18 vs 40 *)
  2338 (* 18 vs 40 *)
  2341     "[|n le m; emb_chain(DD,ee); x:set(Dinf(DD,ee)); m:nat; n:nat|] ==>   \
  2341     "[|n le m; emb_chain(DD,ee); x:set(Dinf(DD,ee)); m:nat; n:nat|] ==>   \
  2342 \    rel(DD`n,e_gr(DD,ee,m,n)`(x`m),x`n)";
  2342 \    rel(DD`n,e_gr(DD,ee,m,n)`(x`m),x`n)";
  2343 by (rtac impE 1 THEN atac 3 THEN rtac(hd prems) 2);  (* For induction proof *)
  2343 by (rtac impE 1 THEN atac 3 THEN rtac(hd prems) 2);  (* For induction proof *)
  2344 by (res_inst_tac[("n","m")]nat_induct 1);
  2344 by (res_inst_tac[("n","m")]nat_induct 1);
  2345 by (rtac impI 2);
  2345 by (rtac impI 2);
  2346 by (asm_full_simp_tac (!simpset addsimps (e_gr_eq::prems)) 2);
  2346 by (asm_full_simp_tac (simpset() addsimps (e_gr_eq::prems)) 2);
  2347 by (stac id_thm 2);
  2347 by (stac id_thm 2);
  2348 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_0I::prems) 1;
  2348 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_0I::prems) 1;
  2349 by (asm_full_simp_tac (!simpset addsimps [le_succ_iff]) 1);
  2349 by (asm_full_simp_tac (simpset() addsimps [le_succ_iff]) 1);
  2350 by (rtac impI 1);
  2350 by (rtac impI 1);
  2351 by (etac disjE 1);
  2351 by (etac disjE 1);
  2352 by (dtac mp 1 THEN atac 1);
  2352 by (dtac mp 1 THEN atac 1);
  2353 by (stac e_gr_le 1);
  2353 by (stac e_gr_le 1);
  2354 by (stac comp_fun_apply 4);
  2354 by (stac comp_fun_apply 4);
  2355 by (stac Dinf_eq 7);
  2355 by (stac Dinf_eq 7);
  2356 brr(emb_chain_emb::emb_chain_cpo::Rp_cont::e_gr_cont::cont_fun::emb_cont::
  2356 brr(emb_chain_emb::emb_chain_cpo::Rp_cont::e_gr_cont::cont_fun::emb_cont::
  2357     apply_type::Dinf_prod::nat_succI::prems) 1;
  2357     apply_type::Dinf_prod::nat_succI::prems) 1;
  2358 by (asm_full_simp_tac (!simpset addsimps (e_gr_eq::prems)) 1);
  2358 by (asm_full_simp_tac (simpset() addsimps (e_gr_eq::prems)) 1);
  2359 by (stac id_thm 1);
  2359 by (stac id_thm 1);
  2360 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_succI::prems) 1;
  2360 brr(apply_type::Dinf_prod::cpo_refl::emb_chain_cpo::nat_succI::prems) 1;
  2361 val lemma2 = result();
  2361 val lemma2 = result();
  2362 
  2362 
  2363 val prems = goalw Limit.thy [eps_def] (* eps1 *)
  2363 val prems = goalw Limit.thy [eps_def] (* eps1 *)
  2379 brr(lam_type::apply_type::Dinf_prod::prems) 1;
  2379 brr(lam_type::apply_type::Dinf_prod::prems) 1;
  2380 by (Asm_simp_tac 1);
  2380 by (Asm_simp_tac 1);
  2381 brr(rel_Dinf::prems) 1;
  2381 brr(rel_Dinf::prems) 1;
  2382 by (stac beta 1);
  2382 by (stac beta 1);
  2383 brr(cpo_Dinf::islub_in::cpo_lub::prems) 1;
  2383 brr(cpo_Dinf::islub_in::cpo_lub::prems) 1;
  2384 by (asm_simp_tac(!simpset addsimps(chain_in::lub_Dinf::prems)) 1);
  2384 by (asm_simp_tac(simpset() addsimps(chain_in::lub_Dinf::prems)) 1);
  2385 qed "lam_Dinf_cont";
  2385 qed "lam_Dinf_cont";
  2386 
  2386 
  2387 val prems = goalw Limit.thy  [rho_proj_def] (* rho_projpair *)
  2387 val prems = goalw Limit.thy  [rho_proj_def] (* rho_projpair *)
  2388     "[| emb_chain(DD,ee); n:nat |] ==> \
  2388     "[| emb_chain(DD,ee); n:nat |] ==> \
  2389 \    projpair(DD`n,Dinf(DD,ee),rho_emb(DD,ee,n),rho_proj(DD,ee,n))";
  2389 \    projpair(DD`n,Dinf(DD,ee),rho_emb(DD,ee,n),rho_proj(DD,ee,n))";
  2431 
  2431 
  2432 val prems = goalw Limit.thy [commute_def]  (* commuteI *)
  2432 val prems = goalw Limit.thy [commute_def]  (* commuteI *)
  2433   "[| !!n. n:nat ==> emb(DD`n,E,r(n));   \
  2433   "[| !!n. n:nat ==> emb(DD`n,E,r(n));   \
  2434 \     !!m n. [|m le n; m:nat; n:nat|] ==> r(n) O eps(DD,ee,m,n) = r(m) |] ==>  \
  2434 \     !!m n. [|m le n; m:nat; n:nat|] ==> r(n) O eps(DD,ee,m,n) = r(m) |] ==>  \
  2435 \  commute(DD,ee,E,r)";
  2435 \  commute(DD,ee,E,r)";
  2436 by (safe_tac (!claset));
  2436 by (safe_tac (claset()));
  2437 brr prems 1;
  2437 brr prems 1;
  2438 qed "commuteI";
  2438 qed "commuteI";
  2439 
  2439 
  2440 val prems = goalw Limit.thy [commute_def]  (* commute_emb *)
  2440 val prems = goalw Limit.thy [commute_def]  (* commute_emb *)
  2441   "!!z. [| commute(DD,ee,E,r); n:nat |] ==> emb(DD`n,E,r(n))";
  2441   "!!z. [| commute(DD,ee,E,r); n:nat |] ==> emb(DD`n,E,r(n))";
  2457 by (rtac fun_extension 1);       (* Manual instantiation in HOL. *)
  2457 by (rtac fun_extension 1);       (* Manual instantiation in HOL. *)
  2458 by (stac comp_fun_apply 3);
  2458 by (stac comp_fun_apply 3);
  2459 by (rtac fun_extension 6); (* Next, clean up and instantiate unknowns *)
  2459 by (rtac fun_extension 6); (* Next, clean up and instantiate unknowns *)
  2460 brr(comp_fun::rho_emb_fun::eps_fun::Dinf_prod::apply_type::prems) 1; 
  2460 brr(comp_fun::rho_emb_fun::eps_fun::Dinf_prod::apply_type::prems) 1; 
  2461 by (asm_simp_tac
  2461 by (asm_simp_tac
  2462     (!simpset addsimps(rho_emb_apply2::(eps_fun RS apply_type)::prems)) 1);
  2462     (simpset() addsimps(rho_emb_apply2::(eps_fun RS apply_type)::prems)) 1);
  2463 by (rtac (comp_fun_apply RS subst) 1);
  2463 by (rtac (comp_fun_apply RS subst) 1);
  2464 by (rtac (eps_split_left RS subst) 4);
  2464 by (rtac (eps_split_left RS subst) 4);
  2465 brr(eps_fun::refl::prems) 1;
  2465 brr(eps_fun::refl::prems) 1;
  2466 qed "rho_emb_commute";
  2466 qed "rho_emb_commute";
  2467 
  2467 
  2547 brr(cpo_lub::rho_emb_chain::cpo_cf::cpo_Dinf::isubI::cont_cf::id_cont::prems) 1;
  2547 brr(cpo_lub::rho_emb_chain::cpo_cf::cpo_Dinf::isubI::cont_cf::id_cont::prems) 1;
  2548 by (Asm_simp_tac 1);
  2548 by (Asm_simp_tac 1);
  2549 brr(embRp_rel::emb_rho_emb::emb_chain_cpo::cpo_Dinf::prems) 1;
  2549 brr(embRp_rel::emb_rho_emb::emb_chain_cpo::cpo_Dinf::prems) 1;
  2550 by (rtac rel_cfI 1);
  2550 by (rtac rel_cfI 1);
  2551 by (asm_simp_tac
  2551 by (asm_simp_tac
  2552     (!simpset addsimps(id_thm::lub_cf::rho_emb_chain::cpo_Dinf::prems)) 1);
  2552     (simpset() addsimps(id_thm::lub_cf::rho_emb_chain::cpo_Dinf::prems)) 1);
  2553 by (rtac rel_DinfI 1); (* Addtional assumptions *)
  2553 by (rtac rel_DinfI 1); (* Addtional assumptions *)
  2554 by (stac lub_Dinf 1);
  2554 by (stac lub_Dinf 1);
  2555 brr(rho_emb_chain_apply1::prems) 1;  
  2555 brr(rho_emb_chain_apply1::prems) 1;  
  2556 brr(Dinf_prod::(cpo_lub RS islub_in)::id_cont::cpo_Dinf::cpo_cf::cf_cont::
  2556 brr(Dinf_prod::(cpo_lub RS islub_in)::id_cont::cpo_Dinf::cpo_cf::cf_cont::
  2557     rho_emb_chain::rho_emb_chain_apply1::(id_cont RS cont_cf)::prems) 2;
  2557     rho_emb_chain::rho_emb_chain_apply1::(id_cont RS cont_cf)::prems) 2;
  2647 by (stac id_comp 4);
  2647 by (stac id_comp 4);
  2648 brr(cont_fun::Rp_cont::emb_r::emb_f::emb_chain_cpo::refl::prems) 1;
  2648 brr(cont_fun::Rp_cont::emb_r::emb_f::emb_chain_cpo::refl::prems) 1;
  2649 val lemma = result();
  2649 val lemma = result();
  2650 
  2650 
  2651 val lemma_assoc = prove_goal Limit.thy "a O b O c O d = a O (b O c) O d"
  2651 val lemma_assoc = prove_goal Limit.thy "a O b O c O d = a O (b O c) O d"
  2652   (fn prems => [simp_tac (!simpset addsimps[comp_assoc]) 1]);
  2652   (fn prems => [simp_tac (simpset() addsimps[comp_assoc]) 1]);
  2653 
  2653 
  2654 fun elem n l = if n = 1 then hd l else elem(n-1)(tl l);
  2654 fun elem n l = if n = 1 then hd l else elem(n-1)(tl l);
  2655 
  2655 
  2656 (* Shorter proof (but lemmas): 19 vs 79 (103 - 24, due to OAssoc)  *)
  2656 (* Shorter proof (but lemmas): 19 vs 79 (103 - 24, due to OAssoc)  *)
  2657 
  2657 
  2661 \     emb_chain(DD,ee); cpo(E); cpo(G) |] ==>  \  
  2661 \     emb_chain(DD,ee); cpo(E); cpo(G) |] ==>  \  
  2662 \  projpair   \
  2662 \  projpair   \
  2663 \   (E,G,   \
  2663 \   (E,G,   \
  2664 \    lub(cf(E,G), lam n:nat. f(n) O Rp(DD`n,E,r(n))),  \
  2664 \    lub(cf(E,G), lam n:nat. f(n) O Rp(DD`n,E,r(n))),  \
  2665 \    lub(cf(G,E), lam n:nat. r(n) O Rp(DD`n,G,f(n))))";
  2665 \    lub(cf(G,E), lam n:nat. r(n) O Rp(DD`n,G,f(n))))";
  2666 by (safe_tac (!claset));
  2666 by (safe_tac (claset()));
  2667 by (stac comp_lubs 3);
  2667 by (stac comp_lubs 3);
  2668 (* The following one line is 15 lines in HOL, and includes existentials. *)
  2668 (* The following one line is 15 lines in HOL, and includes existentials. *)
  2669 brr(cf_cont::islub_in::cpo_lub::cpo_cf::theta_chain::theta_proj_chain::prems) 1;
  2669 brr(cf_cont::islub_in::cpo_lub::cpo_cf::theta_chain::theta_proj_chain::prems) 1;
  2670 by (simp_tac (!simpset addsimps[comp_assoc]) 1);
  2670 by (simp_tac (simpset() addsimps[comp_assoc]) 1);
  2671 by (simp_tac (!simpset addsimps[(tl prems) MRS lemma]) 1);
  2671 by (simp_tac (simpset() addsimps[(tl prems) MRS lemma]) 1);
  2672 by (stac comp_lubs 2);
  2672 by (stac comp_lubs 2);
  2673 brr(cf_cont::islub_in::cpo_lub::cpo_cf::theta_chain::theta_proj_chain::prems) 1;
  2673 brr(cf_cont::islub_in::cpo_lub::cpo_cf::theta_chain::theta_proj_chain::prems) 1;
  2674 by (simp_tac (!simpset addsimps[comp_assoc]) 1);
  2674 by (simp_tac (simpset() addsimps[comp_assoc]) 1);
  2675 by (simp_tac (!simpset addsimps[
  2675 by (simp_tac (simpset() addsimps[
  2676    [elem 3 prems,elem 2 prems,elem 4 prems,elem 6 prems, elem 5 prems] 
  2676    [elem 3 prems,elem 2 prems,elem 4 prems,elem 6 prems, elem 5 prems] 
  2677    MRS lemma]) 1);
  2677    MRS lemma]) 1);
  2678 by (rtac dominate_islub 1);
  2678 by (rtac dominate_islub 1);
  2679 by (rtac cpo_lub 2);
  2679 by (rtac cpo_lub 2);
  2680 brr(commute_chain::emb_f::islub_const::cont_cf::id_cont::cpo_cf::
  2680 brr(commute_chain::emb_f::islub_const::cont_cf::id_cont::cpo_cf::
  2719 by (stac beta 3);
  2719 by (stac beta 3);
  2720 by (stac beta 4);
  2720 by (stac beta 4);
  2721 by (stac beta 5);
  2721 by (stac beta 5);
  2722 by (rtac lam_type 1);
  2722 by (rtac lam_type 1);
  2723 by (stac beta 1);
  2723 by (stac beta 1);
  2724 by (ALLGOALS(asm_simp_tac (!simpset addsimps prems)));
  2724 by (ALLGOALS(asm_simp_tac (simpset() addsimps prems)));
  2725 brr(lam_type::comp_pres_cont::Rp_cont::emb_cont::emb_r::emb_f::
  2725 brr(lam_type::comp_pres_cont::Rp_cont::emb_cont::emb_r::emb_f::
  2726     emb_chain_cpo::prems) 1;
  2726     emb_chain_cpo::prems) 1;
  2727 val lemma = result();
  2727 val lemma = result();
  2728 
  2728 
  2729 val prems = goal Limit.thy (* chain_lemma *)
  2729 val prems = goal Limit.thy (* chain_lemma *)
  2740 
  2740 
  2741 val prems = goalw Limit.thy [suffix_def] (* suffix_lemma *)
  2741 val prems = goalw Limit.thy [suffix_def] (* suffix_lemma *)
  2742   "[| commute(DD,ee,E,r); commute(DD,ee,G,f);   \
  2742   "[| commute(DD,ee,E,r); commute(DD,ee,G,f);   \
  2743 \     emb_chain(DD,ee); cpo(E); cpo(G); cpo(DD`x); x:nat |] ==>  \  
  2743 \     emb_chain(DD,ee); cpo(E); cpo(G); cpo(DD`x); x:nat |] ==>  \  
  2744 \  suffix(lam n:nat. (f(n) O Rp(DD`n,E,r(n))) O r(x),x) = (lam n:nat. f(x))";
  2744 \  suffix(lam n:nat. (f(n) O Rp(DD`n,E,r(n))) O r(x),x) = (lam n:nat. f(x))";
  2745 by (simp_tac (!simpset addsimps prems) 1);
  2745 by (simp_tac (simpset() addsimps prems) 1);
  2746 by (rtac fun_extension 1); 
  2746 by (rtac fun_extension 1); 
  2747 brr(lam_type::comp_fun::cont_fun::Rp_cont::emb_cont::emb_r::emb_f::
  2747 brr(lam_type::comp_fun::cont_fun::Rp_cont::emb_cont::emb_r::emb_f::
  2748     add_type::emb_chain_cpo::prems) 1;
  2748     add_type::emb_chain_cpo::prems) 1;
  2749 by (Asm_simp_tac 1);
  2749 by (Asm_simp_tac 1);
  2750 by (res_inst_tac[("r1","r"),("m1","x")](commute_eq RS subst) 1);
  2750 by (res_inst_tac[("r1","r"),("m1","x")](commute_eq RS subst) 1);
  2757 brr(emb_r::add_type::eps_fun::add_le_self::refl::emb_chain_cpo::prems) 1;
  2757 brr(emb_r::add_type::eps_fun::add_le_self::refl::emb_chain_cpo::prems) 1;
  2758 qed "suffix_lemma";
  2758 qed "suffix_lemma";
  2759 
  2759 
  2760 val mediatingI = prove_goalw Limit.thy [mediating_def]
  2760 val mediatingI = prove_goalw Limit.thy [mediating_def]
  2761   "[|emb(E,G,t);  !!n. n:nat ==> f(n) = t O r(n) |]==>mediating(E,G,r,f,t)"
  2761   "[|emb(E,G,t);  !!n. n:nat ==> f(n) = t O r(n) |]==>mediating(E,G,r,f,t)"
  2762  (fn prems => [safe_tac (!claset),trr prems 1]);
  2762  (fn prems => [safe_tac (claset()),trr prems 1]);
  2763 
  2763 
  2764 val mediating_emb = prove_goalw Limit.thy [mediating_def]
  2764 val mediating_emb = prove_goalw Limit.thy [mediating_def]
  2765   "!!z. mediating(E,G,r,f,t) ==> emb(E,G,t)"
  2765   "!!z. mediating(E,G,r,f,t) ==> emb(E,G,t)"
  2766  (fn prems => [Fast_tac 1]);
  2766  (fn prems => [Fast_tac 1]);
  2767 
  2767 
  2795 \  t = lub(cf(E,G), lam n:nat. f(n) O Rp(DD`n,E,r(n)))";
  2795 \  t = lub(cf(E,G), lam n:nat. f(n) O Rp(DD`n,E,r(n)))";
  2796 by (res_inst_tac[("b","t")](comp_id RS subst) 1);
  2796 by (res_inst_tac[("b","t")](comp_id RS subst) 1);
  2797 by (rtac (hd(tl prems) RS subst) 2);
  2797 by (rtac (hd(tl prems) RS subst) 2);
  2798 by (res_inst_tac[("b","t")](lub_const RS subst) 2);
  2798 by (res_inst_tac[("b","t")](lub_const RS subst) 2);
  2799 by (stac comp_lubs 4);
  2799 by (stac comp_lubs 4);
  2800 by (simp_tac (!simpset addsimps(comp_assoc::(hd prems RS mediating_eq)::prems)) 9);
  2800 by (simp_tac (simpset() addsimps(comp_assoc::(hd prems RS mediating_eq)::prems)) 9);
  2801 brr(cont_fun::emb_cont::mediating_emb::cont_cf::cpo_cf::chain_const::
  2801 brr(cont_fun::emb_cont::mediating_emb::cont_cf::cpo_cf::chain_const::
  2802     commute_chain::emb_chain_cpo::prems) 1;
  2802     commute_chain::emb_chain_cpo::prems) 1;
  2803 qed "lub_universal_unique";
  2803 qed "lub_universal_unique";
  2804 
  2804 
  2805 (*---------------------------------------------------------------------*)
  2805 (*---------------------------------------------------------------------*)
  2814 \    lub(cf(Dinf(DD,ee),G),   \
  2814 \    lub(cf(Dinf(DD,ee),G),   \
  2815 \        lam n:nat. f(n) O Rp(DD`n,Dinf(DD,ee),rho_emb(DD,ee,n)))) &  \
  2815 \        lam n:nat. f(n) O Rp(DD`n,Dinf(DD,ee),rho_emb(DD,ee,n)))) &  \
  2816 \  (ALL t. mediating(Dinf(DD,ee),G,rho_emb(DD,ee),f,t) -->  \
  2816 \  (ALL t. mediating(Dinf(DD,ee),G,rho_emb(DD,ee),f,t) -->  \
  2817 \    t = lub(cf(Dinf(DD,ee),G),   \
  2817 \    t = lub(cf(Dinf(DD,ee),G),   \
  2818 \        lam n:nat. f(n) O Rp(DD`n,Dinf(DD,ee),rho_emb(DD,ee,n))))";
  2818 \        lam n:nat. f(n) O Rp(DD`n,Dinf(DD,ee),rho_emb(DD,ee,n))))";
  2819 by (safe_tac (!claset));
  2819 by (safe_tac (claset()));
  2820 brr(lub_universal_mediating::rho_emb_commute::rho_emb_lub::cpo_Dinf::prems) 1;
  2820 brr(lub_universal_mediating::rho_emb_commute::rho_emb_lub::cpo_Dinf::prems) 1;
  2821 brr(lub_universal_unique::rho_emb_commute::rho_emb_lub::cpo_Dinf::prems) 1;
  2821 brr(lub_universal_unique::rho_emb_commute::rho_emb_lub::cpo_Dinf::prems) 1;
  2822 qed "Dinf_universal";
  2822 qed "Dinf_universal";
  2823 
  2823