src/ZF/Resid/Reduction.thy
changeset 13339 0f89104dd377
parent 12593 cd35fe5947d4
child 13612 55d32e76ef4e
equal deleted inserted replaced
13338:20ca66539bef 13339:0f89104dd377
    16 
    16 
    17 translations
    17 translations
    18   "Apl(n,m)" == "App(0,n,m)"
    18   "Apl(n,m)" == "App(0,n,m)"
    19   
    19   
    20 inductive
    20 inductive
    21   domains       "lambda" <= "redexes"
    21   domains       "lambda" <= redexes
    22   intros
    22   intros
    23     Lambda_Var:  "               n \<in> nat ==>     Var(n) \<in> lambda"
    23     Lambda_Var:  "               n \<in> nat ==>     Var(n) \<in> lambda"
    24     Lambda_Fun:  "            u \<in> lambda ==>     Fun(u) \<in> lambda"
    24     Lambda_Fun:  "            u \<in> lambda ==>     Fun(u) \<in> lambda"
    25     Lambda_App:  "[|u \<in> lambda; v \<in> lambda|] ==> Apl(u,v) \<in> lambda"
    25     Lambda_App:  "[|u \<in> lambda; v \<in> lambda|] ==> Apl(u,v) \<in> lambda"
    26   type_intros    redexes.intros bool_typechecks
    26   type_intros    redexes.intros bool_typechecks
   154 (*     Lemmas for reduction                                                  *)
   154 (*     Lemmas for reduction                                                  *)
   155 (* ------------------------------------------------------------------------- *)
   155 (* ------------------------------------------------------------------------- *)
   156 
   156 
   157 lemma red_Fun: "m--->n ==> Fun(m) ---> Fun(n)"
   157 lemma red_Fun: "m--->n ==> Fun(m) ---> Fun(n)"
   158 apply (erule Sred.induct)
   158 apply (erule Sred.induct)
   159 apply (rule_tac [3] Sred.trans)
   159 apply (rule_tac [3] Sred.trans, simp_all)
   160 apply simp_all
       
   161 done
   160 done
   162 
   161 
   163 lemma red_Apll: "[|n \<in> lambda; m ---> m'|] ==> Apl(m,n)--->Apl(m',n)"
   162 lemma red_Apll: "[|n \<in> lambda; m ---> m'|] ==> Apl(m,n)--->Apl(m',n)"
   164 apply (erule Sred.induct)
   163 apply (erule Sred.induct)
   165 apply (rule_tac [3] Sred.trans)
   164 apply (rule_tac [3] Sred.trans, simp_all)
   166 apply simp_all
       
   167 done
   165 done
   168 
   166 
   169 lemma red_Aplr: "[|n \<in> lambda; m ---> m'|] ==> Apl(n,m)--->Apl(n,m')"
   167 lemma red_Aplr: "[|n \<in> lambda; m ---> m'|] ==> Apl(n,m)--->Apl(n,m')"
   170 apply (erule Sred.induct)
   168 apply (erule Sred.induct)
   171 apply (rule_tac [3] Sred.trans)
   169 apply (rule_tac [3] Sred.trans, simp_all)
   172 apply simp_all
       
   173 done
   170 done
   174 
   171 
   175 lemma red_Apl: "[|m ---> m'; n--->n'|] ==> Apl(m,n)--->Apl(m',n')"
   172 lemma red_Apl: "[|m ---> m'; n--->n'|] ==> Apl(m,n)--->Apl(m',n')"
   176 apply (rule_tac n = "Apl (m',n) " in Sred.trans)
   173 apply (rule_tac n = "Apl (m',n) " in Sred.trans)
   177 apply (simp_all add: red_Apll red_Aplr)
   174 apply (simp_all add: red_Apll red_Aplr)
   178 done
   175 done
   179 
   176 
   180 lemma red_beta: "[|m \<in> lambda; m':lambda; n \<in> lambda; n':lambda; m ---> m'; n--->n'|] ==>  
   177 lemma red_beta: "[|m \<in> lambda; m':lambda; n \<in> lambda; n':lambda; m ---> m'; n--->n'|] ==>  
   181                Apl(Fun(m),n)---> n'/m'"
   178                Apl(Fun(m),n)---> n'/m'"
   182 apply (rule_tac n = "Apl (Fun (m') ,n') " in Sred.trans)
   179 apply (rule_tac n = "Apl (Fun (m'),n') " in Sred.trans)
   183 apply (simp_all add: red_Apl red_Fun)
   180 apply (simp_all add: red_Apl red_Fun)
   184 done
   181 done
   185 
   182 
   186 
   183 
   187 (* ------------------------------------------------------------------------- *)
   184 (* ------------------------------------------------------------------------- *)