17 Goalw [part_ord_def, irrefl_def, trans_on_def, asym_def] |
17 Goalw [part_ord_def, irrefl_def, trans_on_def, asym_def] |
18 "part_ord(A,r) ==> asym(r Int A*A)"; |
18 "part_ord(A,r) ==> asym(r Int A*A)"; |
19 by (Blast_tac 1); |
19 by (Blast_tac 1); |
20 qed "part_ord_Imp_asym"; |
20 qed "part_ord_Imp_asym"; |
21 |
21 |
22 val major::premx::premy::prems = goalw Order.thy [linear_def] |
22 val major::premx::premy::prems = Goalw [linear_def] |
23 "[| linear(A,r); x:A; y:A; \ |
23 "[| linear(A,r); x:A; y:A; \ |
24 \ <x,y>:r ==> P; x=y ==> P; <y,x>:r ==> P |] ==> P"; |
24 \ <x,y>:r ==> P; x=y ==> P; <y,x>:r ==> P |] ==> P"; |
25 by (cut_facts_tac [major,premx,premy] 1); |
25 by (cut_facts_tac [major,premx,premy] 1); |
26 by (REPEAT_FIRST (eresolve_tac [ballE,disjE])); |
26 by (REPEAT_FIRST (eresolve_tac [ballE,disjE])); |
27 by (EVERY1 (map etac prems)); |
27 by (EVERY1 (map etac prems)); |
64 by (Blast_tac 1); |
64 by (Blast_tac 1); |
65 qed "pred_iff"; |
65 qed "pred_iff"; |
66 |
66 |
67 bind_thm ("predI", conjI RS (pred_iff RS iffD2)); |
67 bind_thm ("predI", conjI RS (pred_iff RS iffD2)); |
68 |
68 |
69 val [major,minor] = goalw Order.thy [pred_def] |
69 val [major,minor] = Goalw [pred_def] |
70 "[| y: pred(A,x,r); [| y:A; <y,x>:r |] ==> P |] ==> P"; |
70 "[| y: pred(A,x,r); [| y:A; <y,x>:r |] ==> P |] ==> P"; |
71 by (rtac (major RS CollectE) 1); |
71 by (rtac (major RS CollectE) 1); |
72 by (REPEAT (ares_tac [minor] 1)); |
72 by (REPEAT (ares_tac [minor] 1)); |
73 qed "predE"; |
73 qed "predE"; |
74 |
74 |
214 qed "mono_map_is_inj"; |
214 qed "mono_map_is_inj"; |
215 |
215 |
216 |
216 |
217 (** Order-isomorphisms -- or similarities, as Suppes calls them **) |
217 (** Order-isomorphisms -- or similarities, as Suppes calls them **) |
218 |
218 |
219 val prems = goalw Order.thy [ord_iso_def] |
219 val prems = Goalw [ord_iso_def] |
220 "[| f: bij(A, B); \ |
220 "[| f: bij(A, B); \ |
221 \ !!x y. [| x:A; y:A |] ==> <x, y> : r <-> <f`x, f`y> : s \ |
221 \ !!x y. [| x:A; y:A |] ==> <x, y> : r <-> <f`x, f`y> : s \ |
222 \ |] ==> f: ord_iso(A,r,B,s)"; |
222 \ |] ==> f: ord_iso(A,r,B,s)"; |
223 by (blast_tac (claset() addSIs prems) 1); |
223 by (blast_tac (claset() addSIs prems) 1); |
224 qed "ord_isoI"; |
224 qed "ord_isoI"; |
296 by (subgoal_tac "<g`(f`x), g`(f`y)> : r" 1); |
296 by (subgoal_tac "<g`(f`x), g`(f`y)> : r" 1); |
297 by (blast_tac (claset() addIs [apply_funtype]) 2); |
297 by (blast_tac (claset() addIs [apply_funtype]) 2); |
298 by (asm_full_simp_tac (simpset() addsimps [comp_eq_id_iff RS iffD1]) 1); |
298 by (asm_full_simp_tac (simpset() addsimps [comp_eq_id_iff RS iffD1]) 1); |
299 qed "mono_ord_isoI"; |
299 qed "mono_ord_isoI"; |
300 |
300 |
301 Goal |
301 Goal "[| well_ord(A,r); well_ord(B,s); \ |
302 "[| well_ord(A,r); well_ord(B,s); \ |
|
303 \ f: mono_map(A,r,B,s); converse(f): mono_map(B,s,A,r) \ |
302 \ f: mono_map(A,r,B,s); converse(f): mono_map(B,s,A,r) \ |
304 \ |] ==> f: ord_iso(A,r,B,s)"; |
303 \ |] ==> f: ord_iso(A,r,B,s)"; |
305 by (REPEAT (ares_tac [mono_ord_isoI] 1)); |
304 by (REPEAT (ares_tac [mono_ord_isoI] 1)); |
306 by (forward_tac [mono_map_is_fun RS fun_is_rel] 1); |
305 by (forward_tac [mono_map_is_fun RS fun_is_rel] 1); |
307 by (etac (converse_converse RS subst) 1 THEN rtac left_comp_inverse 1); |
306 by (etac (converse_converse RS subst) 1 THEN rtac left_comp_inverse 1); |
360 by (Blast_tac 1); |
359 by (Blast_tac 1); |
361 qed "well_ord_iso_subset_lemma"; |
360 qed "well_ord_iso_subset_lemma"; |
362 |
361 |
363 (*Kunen's Lemma 6.1: there's no order-isomorphism to an initial segment |
362 (*Kunen's Lemma 6.1: there's no order-isomorphism to an initial segment |
364 of a well-ordering*) |
363 of a well-ordering*) |
365 Goal |
364 Goal "[| well_ord(A,r); f : ord_iso(A, r, pred(A,x,r), r); x:A |] ==> P"; |
366 "[| well_ord(A,r); f : ord_iso(A, r, pred(A,x,r), r); x:A |] ==> P"; |
|
367 by (metacut_tac well_ord_iso_subset_lemma 1); |
365 by (metacut_tac well_ord_iso_subset_lemma 1); |
368 by (REPEAT_FIRST (ares_tac [pred_subset])); |
366 by (REPEAT_FIRST (ares_tac [pred_subset])); |
369 (*Now we know f`x < x *) |
367 (*Now we know f`x < x *) |
370 by (EVERY1 [dtac (ord_iso_is_bij RS bij_is_fun RS apply_type), |
368 by (EVERY1 [dtac (ord_iso_is_bij RS bij_is_fun RS apply_type), |
371 assume_tac]); |
369 assume_tac]); |
372 (*Now we also know f`x : pred(A,x,r); contradiction! *) |
370 (*Now we also know f`x : pred(A,x,r); contradiction! *) |
373 by (asm_full_simp_tac (simpset() addsimps [well_ord_def, pred_def]) 1); |
371 by (asm_full_simp_tac (simpset() addsimps [well_ord_def, pred_def]) 1); |
374 qed "well_ord_iso_predE"; |
372 qed "well_ord_iso_predE"; |
375 |
373 |
376 (*Simple consequence of Lemma 6.1*) |
374 (*Simple consequence of Lemma 6.1*) |
377 Goal |
375 Goal "[| well_ord(A,r); f : ord_iso(pred(A,a,r), r, pred(A,c,r), r); \ |
378 "[| well_ord(A,r); f : ord_iso(pred(A,a,r), r, pred(A,c,r), r); \ |
|
379 \ a:A; c:A |] ==> a=c"; |
376 \ a:A; c:A |] ==> a=c"; |
380 by (forward_tac [well_ord_is_trans_on] 1); |
377 by (forward_tac [well_ord_is_trans_on] 1); |
381 by (forward_tac [well_ord_is_linear] 1); |
378 by (forward_tac [well_ord_is_linear] 1); |
382 by (linear_case_tac 1); |
379 by (linear_case_tac 1); |
383 by (dtac ord_iso_sym 1); |
380 by (dtac ord_iso_sym 1); |
402 by (asm_simp_tac bij_inverse_ss 1); |
399 by (asm_simp_tac bij_inverse_ss 1); |
403 qed "ord_iso_image_pred"; |
400 qed "ord_iso_image_pred"; |
404 |
401 |
405 (*But in use, A and B may themselves be initial segments. Then use |
402 (*But in use, A and B may themselves be initial segments. Then use |
406 trans_pred_pred_eq to simplify the pred(pred...) terms. See just below.*) |
403 trans_pred_pred_eq to simplify the pred(pred...) terms. See just below.*) |
407 Goal |
404 Goal "[| f : ord_iso(A,r,B,s); a:A |] ==> \ |
408 "[| f : ord_iso(A,r,B,s); a:A |] ==> \ |
|
409 \ restrict(f, pred(A,a,r)) : ord_iso(pred(A,a,r), r, pred(B, f`a, s), s)"; |
405 \ restrict(f, pred(A,a,r)) : ord_iso(pred(A,a,r), r, pred(B, f`a, s), s)"; |
410 by (asm_simp_tac (simpset() addsimps [ord_iso_image_pred RS sym]) 1); |
406 by (asm_simp_tac (simpset() addsimps [ord_iso_image_pred RS sym]) 1); |
411 by (rewtac ord_iso_def); |
407 by (rewtac ord_iso_def); |
412 by (etac CollectE 1); |
408 by (etac CollectE 1); |
413 by (rtac CollectI 1); |
409 by (rtac CollectI 1); |
414 by (asm_full_simp_tac (simpset() addsimps [pred_def]) 2); |
410 by (asm_full_simp_tac (simpset() addsimps [pred_def]) 2); |
415 by (eresolve_tac [[bij_is_inj, pred_subset] MRS restrict_bij] 1); |
411 by (eresolve_tac [[bij_is_inj, pred_subset] MRS restrict_bij] 1); |
416 qed "ord_iso_restrict_pred"; |
412 qed "ord_iso_restrict_pred"; |
417 |
413 |
418 (*Tricky; a lot of forward proof!*) |
414 (*Tricky; a lot of forward proof!*) |
419 Goal |
415 Goal "[| well_ord(A,r); well_ord(B,s); <a,c>: r; \ |
420 "[| well_ord(A,r); well_ord(B,s); <a,c>: r; \ |
|
421 \ f : ord_iso(pred(A,a,r), r, pred(B,b,s), s); \ |
416 \ f : ord_iso(pred(A,a,r), r, pred(B,b,s), s); \ |
422 \ g : ord_iso(pred(A,c,r), r, pred(B,d,s), s); \ |
417 \ g : ord_iso(pred(A,c,r), r, pred(B,d,s), s); \ |
423 \ a:A; c:A; b:B; d:B |] ==> <b,d>: s"; |
418 \ a:A; c:A; b:B; d:B |] ==> <b,d>: s"; |
424 by (forward_tac [ord_iso_is_bij RS bij_is_fun RS apply_type] 1 THEN |
419 by (forward_tac [ord_iso_is_bij RS bij_is_fun RS apply_type] 1 THEN |
425 REPEAT1 (eresolve_tac [asm_rl, predI, predE] 1)); |
420 REPEAT1 (eresolve_tac [asm_rl, predI, predE] 1)); |
437 |
432 |
438 val bij_apply_cs = claset() addSIs [bij_converse_bij] |
433 val bij_apply_cs = claset() addSIs [bij_converse_bij] |
439 addIs [ord_iso_is_bij, bij_is_fun, apply_funtype]; |
434 addIs [ord_iso_is_bij, bij_is_fun, apply_funtype]; |
440 |
435 |
441 (*See Halmos, page 72*) |
436 (*See Halmos, page 72*) |
442 Goal |
437 Goal "[| well_ord(A,r); \ |
443 "[| well_ord(A,r); \ |
|
444 \ f: ord_iso(A,r, B,s); g: ord_iso(A,r, B,s); y: A |] \ |
438 \ f: ord_iso(A,r, B,s); g: ord_iso(A,r, B,s); y: A |] \ |
445 \ ==> ~ <g`y, f`y> : s"; |
439 \ ==> ~ <g`y, f`y> : s"; |
446 by (forward_tac [well_ord_iso_subset_lemma] 1); |
440 by (forward_tac [well_ord_iso_subset_lemma] 1); |
447 by (res_inst_tac [("f","converse(f)"), ("g","g")] ord_iso_trans 1); |
441 by (res_inst_tac [("f","converse(f)"), ("g","g")] ord_iso_trans 1); |
448 by (REPEAT_FIRST (ares_tac [subset_refl, ord_iso_sym])); |
442 by (REPEAT_FIRST (ares_tac [subset_refl, ord_iso_sym])); |
451 by (EVERY (map (blast_tac bij_apply_cs) [1,1,1])); |
445 by (EVERY (map (blast_tac bij_apply_cs) [1,1,1])); |
452 by (asm_full_simp_tac bij_inverse_ss 1); |
446 by (asm_full_simp_tac bij_inverse_ss 1); |
453 qed "well_ord_iso_unique_lemma"; |
447 qed "well_ord_iso_unique_lemma"; |
454 |
448 |
455 (*Kunen's Lemma 6.2: Order-isomorphisms between well-orderings are unique*) |
449 (*Kunen's Lemma 6.2: Order-isomorphisms between well-orderings are unique*) |
456 Goal |
450 Goal "[| well_ord(A,r); \ |
457 "[| well_ord(A,r); \ |
|
458 \ f: ord_iso(A,r, B,s); g: ord_iso(A,r, B,s) |] ==> f = g"; |
451 \ f: ord_iso(A,r, B,s); g: ord_iso(A,r, B,s) |] ==> f = g"; |
459 by (rtac fun_extension 1); |
452 by (rtac fun_extension 1); |
460 by (REPEAT (etac (ord_iso_is_bij RS bij_is_fun) 1)); |
453 by (REPEAT (etac (ord_iso_is_bij RS bij_is_fun) 1)); |
461 by (subgoals_tac ["f`x : B", "g`x : B", "linear(B,s)"] 1); |
454 by (subgoals_tac ["f`x : B", "g`x : B", "linear(B,s)"] 1); |
462 by (REPEAT (blast_tac bij_apply_cs 3)); |
455 by (REPEAT (blast_tac bij_apply_cs 3)); |
490 "well_ord(B,s) ==> function(ord_iso_map(A,r,B,s))"; |
483 "well_ord(B,s) ==> function(ord_iso_map(A,r,B,s))"; |
491 by (blast_tac (claset() addIs [well_ord_iso_pred_eq, |
484 by (blast_tac (claset() addIs [well_ord_iso_pred_eq, |
492 ord_iso_sym, ord_iso_trans]) 1); |
485 ord_iso_sym, ord_iso_trans]) 1); |
493 qed "function_ord_iso_map"; |
486 qed "function_ord_iso_map"; |
494 |
487 |
495 Goal |
488 Goal "well_ord(B,s) ==> ord_iso_map(A,r,B,s) \ |
496 "well_ord(B,s) ==> ord_iso_map(A,r,B,s) \ |
|
497 \ : domain(ord_iso_map(A,r,B,s)) -> range(ord_iso_map(A,r,B,s))"; |
489 \ : domain(ord_iso_map(A,r,B,s)) -> range(ord_iso_map(A,r,B,s))"; |
498 by (asm_simp_tac |
490 by (asm_simp_tac |
499 (simpset() addsimps [Pi_iff, function_ord_iso_map, |
491 (simpset() addsimps [Pi_iff, function_ord_iso_map, |
500 ord_iso_map_subset RS domain_times_range]) 1); |
492 ord_iso_map_subset RS domain_times_range]) 1); |
501 qed "ord_iso_map_fun"; |
493 qed "ord_iso_map_fun"; |
549 (simpset() addsimps [well_ord_is_trans_on, trans_pred_pred_eq]) 1); |
541 (simpset() addsimps [well_ord_is_trans_on, trans_pred_pred_eq]) 1); |
550 by (Blast_tac 1); |
542 by (Blast_tac 1); |
551 qed "domain_ord_iso_map_subset"; |
543 qed "domain_ord_iso_map_subset"; |
552 |
544 |
553 (*For the 4-way case analysis in the main result*) |
545 (*For the 4-way case analysis in the main result*) |
554 Goal |
546 Goal "[| well_ord(A,r); well_ord(B,s) |] ==> \ |
555 "[| well_ord(A,r); well_ord(B,s) |] ==> \ |
|
556 \ domain(ord_iso_map(A,r,B,s)) = A | \ |
547 \ domain(ord_iso_map(A,r,B,s)) = A | \ |
557 \ (EX x:A. domain(ord_iso_map(A,r,B,s)) = pred(A,x,r))"; |
548 \ (EX x:A. domain(ord_iso_map(A,r,B,s)) = pred(A,x,r))"; |
558 by (forward_tac [well_ord_is_wf] 1); |
549 by (forward_tac [well_ord_is_wf] 1); |
559 by (rewrite_goals_tac [wf_on_def, wf_def]); |
550 by (rewrite_goals_tac [wf_on_def, wf_def]); |
560 by (dres_inst_tac [("x", "A-domain(ord_iso_map(A,r,B,s))")] spec 1); |
551 by (dres_inst_tac [("x", "A-domain(ord_iso_map(A,r,B,s))")] spec 1); |
570 by (blast_tac (claset() addSEs [predE]) 2); |
561 by (blast_tac (claset() addSEs [predE]) 2); |
571 by (REPEAT (ares_tac [domain_ord_iso_map_subset] 1)); |
562 by (REPEAT (ares_tac [domain_ord_iso_map_subset] 1)); |
572 qed "domain_ord_iso_map_cases"; |
563 qed "domain_ord_iso_map_cases"; |
573 |
564 |
574 (*As above, by duality*) |
565 (*As above, by duality*) |
575 Goal |
566 Goal "[| well_ord(A,r); well_ord(B,s) |] ==> \ |
576 "[| well_ord(A,r); well_ord(B,s) |] ==> \ |
|
577 \ range(ord_iso_map(A,r,B,s)) = B | \ |
567 \ range(ord_iso_map(A,r,B,s)) = B | \ |
578 \ (EX y:B. range(ord_iso_map(A,r,B,s))= pred(B,y,s))"; |
568 \ (EX y:B. range(ord_iso_map(A,r,B,s))= pred(B,y,s))"; |
579 by (resolve_tac [converse_ord_iso_map RS subst] 1); |
569 by (resolve_tac [converse_ord_iso_map RS subst] 1); |
580 by (asm_simp_tac |
570 by (asm_simp_tac |
581 (simpset() addsimps [range_converse, domain_ord_iso_map_cases]) 1); |
571 (simpset() addsimps [range_converse, domain_ord_iso_map_cases]) 1); |
582 qed "range_ord_iso_map_cases"; |
572 qed "range_ord_iso_map_cases"; |
583 |
573 |
584 (*Kunen's Theorem 6.3: Fundamental Theorem for Well-Ordered Sets*) |
574 (*Kunen's Theorem 6.3: Fundamental Theorem for Well-Ordered Sets*) |
585 Goal |
575 Goal "[| well_ord(A,r); well_ord(B,s) |] ==> \ |
586 "[| well_ord(A,r); well_ord(B,s) |] ==> \ |
|
587 \ ord_iso_map(A,r,B,s) : ord_iso(A, r, B, s) | \ |
576 \ ord_iso_map(A,r,B,s) : ord_iso(A, r, B, s) | \ |
588 \ (EX x:A. ord_iso_map(A,r,B,s) : ord_iso(pred(A,x,r), r, B, s)) | \ |
577 \ (EX x:A. ord_iso_map(A,r,B,s) : ord_iso(pred(A,x,r), r, B, s)) | \ |
589 \ (EX y:B. ord_iso_map(A,r,B,s) : ord_iso(A, r, pred(B,y,s), s))"; |
578 \ (EX y:B. ord_iso_map(A,r,B,s) : ord_iso(A, r, pred(B,y,s), s))"; |
590 by (forw_inst_tac [("B","B")] domain_ord_iso_map_cases 1); |
579 by (forw_inst_tac [("B","B")] domain_ord_iso_map_cases 1); |
591 by (forw_inst_tac [("B","B")] range_ord_iso_map_cases 2); |
580 by (forw_inst_tac [("B","B")] range_ord_iso_map_cases 2); |