src/ZF/Order.ML
changeset 437 435875e4b21d
parent 435 ca5356bd315a
child 467 92868dab2939
equal deleted inserted replaced
436:0cdc840297bb 437:435875e4b21d
     3     Author: 	Lawrence C Paulson, Cambridge University Computer Laboratory
     3     Author: 	Lawrence C Paulson, Cambridge University Computer Laboratory
     4     Copyright   1994  University of Cambridge
     4     Copyright   1994  University of Cambridge
     5 
     5 
     6 For Order.thy.  Orders in Zermelo-Fraenkel Set Theory 
     6 For Order.thy.  Orders in Zermelo-Fraenkel Set Theory 
     7 *)
     7 *)
     8 
       
     9 (*TO PURE/TACTIC.ML*)
       
    10 fun subgoals_tac sprops = EVERY' (map subgoal_tac sprops);
       
    11 
     8 
    12 
     9 
    13 open Order;
    10 open Order;
    14 
    11 
    15 val bij_apply_cs = ZF_cs addSEs [bij_converse_bij]
    12 val bij_apply_cs = ZF_cs addSEs [bij_converse_bij]
    42 val ord_iso_apply = result();
    39 val ord_iso_apply = result();
    43 
    40 
    44 goalw Order.thy [ord_iso_def] 
    41 goalw Order.thy [ord_iso_def] 
    45     "!!f. [| f: ord_iso(A,r,B,s);  <x,y>: s;  x:B;  y:B |] ==> \
    42     "!!f. [| f: ord_iso(A,r,B,s);  <x,y>: s;  x:B;  y:B |] ==> \
    46 \         <converse(f) ` x, converse(f) ` y> : r";
    43 \         <converse(f) ` x, converse(f) ` y> : r";
    47 be CollectE 1;
    44 by (etac CollectE 1);
    48 be (bspec RS bspec RS iffD2) 1;
    45 by (etac (bspec RS bspec RS iffD2) 1);
    49 by (REPEAT (eresolve_tac [asm_rl, 
    46 by (REPEAT (eresolve_tac [asm_rl, 
    50 			  bij_converse_bij RS bij_is_fun RS apply_type] 1));
    47 			  bij_converse_bij RS bij_is_fun RS apply_type] 1));
    51 by (asm_simp_tac (ZF_ss addsimps [right_inverse_bij]) 1);
    48 by (asm_simp_tac (ZF_ss addsimps [right_inverse_bij]) 1);
    52 val ord_iso_converse = result();
    49 val ord_iso_converse = result();
    53 
    50 
   140 
   137 
   141 (*Kunen's Lemma 6.2: Order-isomorphisms between well-orderings are unique*)
   138 (*Kunen's Lemma 6.2: Order-isomorphisms between well-orderings are unique*)
   142 goal Order.thy
   139 goal Order.thy
   143     "!!r. [| well_ord(A,r);  well_ord(B,s);  \
   140     "!!r. [| well_ord(A,r);  well_ord(B,s);  \
   144 \            f: ord_iso(A,r, B,s);  g: ord_iso(A,r, B,s) |] ==> f = g";
   141 \            f: ord_iso(A,r, B,s);  g: ord_iso(A,r, B,s) |] ==> f = g";
   145 br fun_extension 1;
   142 by (rtac fun_extension 1);
   146 be (ord_iso_is_bij RS bij_is_fun) 1;
   143 by (etac (ord_iso_is_bij RS bij_is_fun) 1);
   147 be (ord_iso_is_bij RS bij_is_fun) 1;
   144 by (etac (ord_iso_is_bij RS bij_is_fun) 1);
   148 br well_ord_iso_unique_lemma 1;
   145 by (rtac well_ord_iso_unique_lemma 1);
   149 by (REPEAT_SOME assume_tac);
   146 by (REPEAT_SOME assume_tac);
   150 val well_ord_iso_unique = result();
   147 val well_ord_iso_unique = result();
   151 
   148 
   152 
   149 
   153 goalw Order.thy [irrefl_def, part_ord_def, tot_ord_def, 
   150 goalw Order.thy [irrefl_def, part_ord_def, tot_ord_def, 
   155     "!!r. [| wf[A](r); linear(A,r) |] ==> well_ord(A,r)";
   152     "!!r. [| wf[A](r); linear(A,r) |] ==> well_ord(A,r)";
   156 by (asm_simp_tac (ZF_ss addsimps [wf_on_not_refl]) 1);
   153 by (asm_simp_tac (ZF_ss addsimps [wf_on_not_refl]) 1);
   157 by (safe_tac ZF_cs);
   154 by (safe_tac ZF_cs);
   158 by (linear_case_tac 1);
   155 by (linear_case_tac 1);
   159 (*case x=xb*)
   156 (*case x=xb*)
   160 by (fast_tac (ZF_cs addSEs [wf_on_anti_sym]) 1);
   157 by (fast_tac (ZF_cs addSEs [wf_on_asym]) 1);
   161 (*case x<xb*)
   158 (*case x<xb*)
   162 by (fast_tac (ZF_cs addSEs [wf_on_chain3]) 1);
   159 by (fast_tac (ZF_cs addSEs [wf_on_chain3]) 1);
   163 val well_ordI = result();
   160 val well_ordI = result();
   164 
   161 
   165 goalw Order.thy [well_ord_def]
   162 goalw Order.thy [well_ord_def]
   170 
   167 
   171 (*** Derived rules for pred(A,x,r) ***)
   168 (*** Derived rules for pred(A,x,r) ***)
   172 
   169 
   173 val [major,minor] = goalw Order.thy [pred_def]
   170 val [major,minor] = goalw Order.thy [pred_def]
   174     "[| y: pred(A,x,r);  [| y:A; <y,x>:r |] ==> P |] ==> P";
   171     "[| y: pred(A,x,r);  [| y:A; <y,x>:r |] ==> P |] ==> P";
   175 br (major RS CollectE) 1;
   172 by (rtac (major RS CollectE) 1);
   176 by (REPEAT (ares_tac [minor] 1));
   173 by (REPEAT (ares_tac [minor] 1));
   177 val predE = result();
   174 val predE = result();
   178 
   175 
   179 goalw Order.thy [pred_def] "pred(A,x,r) <= r -`` {x}";
   176 goalw Order.thy [pred_def] "pred(A,x,r) <= r -`` {x}";
   180 by (fast_tac ZF_cs 1);
   177 by (fast_tac ZF_cs 1);