--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/ZF/OrderArith.ML Thu Jun 23 17:38:12 1994 +0200
@@ -0,0 +1,246 @@
+(* Title: ZF/OrderArith.ML
+ ID: $Id$
+ Author: Lawrence C Paulson, Cambridge University Computer Laboratory
+ Copyright 1994 University of Cambridge
+
+Towards ordinal arithmetic
+*)
+
+(*for deleting an unwanted assumption*)
+val thin = prove_goal pure_thy "[| PROP P; PROP Q |] ==> PROP Q"
+ (fn prems => [resolve_tac prems 1]);
+
+open OrderArith;
+
+
+(**** Addition of relations -- disjoint sum ****)
+
+(** Rewrite rules. Can be used to obtain introduction rules **)
+
+goalw OrderArith.thy [radd_def]
+ "<Inl(a), Inr(b)> : radd(A,r,B,s) <-> a:A & b:B";
+by (fast_tac sum_cs 1);
+val radd_Inl_Inr_iff = result();
+
+goalw OrderArith.thy [radd_def]
+ "<Inl(a'), Inl(a)> : radd(A,r,B,s) <-> <a',a>:r & a':A & a:A";
+by (fast_tac sum_cs 1);
+val radd_Inl_iff = result();
+
+goalw OrderArith.thy [radd_def]
+ "<Inr(b'), Inr(b)> : radd(A,r,B,s) <-> <b',b>:s & b':B & b:B";
+by (fast_tac sum_cs 1);
+val radd_Inr_iff = result();
+
+goalw OrderArith.thy [radd_def]
+ "<Inr(b), Inl(a)> : radd(A,r,B,s) <-> False";
+by (fast_tac sum_cs 1);
+val radd_Inr_Inl_iff = result();
+
+(** Elimination Rule **)
+
+val major::prems = goalw OrderArith.thy [radd_def]
+ "[| <p',p> : radd(A,r,B,s); \
+\ !!x y. [| p'=Inl(x); x:A; p=Inr(y); y:B |] ==> Q; \
+\ !!x' x. [| p'=Inl(x'); p=Inl(x); <x',x>: r; x':A; x:A |] ==> Q; \
+\ !!y' y. [| p'=Inr(y'); p=Inr(y); <y',y>: s; y':B; y:B |] ==> Q \
+\ |] ==> Q";
+by (cut_facts_tac [major] 1);
+(*Split into the three cases*)
+by (REPEAT_FIRST
+ (eresolve_tac [CollectE, Pair_inject, conjE, exE, SigmaE, disjE]));
+(*Apply each premise to correct subgoal; can't just use fast_tac
+ because hyp_subst_tac would delete equalities too quickly*)
+by (EVERY (map (fn prem =>
+ EVERY1 [rtac prem, assume_tac, REPEAT o fast_tac sum_cs])
+ prems));
+val raddE = result();
+
+(** Type checking **)
+
+goalw OrderArith.thy [radd_def] "radd(A,r,B,s) <= (A+B) * (A+B)";
+by (rtac Collect_subset 1);
+val radd_type = result();
+
+val field_radd = standard (radd_type RS field_rel_subset);
+
+(** Linearity **)
+
+val sum_ss = ZF_ss addsimps [Pair_iff, InlI, InrI, Inl_iff, Inr_iff,
+ Inl_Inr_iff, Inr_Inl_iff];
+
+val radd_ss = sum_ss addsimps [radd_Inl_iff, radd_Inr_iff,
+ radd_Inl_Inr_iff, radd_Inr_Inl_iff];
+
+goalw OrderArith.thy [linear_def]
+ "!!r s. [| linear(A,r); linear(B,s) |] ==> linear(A+B,radd(A,r,B,s))";
+by (REPEAT_FIRST (ares_tac [ballI] ORELSE' etac sumE));
+by (ALLGOALS (asm_simp_tac radd_ss));
+val linear_radd = result();
+
+
+(** Well-foundedness **)
+
+goal OrderArith.thy
+ "!!r s. [| wf[A](r); wf[B](s) |] ==> wf[A+B](radd(A,r,B,s))";
+by (rtac wf_onI2 1);
+by (subgoal_tac "ALL x:A. Inl(x): Ba" 1);
+(*Proving the lemma, which is needed twice!*)
+by (eres_inst_tac [("P", "y : A + B")] thin 2);
+by (rtac ballI 2);
+by (eres_inst_tac [("r","r"),("a","x")] wf_on_induct 2 THEN assume_tac 2);
+by (etac (bspec RS mp) 2);
+by (fast_tac sum_cs 2);
+by (best_tac (sum_cs addSEs [raddE]) 2);
+(*Returning to main part of proof*)
+by (REPEAT_FIRST (eresolve_tac [sumE, ssubst]));
+by (best_tac sum_cs 1);
+by (eres_inst_tac [("r","s"),("a","ya")] wf_on_induct 1 THEN assume_tac 1);
+by (etac (bspec RS mp) 1);
+by (fast_tac sum_cs 1);
+by (best_tac (sum_cs addSEs [raddE]) 1);
+val wf_on_radd = result();
+
+goal OrderArith.thy
+ "!!r s. [| wf(r); wf(s) |] ==> wf(radd(field(r),r,field(s),s))";
+by (asm_full_simp_tac (ZF_ss addsimps [wf_iff_wf_on_field]) 1);
+by (rtac (field_radd RSN (2, wf_on_subset_A)) 1);
+by (REPEAT (ares_tac [wf_on_radd] 1));
+val wf_radd = result();
+
+goal OrderArith.thy
+ "!!r s. [| well_ord(A,r); well_ord(B,s) |] ==> \
+\ well_ord(A+B, radd(A,r,B,s))";
+by (rtac well_ordI 1);
+by (asm_full_simp_tac (ZF_ss addsimps [well_ord_def, wf_on_radd]) 1);
+by (asm_full_simp_tac
+ (ZF_ss addsimps [well_ord_def, tot_ord_def, linear_radd]) 1);
+val well_ord_radd = result();
+
+
+(**** Multiplication of relations -- lexicographic product ****)
+
+(** Rewrite rule. Can be used to obtain introduction rules **)
+
+goalw OrderArith.thy [rmult_def]
+ "!!r s. <<a',b'>, <a,b>> : rmult(A,r,B,s) <-> \
+\ (<a',a>: r & a':A & a:A & b': B & b: B) | \
+\ (<b',b>: s & a'=a & a:A & b': B & b: B)";
+by (fast_tac ZF_cs 1);
+val rmult_iff = result();
+
+val major::prems = goal OrderArith.thy
+ "[| <<a',b'>, <a,b>> : rmult(A,r,B,s); \
+\ [| <a',a>: r; a':A; a:A; b':B; b:B |] ==> Q; \
+\ [| <b',b>: s; a:A; a'=a; b':B; b:B |] ==> Q \
+\ |] ==> Q";
+by (rtac (major RS (rmult_iff RS iffD1) RS disjE) 1);
+by (DEPTH_SOLVE (eresolve_tac ([asm_rl, conjE] @ prems) 1));
+val rmultE = result();
+
+(** Type checking **)
+
+goalw OrderArith.thy [rmult_def] "rmult(A,r,B,s) <= (A*B) * (A*B)";
+by (rtac Collect_subset 1);
+val rmult_type = result();
+
+val field_rmult = standard (rmult_type RS field_rel_subset);
+
+(** Linearity **)
+
+val [lina,linb] = goal OrderArith.thy
+ "[| linear(A,r); linear(B,s) |] ==> linear(A*B,rmult(A,r,B,s))";
+by (rewtac linear_def); (*Note! the premises are NOT rewritten*)
+by (REPEAT_FIRST (ares_tac [ballI] ORELSE' etac SigmaE));
+by (asm_simp_tac (ZF_ss addsimps [rmult_iff]) 1);
+by (res_inst_tac [("x","xa"), ("y","xb")] (lina RS linearE) 1);
+by (res_inst_tac [("x","ya"), ("y","yb")] (linb RS linearE) 4);
+by (REPEAT_SOME (fast_tac ZF_cs));
+val linear_rmult = result();
+
+
+(** Well-foundedness **)
+
+goal OrderArith.thy
+ "!!r s. [| wf[A](r); wf[B](s) |] ==> wf[A*B](rmult(A,r,B,s))";
+by (rtac wf_onI2 1);
+by (etac SigmaE 1);
+by (etac ssubst 1);
+by (subgoal_tac "ALL b:B. <x,b>: Ba" 1);
+by (fast_tac ZF_cs 1);
+by (eres_inst_tac [("a","x")] wf_on_induct 1 THEN assume_tac 1);
+by (rtac ballI 1);
+by (eres_inst_tac [("a","b")] wf_on_induct 1 THEN assume_tac 1);
+by (etac (bspec RS mp) 1);
+by (fast_tac ZF_cs 1);
+by (best_tac (ZF_cs addSEs [rmultE]) 1);
+val wf_on_rmult = result();
+
+
+goal OrderArith.thy
+ "!!r s. [| wf(r); wf(s) |] ==> wf(rmult(field(r),r,field(s),s))";
+by (asm_full_simp_tac (ZF_ss addsimps [wf_iff_wf_on_field]) 1);
+by (rtac (field_rmult RSN (2, wf_on_subset_A)) 1);
+by (REPEAT (ares_tac [wf_on_rmult] 1));
+val wf_rmult = result();
+
+goal OrderArith.thy
+ "!!r s. [| well_ord(A,r); well_ord(B,s) |] ==> \
+\ well_ord(A*B, rmult(A,r,B,s))";
+by (rtac well_ordI 1);
+by (asm_full_simp_tac (ZF_ss addsimps [well_ord_def, wf_on_rmult]) 1);
+by (asm_full_simp_tac
+ (ZF_ss addsimps [well_ord_def, tot_ord_def, linear_rmult]) 1);
+val well_ord_rmult = result();
+
+
+(**** Inverse image of a relation ****)
+
+(** Rewrite rule **)
+
+goalw OrderArith.thy [rvimage_def]
+ "<a,b> : rvimage(A,f,r) <-> <f`a,f`b>: r & a:A & b:A";
+by (fast_tac ZF_cs 1);
+val rvimage_iff = result();
+
+(** Type checking **)
+
+goalw OrderArith.thy [rvimage_def] "rvimage(A,f,r) <= A*A";
+by (rtac Collect_subset 1);
+val rvimage_type = result();
+
+val field_rvimage = standard (rvimage_type RS field_rel_subset);
+
+
+(** Linearity **)
+
+val [finj,lin] = goalw OrderArith.thy [inj_def]
+ "[| f: inj(A,B); linear(B,r) |] ==> linear(A,rvimage(A,f,r))";
+by (rewtac linear_def); (*Note! the premises are NOT rewritten*)
+by (REPEAT_FIRST (ares_tac [ballI]));
+by (asm_simp_tac (ZF_ss addsimps [rvimage_iff]) 1);
+by (cut_facts_tac [finj] 1);
+by (res_inst_tac [("x","f`x"), ("y","f`y")] (lin RS linearE) 1);
+by (REPEAT_SOME (fast_tac (ZF_cs addSIs [apply_type])));
+val linear_rvimage = result();
+
+
+(** Well-foundedness **)
+
+goal OrderArith.thy
+ "!!r. [| f: A->B; wf[B](r) |] ==> wf[A](rvimage(A,f,r))";
+by (rtac wf_onI2 1);
+by (subgoal_tac "ALL z:A. f`z=f`y --> z: Ba" 1);
+by (fast_tac ZF_cs 1);
+by (eres_inst_tac [("a","f`y")] wf_on_induct 1);
+by (fast_tac (ZF_cs addSIs [apply_type]) 1);
+by (best_tac (ZF_cs addSIs [apply_type] addSDs [rvimage_iff RS iffD1]) 1);
+val wf_on_rvimage = result();
+
+goal OrderArith.thy
+ "!!r. [| f: inj(A,B); well_ord(B,r) |] ==> well_ord(A, rvimage(A,f,r))";
+by (rtac well_ordI 1);
+by (rewrite_goals_tac [well_ord_def, tot_ord_def]);
+by (fast_tac (ZF_cs addSIs [wf_on_rvimage, inj_is_fun]) 1);
+by (fast_tac (ZF_cs addSIs [linear_rvimage]) 1);
+val well_ord_rvimage = result();