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); |
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 |
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); |
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 |
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 |
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); |
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 **) |