equal
deleted
inserted
replaced
19 Var [intro]: "listsp IT rs ==> IT (Var n \<degree>\<degree> rs)" |
19 Var [intro]: "listsp IT rs ==> IT (Var n \<degree>\<degree> rs)" |
20 | Lambda [intro]: "IT r ==> IT (Abs r)" |
20 | Lambda [intro]: "IT r ==> IT (Abs r)" |
21 | Beta [intro]: "IT ((r[s/0]) \<degree>\<degree> ss) ==> IT s ==> IT ((Abs r \<degree> s) \<degree>\<degree> ss)" |
21 | Beta [intro]: "IT ((r[s/0]) \<degree>\<degree> ss) ==> IT s ==> IT ((Abs r \<degree> s) \<degree>\<degree> ss)" |
22 |
22 |
23 |
23 |
24 subsection {* Every term in IT terminates *} |
24 subsection {* Every term in @{text "IT"} terminates *} |
25 |
25 |
26 lemma double_induction_lemma [rule_format]: |
26 lemma double_induction_lemma [rule_format]: |
27 "termip beta s ==> \<forall>t. termip beta t --> |
27 "termip beta s ==> \<forall>t. termip beta t --> |
28 (\<forall>r ss. t = r[s/0] \<degree>\<degree> ss --> termip beta (Abs r \<degree> s \<degree>\<degree> ss))" |
28 (\<forall>r ss. t = r[s/0] \<degree>\<degree> ss --> termip beta (Abs r \<degree> s \<degree>\<degree> ss))" |
29 apply (erule accp_induct) |
29 apply (erule accp_induct) |
54 apply blast |
54 apply blast |
55 apply (blast intro: double_induction_lemma) |
55 apply (blast intro: double_induction_lemma) |
56 done |
56 done |
57 |
57 |
58 |
58 |
59 subsection {* Every terminating term is in IT *} |
59 subsection {* Every terminating term is in @{text "IT"} *} |
60 |
60 |
61 declare Var_apps_neq_Abs_apps [symmetric, simp] |
61 declare Var_apps_neq_Abs_apps [symmetric, simp] |
62 |
62 |
63 lemma [simp, THEN not_sym, simp]: "Var n \<degree>\<degree> ss \<noteq> Abs r \<degree> s \<degree>\<degree> ts" |
63 lemma [simp, THEN not_sym, simp]: "Var n \<degree>\<degree> ss \<noteq> Abs r \<degree> s \<degree>\<degree> ts" |
64 by (simp add: foldl_Cons [symmetric] del: foldl_Cons) |
64 by (simp add: foldl_Cons [symmetric] del: foldl_Cons) |