diff -r 3a8d722fd3ff -r 16c4ea954511 Univ.ML --- a/Univ.ML Fri Nov 11 10:35:03 1994 +0100 +++ b/Univ.ML Mon Nov 21 17:50:34 1994 +0100 @@ -17,7 +17,7 @@ by (fast_tac (HOL_cs addSIs [prem1,prem2]) 1); by (cut_facts_tac [less_linear] 1); by (fast_tac (HOL_cs addSIs [prem1] addSDs [prem2]) 1); -val Least_equality = result(); +qed "Least_equality"; val [prem] = goal Univ.thy "P(k) ==> P(LEAST x.P(x))"; by (rtac (prem RS rev_mp) 1); @@ -28,7 +28,7 @@ by (assume_tac 1); by (assume_tac 2); by (fast_tac HOL_cs 1); -val LeastI = result(); +qed "LeastI"; (*Proof is almost identical to the one above!*) val [prem] = goal Univ.thy "P(k) ==> (LEAST x.P(x)) <= k"; @@ -40,20 +40,20 @@ by (assume_tac 1); by (rtac le_refl 2); by (fast_tac (HOL_cs addIs [less_imp_le,le_trans]) 1); -val Least_le = result(); +qed "Least_le"; val [prem] = goal Univ.thy "k < (LEAST x.P(x)) ==> ~P(k)"; by (rtac notI 1); by (etac (rewrite_rule [le_def] Least_le RS notE) 1); by (rtac prem 1); -val not_less_Least = result(); +qed "not_less_Least"; (** apfst -- can be used in similar type definitions **) goalw Univ.thy [apfst_def] "apfst(f,) = "; by (rtac split 1); -val apfst = result(); +qed "apfst"; val [major,minor] = goal Univ.thy "[| q = apfst(f,p); !!x y. [| p = ; q = |] ==> R \ @@ -64,7 +64,7 @@ by (rtac (major RS trans) 1); by (etac ssubst 1); by (rtac apfst 1); -val apfstE = result(); +qed "apfstE"; (** Push -- an injection, analogous to Cons on lists **) @@ -72,37 +72,37 @@ by (rtac (major RS fun_cong RS box_equals RS Suc_inject) 1); by (rtac nat_case_0 1); by (rtac nat_case_0 1); -val Push_inject1 = result(); +qed "Push_inject1"; val [major] = goalw Univ.thy [Push_def] "Push(i,f)=Push(j,g) ==> f=g"; by (rtac (major RS fun_cong RS ext RS box_equals) 1); by (rtac (nat_case_Suc RS ext) 1); by (rtac (nat_case_Suc RS ext) 1); -val Push_inject2 = result(); +qed "Push_inject2"; val [major,minor] = goal Univ.thy "[| Push(i,f)=Push(j,g); [| i=j; f=g |] ==> P \ \ |] ==> P"; by (rtac ((major RS Push_inject2) RS ((major RS Push_inject1) RS minor)) 1); -val Push_inject = result(); +qed "Push_inject"; val [major] = goalw Univ.thy [Push_def] "Push(k,f)=(%z.0) ==> P"; by (rtac (major RS fun_cong RS box_equals RS Suc_neq_Zero) 1); by (rtac nat_case_0 1); by (rtac refl 1); -val Push_neq_K0 = result(); +qed "Push_neq_K0"; (*** Isomorphisms ***) goal Univ.thy "inj(Rep_Node)"; by (rtac inj_inverseI 1); (*cannot combine by RS: multiple unifiers*) by (rtac Rep_Node_inverse 1); -val inj_Rep_Node = result(); +qed "inj_Rep_Node"; goal Univ.thy "inj_onto(Abs_Node,Node)"; by (rtac inj_onto_inverseI 1); by (etac Abs_Node_inverse 1); -val inj_onto_Abs_Node = result(); +qed "inj_onto_Abs_Node"; val Abs_Node_inject = inj_onto_Abs_Node RS inj_ontoD; @@ -111,12 +111,12 @@ goalw Univ.thy [Node_def] "<%k. 0,a> : Node"; by (fast_tac set_cs 1); -val Node_K0_I = result(); +qed "Node_K0_I"; goalw Univ.thy [Node_def,Push_def] "!!p. p: Node ==> apfst(Push(i), p) : Node"; by (fast_tac (set_cs addSIs [apfst, nat_case_Suc RS trans]) 1); -val Node_Push_I = result(); +qed "Node_Push_I"; (*** Distinctness of constructors ***) @@ -130,7 +130,7 @@ by (REPEAT (eresolve_tac [imageE, Abs_Node_inject RS apfstE, Pair_inject, sym RS Push_neq_K0] 1 ORELSE resolve_tac [Node_K0_I, Rep_Node RS Node_Push_I] 1)); -val Scons_not_Atom = result(); +qed "Scons_not_Atom"; val Atom_not_Scons = standard (Scons_not_Atom RS not_sym); val Scons_neq_Atom = standard (Scons_not_Atom RS notE); @@ -144,20 +144,20 @@ by (rtac injI 1); by (etac (singleton_inject RS Abs_Node_inject RS Pair_inject) 1); by (REPEAT (ares_tac [Node_K0_I] 1)); -val inj_Atom = result(); +qed "inj_Atom"; val Atom_inject = inj_Atom RS injD; goalw Univ.thy [Leaf_def,o_def] "inj(Leaf)"; by (rtac injI 1); by (etac (Atom_inject RS Inl_inject) 1); -val inj_Leaf = result(); +qed "inj_Leaf"; val Leaf_inject = inj_Leaf RS injD; goalw Univ.thy [Numb_def,o_def] "inj(Numb)"; by (rtac injI 1); by (etac (Atom_inject RS Inr_inject) 1); -val inj_Numb = result(); +qed "inj_Numb"; val Numb_inject = inj_Numb RS injD; @@ -175,7 +175,7 @@ by (rtac (inj_Rep_Node RS injD) 1); by (etac trans 1); by (safe_tac (HOL_cs addSEs [Pair_inject,Push_inject,sym])); -val Push_Node_inject = result(); +qed "Push_Node_inject"; (** Injectiveness of Scons **) @@ -184,38 +184,38 @@ by (cut_facts_tac [major] 1); by (fast_tac (set_cs addSDs [Suc_inject] addSEs [Push_Node_inject, Zero_neq_Suc]) 1); -val Scons_inject_lemma1 = result(); +qed "Scons_inject_lemma1"; val [major] = goalw Univ.thy [Scons_def] "M$N <= M'$N' ==> N<=N'"; by (cut_facts_tac [major] 1); by (fast_tac (set_cs addSDs [Suc_inject] addSEs [Push_Node_inject, Suc_neq_Zero]) 1); -val Scons_inject_lemma2 = result(); +qed "Scons_inject_lemma2"; val [major] = goal Univ.thy "M$N = M'$N' ==> M=M'"; by (rtac (major RS equalityE) 1); by (REPEAT (ares_tac [equalityI, Scons_inject_lemma1] 1)); -val Scons_inject1 = result(); +qed "Scons_inject1"; val [major] = goal Univ.thy "M$N = M'$N' ==> N=N'"; by (rtac (major RS equalityE) 1); by (REPEAT (ares_tac [equalityI, Scons_inject_lemma2] 1)); -val Scons_inject2 = result(); +qed "Scons_inject2"; val [major,minor] = goal Univ.thy "[| M$N = M'$N'; [| M=M'; N=N' |] ==> P \ \ |] ==> P"; by (rtac ((major RS Scons_inject2) RS ((major RS Scons_inject1) RS minor)) 1); -val Scons_inject = result(); +qed "Scons_inject"; (*rewrite rules*) goal Univ.thy "(Atom(a)=Atom(b)) = (a=b)"; by (fast_tac (HOL_cs addSEs [Atom_inject]) 1); -val Atom_Atom_eq = result(); +qed "Atom_Atom_eq"; goal Univ.thy "(M$N = M'$N') = (M=M' & N=N')"; by (fast_tac (HOL_cs addSEs [Scons_inject]) 1); -val Scons_Scons_eq = result(); +qed "Scons_Scons_eq"; (*** Distinctness involving Leaf and Numb ***) @@ -223,7 +223,7 @@ goalw Univ.thy [Leaf_def,o_def] "(M$N) ~= Leaf(a)"; by (rtac Scons_not_Atom 1); -val Scons_not_Leaf = result(); +qed "Scons_not_Leaf"; val Leaf_not_Scons = standard (Scons_not_Leaf RS not_sym); val Scons_neq_Leaf = standard (Scons_not_Leaf RS notE); @@ -233,7 +233,7 @@ goalw Univ.thy [Numb_def,o_def] "(M$N) ~= Numb(k)"; by (rtac Scons_not_Atom 1); -val Scons_not_Numb = result(); +qed "Scons_not_Numb"; val Numb_not_Scons = standard (Scons_not_Numb RS not_sym); val Scons_neq_Numb = standard (Scons_not_Numb RS notE); @@ -243,7 +243,7 @@ goalw Univ.thy [Leaf_def,Numb_def] "Leaf(a) ~= Numb(k)"; by (simp_tac (HOL_ss addsimps [Atom_Atom_eq,Inl_not_Inr]) 1); -val Leaf_not_Numb = result(); +qed "Leaf_not_Numb"; val Numb_not_Leaf = standard (Leaf_not_Numb RS not_sym); val Leaf_neq_Numb = standard (Leaf_not_Numb RS notE); @@ -261,14 +261,14 @@ by (rtac Least_equality 1); by (rtac refl 1); by (etac less_zeroE 1); -val ndepth_K0 = result(); +qed "ndepth_K0"; goal Univ.thy "k < Suc(LEAST x. f(x)=0) --> nat_case(Suc(i), f, k) ~= 0"; by (nat_ind_tac "k" 1); by (ALLGOALS (simp_tac nat_ss)); by (rtac impI 1); by (etac not_less_Least 1); -val ndepth_Push_lemma = result(); +qed "ndepth_Push_lemma"; goalw Univ.thy [ndepth_def,Push_Node_def] "ndepth (Push_Node(i,n)) = Suc(ndepth(n))"; @@ -282,28 +282,28 @@ by (rtac (nat_case_Suc RS trans) 1); by (etac LeastI 1); by (etac (ndepth_Push_lemma RS mp) 1); -val ndepth_Push_Node = result(); +qed "ndepth_Push_Node"; (*** ntrunc applied to the various node sets ***) goalw Univ.thy [ntrunc_def] "ntrunc(0, M) = {}"; by (safe_tac (set_cs addSIs [equalityI] addSEs [less_zeroE])); -val ntrunc_0 = result(); +qed "ntrunc_0"; goalw Univ.thy [Atom_def,ntrunc_def] "ntrunc(Suc(k), Atom(a)) = Atom(a)"; by (safe_tac (set_cs addSIs [equalityI])); by (stac ndepth_K0 1); by (rtac zero_less_Suc 1); -val ntrunc_Atom = result(); +qed "ntrunc_Atom"; goalw Univ.thy [Leaf_def,o_def] "ntrunc(Suc(k), Leaf(a)) = Leaf(a)"; by (rtac ntrunc_Atom 1); -val ntrunc_Leaf = result(); +qed "ntrunc_Leaf"; goalw Univ.thy [Numb_def,o_def] "ntrunc(Suc(k), Numb(i)) = Numb(i)"; by (rtac ntrunc_Atom 1); -val ntrunc_Numb = result(); +qed "ntrunc_Numb"; goalw Univ.thy [Scons_def,ntrunc_def] "ntrunc(Suc(k), M$N) = ntrunc(k,M) $ ntrunc(k,N)"; @@ -312,7 +312,7 @@ by (REPEAT (rtac Suc_less_SucD 1 THEN rtac (ndepth_Push_Node RS subst) 1 THEN assume_tac 1)); -val ntrunc_Scons = result(); +qed "ntrunc_Scons"; (** Injection nodes **) @@ -320,30 +320,30 @@ by (simp_tac (univ_ss addsimps [ntrunc_Scons,ntrunc_0]) 1); by (rewtac Scons_def); by (safe_tac (set_cs addSIs [equalityI])); -val ntrunc_one_In0 = result(); +qed "ntrunc_one_In0"; goalw Univ.thy [In0_def] "ntrunc(Suc(Suc(k)), In0(M)) = In0 (ntrunc(Suc(k),M))"; by (simp_tac (univ_ss addsimps [ntrunc_Scons,ntrunc_Numb]) 1); -val ntrunc_In0 = result(); +qed "ntrunc_In0"; goalw Univ.thy [In1_def] "ntrunc(Suc(0), In1(M)) = {}"; by (simp_tac (univ_ss addsimps [ntrunc_Scons,ntrunc_0]) 1); by (rewtac Scons_def); by (safe_tac (set_cs addSIs [equalityI])); -val ntrunc_one_In1 = result(); +qed "ntrunc_one_In1"; goalw Univ.thy [In1_def] "ntrunc(Suc(Suc(k)), In1(M)) = In1 (ntrunc(Suc(k),M))"; by (simp_tac (univ_ss addsimps [ntrunc_Scons,ntrunc_Numb]) 1); -val ntrunc_In1 = result(); +qed "ntrunc_In1"; (*** Cartesian Product ***) goalw Univ.thy [uprod_def] "!!M N. [| M:A; N:B |] ==> (M$N) : A<*>B"; by (REPEAT (ares_tac [singletonI,UN_I] 1)); -val uprodI = result(); +qed "uprodI"; (*The general elimination rule*) val major::prems = goalw Univ.thy [uprod_def] @@ -353,7 +353,7 @@ by (cut_facts_tac [major] 1); by (REPEAT (eresolve_tac [asm_rl,singletonE,UN_E] 1 ORELSE resolve_tac prems 1)); -val uprodE = result(); +qed "uprodE"; (*Elimination of a pair -- introduces no eigenvariables*) val prems = goal Univ.thy @@ -361,18 +361,18 @@ \ |] ==> P"; by (rtac uprodE 1); by (REPEAT (ares_tac prems 1 ORELSE eresolve_tac [Scons_inject,ssubst] 1)); -val uprodE2 = result(); +qed "uprodE2"; (*** Disjoint Sum ***) goalw Univ.thy [usum_def] "!!M. M:A ==> In0(M) : A<+>B"; by (fast_tac set_cs 1); -val usum_In0I = result(); +qed "usum_In0I"; goalw Univ.thy [usum_def] "!!N. N:B ==> In1(N) : A<+>B"; by (fast_tac set_cs 1); -val usum_In1I = result(); +qed "usum_In1I"; val major::prems = goalw Univ.thy [usum_def] "[| u : A<+>B; \ @@ -382,7 +382,7 @@ by (rtac (major RS UnE) 1); by (REPEAT (rtac refl 1 ORELSE eresolve_tac (prems@[imageE,ssubst]) 1)); -val usumE = result(); +qed "usumE"; (** Injection **) @@ -390,7 +390,7 @@ goalw Univ.thy [In0_def,In1_def] "In0(M) ~= In1(N)"; by (rtac notI 1); by (etac (Scons_inject1 RS Numb_inject RS Zero_neq_Suc) 1); -val In0_not_In1 = result(); +qed "In0_not_In1"; val In1_not_In0 = standard (In0_not_In1 RS not_sym); val In0_neq_In1 = standard (In0_not_In1 RS notE); @@ -398,24 +398,24 @@ val [major] = goalw Univ.thy [In0_def] "In0(M) = In0(N) ==> M=N"; by (rtac (major RS Scons_inject2) 1); -val In0_inject = result(); +qed "In0_inject"; val [major] = goalw Univ.thy [In1_def] "In1(M) = In1(N) ==> M=N"; by (rtac (major RS Scons_inject2) 1); -val In1_inject = result(); +qed "In1_inject"; (*** proving equality of sets and functions using ntrunc ***) goalw Univ.thy [ntrunc_def] "ntrunc(k,M) <= M"; by (fast_tac set_cs 1); -val ntrunc_subsetI = result(); +qed "ntrunc_subsetI"; val [major] = goalw Univ.thy [ntrunc_def] "(!!k. ntrunc(k,M) <= N) ==> M<=N"; by (fast_tac (set_cs addIs [less_add_Suc1, less_add_Suc2, major RS subsetD]) 1); -val ntrunc_subsetD = result(); +qed "ntrunc_subsetD"; (*A generalized form of the take-lemma*) val [major] = goal Univ.thy "(!!k. ntrunc(k,M) = ntrunc(k,N)) ==> M=N"; @@ -424,81 +424,81 @@ by (ALLGOALS (rtac (ntrunc_subsetI RSN (2, subset_trans)))); by (rtac (major RS equalityD1) 1); by (rtac (major RS equalityD2) 1); -val ntrunc_equality = result(); +qed "ntrunc_equality"; val [major] = goalw Univ.thy [o_def] "[| !!k. (ntrunc(k) o h1) = (ntrunc(k) o h2) |] ==> h1=h2"; by (rtac (ntrunc_equality RS ext) 1); by (rtac (major RS fun_cong) 1); -val ntrunc_o_equality = result(); +qed "ntrunc_o_equality"; (*** Monotonicity ***) goalw Univ.thy [uprod_def] "!!A B. [| A<=A'; B<=B' |] ==> A<*>B <= A'<*>B'"; by (fast_tac set_cs 1); -val uprod_mono = result(); +qed "uprod_mono"; goalw Univ.thy [usum_def] "!!A B. [| A<=A'; B<=B' |] ==> A<+>B <= A'<+>B'"; by (fast_tac set_cs 1); -val usum_mono = result(); +qed "usum_mono"; goalw Univ.thy [Scons_def] "!!M N. [| M<=M'; N<=N' |] ==> M$N <= M'$N'"; by (fast_tac set_cs 1); -val Scons_mono = result(); +qed "Scons_mono"; goalw Univ.thy [In0_def] "!!M N. M<=N ==> In0(M) <= In0(N)"; by (REPEAT (ares_tac [subset_refl,Scons_mono] 1)); -val In0_mono = result(); +qed "In0_mono"; goalw Univ.thy [In1_def] "!!M N. M<=N ==> In1(M) <= In1(N)"; by (REPEAT (ares_tac [subset_refl,Scons_mono] 1)); -val In1_mono = result(); +qed "In1_mono"; (*** Split and Case ***) goalw Univ.thy [Split_def] "Split(c, M$N) = c(M,N)"; by (fast_tac (set_cs addIs [select_equality] addEs [Scons_inject]) 1); -val Split = result(); +qed "Split"; goalw Univ.thy [Case_def] "Case(c, d, In0(M)) = c(M)"; by (fast_tac (set_cs addIs [select_equality] addEs [make_elim In0_inject, In0_neq_In1]) 1); -val Case_In0 = result(); +qed "Case_In0"; goalw Univ.thy [Case_def] "Case(c, d, In1(N)) = d(N)"; by (fast_tac (set_cs addIs [select_equality] addEs [make_elim In1_inject, In1_neq_In0]) 1); -val Case_In1 = result(); +qed "Case_In1"; (**** UN x. B(x) rules ****) goalw Univ.thy [ntrunc_def] "ntrunc(k, UN x.f(x)) = (UN x. ntrunc(k, f(x)))"; by (fast_tac (set_cs addIs [equalityI]) 1); -val ntrunc_UN1 = result(); +qed "ntrunc_UN1"; goalw Univ.thy [Scons_def] "(UN x.f(x)) $ M = (UN x. f(x) $ M)"; by (fast_tac (set_cs addIs [equalityI]) 1); -val Scons_UN1_x = result(); +qed "Scons_UN1_x"; goalw Univ.thy [Scons_def] "M $ (UN x.f(x)) = (UN x. M $ f(x))"; by (fast_tac (set_cs addIs [equalityI]) 1); -val Scons_UN1_y = result(); +qed "Scons_UN1_y"; goalw Univ.thy [In0_def] "In0(UN x.f(x)) = (UN x. In0(f(x)))"; br Scons_UN1_y 1; -val In0_UN1 = result(); +qed "In0_UN1"; goalw Univ.thy [In1_def] "In1(UN x.f(x)) = (UN x. In1(f(x)))"; br Scons_UN1_y 1; -val In1_UN1 = result(); +qed "In1_UN1"; (*** Equality : the diagonal relation ***) goalw Univ.thy [diag_def] "!!a A. [| a=b; a:A |] ==> : diag(A)"; by (fast_tac set_cs 1); -val diag_eqI = result(); +qed "diag_eqI"; val diagI = refl RS diag_eqI |> standard; @@ -509,14 +509,14 @@ \ |] ==> P"; by (rtac (major RS UN_E) 1); by (REPEAT (eresolve_tac [asm_rl,singletonE] 1 ORELSE resolve_tac prems 1)); -val diagE = result(); +qed "diagE"; (*** Equality for Cartesian Product ***) goalw Univ.thy [dprod_def] "!!r s. [| :r; :s |] ==> : r<**>s"; by (fast_tac prod_cs 1); -val dprodI = result(); +qed "dprodI"; (*The general elimination rule*) val major::prems = goalw Univ.thy [dprod_def] @@ -526,18 +526,18 @@ by (cut_facts_tac [major] 1); by (REPEAT_FIRST (eresolve_tac [asm_rl, UN_E, mem_splitE, singletonE])); by (REPEAT (ares_tac prems 1 ORELSE hyp_subst_tac 1)); -val dprodE = result(); +qed "dprodE"; (*** Equality for Disjoint Sum ***) goalw Univ.thy [dsum_def] "!!r. :r ==> : r<++>s"; by (fast_tac prod_cs 1); -val dsum_In0I = result(); +qed "dsum_In0I"; goalw Univ.thy [dsum_def] "!!r. :s ==> : r<++>s"; by (fast_tac prod_cs 1); -val dsum_In1I = result(); +qed "dsum_In1I"; val major::prems = goalw Univ.thy [dsum_def] "[| w : r<++>s; \ @@ -547,7 +547,7 @@ by (cut_facts_tac [major] 1); by (REPEAT_FIRST (eresolve_tac [asm_rl, UN_E, UnE, mem_splitE, singletonE])); by (DEPTH_SOLVE (ares_tac prems 1 ORELSE hyp_subst_tac 1)); -val dsumE = result(); +qed "dsumE"; val univ_cs = @@ -560,22 +560,22 @@ goal Univ.thy "!!r s. [| r<=r'; s<=s' |] ==> r<**>s <= r'<**>s'"; by (fast_tac univ_cs 1); -val dprod_mono = result(); +qed "dprod_mono"; goal Univ.thy "!!r s. [| r<=r'; s<=s' |] ==> r<++>s <= r'<++>s'"; by (fast_tac univ_cs 1); -val dsum_mono = result(); +qed "dsum_mono"; (*** Bounding theorems ***) goal Univ.thy "diag(A) <= Sigma(A,%x.A)"; by (fast_tac univ_cs 1); -val diag_subset_Sigma = result(); +qed "diag_subset_Sigma"; goal Univ.thy "(Sigma(A,%x.B) <**> Sigma(C,%x.D)) <= Sigma(A<*>C, %z. B<*>D)"; by (fast_tac univ_cs 1); -val dprod_Sigma = result(); +qed "dprod_Sigma"; val dprod_subset_Sigma = [dprod_mono, dprod_Sigma] MRS subset_trans |>standard; @@ -585,11 +585,11 @@ by (safe_tac univ_cs); by (stac Split 1); by (fast_tac univ_cs 1); -val dprod_subset_Sigma2 = result(); +qed "dprod_subset_Sigma2"; goal Univ.thy "(Sigma(A,%x.B) <++> Sigma(C,%x.D)) <= Sigma(A<+>C, %z. B<+>D)"; by (fast_tac univ_cs 1); -val dsum_Sigma = result(); +qed "dsum_Sigma"; val dsum_subset_Sigma = [dsum_mono, dsum_Sigma] MRS subset_trans |> standard; @@ -598,18 +598,18 @@ goal Univ.thy "fst `` diag(A) = A"; by (fast_tac (prod_cs addIs [equalityI, diagI] addSEs [diagE]) 1); -val fst_image_diag = result(); +qed "fst_image_diag"; goal Univ.thy "fst `` (r<**>s) = (fst``r) <*> (fst``s)"; by (fast_tac (prod_cs addIs [equalityI, uprodI, dprodI] addSEs [uprodE, dprodE]) 1); -val fst_image_dprod = result(); +qed "fst_image_dprod"; goal Univ.thy "fst `` (r<++>s) = (fst``r) <+> (fst``s)"; by (fast_tac (prod_cs addIs [equalityI, usum_In0I, usum_In1I, dsum_In0I, dsum_In1I] addSEs [usumE, dsumE]) 1); -val fst_image_dsum = result(); +qed "fst_image_dsum"; val fst_image_simps = [fst_image_diag, fst_image_dprod, fst_image_dsum]; val fst_image_ss = univ_ss addsimps fst_image_simps;