src/ZF/OrderType.ML
changeset 4152 451104c223e2
parent 4091 771b1f6422a8
child 5067 62b6288e6005
equal deleted inserted replaced
4151:5c19cd418c33 4152:451104c223e2
   101            assume_tac (i+1),
   101            assume_tac (i+1),
   102            assume_tac i];
   102            assume_tac i];
   103 
   103 
   104 goalw OrderType.thy [well_ord_def, tot_ord_def, part_ord_def]
   104 goalw OrderType.thy [well_ord_def, tot_ord_def, part_ord_def]
   105     "!!r. [| well_ord(A,r);  x:A |] ==> Ord(ordermap(A,r) ` x)";
   105     "!!r. [| well_ord(A,r);  x:A |] ==> Ord(ordermap(A,r) ` x)";
   106 by (safe_tac (claset()));
   106 by Safe_tac;
   107 by (wf_on_ind_tac "x" [] 1);
   107 by (wf_on_ind_tac "x" [] 1);
   108 by (asm_simp_tac (simpset() addsimps [ordermap_pred_unfold]) 1);
   108 by (asm_simp_tac (simpset() addsimps [ordermap_pred_unfold]) 1);
   109 by (rtac (Ord_is_Transset RSN (2,OrdI)) 1);
   109 by (rtac (Ord_is_Transset RSN (2,OrdI)) 1);
   110 by (rewrite_goals_tac [pred_def,Transset_def]);
   110 by (rewrite_goals_tac [pred_def,Transset_def]);
   111 by (Blast_tac 2);
   111 by (Blast_tac 2);
   112 by (safe_tac (claset()));
   112 by Safe_tac;
   113 by (ordermap_elim_tac 1);
   113 by (ordermap_elim_tac 1);
   114 by (fast_tac (claset() addSEs [trans_onD]) 1);
   114 by (fast_tac (claset() addSEs [trans_onD]) 1);
   115 qed "Ord_ordermap";
   115 qed "Ord_ordermap";
   116 
   116 
   117 goalw OrderType.thy [ordertype_def]
   117 goalw OrderType.thy [ordertype_def]
   118     "!!r. well_ord(A,r) ==> Ord(ordertype(A,r))";
   118     "!!r. well_ord(A,r) ==> Ord(ordertype(A,r))";
   119 by (stac ([ordermap_type, subset_refl] MRS image_fun) 1);
   119 by (stac ([ordermap_type, subset_refl] MRS image_fun) 1);
   120 by (rtac (Ord_is_Transset RSN (2,OrdI)) 1);
   120 by (rtac (Ord_is_Transset RSN (2,OrdI)) 1);
   121 by (blast_tac (claset() addIs [Ord_ordermap]) 2);
   121 by (blast_tac (claset() addIs [Ord_ordermap]) 2);
   122 by (rewrite_goals_tac [Transset_def,well_ord_def]);
   122 by (rewrite_goals_tac [Transset_def,well_ord_def]);
   123 by (safe_tac (claset()));
   123 by Safe_tac;
   124 by (ordermap_elim_tac 1);
   124 by (ordermap_elim_tac 1);
   125 by (Blast_tac 1);
   125 by (Blast_tac 1);
   126 qed "Ord_ordertype";
   126 qed "Ord_ordertype";
   127 
   127 
   128 (*** ordermap preserves the orderings in both directions ***)
   128 (*** ordermap preserves the orderings in both directions ***)
   137 
   137 
   138 (*linearity of r is crucial here*)
   138 (*linearity of r is crucial here*)
   139 goalw OrderType.thy [well_ord_def, tot_ord_def]
   139 goalw OrderType.thy [well_ord_def, tot_ord_def]
   140     "!!r. [| ordermap(A,r)`w : ordermap(A,r)`x;  well_ord(A,r);  \
   140     "!!r. [| ordermap(A,r)`w : ordermap(A,r)`x;  well_ord(A,r);  \
   141 \            w: A; x: A |] ==> <w,x>: r";
   141 \            w: A; x: A |] ==> <w,x>: r";
   142 by (safe_tac (claset()));
   142 by Safe_tac;
   143 by (linear_case_tac 1);
   143 by (linear_case_tac 1);
   144 by (blast_tac (claset() addSEs [mem_not_refl RS notE]) 1);
   144 by (blast_tac (claset() addSEs [mem_not_refl RS notE]) 1);
   145 by (dtac ordermap_mono 1);
   145 by (dtac ordermap_mono 1);
   146 by (REPEAT_SOME assume_tac);
   146 by (REPEAT_SOME assume_tac);
   147 by (etac mem_asym 1);
   147 by (etac mem_asym 1);
   310 
   310 
   311 (** Addition with 0 **)
   311 (** Addition with 0 **)
   312 
   312 
   313 goal OrderType.thy "(lam z:A+0. case(%x. x, %y. y, z)) : bij(A+0, A)";
   313 goal OrderType.thy "(lam z:A+0. case(%x. x, %y. y, z)) : bij(A+0, A)";
   314 by (res_inst_tac [("d", "Inl")] lam_bijective 1);
   314 by (res_inst_tac [("d", "Inl")] lam_bijective 1);
   315 by (safe_tac (claset()));
   315 by Safe_tac;
   316 by (ALLGOALS Asm_simp_tac);
   316 by (ALLGOALS Asm_simp_tac);
   317 qed "bij_sum_0";
   317 qed "bij_sum_0";
   318 
   318 
   319 goal OrderType.thy
   319 goal OrderType.thy
   320  "!!A r. well_ord(A,r) ==> ordertype(A+0, radd(A,r,0,s)) = ordertype(A,r)";
   320  "!!A r. well_ord(A,r) ==> ordertype(A+0, radd(A,r,0,s)) = ordertype(A,r)";
   323 by (fast_tac (claset() addss (simpset() addsimps [radd_Inl_iff, Memrel_iff])) 1);
   323 by (fast_tac (claset() addss (simpset() addsimps [radd_Inl_iff, Memrel_iff])) 1);
   324 qed "ordertype_sum_0_eq";
   324 qed "ordertype_sum_0_eq";
   325 
   325 
   326 goal OrderType.thy "(lam z:0+A. case(%x. x, %y. y, z)) : bij(0+A, A)";
   326 goal OrderType.thy "(lam z:0+A. case(%x. x, %y. y, z)) : bij(0+A, A)";
   327 by (res_inst_tac [("d", "Inr")] lam_bijective 1);
   327 by (res_inst_tac [("d", "Inr")] lam_bijective 1);
   328 by (safe_tac (claset()));
   328 by Safe_tac;
   329 by (ALLGOALS Asm_simp_tac);
   329 by (ALLGOALS Asm_simp_tac);
   330 qed "bij_0_sum";
   330 qed "bij_0_sum";
   331 
   331 
   332 goal OrderType.thy
   332 goal OrderType.thy
   333  "!!A r. well_ord(A,r) ==> ordertype(0+A, radd(0,s,A,r)) = ordertype(A,r)";
   333  "!!A r. well_ord(A,r) ==> ordertype(0+A, radd(0,s,A,r)) = ordertype(A,r)";
   342 goalw OrderType.thy [pred_def]
   342 goalw OrderType.thy [pred_def]
   343  "!!A B. a:A ==>  \
   343  "!!A B. a:A ==>  \
   344 \        (lam x:pred(A,a,r). Inl(x))    \
   344 \        (lam x:pred(A,a,r). Inl(x))    \
   345 \        : bij(pred(A,a,r), pred(A+B, Inl(a), radd(A,r,B,s)))";
   345 \        : bij(pred(A,a,r), pred(A+B, Inl(a), radd(A,r,B,s)))";
   346 by (res_inst_tac [("d", "case(%x. x, %y. y)")] lam_bijective 1);
   346 by (res_inst_tac [("d", "case(%x. x, %y. y)")] lam_bijective 1);
   347 by (safe_tac (claset()));
   347 by Safe_tac;
   348 by (ALLGOALS
   348 by (ALLGOALS
   349     (asm_full_simp_tac 
   349     (asm_full_simp_tac 
   350      (simpset() addsimps [radd_Inl_iff, radd_Inr_Inl_iff])));
   350      (simpset() addsimps [radd_Inl_iff, radd_Inr_Inl_iff])));
   351 qed "pred_Inl_bij";
   351 qed "pred_Inl_bij";
   352 
   352 
   362 goalw OrderType.thy [pred_def, id_def]
   362 goalw OrderType.thy [pred_def, id_def]
   363  "!!A B. b:B ==>  \
   363  "!!A B. b:B ==>  \
   364 \        id(A+pred(B,b,s))      \
   364 \        id(A+pred(B,b,s))      \
   365 \        : bij(A+pred(B,b,s), pred(A+B, Inr(b), radd(A,r,B,s)))";
   365 \        : bij(A+pred(B,b,s), pred(A+B, Inr(b), radd(A,r,B,s)))";
   366 by (res_inst_tac [("d", "%z. z")] lam_bijective 1);
   366 by (res_inst_tac [("d", "%z. z")] lam_bijective 1);
   367 by (safe_tac (claset()));
   367 by Safe_tac;
   368 by (ALLGOALS (Asm_full_simp_tac));
   368 by (ALLGOALS (Asm_full_simp_tac));
   369 qed "pred_Inr_bij";
   369 qed "pred_Inr_bij";
   370 
   370 
   371 goal OrderType.thy
   371 goal OrderType.thy
   372  "!!A B. [| b:B;  well_ord(A,r);  well_ord(B,s) |] ==>  \
   372  "!!A B. [| b:B;  well_ord(A,r);  well_ord(B,s) |] ==>  \
   669 goalw OrderType.thy [pred_def]
   669 goalw OrderType.thy [pred_def]
   670  "!!A B. [| a:A;  b:B |] ==>                    \
   670  "!!A B. [| a:A;  b:B |] ==>                    \
   671 \        pred(A*B, <a,b>, rmult(A,r,B,s)) =     \
   671 \        pred(A*B, <a,b>, rmult(A,r,B,s)) =     \
   672 \        pred(A,a,r)*B Un ({a} * pred(B,b,s))";
   672 \        pred(A,a,r)*B Un ({a} * pred(B,b,s))";
   673 by (rtac equalityI 1);
   673 by (rtac equalityI 1);
   674 by (safe_tac (claset()));
   674 by Safe_tac;
   675 by (ALLGOALS (asm_full_simp_tac (simpset() addsimps [rmult_iff])));
   675 by (ALLGOALS (asm_full_simp_tac (simpset() addsimps [rmult_iff])));
   676 by (ALLGOALS (Blast_tac));
   676 by (ALLGOALS (Blast_tac));
   677 qed "pred_Pair_eq";
   677 qed "pred_Pair_eq";
   678 
   678 
   679 goal OrderType.thy
   679 goal OrderType.thy
   701 by (resolve_tac [id_bij RS ord_isoI RS ordertype_eq] 1);
   701 by (resolve_tac [id_bij RS ord_isoI RS ordertype_eq] 1);
   702 by (REPEAT_FIRST (eresolve_tac [SigmaE, sumE, ltE, ssubst]));
   702 by (REPEAT_FIRST (eresolve_tac [SigmaE, sumE, ltE, ssubst]));
   703 by (REPEAT_FIRST (ares_tac [well_ord_rmult, well_ord_radd, well_ord_Memrel, 
   703 by (REPEAT_FIRST (ares_tac [well_ord_rmult, well_ord_radd, well_ord_Memrel, 
   704                             Ord_ordertype]));
   704                             Ord_ordertype]));
   705 by (ALLGOALS (asm_simp_tac (simpset() addsimps [Memrel_iff])));
   705 by (ALLGOALS (asm_simp_tac (simpset() addsimps [Memrel_iff])));
   706 by (safe_tac (claset()));
   706 by Safe_tac;
   707 by (ALLGOALS (blast_tac (claset() addIs [Ord_trans])));
   707 by (ALLGOALS (blast_tac (claset() addIs [Ord_trans])));
   708 qed "ordertype_pred_Pair_lemma";
   708 qed "ordertype_pred_Pair_lemma";
   709 
   709 
   710 goalw OrderType.thy [omult_def]
   710 goalw OrderType.thy [omult_def]
   711  "!!i j. [| Ord(i);  Ord(j);  k<j**i |] ==>  \
   711  "!!i j. [| Ord(i);  Ord(j);  k<j**i |] ==>  \