src/HOL/Lambda/Lambda.thy
changeset 9941 fe05af7ec816
parent 9906 5c027cca6262
child 10851 31ac62e3a0ed
equal deleted inserted replaced
9940:102f2430cef9 9941:fe05af7ec816
   118 
   118 
   119 lemma subst_lt [simp]: "j < i ==> (Var j)[u/i] = Var j"
   119 lemma subst_lt [simp]: "j < i ==> (Var j)[u/i] = Var j"
   120   apply (simp add: subst_Var)
   120   apply (simp add: subst_Var)
   121   done
   121   done
   122 
   122 
   123 lemma lift_lift [rulified]:
   123 lemma lift_lift [rule_format]:
   124     "\<forall>i k. i < k + 1 --> lift (lift t i) (Suc k) = lift (lift t k) i"
   124     "\<forall>i k. i < k + 1 --> lift (lift t i) (Suc k) = lift (lift t k) i"
   125   apply (induct_tac t)
   125   apply (induct_tac t)
   126     apply auto
   126     apply auto
   127   done
   127   done
   128 
   128 
   142     "\<forall>k s. (lift t k)[s/k] = t"
   142     "\<forall>k s. (lift t k)[s/k] = t"
   143   apply (induct_tac t)
   143   apply (induct_tac t)
   144     apply simp_all
   144     apply simp_all
   145   done
   145   done
   146 
   146 
   147 lemma subst_subst [rulified]:
   147 lemma subst_subst [rule_format]:
   148     "\<forall>i j u v. i < j + 1 --> t[lift v i / Suc j][u[v/j]/i] = t[u/i][v/j]"
   148     "\<forall>i j u v. i < j + 1 --> t[lift v i / Suc j][u[v/j]/i] = t[u/i][v/j]"
   149   apply (induct_tac t)
   149   apply (induct_tac t)
   150     apply (simp_all
   150     apply (simp_all
   151       add: diff_Suc subst_Var lift_lift [symmetric] lift_subst_lt
   151       add: diff_Suc subst_Var lift_lift [symmetric] lift_subst_lt
   152       split: nat.split)
   152       split: nat.split)
   181 subsection {* Preservation theorems *}
   181 subsection {* Preservation theorems *}
   182 
   182 
   183 text {* Not used in Church-Rosser proof, but in Strong
   183 text {* Not used in Church-Rosser proof, but in Strong
   184   Normalization. \medskip *}
   184   Normalization. \medskip *}
   185 
   185 
   186 theorem subst_preserves_beta [rulified, simp]:
   186 theorem subst_preserves_beta [rule_format, simp]:
   187     "r -> s ==> \<forall>t i. r[t/i] -> s[t/i]"
   187     "r -> s ==> \<forall>t i. r[t/i] -> s[t/i]"
   188   apply (erule beta.induct)
   188   apply (erule beta.induct)
   189      apply (simp_all add: subst_subst [symmetric])
   189      apply (simp_all add: subst_subst [symmetric])
   190   done
   190   done
   191 
   191 
   192 theorem lift_preserves_beta [rulified, simp]:
   192 theorem lift_preserves_beta [rule_format, simp]:
   193     "r -> s ==> \<forall>i. lift r i -> lift s i"
   193     "r -> s ==> \<forall>i. lift r i -> lift s i"
   194   apply (erule beta.induct)
   194   apply (erule beta.induct)
   195      apply auto
   195      apply auto
   196   done
   196   done
   197 
   197 
   198 theorem subst_preserves_beta2 [rulified, simp]:
   198 theorem subst_preserves_beta2 [rule_format, simp]:
   199     "\<forall>r s i. r -> s --> t[r/i] ->> t[s/i]"
   199     "\<forall>r s i. r -> s --> t[r/i] ->> t[s/i]"
   200   apply (induct_tac t)
   200   apply (induct_tac t)
   201     apply (simp add: subst_Var r_into_rtrancl)
   201     apply (simp add: subst_Var r_into_rtrancl)
   202    apply (simp add: rtrancl_beta_App)
   202    apply (simp add: rtrancl_beta_App)
   203   apply (simp add: rtrancl_beta_Abs)
   203   apply (simp add: rtrancl_beta_Abs)