38 |
38 |
39 (*Induction for the set Term(A) *) |
39 (*Induction for the set Term(A) *) |
40 val [major,minor] = goal Term.thy |
40 val [major,minor] = goal Term.thy |
41 "[| M: Term(A); \ |
41 "[| M: Term(A); \ |
42 \ !!x zs. [| x: A; zs: List(Term(A)); zs: List({x.R(x)}) \ |
42 \ !!x zs. [| x: A; zs: List(Term(A)); zs: List({x.R(x)}) \ |
43 \ |] ==> R(x.zs) \ |
43 \ |] ==> R(x$zs) \ |
44 \ |] ==> R(M)"; |
44 \ |] ==> R(M)"; |
45 by (rtac (major RS (Term_def RS def_induct)) 1); |
45 by (rtac (major RS (Term_def RS def_induct)) 1); |
46 by (rtac Term_fun_mono 1); |
46 by (rtac Term_fun_mono 1); |
47 by (REPEAT (eresolve_tac ([uprodE, ssubst, minor] @ |
47 by (REPEAT (eresolve_tac ([uprodE, ssubst, minor] @ |
48 ([Int_lower1,Int_lower2] RL [List_mono RS subsetD])) 1)); |
48 ([Int_lower1,Int_lower2] RL [List_mono RS subsetD])) 1)); |
49 val Term_induct = result(); |
49 val Term_induct = result(); |
50 |
50 |
51 (*Induction on Term(A) followed by induction on List *) |
51 (*Induction on Term(A) followed by induction on List *) |
52 val major::prems = goal Term.thy |
52 val major::prems = goal Term.thy |
53 "[| M: Term(A); \ |
53 "[| M: Term(A); \ |
54 \ !!x. [| x: A |] ==> R(x.NIL); \ |
54 \ !!x. [| x: A |] ==> R(x$NIL); \ |
55 \ !!x z zs. [| x: A; z: Term(A); zs: List(Term(A)); R(x.zs) \ |
55 \ !!x z zs. [| x: A; z: Term(A); zs: List(Term(A)); R(x$zs) \ |
56 \ |] ==> R(x . CONS(z,zs)) \ |
56 \ |] ==> R(x $ CONS(z,zs)) \ |
57 \ |] ==> R(M)"; |
57 \ |] ==> R(M)"; |
58 by (rtac (major RS Term_induct) 1); |
58 by (rtac (major RS Term_induct) 1); |
59 by (etac List_induct 1); |
59 by (etac List_induct 1); |
60 by (REPEAT (ares_tac prems 1)); |
60 by (REPEAT (ares_tac prems 1)); |
61 val Term_induct2 = result(); |
61 val Term_induct2 = result(); |
95 val term_induct = result(); |
95 val term_induct = result(); |
96 |
96 |
97 (*Induction for the abstract type 'a term*) |
97 (*Induction for the abstract type 'a term*) |
98 val prems = goal Term.thy |
98 val prems = goal Term.thy |
99 "[| !!x. R(App(x,Nil)); \ |
99 "[| !!x. R(App(x,Nil)); \ |
100 \ !!x t ts. R(App(x,ts)) ==> R(App(x, Cons(t,ts))) \ |
100 \ !!x t ts. R(App(x,ts)) ==> R(App(x, t#ts)) \ |
101 \ |] ==> R(t)"; |
101 \ |] ==> R(t)"; |
102 by (rtac term_induct 1); (*types force good instantiation*) |
102 by (rtac term_induct 1); (*types force good instantiation*) |
103 by (etac rev_mp 1); |
103 by (etac rev_mp 1); |
104 by (rtac list_induct 1); (*types force good instantiation*) |
104 by (rtac list_induct 1); (*types force good instantiation*) |
105 by (ALLGOALS (asm_simp_tac (list_all_ss addsimps prems))); |
105 by (ALLGOALS (asm_simp_tac (list_all_ss addsimps prems))); |
115 |
115 |
116 (* c : A <*> List(Term(A)) ==> c : Term(A) *) |
116 (* c : A <*> List(Term(A)) ==> c : Term(A) *) |
117 val TermI = standard (Term_unfold RS equalityD2 RS subsetD); |
117 val TermI = standard (Term_unfold RS equalityD2 RS subsetD); |
118 |
118 |
119 (*The constant APP is not declared; it is simply . *) |
119 (*The constant APP is not declared; it is simply . *) |
120 val prems = goal Term.thy "[| M: A; N : List(Term(A)) |] ==> M.N : Term(A)"; |
120 val prems = goal Term.thy "[| M: A; N : List(Term(A)) |] ==> M$N : Term(A)"; |
121 by (REPEAT (resolve_tac (prems@[TermI, ListI, uprodI]) 1)); |
121 by (REPEAT (resolve_tac (prems@[TermI, ListI, uprodI]) 1)); |
122 val APP_I = result(); |
122 val APP_I = result(); |
123 |
123 |
124 |
124 |
125 (*** Term_rec -- by wf recursion on pred_Sexp ***) |
125 (*** Term_rec -- by wf recursion on pred_Sexp ***) |
141 by (asm_simp_tac (list_all_ss addsimps [trancl_pred_SexpD1, cut_apply]) 1); |
141 by (asm_simp_tac (list_all_ss addsimps [trancl_pred_SexpD1, cut_apply]) 1); |
142 val Abs_map_lemma = result(); |
142 val Abs_map_lemma = result(); |
143 |
143 |
144 val [prem1,prem2,A_subset_Sexp] = goal Term.thy |
144 val [prem1,prem2,A_subset_Sexp] = goal Term.thy |
145 "[| M: Sexp; N: List(Term(A)); A<=Sexp |] ==> \ |
145 "[| M: Sexp; N: List(Term(A)); A<=Sexp |] ==> \ |
146 \ Term_rec(M.N, d) = d(M, N, Abs_map(%Z. Term_rec(Z,d), N))"; |
146 \ Term_rec(M$N, d) = d(M, N, Abs_map(%Z. Term_rec(Z,d), N))"; |
147 by (rtac (Term_rec_unfold RS trans) 1); |
147 by (rtac (Term_rec_unfold RS trans) 1); |
148 by (rtac (Split RS trans) 1); |
148 by (rtac (Split RS trans) 1); |
149 by (simp_tac (HOL_ss addsimps |
149 by (simp_tac (HOL_ss addsimps |
150 [prem2 RS Abs_map_lemma RS spec RS mp, pred_SexpI2 RS r_into_trancl, |
150 [prem2 RS Abs_map_lemma RS spec RS mp, pred_SexpI2 RS r_into_trancl, |
151 prem1, prem2 RS rev_subsetD, List_subset_Sexp, |
151 prem1, prem2 RS rev_subsetD, List_subset_Sexp, |