src/ZF/ex/Term.ML
changeset 6046 2c8a8be36c94
parent 5147 825877190618
child 6112 5e4871c5136b
equal deleted inserted replaced
6045:6a9dc67d48f5 6046:2c8a8be36c94
    14 by (fast_tac (claset() addSIs (map rew intrs) addEs [rew elim]) 1)
    14 by (fast_tac (claset() addSIs (map rew intrs) addEs [rew elim]) 1)
    15 end;
    15 end;
    16 qed "term_unfold";
    16 qed "term_unfold";
    17 
    17 
    18 (*Induction on term(A) followed by induction on List *)
    18 (*Induction on term(A) followed by induction on List *)
    19 val major::prems = goal Term.thy
    19 val major::prems = Goal
    20     "[| t: term(A);  \
    20     "[| t: term(A);  \
    21 \       !!x.      [| x: A |] ==> P(Apply(x,Nil));  \
    21 \       !!x.      [| x: A |] ==> P(Apply(x,Nil));  \
    22 \       !!x z zs. [| x: A;  z: term(A);  zs: list(term(A));  P(Apply(x,zs))  \
    22 \       !!x z zs. [| x: A;  z: term(A);  zs: list(term(A));  P(Apply(x,zs))  \
    23 \                 |] ==> P(Apply(x, Cons(z,zs)))  \
    23 \                 |] ==> P(Apply(x, Cons(z,zs)))  \
    24 \    |] ==> P(t)";
    24 \    |] ==> P(t)";
    27 by (etac CollectE 2);
    27 by (etac CollectE 2);
    28 by (REPEAT (ares_tac (prems@[list_CollectD]) 1));
    28 by (REPEAT (ares_tac (prems@[list_CollectD]) 1));
    29 qed "term_induct2";
    29 qed "term_induct2";
    30 
    30 
    31 (*Induction on term(A) to prove an equation*)
    31 (*Induction on term(A) to prove an equation*)
    32 val major::prems = goal Term.thy
    32 val major::prems = Goal
    33     "[| t: term(A);  \
    33     "[| t: term(A);  \
    34 \       !!x zs. [| x: A;  zs: list(term(A));  map(f,zs) = map(g,zs) |] ==> \
    34 \       !!x zs. [| x: A;  zs: list(term(A));  map(f,zs) = map(g,zs) |] ==> \
    35 \               f(Apply(x,zs)) = g(Apply(x,zs))  \
    35 \               f(Apply(x,zs)) = g(Apply(x,zs))  \
    36 \    |] ==> f(t)=g(t)";
    36 \    |] ==> f(t)=g(t)";
    37 by (rtac (major RS term.induct) 1);
    37 by (rtac (major RS term.induct) 1);
    64 
    64 
    65 
    65 
    66 (*** term_rec -- by Vset recursion ***)
    66 (*** term_rec -- by Vset recursion ***)
    67 
    67 
    68 (*Lemma: map works correctly on the underlying list of terms*)
    68 (*Lemma: map works correctly on the underlying list of terms*)
    69 val [major,ordi] = goal list.thy
    69 Goal "[| l: list(A);  Ord(i) |] ==>  \
    70     "[| l: list(A);  Ord(i) |] ==>  \
    70 \     rank(l)<i --> map(%z. (lam x:Vset(i).h(x)) ` z, l) = map(h,l)";
    71 \    rank(l)<i --> map(%z. (lam x:Vset(i).h(x)) ` z, l) = map(h,l)";
    71 by (etac list.induct 1);
    72 by (rtac (major RS list.induct) 1);
       
    73 by (Simp_tac 1);
    72 by (Simp_tac 1);
    74 by (rtac impI 1);
    73 by (rtac impI 1);
    75 by (forward_tac [rank_Cons1 RS lt_trans] 1);
    74 by (subgoal_tac "rank(a)<i & rank(l) < i" 1);
    76 by (dtac (rank_Cons2 RS lt_trans) 1);
    75 by (asm_simp_tac (simpset() addsimps [VsetI]) 1);
    77 by (asm_simp_tac (simpset() addsimps [ordi, VsetI]) 1);
    76 by (full_simp_tac (simpset() addsimps list.con_defs) 1);
       
    77 by (blast_tac (claset() addDs (rank_rls RL [lt_trans])) 1);
    78 qed "map_lemma";
    78 qed "map_lemma";
    79 
    79 
    80 (*Typing premise is necessary to invoke map_lemma*)
    80 (*Typing premise is necessary to invoke map_lemma*)
    81 val [prem] = goal Term.thy
    81 Goal "ts: list(A) ==> \
    82     "ts: list(A) ==> \
    82 \     term_rec(Apply(a,ts), d) = d(a, ts, map (%z. term_rec(z,d), ts))";
    83 \    term_rec(Apply(a,ts), d) = d(a, ts, map (%z. term_rec(z,d), ts))";
       
    84 by (rtac (term_rec_def RS def_Vrec RS trans) 1);
    83 by (rtac (term_rec_def RS def_Vrec RS trans) 1);
    85 by (rewrite_goals_tac term.con_defs);
    84 by (rewrite_goals_tac term.con_defs);
    86 by (simp_tac (simpset() addsimps [Ord_rank, rank_pair2, prem RS map_lemma]) 1);;
    85 by (asm_simp_tac (simpset() addsimps [Ord_rank, rank_pair2, map_lemma]) 1);;
    87 qed "term_rec";
    86 qed "term_rec";
    88 
    87 
    89 (*Slightly odd typing condition on r in the second premise!*)
    88 (*Slightly odd typing condition on r in the second premise!*)
    90 val major::prems = goal Term.thy
    89 val major::prems = Goal
    91     "[| t: term(A);                                     \
    90     "[| t: term(A);                                     \
    92 \       !!x zs r. [| x: A;  zs: list(term(A));          \
    91 \       !!x zs r. [| x: A;  zs: list(term(A));          \
    93 \                    r: list(UN t:term(A). C(t)) |]     \
    92 \                    r: list(UN t:term(A). C(t)) |]     \
    94 \                 ==> d(x, zs, r): C(Apply(x,zs))       \
    93 \                 ==> d(x, zs, r): C(Apply(x,zs))       \
    95 \    |] ==> term_rec(t,d) : C(t)";
    94 \    |] ==> term_rec(t,d) : C(t)";
   101 by (ALLGOALS (asm_simp_tac (simpset() addsimps [term_rec])));
   100 by (ALLGOALS (asm_simp_tac (simpset() addsimps [term_rec])));
   102 by (etac CollectE 1);
   101 by (etac CollectE 1);
   103 by (REPEAT (ares_tac [list.Cons_I, UN_I] 1));
   102 by (REPEAT (ares_tac [list.Cons_I, UN_I] 1));
   104 qed "term_rec_type";
   103 qed "term_rec_type";
   105 
   104 
   106 val [rew,tslist] = goal Term.thy
   105 val [rew,tslist] = Goal
   107     "[| !!t. j(t)==term_rec(t,d);  ts: list(A) |] ==> \
   106     "[| !!t. j(t)==term_rec(t,d);  ts: list(A) |] ==> \
   108 \    j(Apply(a,ts)) = d(a, ts, map(%Z. j(Z), ts))";
   107 \    j(Apply(a,ts)) = d(a, ts, map(%Z. j(Z), ts))";
   109 by (rewtac rew);
   108 by (rewtac rew);
   110 by (rtac (tslist RS term_rec) 1);
   109 by (rtac (tslist RS term_rec) 1);
   111 qed "def_term_rec";
   110 qed "def_term_rec";
   112 
   111 
   113 val prems = goal Term.thy
   112 val prems = Goal
   114     "[| t: term(A);                                          \
   113     "[| t: term(A);                                          \
   115 \       !!x zs r. [| x: A;  zs: list(term(A));  r: list(C) |]  \
   114 \       !!x zs r. [| x: A;  zs: list(term(A));  r: list(C) |]  \
   116 \                 ==> d(x, zs, r): C                 \
   115 \                 ==> d(x, zs, r): C                 \
   117 \    |] ==> term_rec(t,d) : C";
   116 \    |] ==> term_rec(t,d) : C";
   118 by (REPEAT (ares_tac (term_rec_type::prems) 1));
   117 by (REPEAT (ares_tac (term_rec_type::prems) 1));
   122 
   121 
   123 (** term_map **)
   122 (** term_map **)
   124 
   123 
   125 bind_thm ("term_map", (term_map_def RS def_term_rec));
   124 bind_thm ("term_map", (term_map_def RS def_term_rec));
   126 
   125 
   127 val prems = goalw Term.thy [term_map_def]
   126 val prems = Goalw [term_map_def]
   128     "[| t: term(A);  !!x. x: A ==> f(x): B |] ==> term_map(f,t) : term(B)";
   127     "[| t: term(A);  !!x. x: A ==> f(x): B |] ==> term_map(f,t) : term(B)";
   129 by (REPEAT (ares_tac ([term_rec_simple_type, term.Apply_I] @ prems) 1));
   128 by (REPEAT (ares_tac ([term_rec_simple_type, term.Apply_I] @ prems) 1));
   130 qed "term_map_type";
   129 qed "term_map_type";
   131 
   130 
   132 val [major] = goal Term.thy
   131 Goal "t: term(A) ==> term_map(f,t) : term({f(u). u:A})";
   133     "t: term(A) ==> term_map(f,t) : term({f(u). u:A})";
   132 by (etac term_map_type 1);
   134 by (rtac (major RS term_map_type) 1);
       
   135 by (etac RepFunI 1);
   133 by (etac RepFunI 1);
   136 qed "term_map_type2";
   134 qed "term_map_type2";
   137 
   135 
   138 
   136 
   139 (** term_size **)
   137 (** term_size **)