src/ZF/Order.ML
changeset 5268 59ef39008514
parent 5262 212d203d6cd3
child 5488 9df083aed63d
equal deleted inserted replaced
5267:41a01176b9de 5268:59ef39008514
    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);