src/HOL/Induct/Term.ML
changeset 4089 96fba19bcbe2
parent 3842 b55686a7b22c
child 5069 3ea049f7979d
equal deleted inserted replaced
4088:9be9e39fd862 4089:96fba19bcbe2
    10 open Term;
    10 open Term;
    11 
    11 
    12 (*** Monotonicity and unfolding of the function ***)
    12 (*** Monotonicity and unfolding of the function ***)
    13 
    13 
    14 goal Term.thy "term(A) = A <*> list(term(A))";
    14 goal Term.thy "term(A) = A <*> list(term(A))";
    15 by (fast_tac (!claset addSIs term.intrs
    15 by (fast_tac (claset() addSIs term.intrs
    16                       addEs [term.elim]) 1);
    16                       addEs [term.elim]) 1);
    17 qed "term_unfold";
    17 qed "term_unfold";
    18 
    18 
    19 (*This justifies using term in other recursive type definitions*)
    19 (*This justifies using term in other recursive type definitions*)
    20 goalw Term.thy term.defs "!!A B. A<=B ==> term(A) <= term(B)";
    20 goalw Term.thy term.defs "!!A B. A<=B ==> term(A) <= term(B)";
    23 
    23 
    24 (** Type checking -- term creates well-founded sets **)
    24 (** Type checking -- term creates well-founded sets **)
    25 
    25 
    26 goalw Term.thy term.defs "term(sexp) <= sexp";
    26 goalw Term.thy term.defs "term(sexp) <= sexp";
    27 by (rtac lfp_lowerbound 1);
    27 by (rtac lfp_lowerbound 1);
    28 by (fast_tac (!claset addIs [sexp.SconsI, list_sexp RS subsetD]) 1);
    28 by (fast_tac (claset() addIs [sexp.SconsI, list_sexp RS subsetD]) 1);
    29 qed "term_sexp";
    29 qed "term_sexp";
    30 
    30 
    31 (* A <= sexp ==> term(A) <= sexp *)
    31 (* A <= sexp ==> term(A) <= sexp *)
    32 bind_thm ("term_subset_sexp", ([term_mono, term_sexp] MRS subset_trans));
    32 bind_thm ("term_subset_sexp", ([term_mono, term_sexp] MRS subset_trans));
    33 
    33 
    96 \       !!x t ts. R(App x ts) ==> R(App x (t#ts))  \
    96 \       !!x t ts. R(App x ts) ==> R(App x (t#ts))  \
    97 \    |] ==> R(t)";
    97 \    |] ==> R(t)";
    98 by (rtac term_induct 1);  (*types force good instantiation*)
    98 by (rtac term_induct 1);  (*types force good instantiation*)
    99 by (etac rev_mp 1);
    99 by (etac rev_mp 1);
   100 by (rtac list_induct2 1);  (*types force good instantiation*)
   100 by (rtac list_induct2 1);  (*types force good instantiation*)
   101 by (ALLGOALS (asm_simp_tac (!simpset addsimps prems)));
   101 by (ALLGOALS (asm_simp_tac (simpset() addsimps prems)));
   102 qed "term_induct2";
   102 qed "term_induct2";
   103 
   103 
   104 (*Perform induction on xs. *)
   104 (*Perform induction on xs. *)
   105 fun term_ind2_tac a i = 
   105 fun term_ind2_tac a i = 
   106     EVERY [res_inst_tac [("t",a)] term_induct2 i,
   106     EVERY [res_inst_tac [("t",a)] term_induct2 i,
   132 \        Abs_map h N";
   132 \        Abs_map h N";
   133 by (rtac (prem RS list.induct) 1);
   133 by (rtac (prem RS list.induct) 1);
   134 by (Simp_tac 1);
   134 by (Simp_tac 1);
   135 by (strip_tac 1);
   135 by (strip_tac 1);
   136 by (etac (pred_sexp_CONS_D RS conjE) 1);
   136 by (etac (pred_sexp_CONS_D RS conjE) 1);
   137 by (asm_simp_tac (!simpset addsimps [trancl_pred_sexpD1]) 1);
   137 by (asm_simp_tac (simpset() addsimps [trancl_pred_sexpD1]) 1);
   138 qed "Abs_map_lemma";
   138 qed "Abs_map_lemma";
   139 
   139 
   140 val [prem1,prem2,A_subset_sexp] = goal Term.thy
   140 val [prem1,prem2,A_subset_sexp] = goal Term.thy
   141     "[| M: sexp;  N: list(term(A));  A<=sexp |] ==> \
   141     "[| M: sexp;  N: list(term(A));  A<=sexp |] ==> \
   142 \    Term_rec (M$N) d = d M N (Abs_map (%Z. Term_rec Z d) N)";
   142 \    Term_rec (M$N) d = d M N (Abs_map (%Z. Term_rec Z d) N)";