src/ZF/Order.ML

Addition of cardinals and order types, various tidying

(*  Title: 	ZF/Order.ML
    ID:         $Id$
    Author: 	Lawrence C Paulson, Cambridge University Computer Laboratory
    Copyright   1994  University of Cambridge

For Order.thy.  Orders in Zermelo-Fraenkel Set Theory 
*)

(*TO PURE/TACTIC.ML*)
fun subgoals_tac sprops = EVERY' (map subgoal_tac sprops);


open Order;

val bij_apply_cs = ZF_cs addSEs [bij_converse_bij]
                         addIs  [bij_is_fun, apply_type];

val bij_inverse_ss = 
    ZF_ss addsimps [bij_is_fun RS apply_type,
		    bij_converse_bij RS bij_is_fun RS apply_type,
		    left_inverse_bij, right_inverse_bij];

(** Basic properties of the definitions **)

(*needed????*)
goalw Order.thy [part_ord_def, irrefl_def, trans_on_def, asym_def]
    "!!r. part_ord(A,r) ==> asym(r Int A*A)";
by (fast_tac ZF_cs 1);
val part_ord_Imp_asym = result();

(** Order-isomorphisms **)

goalw Order.thy [ord_iso_def] 
    "!!f. f: ord_iso(A,r,B,s) ==> f: bij(A,B)";
by (etac CollectD1 1);
val ord_iso_is_bij = result();

goalw Order.thy [ord_iso_def] 
    "!!f. [| f: ord_iso(A,r,B,s);  <x,y>: r;  x:A;  y:A |] ==> \
\         <f`x, f`y> : s";
by (fast_tac ZF_cs 1);
val ord_iso_apply = result();

goalw Order.thy [ord_iso_def] 
    "!!f. [| f: ord_iso(A,r,B,s);  <x,y>: s;  x:B;  y:B |] ==> \
\         <converse(f) ` x, converse(f) ` y> : r";
be CollectE 1;
be (bspec RS bspec RS iffD2) 1;
by (REPEAT (eresolve_tac [asm_rl, 
			  bij_converse_bij RS bij_is_fun RS apply_type] 1));
by (asm_simp_tac (ZF_ss addsimps [right_inverse_bij]) 1);
val ord_iso_converse = result();

val major::premx::premy::prems = goalw Order.thy [linear_def]
    "[| linear(A,r);  x:A;  y:A;  \
\       <x,y>:r ==> P;  x=y ==> P;  <y,x>:r ==> P |] ==> P";
by (cut_facts_tac [major,premx,premy] 1);
by (REPEAT_FIRST (eresolve_tac [ballE,disjE]));
by (EVERY1 (map etac prems));
by (ALLGOALS contr_tac);
val linearE = result();

(*Does the case analysis, deleting linear(A,r) and proving trivial subgoals*)
val linear_case_tac =
    SELECT_GOAL (EVERY [etac linearE 1, assume_tac 1, assume_tac 1,
			REPEAT_SOME assume_tac]);

(*Inductive argument for proving Kunen's Lemma 6.1*)
goalw Order.thy [well_ord_def, tot_ord_def, part_ord_def, pred_def]
  "!!r. [| well_ord(A,r);  x: A;  f: ord_iso(A, r, pred(A,x,r), r);  y: A |] \
\       ==> f`y = y";
by (safe_tac ZF_cs);
by (wf_on_ind_tac "y" [] 1);
by (forward_tac [ord_iso_is_bij] 1);
by (subgoal_tac "f`y1 : {y: A . <y, x> : r}" 1);
by (fast_tac (ZF_cs addSEs [bij_is_fun RS apply_type]) 2);
(*Now we know f`y1 : A  and  <f`y1, x> : r  *)
by (etac CollectE 1);
by (linear_case_tac 1);
(*Case  <f`y1, y1> : r *)   (*use induction hyp*)
by (dtac bspec 1 THEN mp_tac 2 THEN assume_tac 1);
by (dres_inst_tac [("t", "op `(converse(f))")] subst_context 1);
by (asm_full_simp_tac (ZF_ss addsimps [left_inverse_bij]) 1);
(*The case  <y1, f`y1> : r  *)
by (subgoal_tac "<y1,x> : r" 1);
by (fast_tac (ZF_cs addSEs [trans_onD]) 2);
by (dtac ord_iso_converse 1 THEN assume_tac 1 THEN fast_tac ZF_cs 2);
by (fast_tac ZF_cs 1);
by (asm_full_simp_tac (ZF_ss addsimps [left_inverse_bij]) 1);
(*now use induction hyp*)
by (dtac bspec 1 THEN mp_tac 2 THEN fast_tac bij_apply_cs 1);
by (dres_inst_tac [("t", "op `(f)")] subst_context 1);
by (asm_full_simp_tac (ZF_ss addsimps [right_inverse_bij]) 1);
val not_well_ord_iso_pred_lemma = result();


(*Kunen's Lemma 6.1: there's no order-isomorphism to an initial segment
                     of a well-ordering*)
goal Order.thy
    "!!r. [| well_ord(A,r);  x:A |] ==> \
\         ALL f. f ~: ord_iso(A, r, pred(A,x,r), r)";
by (safe_tac ZF_cs);
by (metacut_tac not_well_ord_iso_pred_lemma 1);
by (REPEAT_SOME assume_tac);
(*Now we know f`x = x*)
by (EVERY1 [dtac (ord_iso_is_bij RS bij_is_fun RS apply_type),
	     assume_tac]);
(*Now we know f`x : pred(A,x,r) *)
by (asm_full_simp_tac (ZF_ss addsimps [well_ord_def, pred_def]) 1);
by (fast_tac (ZF_cs addSEs [wf_on_not_refl RS notE]) 1);
val not_well_ord_iso_pred = result();


(*Inductive argument for proving Kunen's Lemma 6.2*)
goalw Order.thy [well_ord_def, tot_ord_def, part_ord_def]
    "!!r. [| well_ord(A,r);  well_ord(B,s);  \
\            f: ord_iso(A,r, B,s);  g: ord_iso(A,r, B,s);  y: A |] \
\         ==> f`y = g`y";
by (safe_tac ZF_cs);
by (wf_on_ind_tac "y" [] 1);
by (subgoals_tac ["f: bij(A,B)", "g: bij(A,B)", "f`y1 : B", "g`y1 : B"] 1);
by (REPEAT (fast_tac (bij_apply_cs addSEs [ord_iso_is_bij]) 2));
by (linear_case_tac 1);
(*The case  <f`y1, g`y1> : s  *)
by (forw_inst_tac [("f","g")] ord_iso_converse 1 THEN REPEAT (assume_tac 1));
by (asm_full_simp_tac (ZF_ss addsimps [left_inverse_bij]) 1);
by (dtac bspec 1 THEN mp_tac 2 THEN fast_tac bij_apply_cs 1);
by (dres_inst_tac [("t", "op `(converse(f))")] subst_context 1);
by (dres_inst_tac [("t", "op `(g)")] subst_context 1);
by (asm_full_simp_tac bij_inverse_ss 1);
(*The case  <g`y1, f`y1> : s  *)
by (forw_inst_tac [("f","f")] ord_iso_converse 1 THEN REPEAT (assume_tac 1));
by (asm_full_simp_tac (ZF_ss addsimps [left_inverse_bij]) 1);
by (dtac bspec 1 THEN mp_tac 2 THEN fast_tac bij_apply_cs 1);
by (dres_inst_tac [("t", "op `(converse(g))")] subst_context 1);
by (dres_inst_tac [("t", "op `(f)")] subst_context 1);
by (asm_full_simp_tac bij_inverse_ss 1);
val well_ord_iso_unique_lemma = result();


(*Kunen's Lemma 6.2: Order-isomorphisms between well-orderings are unique*)
goal Order.thy
    "!!r. [| well_ord(A,r);  well_ord(B,s);  \
\            f: ord_iso(A,r, B,s);  g: ord_iso(A,r, B,s) |] ==> f = g";
br fun_extension 1;
be (ord_iso_is_bij RS bij_is_fun) 1;
be (ord_iso_is_bij RS bij_is_fun) 1;
br well_ord_iso_unique_lemma 1;
by (REPEAT_SOME assume_tac);
val well_ord_iso_unique = result();


goalw Order.thy [irrefl_def, part_ord_def, tot_ord_def, 
		 trans_on_def, well_ord_def]
    "!!r. [| wf[A](r); linear(A,r) |] ==> well_ord(A,r)";
by (asm_simp_tac (ZF_ss addsimps [wf_on_not_refl]) 1);
by (safe_tac ZF_cs);
by (linear_case_tac 1);
(*case x=xb*)
by (fast_tac (ZF_cs addSEs [wf_on_anti_sym]) 1);
(*case x<xb*)
by (fast_tac (ZF_cs addSEs [wf_on_chain3]) 1);
val well_ordI = result();

goalw Order.thy [well_ord_def]
    "!!r. well_ord(A,r) ==> wf[A](r)";
by (safe_tac ZF_cs);
val well_ord_is_wf = result();


(*** Derived rules for pred(A,x,r) ***)

val [major,minor] = goalw Order.thy [pred_def]
    "[| y: pred(A,x,r);  [| y:A; <y,x>:r |] ==> P |] ==> P";
br (major RS CollectE) 1;
by (REPEAT (ares_tac [minor] 1));
val predE = result();

goalw Order.thy [pred_def] "pred(A,x,r) <= r -`` {x}";
by (fast_tac ZF_cs 1);
val pred_subset_under = result();

goalw Order.thy [pred_def] "pred(A,x,r) <= A";
by (fast_tac ZF_cs 1);
val pred_subset = result();