src/ZF/Order.ML
changeset 4091 771b1f6422a8
parent 3736 39ee3d31cfbc
child 4152 451104c223e2
equal deleted inserted replaced
4090:9f1eaab75e8c 4091:771b1f6422a8
    36 (** General properties of well_ord **)
    36 (** General properties of well_ord **)
    37 
    37 
    38 goalw Order.thy [irrefl_def, part_ord_def, tot_ord_def, 
    38 goalw Order.thy [irrefl_def, part_ord_def, tot_ord_def, 
    39                  trans_on_def, well_ord_def]
    39                  trans_on_def, well_ord_def]
    40     "!!r. [| wf[A](r); linear(A,r) |] ==> well_ord(A,r)";
    40     "!!r. [| wf[A](r); linear(A,r) |] ==> well_ord(A,r)";
    41 by (asm_simp_tac (!simpset addsimps [wf_on_not_refl]) 1);
    41 by (asm_simp_tac (simpset() addsimps [wf_on_not_refl]) 1);
    42 by (fast_tac (!claset addEs [linearE, wf_on_asym, wf_on_chain3]) 1);
    42 by (fast_tac (claset() addEs [linearE, wf_on_asym, wf_on_chain3]) 1);
    43 qed "well_ordI";
    43 qed "well_ordI";
    44 
    44 
    45 goalw Order.thy [well_ord_def]
    45 goalw Order.thy [well_ord_def]
    46     "!!r. well_ord(A,r) ==> wf[A](r)";
    46     "!!r. well_ord(A,r) ==> wf[A](r)";
    47 by (safe_tac (!claset));
    47 by (safe_tac (claset()));
    48 qed "well_ord_is_wf";
    48 qed "well_ord_is_wf";
    49 
    49 
    50 goalw Order.thy [well_ord_def, tot_ord_def, part_ord_def]
    50 goalw Order.thy [well_ord_def, tot_ord_def, part_ord_def]
    51     "!!r. well_ord(A,r) ==> trans[A](r)";
    51     "!!r. well_ord(A,r) ==> trans[A](r)";
    52 by (safe_tac (!claset));
    52 by (safe_tac (claset()));
    53 qed "well_ord_is_trans_on";
    53 qed "well_ord_is_trans_on";
    54 
    54 
    55 goalw Order.thy [well_ord_def, tot_ord_def]
    55 goalw Order.thy [well_ord_def, tot_ord_def]
    56   "!!r. well_ord(A,r) ==> linear(A,r)";
    56   "!!r. well_ord(A,r) ==> linear(A,r)";
    57 by (Blast_tac 1);
    57 by (Blast_tac 1);
   106 by (Blast_tac 1);
   106 by (Blast_tac 1);
   107 qed "linear_subset";
   107 qed "linear_subset";
   108 
   108 
   109 goalw Order.thy [tot_ord_def]
   109 goalw Order.thy [tot_ord_def]
   110     "!!A B r. [| tot_ord(A,r);  B<=A |] ==> tot_ord(B,r)";
   110     "!!A B r. [| tot_ord(A,r);  B<=A |] ==> tot_ord(B,r)";
   111 by (fast_tac (!claset addSEs [part_ord_subset, linear_subset]) 1);
   111 by (fast_tac (claset() addSEs [part_ord_subset, linear_subset]) 1);
   112 qed "tot_ord_subset";
   112 qed "tot_ord_subset";
   113 
   113 
   114 goalw Order.thy [well_ord_def]
   114 goalw Order.thy [well_ord_def]
   115     "!!A B r. [| well_ord(A,r);  B<=A |] ==> well_ord(B,r)";
   115     "!!A B r. [| well_ord(A,r);  B<=A |] ==> well_ord(B,r)";
   116 by (fast_tac (!claset addSEs [tot_ord_subset, wf_on_subset_A]) 1);
   116 by (fast_tac (claset() addSEs [tot_ord_subset, wf_on_subset_A]) 1);
   117 qed "well_ord_subset";
   117 qed "well_ord_subset";
   118 
   118 
   119 
   119 
   120 (** Relations restricted to a smaller domain, by Krzysztof Grabczewski **)
   120 (** Relations restricted to a smaller domain, by Krzysztof Grabczewski **)
   121 
   121 
   126 goalw Order.thy [trans_on_def] "trans[A](r Int A*A) <-> trans[A](r)";
   126 goalw Order.thy [trans_on_def] "trans[A](r Int A*A) <-> trans[A](r)";
   127 by (Blast_tac 1);
   127 by (Blast_tac 1);
   128 qed "trans_on_Int_iff";
   128 qed "trans_on_Int_iff";
   129 
   129 
   130 goalw Order.thy [part_ord_def] "part_ord(A,r Int A*A) <-> part_ord(A,r)";
   130 goalw Order.thy [part_ord_def] "part_ord(A,r Int A*A) <-> part_ord(A,r)";
   131 by (simp_tac (!simpset addsimps [irrefl_Int_iff, trans_on_Int_iff]) 1);
   131 by (simp_tac (simpset() addsimps [irrefl_Int_iff, trans_on_Int_iff]) 1);
   132 qed "part_ord_Int_iff";
   132 qed "part_ord_Int_iff";
   133 
   133 
   134 goalw Order.thy [linear_def] "linear(A,r Int A*A) <-> linear(A,r)";
   134 goalw Order.thy [linear_def] "linear(A,r Int A*A) <-> linear(A,r)";
   135 by (Blast_tac 1);
   135 by (Blast_tac 1);
   136 qed "linear_Int_iff";
   136 qed "linear_Int_iff";
   137 
   137 
   138 goalw Order.thy [tot_ord_def] "tot_ord(A,r Int A*A) <-> tot_ord(A,r)";
   138 goalw Order.thy [tot_ord_def] "tot_ord(A,r Int A*A) <-> tot_ord(A,r)";
   139 by (simp_tac (!simpset addsimps [part_ord_Int_iff, linear_Int_iff]) 1);
   139 by (simp_tac (simpset() addsimps [part_ord_Int_iff, linear_Int_iff]) 1);
   140 qed "tot_ord_Int_iff";
   140 qed "tot_ord_Int_iff";
   141 
   141 
   142 goalw Order.thy [wf_on_def, wf_def] "wf[A](r Int A*A) <-> wf[A](r)";
   142 goalw Order.thy [wf_on_def, wf_def] "wf[A](r Int A*A) <-> wf[A](r)";
   143 by (Blast_tac 1);
   143 by (Blast_tac 1);
   144 qed "wf_on_Int_iff";
   144 qed "wf_on_Int_iff";
   145 
   145 
   146 goalw Order.thy [well_ord_def] "well_ord(A,r Int A*A) <-> well_ord(A,r)";
   146 goalw Order.thy [well_ord_def] "well_ord(A,r Int A*A) <-> well_ord(A,r)";
   147 by (simp_tac (!simpset addsimps [tot_ord_Int_iff, wf_on_Int_iff]) 1);
   147 by (simp_tac (simpset() addsimps [tot_ord_Int_iff, wf_on_Int_iff]) 1);
   148 qed "well_ord_Int_iff";
   148 qed "well_ord_Int_iff";
   149 
   149 
   150 
   150 
   151 (** Relations over the Empty Set **)
   151 (** Relations over the Empty Set **)
   152 
   152 
   157 goalw Order.thy [trans_on_def] "trans[0](r)";
   157 goalw Order.thy [trans_on_def] "trans[0](r)";
   158 by (Blast_tac 1);
   158 by (Blast_tac 1);
   159 qed "trans_on_0";
   159 qed "trans_on_0";
   160 
   160 
   161 goalw Order.thy [part_ord_def] "part_ord(0,r)";
   161 goalw Order.thy [part_ord_def] "part_ord(0,r)";
   162 by (simp_tac (!simpset addsimps [irrefl_0, trans_on_0]) 1);
   162 by (simp_tac (simpset() addsimps [irrefl_0, trans_on_0]) 1);
   163 qed "part_ord_0";
   163 qed "part_ord_0";
   164 
   164 
   165 goalw Order.thy [linear_def] "linear(0,r)";
   165 goalw Order.thy [linear_def] "linear(0,r)";
   166 by (Blast_tac 1);
   166 by (Blast_tac 1);
   167 qed "linear_0";
   167 qed "linear_0";
   168 
   168 
   169 goalw Order.thy [tot_ord_def] "tot_ord(0,r)";
   169 goalw Order.thy [tot_ord_def] "tot_ord(0,r)";
   170 by (simp_tac (!simpset addsimps [part_ord_0, linear_0]) 1);
   170 by (simp_tac (simpset() addsimps [part_ord_0, linear_0]) 1);
   171 qed "tot_ord_0";
   171 qed "tot_ord_0";
   172 
   172 
   173 goalw Order.thy [wf_on_def, wf_def] "wf[0](r)";
   173 goalw Order.thy [wf_on_def, wf_def] "wf[0](r)";
   174 by (Blast_tac 1);
   174 by (Blast_tac 1);
   175 qed "wf_on_0";
   175 qed "wf_on_0";
   176 
   176 
   177 goalw Order.thy [well_ord_def] "well_ord(0,r)";
   177 goalw Order.thy [well_ord_def] "well_ord(0,r)";
   178 by (simp_tac (!simpset addsimps [tot_ord_0, wf_on_0]) 1);
   178 by (simp_tac (simpset() addsimps [tot_ord_0, wf_on_0]) 1);
   179 qed "well_ord_0";
   179 qed "well_ord_0";
   180 
   180 
   181 
   181 
   182 (** Order-preserving (monotone) maps **)
   182 (** Order-preserving (monotone) maps **)
   183 
   183 
   202 
   202 
   203 val prems = goalw Order.thy [ord_iso_def]
   203 val prems = goalw Order.thy [ord_iso_def]
   204     "[| f: bij(A, B);   \
   204     "[| f: bij(A, B);   \
   205 \       !!x y. [| x:A; y:A |] ==> <x, y> : r <-> <f`x, f`y> : s \
   205 \       !!x y. [| x:A; y:A |] ==> <x, y> : r <-> <f`x, f`y> : s \
   206 \    |] ==> f: ord_iso(A,r,B,s)";
   206 \    |] ==> f: ord_iso(A,r,B,s)";
   207 by (blast_tac (!claset addSIs prems) 1);
   207 by (blast_tac (claset() addSIs prems) 1);
   208 qed "ord_isoI";
   208 qed "ord_isoI";
   209 
   209 
   210 goalw Order.thy [ord_iso_def, mono_map_def]
   210 goalw Order.thy [ord_iso_def, mono_map_def]
   211     "!!f. f: ord_iso(A,r,B,s) ==> f: mono_map(A,r,B,s)";
   211     "!!f. f: ord_iso(A,r,B,s) ==> f: mono_map(A,r,B,s)";
   212 by (blast_tac (!claset addSDs [bij_is_fun]) 1);
   212 by (blast_tac (claset() addSDs [bij_is_fun]) 1);
   213 qed "ord_iso_is_mono_map";
   213 qed "ord_iso_is_mono_map";
   214 
   214 
   215 goalw Order.thy [ord_iso_def] 
   215 goalw Order.thy [ord_iso_def] 
   216     "!!f. f: ord_iso(A,r,B,s) ==> f: bij(A,B)";
   216     "!!f. f: ord_iso(A,r,B,s) ==> f: bij(A,B)";
   217 by (etac CollectD1 1);
   217 by (etac CollectD1 1);
   229 \         <converse(f) ` x, converse(f) ` y> : r";
   229 \         <converse(f) ` x, converse(f) ` y> : r";
   230 by (etac CollectE 1);
   230 by (etac CollectE 1);
   231 by (etac (bspec RS bspec RS iffD2) 1);
   231 by (etac (bspec RS bspec RS iffD2) 1);
   232 by (REPEAT (eresolve_tac [asm_rl, 
   232 by (REPEAT (eresolve_tac [asm_rl, 
   233                           bij_converse_bij RS bij_is_fun RS apply_type] 1));
   233                           bij_converse_bij RS bij_is_fun RS apply_type] 1));
   234 by (asm_simp_tac (!simpset addsimps [right_inverse_bij]) 1);
   234 by (asm_simp_tac (simpset() addsimps [right_inverse_bij]) 1);
   235 qed "ord_iso_converse";
   235 qed "ord_iso_converse";
   236 
   236 
   237 
   237 
   238 (*Rewriting with bijections and converse (function inverse)*)
   238 (*Rewriting with bijections and converse (function inverse)*)
   239 val bij_inverse_ss = 
   239 val bij_inverse_ss = 
   240     !simpset setSolver (type_auto_tac [ord_iso_is_bij, bij_is_fun, apply_type, 
   240     simpset() setSolver (type_auto_tac [ord_iso_is_bij, bij_is_fun, apply_type, 
   241                                        bij_converse_bij, comp_fun, comp_bij])
   241                                        bij_converse_bij, comp_fun, comp_bij])
   242           addsimps [right_inverse_bij, left_inverse_bij];
   242           addsimps [right_inverse_bij, left_inverse_bij];
   243 
   243 
   244 (** Symmetry and Transitivity Rules **)
   244 (** Symmetry and Transitivity Rules **)
   245 
   245 
   250 qed "ord_iso_refl";
   250 qed "ord_iso_refl";
   251 
   251 
   252 (*Symmetry of similarity*)
   252 (*Symmetry of similarity*)
   253 goalw Order.thy [ord_iso_def] 
   253 goalw Order.thy [ord_iso_def] 
   254     "!!f. f: ord_iso(A,r,B,s) ==> converse(f): ord_iso(B,s,A,r)";
   254     "!!f. f: ord_iso(A,r,B,s) ==> converse(f): ord_iso(B,s,A,r)";
   255 by (fast_tac (!claset addss bij_inverse_ss) 1);
   255 by (fast_tac (claset() addss bij_inverse_ss) 1);
   256 qed "ord_iso_sym";
   256 qed "ord_iso_sym";
   257 
   257 
   258 (*Transitivity of similarity*)
   258 (*Transitivity of similarity*)
   259 goalw Order.thy [mono_map_def] 
   259 goalw Order.thy [mono_map_def] 
   260     "!!f. [| g: mono_map(A,r,B,s);  f: mono_map(B,s,C,t) |] ==> \
   260     "!!f. [| g: mono_map(A,r,B,s);  f: mono_map(B,s,C,t) |] ==> \
   261 \         (f O g): mono_map(A,r,C,t)";
   261 \         (f O g): mono_map(A,r,C,t)";
   262 by (fast_tac (!claset addss bij_inverse_ss) 1);
   262 by (fast_tac (claset() addss bij_inverse_ss) 1);
   263 qed "mono_map_trans";
   263 qed "mono_map_trans";
   264 
   264 
   265 (*Transitivity of similarity: the order-isomorphism relation*)
   265 (*Transitivity of similarity: the order-isomorphism relation*)
   266 goalw Order.thy [ord_iso_def] 
   266 goalw Order.thy [ord_iso_def] 
   267     "!!f. [| g: ord_iso(A,r,B,s);  f: ord_iso(B,s,C,t) |] ==> \
   267     "!!f. [| g: ord_iso(A,r,B,s);  f: ord_iso(B,s,C,t) |] ==> \
   268 \         (f O g): ord_iso(A,r,C,t)";
   268 \         (f O g): ord_iso(A,r,C,t)";
   269 by (fast_tac (!claset addss bij_inverse_ss) 1);
   269 by (fast_tac (claset() addss bij_inverse_ss) 1);
   270 qed "ord_iso_trans";
   270 qed "ord_iso_trans";
   271 
   271 
   272 (** Two monotone maps can make an order-isomorphism **)
   272 (** Two monotone maps can make an order-isomorphism **)
   273 
   273 
   274 goalw Order.thy [ord_iso_def, mono_map_def]
   274 goalw Order.thy [ord_iso_def, mono_map_def]
   275     "!!f g. [| f: mono_map(A,r,B,s);  g: mono_map(B,s,A,r);     \
   275     "!!f g. [| f: mono_map(A,r,B,s);  g: mono_map(B,s,A,r);     \
   276 \              f O g = id(B);  g O f = id(A) |] ==> f: ord_iso(A,r,B,s)";
   276 \              f O g = id(B);  g O f = id(A) |] ==> f: ord_iso(A,r,B,s)";
   277 by (safe_tac (!claset));
   277 by (safe_tac (claset()));
   278 by (REPEAT_FIRST (ares_tac [fg_imp_bijective]));
   278 by (REPEAT_FIRST (ares_tac [fg_imp_bijective]));
   279 by (Blast_tac 1);
   279 by (Blast_tac 1);
   280 by (subgoal_tac "<g`(f`x), g`(f`y)> : r" 1);
   280 by (subgoal_tac "<g`(f`x), g`(f`y)> : r" 1);
   281 by (blast_tac (!claset addIs [apply_funtype]) 2);
   281 by (blast_tac (claset() addIs [apply_funtype]) 2);
   282 by (asm_full_simp_tac (!simpset addsimps [comp_eq_id_iff RS iffD1]) 1);
   282 by (asm_full_simp_tac (simpset() addsimps [comp_eq_id_iff RS iffD1]) 1);
   283 qed "mono_ord_isoI";
   283 qed "mono_ord_isoI";
   284 
   284 
   285 goal Order.thy
   285 goal Order.thy
   286     "!!B. [| well_ord(A,r);  well_ord(B,s);                             \
   286     "!!B. [| well_ord(A,r);  well_ord(B,s);                             \
   287 \            f: mono_map(A,r,B,s);  converse(f): mono_map(B,s,A,r)      \
   287 \            f: mono_map(A,r,B,s);  converse(f): mono_map(B,s,A,r)      \
   297 (** Order-isomorphisms preserve the ordering's properties **)
   297 (** Order-isomorphisms preserve the ordering's properties **)
   298 
   298 
   299 goalw Order.thy [part_ord_def, irrefl_def, trans_on_def, ord_iso_def]
   299 goalw Order.thy [part_ord_def, irrefl_def, trans_on_def, ord_iso_def]
   300     "!!A B r. [| part_ord(B,s);  f: ord_iso(A,r,B,s) |] ==> part_ord(A,r)";
   300     "!!A B r. [| part_ord(B,s);  f: ord_iso(A,r,B,s) |] ==> part_ord(A,r)";
   301 by (Asm_simp_tac 1);
   301 by (Asm_simp_tac 1);
   302 by (fast_tac (!claset addIs [bij_is_fun RS apply_type]) 1);
   302 by (fast_tac (claset() addIs [bij_is_fun RS apply_type]) 1);
   303 qed "part_ord_ord_iso";
   303 qed "part_ord_ord_iso";
   304 
   304 
   305 goalw Order.thy [linear_def, ord_iso_def]
   305 goalw Order.thy [linear_def, ord_iso_def]
   306     "!!A B r. [| linear(B,s);  f: ord_iso(A,r,B,s) |] ==> linear(A,r)";
   306     "!!A B r. [| linear(B,s);  f: ord_iso(A,r,B,s) |] ==> linear(A,r)";
   307 by (Asm_simp_tac 1);
   307 by (Asm_simp_tac 1);
   308 by (safe_tac (!claset));
   308 by (safe_tac (claset()));
   309 by (dres_inst_tac [("x1", "f`x"), ("x", "f`xa")] (bspec RS bspec) 1);
   309 by (dres_inst_tac [("x1", "f`x"), ("x", "f`xa")] (bspec RS bspec) 1);
   310 by (safe_tac (!claset addSEs [bij_is_fun RS apply_type]));
   310 by (safe_tac (claset() addSEs [bij_is_fun RS apply_type]));
   311 by (dres_inst_tac [("t", "op `(converse(f))")] subst_context 1);
   311 by (dres_inst_tac [("t", "op `(converse(f))")] subst_context 1);
   312 by (asm_full_simp_tac (!simpset addsimps [left_inverse_bij]) 1);
   312 by (asm_full_simp_tac (simpset() addsimps [left_inverse_bij]) 1);
   313 qed "linear_ord_iso";
   313 qed "linear_ord_iso";
   314 
   314 
   315 goalw Order.thy [wf_on_def, wf_def, ord_iso_def]
   315 goalw Order.thy [wf_on_def, wf_def, ord_iso_def]
   316     "!!A B r. [| wf[B](s);  f: ord_iso(A,r,B,s) |] ==> wf[A](r)";
   316     "!!A B r. [| wf[B](s);  f: ord_iso(A,r,B,s) |] ==> wf[A](r)";
   317 (*reversed &-congruence rule handles context of membership in A*)
   317 (*reversed &-congruence rule handles context of membership in A*)
   318 by (asm_full_simp_tac (!simpset addcongs [conj_cong2]) 1);
   318 by (asm_full_simp_tac (simpset() addcongs [conj_cong2]) 1);
   319 by (safe_tac (!claset));
   319 by (safe_tac (claset()));
   320 by (dres_inst_tac [("x", "{f`z. z:Z Int A}")] spec 1);
   320 by (dres_inst_tac [("x", "{f`z. z:Z Int A}")] spec 1);
   321 by (safe_tac (!claset addSIs [equalityI]));
   321 by (safe_tac (claset() addSIs [equalityI]));
   322 by (ALLGOALS (blast_tac
   322 by (ALLGOALS (blast_tac
   323 	      (!claset addSDs [equalityD1] addIs [bij_is_fun RS apply_type])));
   323 	      (claset() addSDs [equalityD1] addIs [bij_is_fun RS apply_type])));
   324 qed "wf_on_ord_iso";
   324 qed "wf_on_ord_iso";
   325 
   325 
   326 goalw Order.thy [well_ord_def, tot_ord_def]
   326 goalw Order.thy [well_ord_def, tot_ord_def]
   327     "!!A B r. [| well_ord(B,s);  f: ord_iso(A,r,B,s) |] ==> well_ord(A,r)";
   327     "!!A B r. [| well_ord(B,s);  f: ord_iso(A,r,B,s) |] ==> well_ord(A,r)";
   328 by (fast_tac
   328 by (fast_tac
   329     (!claset addSEs [part_ord_ord_iso, linear_ord_iso, wf_on_ord_iso]) 1);
   329     (claset() addSEs [part_ord_ord_iso, linear_ord_iso, wf_on_ord_iso]) 1);
   330 qed "well_ord_ord_iso";
   330 qed "well_ord_ord_iso";
   331 
   331 
   332 
   332 
   333 (*** Main results of Kunen, Chapter 1 section 6 ***)
   333 (*** Main results of Kunen, Chapter 1 section 6 ***)
   334 
   334 
   352 by (REPEAT_FIRST (ares_tac [pred_subset]));
   352 by (REPEAT_FIRST (ares_tac [pred_subset]));
   353 (*Now we know  f`x < x *)
   353 (*Now we know  f`x < x *)
   354 by (EVERY1 [dtac (ord_iso_is_bij RS bij_is_fun RS apply_type),
   354 by (EVERY1 [dtac (ord_iso_is_bij RS bij_is_fun RS apply_type),
   355              assume_tac]);
   355              assume_tac]);
   356 (*Now we also know f`x : pred(A,x,r);  contradiction! *)
   356 (*Now we also know f`x : pred(A,x,r);  contradiction! *)
   357 by (asm_full_simp_tac (!simpset addsimps [well_ord_def, pred_def]) 1);
   357 by (asm_full_simp_tac (simpset() addsimps [well_ord_def, pred_def]) 1);
   358 qed "well_ord_iso_predE";
   358 qed "well_ord_iso_predE";
   359 
   359 
   360 (*Simple consequence of Lemma 6.1*)
   360 (*Simple consequence of Lemma 6.1*)
   361 goal Order.thy
   361 goal Order.thy
   362  "!!r. [| well_ord(A,r);  f : ord_iso(pred(A,a,r), r, pred(A,c,r), r);  \
   362  "!!r. [| well_ord(A,r);  f : ord_iso(pred(A,a,r), r, pred(A,c,r), r);  \
   366 by (linear_case_tac 1);
   366 by (linear_case_tac 1);
   367 by (dtac ord_iso_sym 1);
   367 by (dtac ord_iso_sym 1);
   368 by (REPEAT   (*because there are two symmetric cases*)
   368 by (REPEAT   (*because there are two symmetric cases*)
   369     (EVERY [eresolve_tac [pred_subset RSN (2, well_ord_subset) RS
   369     (EVERY [eresolve_tac [pred_subset RSN (2, well_ord_subset) RS
   370                           well_ord_iso_predE] 1,
   370                           well_ord_iso_predE] 1,
   371             blast_tac (!claset addSIs [predI]) 2,
   371             blast_tac (claset() addSIs [predI]) 2,
   372             asm_simp_tac (!simpset addsimps [trans_pred_pred_eq]) 1]));
   372             asm_simp_tac (simpset() addsimps [trans_pred_pred_eq]) 1]));
   373 qed "well_ord_iso_pred_eq";
   373 qed "well_ord_iso_pred_eq";
   374 
   374 
   375 (*Does not assume r is a wellordering!*)
   375 (*Does not assume r is a wellordering!*)
   376 goalw Order.thy [ord_iso_def, pred_def]
   376 goalw Order.thy [ord_iso_def, pred_def]
   377  "!!r. [| f : ord_iso(A,r,B,s);   a:A |] ==>    \
   377  "!!r. [| f : ord_iso(A,r,B,s);   a:A |] ==>    \
   378 \      f `` pred(A,a,r) = pred(B, f`a, s)";
   378 \      f `` pred(A,a,r) = pred(B, f`a, s)";
   379 by (etac CollectE 1);
   379 by (etac CollectE 1);
   380 by (asm_simp_tac 
   380 by (asm_simp_tac 
   381     (!simpset addsimps [[bij_is_fun, Collect_subset] MRS image_fun]) 1);
   381     (simpset() addsimps [[bij_is_fun, Collect_subset] MRS image_fun]) 1);
   382 by (rtac equalityI 1);
   382 by (rtac equalityI 1);
   383 by (safe_tac (!claset addSEs [bij_is_fun RS apply_type]));
   383 by (safe_tac (claset() addSEs [bij_is_fun RS apply_type]));
   384 by (rtac RepFun_eqI 1);
   384 by (rtac RepFun_eqI 1);
   385 by (blast_tac (!claset addSIs [right_inverse_bij RS sym]) 1);
   385 by (blast_tac (claset() addSIs [right_inverse_bij RS sym]) 1);
   386 by (asm_simp_tac bij_inverse_ss 1);
   386 by (asm_simp_tac bij_inverse_ss 1);
   387 qed "ord_iso_image_pred";
   387 qed "ord_iso_image_pred";
   388 
   388 
   389 (*But in use, A and B may themselves be initial segments.  Then use
   389 (*But in use, A and B may themselves be initial segments.  Then use
   390   trans_pred_pred_eq to simplify the pred(pred...) terms.  See just below.*)
   390   trans_pred_pred_eq to simplify the pred(pred...) terms.  See just below.*)
   391 goal Order.thy
   391 goal Order.thy
   392  "!!r. [| f : ord_iso(A,r,B,s);   a:A |] ==>    \
   392  "!!r. [| f : ord_iso(A,r,B,s);   a:A |] ==>    \
   393 \      restrict(f, pred(A,a,r)) : ord_iso(pred(A,a,r), r, pred(B, f`a, s), s)";
   393 \      restrict(f, pred(A,a,r)) : ord_iso(pred(A,a,r), r, pred(B, f`a, s), s)";
   394 by (asm_simp_tac (!simpset addsimps [ord_iso_image_pred RS sym]) 1);
   394 by (asm_simp_tac (simpset() addsimps [ord_iso_image_pred RS sym]) 1);
   395 by (rewtac ord_iso_def);
   395 by (rewtac ord_iso_def);
   396 by (etac CollectE 1);
   396 by (etac CollectE 1);
   397 by (rtac CollectI 1);
   397 by (rtac CollectI 1);
   398 by (asm_full_simp_tac (!simpset addsimps [pred_def]) 2);
   398 by (asm_full_simp_tac (simpset() addsimps [pred_def]) 2);
   399 by (eresolve_tac [[bij_is_inj, pred_subset] MRS restrict_bij] 1);
   399 by (eresolve_tac [[bij_is_inj, pred_subset] MRS restrict_bij] 1);
   400 qed "ord_iso_restrict_pred";
   400 qed "ord_iso_restrict_pred";
   401 
   401 
   402 (*Tricky; a lot of forward proof!*)
   402 (*Tricky; a lot of forward proof!*)
   403 goal Order.thy
   403 goal Order.thy
   412 by (rtac well_ord_iso_pred_eq 1);
   412 by (rtac well_ord_iso_pred_eq 1);
   413 by (REPEAT_SOME assume_tac);
   413 by (REPEAT_SOME assume_tac);
   414 by (forward_tac [ord_iso_restrict_pred] 1  THEN
   414 by (forward_tac [ord_iso_restrict_pred] 1  THEN
   415     REPEAT1 (eresolve_tac [asm_rl, predI] 1));
   415     REPEAT1 (eresolve_tac [asm_rl, predI] 1));
   416 by (asm_full_simp_tac
   416 by (asm_full_simp_tac
   417     (!simpset addsimps [well_ord_is_trans_on, trans_pred_pred_eq]) 1);
   417     (simpset() addsimps [well_ord_is_trans_on, trans_pred_pred_eq]) 1);
   418 by (eresolve_tac [ord_iso_sym RS ord_iso_trans] 1);
   418 by (eresolve_tac [ord_iso_sym RS ord_iso_trans] 1);
   419 by (assume_tac 1);
   419 by (assume_tac 1);
   420 qed "well_ord_iso_preserving";
   420 qed "well_ord_iso_preserving";
   421 
   421 
   422 val  bij_apply_cs = !claset addSIs [bij_converse_bij]
   422 val  bij_apply_cs = claset() addSIs [bij_converse_bij]
   423                             addIs  [ord_iso_is_bij, bij_is_fun, apply_funtype];
   423                             addIs  [ord_iso_is_bij, bij_is_fun, apply_funtype];
   424 
   424 
   425 (*See Halmos, page 72*)
   425 (*See Halmos, page 72*)
   426 goal Order.thy
   426 goal Order.thy
   427     "!!r. [| well_ord(A,r);  \
   427     "!!r. [| well_ord(A,r);  \
   428 \            f: ord_iso(A,r, B,s);  g: ord_iso(A,r, B,s);  y: A |] \
   428 \            f: ord_iso(A,r, B,s);  g: ord_iso(A,r, B,s);  y: A |] \
   429 \         ==> ~ <g`y, f`y> : s";
   429 \         ==> ~ <g`y, f`y> : s";
   430 by (forward_tac [well_ord_iso_subset_lemma] 1);
   430 by (forward_tac [well_ord_iso_subset_lemma] 1);
   431 by (res_inst_tac [("f","converse(f)"), ("g","g")] ord_iso_trans 1);
   431 by (res_inst_tac [("f","converse(f)"), ("g","g")] ord_iso_trans 1);
   432 by (REPEAT_FIRST (ares_tac [subset_refl, ord_iso_sym]));
   432 by (REPEAT_FIRST (ares_tac [subset_refl, ord_iso_sym]));
   433 by (safe_tac (!claset));
   433 by (safe_tac (claset()));
   434 by (forward_tac [ord_iso_converse] 1);
   434 by (forward_tac [ord_iso_converse] 1);
   435 by (EVERY (map (blast_tac bij_apply_cs) [1,1,1]));
   435 by (EVERY (map (blast_tac bij_apply_cs) [1,1,1]));
   436 by (asm_full_simp_tac bij_inverse_ss 1);
   436 by (asm_full_simp_tac bij_inverse_ss 1);
   437 qed "well_ord_iso_unique_lemma";
   437 qed "well_ord_iso_unique_lemma";
   438 
   438 
   443 by (rtac fun_extension 1);
   443 by (rtac fun_extension 1);
   444 by (REPEAT (etac (ord_iso_is_bij RS bij_is_fun) 1));
   444 by (REPEAT (etac (ord_iso_is_bij RS bij_is_fun) 1));
   445 by (subgoals_tac ["f`x : B", "g`x : B", "linear(B,s)"] 1);
   445 by (subgoals_tac ["f`x : B", "g`x : B", "linear(B,s)"] 1);
   446 by (REPEAT (blast_tac bij_apply_cs 3));
   446 by (REPEAT (blast_tac bij_apply_cs 3));
   447 by (dtac well_ord_ord_iso 2 THEN etac ord_iso_sym 2);
   447 by (dtac well_ord_ord_iso 2 THEN etac ord_iso_sym 2);
   448 by (asm_full_simp_tac (!simpset addsimps [tot_ord_def, well_ord_def]) 2);
   448 by (asm_full_simp_tac (simpset() addsimps [tot_ord_def, well_ord_def]) 2);
   449 by (linear_case_tac 1);
   449 by (linear_case_tac 1);
   450 by (DEPTH_SOLVE (eresolve_tac [asm_rl, well_ord_iso_unique_lemma RS notE] 1));
   450 by (DEPTH_SOLVE (eresolve_tac [asm_rl, well_ord_iso_unique_lemma RS notE] 1));
   451 qed "well_ord_iso_unique";
   451 qed "well_ord_iso_unique";
   452 
   452 
   453 
   453 
   465 by (Blast_tac 1);
   465 by (Blast_tac 1);
   466 qed "range_ord_iso_map";
   466 qed "range_ord_iso_map";
   467 
   467 
   468 goalw Order.thy [ord_iso_map_def]
   468 goalw Order.thy [ord_iso_map_def]
   469     "converse(ord_iso_map(A,r,B,s)) = ord_iso_map(B,s,A,r)";
   469     "converse(ord_iso_map(A,r,B,s)) = ord_iso_map(B,s,A,r)";
   470 by (blast_tac (!claset addIs [ord_iso_sym]) 1);
   470 by (blast_tac (claset() addIs [ord_iso_sym]) 1);
   471 qed "converse_ord_iso_map";
   471 qed "converse_ord_iso_map";
   472 
   472 
   473 goalw Order.thy [ord_iso_map_def, function_def]
   473 goalw Order.thy [ord_iso_map_def, function_def]
   474     "!!B. well_ord(B,s) ==> function(ord_iso_map(A,r,B,s))";
   474     "!!B. well_ord(B,s) ==> function(ord_iso_map(A,r,B,s))";
   475 by (blast_tac (!claset addIs [well_ord_iso_pred_eq, 
   475 by (blast_tac (claset() addIs [well_ord_iso_pred_eq, 
   476 			      ord_iso_sym, ord_iso_trans]) 1);
   476 			      ord_iso_sym, ord_iso_trans]) 1);
   477 qed "function_ord_iso_map";
   477 qed "function_ord_iso_map";
   478 
   478 
   479 goal Order.thy
   479 goal Order.thy
   480     "!!B. well_ord(B,s) ==> ord_iso_map(A,r,B,s)        \
   480     "!!B. well_ord(B,s) ==> ord_iso_map(A,r,B,s)        \
   481 \          : domain(ord_iso_map(A,r,B,s)) -> range(ord_iso_map(A,r,B,s))";
   481 \          : domain(ord_iso_map(A,r,B,s)) -> range(ord_iso_map(A,r,B,s))";
   482 by (asm_simp_tac 
   482 by (asm_simp_tac 
   483     (!simpset addsimps [Pi_iff, function_ord_iso_map,
   483     (simpset() addsimps [Pi_iff, function_ord_iso_map,
   484                      ord_iso_map_subset RS domain_times_range]) 1);
   484                      ord_iso_map_subset RS domain_times_range]) 1);
   485 qed "ord_iso_map_fun";
   485 qed "ord_iso_map_fun";
   486 
   486 
   487 goalw Order.thy [mono_map_def]
   487 goalw Order.thy [mono_map_def]
   488     "!!B. [| well_ord(A,r);  well_ord(B,s) |] ==> ord_iso_map(A,r,B,s)  \
   488     "!!B. [| well_ord(A,r);  well_ord(B,s) |] ==> ord_iso_map(A,r,B,s)  \
   489 \          : mono_map(domain(ord_iso_map(A,r,B,s)), r,  \
   489 \          : mono_map(domain(ord_iso_map(A,r,B,s)), r,  \
   490 \                     range(ord_iso_map(A,r,B,s)), s)";
   490 \                     range(ord_iso_map(A,r,B,s)), s)";
   491 by (asm_simp_tac (!simpset addsimps [ord_iso_map_fun]) 1);
   491 by (asm_simp_tac (simpset() addsimps [ord_iso_map_fun]) 1);
   492 by (safe_tac (!claset));
   492 by (safe_tac (claset()));
   493 by (subgoals_tac ["x:A", "xa:A", "y:B", "ya:B"] 1);
   493 by (subgoals_tac ["x:A", "xa:A", "y:B", "ya:B"] 1);
   494 by (REPEAT 
   494 by (REPEAT 
   495     (blast_tac (!claset addSEs [ord_iso_map_subset RS subsetD RS SigmaE]) 2));
   495     (blast_tac (claset() addSEs [ord_iso_map_subset RS subsetD RS SigmaE]) 2));
   496 by (asm_simp_tac 
   496 by (asm_simp_tac 
   497     (!simpset addsimps [ord_iso_map_fun RSN (2,apply_equality)]) 1);
   497     (simpset() addsimps [ord_iso_map_fun RSN (2,apply_equality)]) 1);
   498 by (rewtac ord_iso_map_def);
   498 by (rewtac ord_iso_map_def);
   499 by (safe_tac (!claset addSEs [UN_E]));
   499 by (safe_tac (claset() addSEs [UN_E]));
   500 by (rtac well_ord_iso_preserving 1 THEN REPEAT_FIRST assume_tac);
   500 by (rtac well_ord_iso_preserving 1 THEN REPEAT_FIRST assume_tac);
   501 qed "ord_iso_map_mono_map";
   501 qed "ord_iso_map_mono_map";
   502 
   502 
   503 goalw Order.thy [mono_map_def]
   503 goalw Order.thy [mono_map_def]
   504     "!!B. [| well_ord(A,r);  well_ord(B,s) |] ==> ord_iso_map(A,r,B,s)  \
   504     "!!B. [| well_ord(A,r);  well_ord(B,s) |] ==> ord_iso_map(A,r,B,s)  \
   505 \          : ord_iso(domain(ord_iso_map(A,r,B,s)), r,   \
   505 \          : ord_iso(domain(ord_iso_map(A,r,B,s)), r,   \
   506 \                     range(ord_iso_map(A,r,B,s)), s)";
   506 \                     range(ord_iso_map(A,r,B,s)), s)";
   507 by (rtac well_ord_mono_ord_isoI 1);
   507 by (rtac well_ord_mono_ord_isoI 1);
   508 by (resolve_tac [converse_ord_iso_map RS subst] 4);
   508 by (resolve_tac [converse_ord_iso_map RS subst] 4);
   509 by (asm_simp_tac 
   509 by (asm_simp_tac 
   510     (!simpset addsimps [ord_iso_map_subset RS converse_converse]) 4);
   510     (simpset() addsimps [ord_iso_map_subset RS converse_converse]) 4);
   511 by (REPEAT (ares_tac [ord_iso_map_mono_map] 3));
   511 by (REPEAT (ares_tac [ord_iso_map_mono_map] 3));
   512 by (ALLGOALS (etac well_ord_subset));
   512 by (ALLGOALS (etac well_ord_subset));
   513 by (ALLGOALS (resolve_tac [domain_ord_iso_map, range_ord_iso_map]));
   513 by (ALLGOALS (resolve_tac [domain_ord_iso_map, range_ord_iso_map]));
   514 qed "ord_iso_map_ord_iso";
   514 qed "ord_iso_map_ord_iso";
   515 
   515 
   516 (*One way of saying that domain(ord_iso_map(A,r,B,s)) is downwards-closed*)
   516 (*One way of saying that domain(ord_iso_map(A,r,B,s)) is downwards-closed*)
   517 goalw Order.thy [ord_iso_map_def]
   517 goalw Order.thy [ord_iso_map_def]
   518   "!!B. [| well_ord(A,r);  well_ord(B,s);               \
   518   "!!B. [| well_ord(A,r);  well_ord(B,s);               \
   519 \          a: A;  a ~: domain(ord_iso_map(A,r,B,s))     \
   519 \          a: A;  a ~: domain(ord_iso_map(A,r,B,s))     \
   520 \       |] ==>  domain(ord_iso_map(A,r,B,s)) <= pred(A, a, r)";
   520 \       |] ==>  domain(ord_iso_map(A,r,B,s)) <= pred(A, a, r)";
   521 by (safe_tac (!claset addSIs [predI]));
   521 by (safe_tac (claset() addSIs [predI]));
   522 (*Case analysis on  xaa vs a in r *)
   522 (*Case analysis on  xaa vs a in r *)
   523 by (forw_inst_tac [("A","A")] well_ord_is_linear 1);
   523 by (forw_inst_tac [("A","A")] well_ord_is_linear 1);
   524 by (linear_case_tac 1);
   524 by (linear_case_tac 1);
   525 (*Trivial case: a=xa*)
   525 (*Trivial case: a=xa*)
   526 by (Blast_tac 2);
   526 by (Blast_tac 2);
   528 by (forward_tac [ord_iso_is_bij RS bij_is_fun RS apply_type] 1  THEN
   528 by (forward_tac [ord_iso_is_bij RS bij_is_fun RS apply_type] 1  THEN
   529     REPEAT1 (eresolve_tac [asm_rl, predI, predE] 1));
   529     REPEAT1 (eresolve_tac [asm_rl, predI, predE] 1));
   530 by (forward_tac [ord_iso_restrict_pred] 1  THEN
   530 by (forward_tac [ord_iso_restrict_pred] 1  THEN
   531     REPEAT1 (eresolve_tac [asm_rl, predI] 1));
   531     REPEAT1 (eresolve_tac [asm_rl, predI] 1));
   532 by (asm_full_simp_tac
   532 by (asm_full_simp_tac
   533     (!simpset addsimps [well_ord_is_trans_on, trans_pred_pred_eq]) 1);
   533     (simpset() addsimps [well_ord_is_trans_on, trans_pred_pred_eq]) 1);
   534 by (Blast_tac 1);
   534 by (Blast_tac 1);
   535 qed "domain_ord_iso_map_subset";
   535 qed "domain_ord_iso_map_subset";
   536 
   536 
   537 (*For the 4-way case analysis in the main result*)
   537 (*For the 4-way case analysis in the main result*)
   538 goal Order.thy
   538 goal Order.thy
   548 by (etac (Diff_eq_0_iff RS iffD1) 1);
   548 by (etac (Diff_eq_0_iff RS iffD1) 1);
   549 (*The other case: the domain equals an initial segment*)
   549 (*The other case: the domain equals an initial segment*)
   550 by (swap_res_tac [bexI] 1);
   550 by (swap_res_tac [bexI] 1);
   551 by (assume_tac 2);
   551 by (assume_tac 2);
   552 by (rtac equalityI 1);
   552 by (rtac equalityI 1);
   553 (*not (!claset) below; that would use rules like domainE!*)
   553 (*not (claset()) below; that would use rules like domainE!*)
   554 by (blast_tac (!claset addSEs [predE]) 2);
   554 by (blast_tac (claset() addSEs [predE]) 2);
   555 by (REPEAT (ares_tac [domain_ord_iso_map_subset] 1));
   555 by (REPEAT (ares_tac [domain_ord_iso_map_subset] 1));
   556 qed "domain_ord_iso_map_cases";
   556 qed "domain_ord_iso_map_cases";
   557 
   557 
   558 (*As above, by duality*)
   558 (*As above, by duality*)
   559 goal Order.thy
   559 goal Order.thy
   560   "!!B. [| well_ord(A,r);  well_ord(B,s) |] ==> \
   560   "!!B. [| well_ord(A,r);  well_ord(B,s) |] ==> \
   561 \       range(ord_iso_map(A,r,B,s)) = B |       \
   561 \       range(ord_iso_map(A,r,B,s)) = B |       \
   562 \       (EX y:B. range(ord_iso_map(A,r,B,s))= pred(B,y,s))";
   562 \       (EX y:B. range(ord_iso_map(A,r,B,s))= pred(B,y,s))";
   563 by (resolve_tac [converse_ord_iso_map RS subst] 1);
   563 by (resolve_tac [converse_ord_iso_map RS subst] 1);
   564 by (asm_simp_tac
   564 by (asm_simp_tac
   565     (!simpset addsimps [range_converse, domain_ord_iso_map_cases]) 1);
   565     (simpset() addsimps [range_converse, domain_ord_iso_map_cases]) 1);
   566 qed "range_ord_iso_map_cases";
   566 qed "range_ord_iso_map_cases";
   567 
   567 
   568 (*Kunen's Theorem 6.3: Fundamental Theorem for Well-Ordered Sets*)
   568 (*Kunen's Theorem 6.3: Fundamental Theorem for Well-Ordered Sets*)
   569 goal Order.thy
   569 goal Order.thy
   570   "!!B. [| well_ord(A,r);  well_ord(B,s) |] ==>         \
   570   "!!B. [| well_ord(A,r);  well_ord(B,s) |] ==>         \
   573 \       (EX y:B. ord_iso_map(A,r,B,s) : ord_iso(A, r, pred(B,y,s), s))";
   573 \       (EX y:B. ord_iso_map(A,r,B,s) : ord_iso(A, r, pred(B,y,s), s))";
   574 by (forw_inst_tac [("B","B")] domain_ord_iso_map_cases 1);
   574 by (forw_inst_tac [("B","B")] domain_ord_iso_map_cases 1);
   575 by (forw_inst_tac [("B","B")] range_ord_iso_map_cases 2);
   575 by (forw_inst_tac [("B","B")] range_ord_iso_map_cases 2);
   576 by (REPEAT_FIRST (eresolve_tac [asm_rl, disjE, bexE]));
   576 by (REPEAT_FIRST (eresolve_tac [asm_rl, disjE, bexE]));
   577 by (ALLGOALS (dtac ord_iso_map_ord_iso THEN' assume_tac THEN' 
   577 by (ALLGOALS (dtac ord_iso_map_ord_iso THEN' assume_tac THEN' 
   578               asm_full_simp_tac (!simpset addsimps [bexI])));
   578               asm_full_simp_tac (simpset() addsimps [bexI])));
   579 by (resolve_tac [wf_on_not_refl RS notE] 1);
   579 by (resolve_tac [wf_on_not_refl RS notE] 1);
   580 by (etac well_ord_is_wf 1);
   580 by (etac well_ord_is_wf 1);
   581 by (assume_tac 1);
   581 by (assume_tac 1);
   582 by (subgoal_tac "<x,y>: ord_iso_map(A,r,B,s)" 1);
   582 by (subgoal_tac "<x,y>: ord_iso_map(A,r,B,s)" 1);
   583 by (dtac rangeI 1);
   583 by (dtac rangeI 1);
   584 by (asm_full_simp_tac (!simpset addsimps [pred_def]) 1);
   584 by (asm_full_simp_tac (simpset() addsimps [pred_def]) 1);
   585 by (rewtac ord_iso_map_def);
   585 by (rewtac ord_iso_map_def);
   586 by (Blast_tac 1);
   586 by (Blast_tac 1);
   587 qed "well_ord_trichotomy";
   587 qed "well_ord_trichotomy";
   588 
   588 
   589 
   589 
   590 (*** Properties of converse(r), by Krzysztof Grabczewski ***)
   590 (*** Properties of converse(r), by Krzysztof Grabczewski ***)
   591 
   591 
   592 goalw Order.thy [irrefl_def] 
   592 goalw Order.thy [irrefl_def] 
   593             "!!A. irrefl(A,r) ==> irrefl(A,converse(r))";
   593             "!!A. irrefl(A,r) ==> irrefl(A,converse(r))";
   594 by (blast_tac (!claset addSIs [converseI]) 1);
   594 by (blast_tac (claset() addSIs [converseI]) 1);
   595 qed "irrefl_converse";
   595 qed "irrefl_converse";
   596 
   596 
   597 goalw Order.thy [trans_on_def] 
   597 goalw Order.thy [trans_on_def] 
   598     "!!A. trans[A](r) ==> trans[A](converse(r))";
   598     "!!A. trans[A](r) ==> trans[A](converse(r))";
   599 by (blast_tac (!claset addSIs [converseI]) 1);
   599 by (blast_tac (claset() addSIs [converseI]) 1);
   600 qed "trans_on_converse";
   600 qed "trans_on_converse";
   601 
   601 
   602 goalw Order.thy [part_ord_def] 
   602 goalw Order.thy [part_ord_def] 
   603     "!!A. part_ord(A,r) ==> part_ord(A,converse(r))";
   603     "!!A. part_ord(A,r) ==> part_ord(A,converse(r))";
   604 by (blast_tac (!claset addSIs [irrefl_converse, trans_on_converse]) 1);
   604 by (blast_tac (claset() addSIs [irrefl_converse, trans_on_converse]) 1);
   605 qed "part_ord_converse";
   605 qed "part_ord_converse";
   606 
   606 
   607 goalw Order.thy [linear_def] 
   607 goalw Order.thy [linear_def] 
   608     "!!A. linear(A,r) ==> linear(A,converse(r))";
   608     "!!A. linear(A,r) ==> linear(A,converse(r))";
   609 by (blast_tac (!claset addSIs [converseI]) 1);
   609 by (blast_tac (claset() addSIs [converseI]) 1);
   610 qed "linear_converse";
   610 qed "linear_converse";
   611 
   611 
   612 goalw Order.thy [tot_ord_def] 
   612 goalw Order.thy [tot_ord_def] 
   613     "!!A. tot_ord(A,r) ==> tot_ord(A,converse(r))";
   613     "!!A. tot_ord(A,r) ==> tot_ord(A,converse(r))";
   614 by (blast_tac (!claset addSIs [part_ord_converse, linear_converse]) 1);
   614 by (blast_tac (claset() addSIs [part_ord_converse, linear_converse]) 1);
   615 qed "tot_ord_converse";
   615 qed "tot_ord_converse";
   616 
   616 
   617 
   617 
   618 (** By Krzysztof Grabczewski.
   618 (** By Krzysztof Grabczewski.
   619     Lemmas involving the first element of a well ordered set **)
   619     Lemmas involving the first element of a well ordered set **)
   628 by (contr_tac 1);
   628 by (contr_tac 1);
   629 by (etac bexE 1);
   629 by (etac bexE 1);
   630 by (res_inst_tac [("a","x")] ex1I 1);
   630 by (res_inst_tac [("a","x")] ex1I 1);
   631 by (Blast_tac 2);
   631 by (Blast_tac 2);
   632 by (rewrite_goals_tac [tot_ord_def, linear_def]);
   632 by (rewrite_goals_tac [tot_ord_def, linear_def]);
   633 by (Blast.depth_tac (!claset) 7 1);
   633 by (Blast.depth_tac (claset()) 7 1);
   634 qed "well_ord_imp_ex1_first";
   634 qed "well_ord_imp_ex1_first";
   635 
   635 
   636 goal thy "!!r. [| well_ord(A,r); B<=A; B~=0 |] ==> (THE b. first(b,B,r)) : B";
   636 goal thy "!!r. [| well_ord(A,r); B<=A; B~=0 |] ==> (THE b. first(b,B,r)) : B";
   637 by (dtac well_ord_imp_ex1_first 1 THEN REPEAT (assume_tac 1));
   637 by (dtac well_ord_imp_ex1_first 1 THEN REPEAT (assume_tac 1));
   638 by (rtac first_is_elem 1);
   638 by (rtac first_is_elem 1);