src/HOL/Lambda/InductTermi.thy
changeset 25972 94b15338da8d
parent 23750 a1db5f819d00
child 26806 40b411ec05aa
equal deleted inserted replaced
25971:21953dda56ee 25972:94b15338da8d
    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)