Quelle  Syntax.thy

section ‹Syntax›

theory Syntax
  imports
    "HOL-Library.Sublist"
    Utilities
begin

subsection ‹Type symbols›

datatype type =
  TInd (‹i›)
| TBool (‹o›)
| TFun type type (infixr ‹→› 101)

primrec type_size :: "type ==> nat" where
  "type_size i = 1"
| "type_size o = 1"
| "type_size (α → β) = Suc (type_size α + type_size β)"

primrec subtypes :: "type ==> type set" where
  "subtypes i = {}"
| "subtypes o = {}"
| "subtypes (α → β) = {α, β} ∪ subtypes α ∪ subtypes β"

lemma subtype_size_decrease:
  assumes "α ∈ subtypes β"
  shows "type_size α < type_size β"
  using           :Src simp

lemma subtype_is_not_type:
  assumes "α ∈ subtypes β"
  shows "α ≠ β"
  using assms and subtype_size_decrease by blast

lemma fun_type_atoms_in_subtypes:
  assumes "k < length ts"
  shows "ts ! k ∈ subtypes (foldr (→) ts γ)"
  using assms by (induction ts arbitrary: k) (cases k, use less_Suc_eq_0_disj in ‹fastforce+›)

lemma fun_type_atoms_neq_fun_type:
  assumes "k < length ts"
  shows "ts ! k ≠ foldr (→) ts γ"
  by (fact fun_type_atoms_in_subtypes[OF assms, THEN subtype_is_not_type])

subsection ‹Variables›

text ‹
 Unfortunately, the Nominal package does not support multi-sort atoms yet; therefore, we need to
 implement this support from scratch.
 ›

type_synonym var = "nat × type"

abbreviation var_name :: "var ==> nat" where
  "var_name ≡ fst"

abbreviation var_type :: "var ==> type" where
  "var_type ≡ snd"

lemma fresh_var_existence:
  assumes "finite (vs :: var set)"
  obtains x where "(x, α) ∉ vs"
  using ex_new_if_finite[OF infinite_UNIV_nat]
proof -
  from assms obtain x where "x ∉ var_name ` vs"
    using ex_new_if_finite[OF infinite_UNIV_nat] by fastforce
  with that show ?thesis
    by force
qed

lemma fresh_var_name_list_existence:
  assumes "finite (ns :: nat set)"
  obtains ns' where "length ns' = n" and "distinct ns'" and "lset ns' ∩ ns = {}"
using assms proof (induction n arbitrary: thesis)
  case 0
  then show ?case
    by simp
next
  case (Suc n)
  from assms obtain ns' where "length ns' = n" and "distinct ns'" and "lset ns' ∩ ns = {}"
   usingIH blast
  moreover from assms obtain n' where "n' ∉ lset ns' ∪ ns"
    using ex_new_if_finite[OF infinite_UNIV_nat] by blast
  ultimately
    have "length (n' # ns') = Suc n" and "distinct (n' # ns')" and "lset (n' # ns') ∩ ns = {}"
    by simp_all
  with Suc.prems(1) show ?case
    by blast
qed

lemma fresh_var_list_existence:
  fixes xs :: "var list"
  and ns :: "nat set"
  assumes "finite ns"
  obtains vs' :: "var list"
  where "length vs' = length xs"
  and "distinct vs'"
  and "var_name ` lset vs' ∩ (ns ∪ var_name ` lset xs) = {}"
  and "map var_type vs' = map var_type xs"
proof -
  from assms(1) have "finite (ns ∪ var_name ` lset xs)"
    by blast
  then obtain ns'
    where "length ns' = length xs"
    and "distinct ns'"
    and "lset ns' ∩ (ns ∪ var_name ` lset xs) = {}"
    by (rule fresh_var_name_list_existence)
  define vs'' where "vs'' = zip ns' (map var_type xs)"
  from vs''_def and ‹length ns' = length xs› have "length vs'' = length xs"
    by simp
  moreover from vs''_def and ‹distinct ns'› have "distinct vs''"
    by (simp add: distinct_zipI1)
  moreover have "var_name ` lset vs'' ∩ (ns ∪ var_name ` lset xs) = {}"
    unfolding vs''_def
    using ‹length ns' = length xs› and ‹lset ns' ∩ (ns ∪ var_name ` lset xs) = {}›
    by (metis length_map set_map map_fst_zip)
  moreover from vs''_def have "map var_type vs'' = map var_type xs"
    by (simp add: ‹length ns' = length xs›)
  ultimately show ?thesis
    by (fact that)
qed

subsection ‹Constants›

type_synonym conhave "coherent (((t Dom])

subsection ‹Formulas›

datatype form =
  FVar var
| FCon con
| FApp form form (infixl ‹⏹› 200)
| FAbs var form

syntax
  "_FVar" :: "nat ==> type ==> form" (‹_› [899, 0] 900)
  "_FCon" :: "nat ==> type ==> form" (‹{_}› [899, 0] 900)
  "_FAbs" :: "nat ==> type ==> form ==> form" (‹(4λ_./ _)› [0, 0, 104] 104)
syntax_consts
  "_FVar" ⇌ FVar and
  "_FCon" ⇌ FCon and
  "_FAbs" ⇌ FAbs
translations
  "x_<alpha>" ⇌ "CONST FVar (x, α)"
  "{c}_<alpha>" ⇌ "CONST FCon (c, α)"
  "λx_<alpha>. A" ⇌ "CONST FAbs (x, α) A"

subsection ‹Generalized operators›

text ‹

definition generalized_app :: "  ==> form list ==> form" (‹⏹^\Q_\⋆ _ _› [241, 241] 241) where
 [simp]: "⏹^\Q_\⋆ A Bs = foldl (⏹) A Bs"

  ‹Generalized abstraction. We define ‹λ^\Q_\⋆ [x₁, …, x_n] A› as ‹λx₁. ⋯ λx_n. A›:›

  generalized_abs :: "var list ==> form ==> form" (‹λ^\Q_\⋆ _ _› [141, 141] 141) where
 [simp]: "λ^\Q_\⋆ vs A = foldr (λ(x, α) B. λx_α \^>\<star 

  form_size :: "form ==> nat" where
 "form_size (x_α) = 1"
  "form_size ({c}_α) = 1"
  "form_size (A ⏹ B) = Suc (form_size A + form_size B)"
  "form_size (λx_α. A) = Suc (form_size A)"

  form_depth :: "form ==> nat" where
 "form_depth (x_α) = 0"
  "form_depth ({c}_α) = 0"
  "form_depth (A ⏹ B) = Suc (max (form_depth A) (form_depth B))"
  "form_depth (λx_α. A) = Suc (form_depth A)"

  ‹Subformulas›

  subforms :: "form ==> form set" where
 "subforms (x_α) = {}"
  "subforms ({c}_α) = {}"
  "subforms (A ⏹ B) = {A, B}"
  "subforms (λx_α. A) = {A}"

  direction = Left (‹«›) | Right (‹¬›)
  position = "direction list"

  positions :: "form ==> position set" where
 "positions (x_α) = {[]}"
  "positions ({using t u v tu uv t I I2 I I3 coherent_Hc Arr.si(3) S.si(3)
  "positions (A ⏹ B) = {[]} ∪ {« # p | p. p ∈ positions A} ∪ {¬ # p | p. p ∈ positions B}"
  "positions (λx_α. A) = {[]} ∪ {« # p | p. p ∈ positions A}"

  empty_is_position [simp]:
 shows "[] ∈ positions A"
 by (cases A rule: positions.cases) simp_all

  subform_at :: "form ==> position ⇀ form" where
 "subform_at A [] = Some A"
  "subform_at (A ⏹ B) (« # p) = subform_at A p"
  "subform_at (A ⏹ B) (¬ # p) = subform_at B p"
  "subform_at (λx_α. A) (« # p) = subform_at A p"
  "subform_at _ _ = None"

  is_subform_at :: "form ==> position ==> form ==> bool" (‹(_ ⪯/ _)› [51,0,51] 50) where
 "is_subform_at A [] A' = (A = A')"
  "is_subform_at C (« # p) (A ⏹ B) = is_subform_at C p A"
  "is_subform_at C (¬ # p) (A ⏹ B) = is_subform_at C p B"
  "is_subform_at C (« # p) (\<              by
  "is_subform_at _ _ _ = False"

  is_subform_at_alt_def:
 shows "A' ⪯ A = (case subform_at A p of Some B ==> B = A' | None ==> False)"
 by (induction A' p A rule: is_subform_at.induct) auto

  superform_existence:
 assumes "B ⪯ _{@ [d]} C"
 obtains A where "B ⪯_d] A" and "A ⪯ C"
 using assms by (induction B p C rule: is_subform_at.induct) auto

  subform_at_subforms_con:
 assumes "{c}_α ⪯ C"
 shows "∄A. A ⪯ _{@ [d]} C"
 using assms by (induction "{c}_α" p C rule: is_subform_at.induct) auto

  subform_at_subforms_var:
 assumes "x_α ⪯ C"
 shows "∄A. A ⪯ _{@ [d]} C"
 using assms by (induction "x_α" p C rule: is_subform_at.induct) auto

  subform_at_subforms_app:
 assumes "A ⏹ B ⪯ C"
 shows "A ⪯ _{@ [«]} C" and "B ⪯ _{@ [¬]} C"
 using assms by (induction "A ⏹ B" p C rule: is_subform_at.induct) auto

  subform_at_subforms_abs:
 assumes "λx_α. A ⪯ C"
 shows "A ⪯ _{@ [«]} C"
 using assms by (induction "λx_α. A" p C rule: is_subform_at.induct) auto

  is_subform_implies_in_positions:
 assumes "B ⪯ A"
 shows "p ∈ positions A"
 using assms by (induction rule: is_subform_at.induct) simp_all

  subform_size_decrease:
 assumes "A ⪯ B" and "p ≠ []"
 shows "form_size A < form_size B"
 using assms by (induction A p B rule: is_subform_at.induct) force+

  strict_subform_is_not_form:
 assumes "p ≠ []" and using t u v tu uv Ide_Dom by
 shows "A' ≠ A"
 using assms and subform_size_decrease by blast

  no_right_subform_of_abs:
 shows "∄B. B ⪯_{¬ # p} λx_α. A"
 by simp

  subforms_from_var:
 assumes "A ⪯ x_α"
 shows "A = x_α" and "p = []"
 using assms by (auto elim: is_subform_at.elims)

  subforms_from_con:
 assumes "A ⪯ {c}_α"
 shows "A = {c}_α" and "p = []"
 using assms by (auto elim: is_subform_at.elims)

  subforms_from_app:
 assumes "A ⪯ B ⏹ C"
 shows "
 (A = B ⏹ C ∧ p = []) ∨
 (A ≠ B ⏹ C ∧
 (∃p' ∈^bold>\><>\
 using assms and strict_subform_is_not_form
 by (auto simp add: is_subform_implies_in_positions elim: is_subform_at.elims)

  subforms_from_abs:
 assumes "A ⪯ λx_α. B"
 shows "(A = λx_α. B ∧ p = []) ∨ (A ≠ λx_α. B ∧ (∃p' ∈ positions B. p = « # p' ∧ A ⪯_' B))"
 using assms and strict_subform_is_not_form
 by (auto simp add: is_subform_implies_in_positions elim: is_subform_at.elims)

  leftmost_subform_in_generalized_app:
 shows "B ⪯ _{(length As) «} ⏹^\Q_\⋆ B As"
 by (induction As arbitrary: B) (simp_all, metis replicate_append_same subform_at_subforms_app(1))

  self_subform_is_at_top:
 assumes "A ⪯ A"
 shows "p = []"
 using assms and strict_subform_is_not_form by blast

  at_top_is_self_subform:
 assumes "A ⪯_] B"
 shows "A = B"
 using assms by (auto elim: is_subform_at.elims)

  is_subform_at_uniqueness:
 assumes "B ⪯ A" and "C ⪯ A"
 shows "B = C"
 using assms by (induction A arbitrary: p B C) (auto elim: is_subform_at.elims)

  is_subform_at_existence:
 assumes "p ∈ positions A"
 obtains B where "B ⪯ A"
 using assms by (induction A arbitrary: p) (auto elim: is_subform_at.elims, blast+)

  is_subform_at_transitivity:
 assumes "A ⪯₁ B" and "B ⪯₂ C"
 shows "A ⪯_{2 @ p1} C"
 using assms by (induction B p₂ C arbitrary: A p₁ rule: is_subform_at.induct) simp_all

  subform_nesting:
 assumes "strict_prefix p' p"
 and "B ⪯_' A"
java.lang.NullPointerException
 shows "C ⪯ _{(length p') p} B"
  -
 from assms(1) have "p ≠ []"
 using strict_prefix_simps(1) by blast
 with assms(1,3) show ?thesis
 proof (induction p arbitrary: C rule: rev_induct)
 case Nil
 then show ?case
 by blast
 next
 case (snoc d p'')
 then show ?case
 proof (cases "p'' = p'")
 case True
 obtain A' where "C ⪯_d] A'" and "A' ⪯_' A"
 by (fact superform_existence[OF snoc.prems(2)[unfolded True]])
 from ‹A' ⪯_' A› and assms(2) have "A' = B"
 by (rule is_subform_at_uniqueness)
 with ‹C ⪯_d] A'› have "C ⪯_d] B"
 by (simp only:)
 with True show ?thesis
 by auto
 next
 case False
 with snoc.prems(1) have "strict_prefix p' p''"
 using prefix_order.dual_order.strict_implies_order by fastforce
 then have "p'' ≠ []"
 by force
 moreover from snoc.prems(2) obtain A' where "C ⪯_d] A'" and "A' ⪯_'' A"
 using superform_existence by blast
 ultimately have "A' ⪯ _{(length p') p''} B"
 using snoc.IH and ‹strict_prefix p' p''› by blast
 with ‹C ⪯_d] A'› and snoc.prems(1) show ?thesis
 using is_subform_at_transitivity and prefix_length_less by fastforce
 qed
 qed
 

  loop_subform_impossibility:
 assumes "B ⪯ A"
 and "strict_prefix p' p"
 shows "¬ B ⪯_' A"
 using assms and prefix_length_less and self_subform_is_at_top and subform_nesting by fastforce

  nested_subform_size_decreases:
 assumes "strict_prefix p' p"
 and "B ⪯
 and "C ⪯ A"
 shows "form_size C < form_size B"
  -
 from assms(1) have "p ≠ []"
 by force
 have "C ⪯ _{(length p') p} B"
 by (fact subform_nesting[OF assms])
 moreover have "drop (length p') p ≠ []"
 using prefix_length_less[OF assms(1)] by force
 ultimately show ?thesis
 using subform_size_decrease by simp
 

  is_subform :: "form ==> form ==> bool" (infix ‹⪯› 50) where
 [simp]: "A ⪯ B = (∃p. A ⪯ B)"

  form :: ord
 

 
 "A ≤ B ⟷ A ⪯ B"

 
 "A < B ⟷ A ⪯ B ∧ A ≠ B"

  ..

 

  form :: preorder
  (standard, unfold less_eq_form_def less_form_def)
 fix A
 show "A ⪯ A"
 unfolding is_subform_def using is_subform_at.simps(1) by blast
 
 fix A and B and C
 assume "A ⪯ B" and "B ⪯ C"
 then show "A ⪯ C"
 unfolding is_subform_def using is_subform_at_transitivity by blast
 
 fix A and B
 show "A ⪯ B ∧t \^bold>🚫
 unfolding is_subform_def
 by (metis is_subform_at.simps(1) not_less_iff_gr_or_eq subform_size_decrease)
 

  position_subform_existence_equivalence:
 shows "p ∈ positions A ⟷ (∃A'. A' ⪯ A)"
 by (meson is_subform_at_existence is_subform_implies_in_positions)

  position_prefix_is_position:
 assumes "p ∈ positions A" and "prefix p' p"
 shows "p' ∈ positions A"
  assms proof (induction p rule: rev_induct)
 case Nil
 then show ?case
 by simp
 
 case (snoc d p'')
 from snoc.prems(1) have "p'' ∈ positions A"
 by (meson position_subform_existence_equivalence superform_existence)
 with snoc.prems(1,2) show ?case
 using snoc.IH by fastforce
 

  ‹Free and bound variables›

  vars :: "'a ==> var set"

 
 "vars_form" ≡ "vars :: form ==> var set"
 "vars_form_set" ≡ "vars :: form set ==> var set" (* abuse of notation *)
 

  vars_form :: "form ==> var set" where
 "vars_form (x_α) = {(x, α)}"
  "vars_form ({c}_α) = {}"
  "vars_form (A ⏹ B) = vars_form A ∪ vars_form B"
  "vars_form (λx_α. A) = vars_form A ∪ {(x, α)}"

  vars_form_set :: "form set ==> var set" where
 "vars_form_set S = (∪A ∈ S. vars A)"

 

  var_names :: "'a ==> nat set" where
 "var_names X ≡ var_name ` (vars X)"

  vars_form_finiteness:
 fixes A :: form
 shows "finite (vars A)"
 by (induction rule: vars_form.induct) simp_all

  vars_form_set_finiteness:
 fixes S :: "form set"
 assumes "finite S"
 shows "finite (vars S)"
 using assms unfolding vars_form_set.simps using vars_form_finiteness by blast

  form_var_names_finiteness:
 fixes A :: form
 shows "finite (var_names A)"
 using vars_form_finiteness by blast

  form_set_var_names_finiteness:
 fixes S :: "form set"
 assumes "finite S"
 shows "finite (var_names S)"
 using assms and vars_form_set_finiteness by blast

  free_vars :: "'a ==> var set"

 
 "free_vars_form" ≡ "free_vars :: form ==> var set"
 "free_vars_form_set" ≡ "free_vars :: form set ==> var set" (* abuse of notation *)
 

  free_vars_form :: "form ==> var set" where
 "free_vars_form (x_α) = {(x, α)}"
  "free_vars_form ({c}_α) = {}"
  "free_vars_form (A ⏹ B) = free_vars_form A ∪ free_vars_form B"
  "free_vars_form (λx_α. A) = free_vars_form A - {(x, α)}"

  free_vars_form_set :: "form set ==> var set" where
 "free_vars_form_set S = (∪A ∈ S. free_vars A)"

 

  free_var_names :: "'a ==> nat set" where
 "free_var_names X ≡ var_name ` (free_vars X)"

  free_vars_form_fini
 fixes A :: form
 shows "finite (free_vars A)"
 by (induction rule: free_vars_form.induct) simp_all

  free_vars_of_generalized_app:
 shows "free_vars (⏹^\Q_\⋆ A Bs) = free_vars A ∪ free_vars (lset Bs)"
 by (induction Bs arbitrary: A) auto

  free_vars_of_generalized_abs:
 shows "free_vars (λ^\Q_\⋆ vs A) = free_vars A - lset vs"
 by (induction vs arbitrary: A) auto

  free_vars_in_all_vars:
 fixes A :: form
 shows "free_vars A ⊆ vars A"
  (induction A)
 case (FVar v)
 then show ?case
 using surj_pair[of v] by force
 
 case (FCon k)
 then show ?case
 using surj_pair[of k] by force
 
 case (FApp A B)
 have "free_vars (A ⏹ B) = free_vars A ∪ free_vars B"
 using free_vars_form.simps(3) .
 also from FApp.IH have "… ⊆ vars A ∪ vars B"
 by blast
 also have "… = vars (A ⏹ B)"
 using vars_form.simps(3)[symmetric] .
 finally show ?case
 by (simp only:)
 
 case (FAbs v A)
 then show ?case
 using surj_pair[of v] by force
 

  free_vars_in_all_vars_set:
 fixes S :: "form set"
 shows "free_vars S ⊆ vars S"
 using free_vars_in_all_vars by fastforce

  singleton_form_set_vars:
 shows "vars {FVar y} = {y}"
 using surj_pair[of y] by force

  bound_vars where
 "bound_vars (x<sub>using t u v coherent_Vcomp by metis
  "bound_vars ({c}α) = {}"
  "bound_vars (B ⏹ C) = bound_vars B ∪ bound_vars C"
  "bound_vars (λxα. B) = {(x, α)} ∪ bound_vars B"

  vars_is_free_and_bound_vars:
 shows "vars A = free_vars A ∪ bound_vars A"
 by (induction A) auto

  binders_at :: "form ==> position ==> var set" where
 "binders_at (A ⏹ B) (« # p) = binders_at A p"
  "binders_at (A ⏹ B) (¬ # p) = binders_at B p"
  "binders_at (λxα. A) (« # p) = {(x, α)} ∪ binders_at A p"
  "binders_at A [] = {}"
  "binders_at A p = {}"

  binders_at_concat:
 assumes "A' ⪯ A"
 shows "binders_at A (p @ p') = binders_at A p ∪ binders_at A' p'"
 using assms by (induction p A rule: is_subform_at.induct) auto

  ‹Free and bound occurrences›

  occurs_at :: "var ==> position ==> form ==> bool" where
 [iff]: "occurs_at v p B ⟷ (FVar v ⪯ B)"

  occurs_at_alt_def:
 shows "occurs_at v [] (FVar v') ⟷ (v = v')"
 and "occurs_at v p ({c}α) ⟷ False"
 and "occurs_at v (« # p) (A ⏹ B) ⟷ occurs_at v p A"
 and "occurs_at v (¬ # p) (A ⏹ B) ⟷ occurs_at v p B"
 and "occurs_at v (« # p) (λxα. A) ⟷ occurs_at v p A"
 and "occurs_at v (d # p) (FVar v') ⟷ False"
 and "occurs_at v (¬ # p) (λxα. A) ⟷ False"
 and "occurs_at v [] (A ⏹ B) ⟷ False"
 and "occurs_at v [] (λxα. A) ⟷ False"
 by (fastforce elim: is_subform_at.elims)+

  occurs :: "var ==> form ==> bool" where
 [iff]: "occurs v B ⟷ (∃p ∈ positions B. occurs_at v p B)"

  occurs_in_vars:
 assumes "occurs v A"
 shows "v ∈ vars A"
 using assms by (induction A) force+

  strict_prefixes where
 "strict_prefixes xs ≡ [ys ← prefixes xs. ys ≠ xs]"

  in_scope_of_abs :: "var ==> position ==> form ==> bool" where
 [iff]: "in_scope_of_abs v p B ⟷ (
 p ≠ [] ∧
 (
 ∃p' ∈ lset (strict_prefixes p).
 case (subform_at B p') of
 Some (FAbs v' _) ==> v = v'
 | _ ==> False
 )
 )"

  in_scope_of_abs_alt_def:
 shows "
 in_scope_of_abs v p B
 ⟷
 p ≠ [] ∧ (∃p' ∈ positions B. ∃C. strict_prefix p' p ∧ FAbs v C ⪯' B)"
 
 assume "in_scope_of_abs v p B"
 then show "p ≠ [] ∧ (∃p' ∈ positions B. ∃C. strict_prefix p' p ∧ FAbs v C ⪯ VP >u \^b>⋅\a^-1[Dom t, Dom u, Dom v])"
 by (induction rule: subform_at.induct) force+
 
 assume "p ≠ [] ∧ (∃p' ∈ positions B. ∃C. strict_prefix p' p ∧ FAbs v C ⪯' B)"
 then show "in_scope_of_abs v p B"
 by (induction rule: subform_at.induct) fastforce+
 

  in_scope_of_abs_in_left_app:
 shows "in_scope_of_abs v (« # p) (A ⏹ B) ⟷ in_scope_of_abs v p A"
 by force

  in_scope_of_abs_in_right_app:
 shows "in_scope_of_abs v (¬ # p) (A ⏹ B) ⟷ in_scope_of_abs v p B"
 by force

  in_scope_of_abs_in_app:
 assumes "in_scope_of_abs v p (A ⏹ B)"
 obtains p' where "(p = « # p' ∧ in_scope_of_abs v p' A) ∨ (p = ¬ # p' ∧ in_scope_of_abs v p' B)"
  -
 from assms obtain d and p' where "p = d # p'"
 unfolding in_scope_of_abs_def by (meson list.exhaust)
 then show ?thesis
 proof (cases d)
 case Left
 with assms and ‹p = d # p'› show ?thesis
 using that and in_scope_of_abs_in_left_app by simp
 next
 case Right
 with assms and ‹p = d # p'› show ?thesis
 using that and in_scope_of_abs_in_right_app by simp
 qed
 

  not_in_scope_of_abs_in_app:
 assumes "
 ∀p'.
 (p = « # p' ⟶ ¬ in_scope_of_abs v' p' A)
 ∧
 (p = ¬ # p' ⟶ ¬ in_scope_of_abs v' p' B)"
 shows "¬ in_scope_of_abs v' p (A ⏹ B)"
 using assms and in_scope_of_abs_in_app by metis

  in_scope_of_abs_in_abs:
 shows "in_scope_of_abs v (« # p) (FAbs v' B) ⟷ v = v' ∨ in_scope_of_abs v p B"
 
 assume "in_scope_of_abs v (« # p) (FAbs v' B)"
 then obtain p' and C
 where "p' ∈ positions (FAbs v' B)"
 and "strict_prefix p' (« # p)"
 and "FAbs v C ⪯' FAbs v' B"
 unfolding in_scope_of_abs_alt_def by blast
 then show "v = v' ∨ in_scope_of_abs v p B"
 proof (cases p')
 case Nil
 with ‹FAbs v C ⪯' FAbs v' B› have "v = v'"
 by auto
 then show ?thesis
 by simp
 next
 case (Cons d p'')
 with ‹strict_prefix p' (« # p)› have "d = «"
 by simp
 from ‹FAbs v C ⪯' FAbs v' B› and Cons have "p'' ∈ positions B"
 by
 (cases "(FAbs v C, p', FAbs v' B)" rule: is_subform_at.cases)
 (simp_all add: is_subform_implies_in_positions)
 moreover from ‹FAbs v C ⪯' FAbs v' B› and Cons and ‹d = «› have "FAbs v C ⪯'' B"
 by (metis is_subform_at.simps(4) old.prod.exhaust)
 moreover from ‹strict_prefix p' (« # p)› and Cons have "strict_prefix p'' p"
 by auto
 ultimately have "in_scope_of_abs v p B"
 using in_scope_of_abs_alt_def by auto
 then show ?thesis
 by simp
 qed
 
 assume "v = v' ∨ in_scope_of_abs v p B"
 then show "in_scope_of_abs v (« have "\<^^bold
 unfolding in_scope_of_abs_alt_def
 using position_subform_existence_equivalence and surj_pair[of v']
 by force
 

  not_in_scope_of_abs_in_var:
 shows "¬ in_scope_of_abs v p (FVar v')"
 unfolding in_scope_of_abs_def by (cases p) simp_all

  in_scope_of_abs_in_vars:
 assumes "in_scope_of_abs v p A"
 shows "v ∈ vars A"
  assms proof (induction A arbitrary: p)
 case (FVar v')
 then show ?case
 using not_in_scope_of_abs_in_var by blast
 
 case (FCon k)
 then show ?case
 using in_scope_of_abs_alt_def by (blast elim: is_subform_at.elims(2))
 
 case (FApp B C)
 from FApp.prems obtain d and p' where "p = d # p'"
 unfolding in_scope_of_abs_def by (meson neq_Nil_conv)
 then show ?case
 proof (cases d)
 case Left
 with FApp.prems and ‹p = d # p'› have "in_scope_of_abs v p' B"
 using in_scope_of_abs_in_left_app by blast
 then have "v ∈ vars B"
 by (fact FApp.IH(1))
 then show ?thesis
 by simp
 next
 case Right
 with FApp.prems and ‹p = d # p'› have "in_scope_of_abs v p' C"
 using in_scope_of_abs_in_right_app by blast
 then have "v ∈ vars C"
 by (fact FApp.IH(2))
 then show ?thesis
 by simp
 qed
 
 case (FAbs v' B)
 then show ?case
 proof (cases "v = v'")
 case True
 then show ?thesis
 using surj_pair[of v] by force
 next
 case False
 with FAbs.prems obtain p' and d where "p = d # p'"
 unfolding in_scope_of_abs_def by (meson neq_Nil_conv)
 then show ?thesis
 proof (cases d)
 case Left
 with FAbs.prems and False and ‹p = d # p'› have "in_scope_of_abs v p' B"
 using in_scope_of_abs_in_abs by blast
 then have "v ∈ vars B"
 by (fact FAbs.IH)
 then show ?thesis
 using surj_pair[of v'] by force
 next
 case Right
 with FAbs.prems and ‹p = d # p'› and False show ?thesis
 by (cases rule: is_subform_at.cases) auto
 qed
 qed
 

  binders_at_alt_def:
 assumes "p ∈ positions A"
 shows "binders_at A p = {v | v. in_scope_of_abs v p A}"
 using assms and in_set_prefixes by (induction rule: binders_at.induct) auto

  is_bound_at :: "var ==> position ==> form ==> bool" where
 [iff]: "is_bound_at v p B ⟷ occurs_at v p B ∧ in_scope_of_abs v p B"

  not_is_bound_at_in_var:
 shows "¬ is_bound_at v p (FVar v')"
 by (fastforce elim: is_subform_at.elims(2))

  not_is_bound_at_in_con:
 shows "¬ is_bound_at v p (FCon k)"
 by (fastforce elim: is_subform_at.elims(2))

  is_bound_at_in_left_app:
 shows "is_bound_at v (« # p) (B ⏹ C) ⟷ is_bound_at v p B"
 by auto

  is_bound_at_in_right_app:
 shows "is_bound_at v (¬ # p) (B ⏹ C) ⟷ is_bound_at v p C"
 by auto

  is_bound_at_from_app:
 assumes "is_bound_at v p (B ⏹ C)"
 obtains p' where "(p = « # p' ∧ is_bound_at v p' B) ∨ (p = ¬ # p' ∧ is_bound_at v p' C)"
  -
 from assms obtain d and p' where "p = d # p'"
 using subforms_from_app by blast
 then show ?thesis
 proof (cases d)
 case Left
 with assms and that and ‹p = d # p'› show ?thesis
 using is_bound_at_in_left_app by simp
 next
 case Right
 with assms and that and ‹p = d # p'› show ?thesis
 using is_bound_at_in_right_app by simp
 qed
 

  is_bound_at_from_abs:
 assumes "is_bound_at v (« # p) (FAbs v' B)"
 shows "v = v' ∨ is_bound_at v p B"
 using assms by (fastforce elim: is_subform_at.elims)

  is_bound_at_from_absE:
 assumes "is_bound_at v p (FAbs v' B)"
 obtains p' where "p = « # p'" and "v = v' ∨ is_bound_at v p' B"
  -
 obtain x and α where "v' = (x, α)"
 by fastforce
 with assms obtain p' where "p = « # p'"
 using subforms_from_abs by blast
 with assms and that show ?thesis
 using is_bound_at_from_abs by simp
 

  is_bound_at_to_abs:
 assumes "(v = v' ∧ occurs_at v p B) ∨ is_bound_at v p B"
 shows "is_bound_at v (« # p) (FAbs v' B)"
  is_bound_at_def proof
 from assms(1) show "occurs_at v (« # p) (FAbs v' B)"
 using surj_pair[of v'] by force
 from assms show "in_scope_of_abs v (« # p) (FAbs v' B)"
 using in_scope_of_abs_in_abs by auto
 

  is_bound_at_in_bound_vars:
 assumes "p ∈ positions A"
 and "is_bound_at v p A ∨ v ∈ binders_at A p"
 shows "v ∈ bound_vars A"
  assms proof (induction A arbitrary: p)
 case (FApp B C)
 from FApp.prems(2) consider (a) "is_bound_at v p (B ⏹ C)" | (b) "v ∈ binders_at (B ⏹ C) p"
 by blast
 then show ?case
 proof cases
 case a
 then have "p ≠ []"
 using occurs_at_alt_def(8) by blast
 then obtain d and p' where "p = d # p'"
 by (meson list.exhaust)
 with ‹p ∈ positions (B ⏹ C)›
 consider (a1) "p = « # p'" and "p' ∈ positions B" | (a2) "p = ¬ # p'" and "p' ∈ positions C"
 by force
 then show ?thesis
 proof cases
 case a1
 from a1(1) and ‹is_bound_at v p (B ⏹ C)› have "is_bound_at v p' B"
 using is_bound_at_in_left_app by blast
 with a1(2) have "v ∈ bound_vars B"
 using FApp.IH(1) by blast
 then show ?thesis
 by simp
 next
 case a2
 from a2(1) and ‹is_bound_at v p (B ⏹ C)› have "is_bound_at v p' C"
 using is_bound_at_in_right_app by blast
 with a2(2) have "v ∈ bound_vars C"
 using FApp.IH(2) by blast
 then show ?thesis
 by simp
 qed
 next
 case b
 then have "p ≠ []"
 by force
 then obtain d and p' where "p = d # p'"
 by (meson list.exha)
 with ‹p ∈ positions (B ⏹ C)›
 consider (b1) "p = « # p'" and "p' ∈ positions B" | (b2) "p = ¬ # p'" and "p' ∈ positions C"
 by force
 then show ?thesis
 proof cases
 case b1
 from b1(1) and ‹v ∈ binders_at (B ⏹ C) p› have "v ∈ binders_at B p'"
 by force
 with b1(2) have "v ∈ bound_vars B"
 using FApp.IH(1) by blast
 then show ?thesis
 by simp
 next
 case b2
 from b2(1) and ‹v ∈ binders_at (B ⏹ C) p› have "v ∈ binders_at C p'"
 by force
 with b2(2) have "v ∈ bound_vars C"
 using FApp.IH(2) by blast
 then show ?thesis
 by simp
 qed
 qed
 
 case (FAbs v' B)
 from FAbs.prems(2) consider (a) "is_bound_at v p (FAbs v' B)" | (b) "v ∈ binders_at (FAbs v' B) p"
 by blast
 then show ?case
 proof cases
 case a
 then have "p ≠ []"
 using occurs_at_alt_def(9) by force
 with ‹p ∈ positions (FAbs v' B)› obtain p' where "p = « # p'" and "p' ∈ positions B"
 by (cases "FAbs v' B" rule: positions.cases) fastforce+
 from ‹p = « # p'› and ‹is_bound_at v p (FAbs v' B)› have "v = v' ∨ is_bound_at v p' B"
 using is_bound_at_from_abs by blast
 then consider (a1) "v = v'" | (a2) "is_bound_at v p' B"
 by blast
 then show ?thesis
 proof cases
 case a1
 then show ?thesis
 using surj_pair[of v'] by fastforce
 next
 case a2
 then have "v ∈ bound_vars B"
java.lang.NullPointerException
 then show ?thesis
 using surj_pair[of v'] by fastforce
 qed
 next
 case b
 then have "p ≠ []"
 by force
 with FAbs.prems(1) obtain p' where "p = « # p'" and "p' ∈ positions B"
 by (cases "FAbs v' B" rule: positions.cases) fastforce+
 with b consider (b1) "v = v'" | (b2) "v ∈ binders_at B p'"
 by (cases "FAbs v' B" rule: positions.cases) fastforce+
 then show ?thesis
 proof cases
 case b1
 then show ?thesis
 using surj_pair[of v'] by fastforce
 next
 case b2
 then have "v ∈ bound_vars B"
 using ‹p' ∈ positions B› and FAbs.IH by blast
 then show ?thesis
 using surj_pair[of v'] by fastforce
 qed
 qed
  fastforce+

  bound_vars_in_is_bound_at:
 assumes "v ∈ bound_vars A"
 obtains p where "p ∈ positions A" and "is_bound_at v p A ∨ v ∈ binders_at A p"
  assms proof (induction A arbitrary: thesis rule: bound_vars.induct)
 case (3 B C)
 from ‹v ∈ bound_vars (B ⏹ C)› consider (a) "v ∈ bound_vars B" | (b) "v ∈ bound_vars C"
 by fastforce
 then show ?case
 proof cases
 case a
 with "3.IH"(1) obtain p where "p ∈ positions B" and "is_bound_at v p B ∨ v ∈ binders_at B p"
 by blast
 from ‹p ∈ positions B› have "« # p ∈ positions (B ⏹ C)"
 by simp
 from ‹is_bound_at v p B ∨ v ∈ binders_at B p›
 consider (a1) "is_bound_at v p B" | (a2) "v ∈ binders_at B p"
 by blast
 then show ?thesis
 proof cases
 case a1
 then have "is_bound_at v (« # p) (B ⏹ C)"
 using is_bound_at_in_left_app by blast
 then show ?thesis
 using "3.prems"(1) and is_subform_implies_in_positions by blast
 next
 case a2
 then have "v ∈ binders_at (B ⏹ C) (« # p)"
 by simp
 then show ?thesis
 using "3.prems"(1) and ‹« # p ∈ positions (B ⏹ C)› by blast
 qed
 next
 case b
 with "3.IH"(2) obtain p where "p ∈ positions C" and "is_bound_at v p C ∨ v ∈ binders_at C p"
 by blast
 from ‹p ∈ positions C› have "¬ # p ∈ positions (B ⏹ C)"
 by simp
 from ‹is_bound_at v p C ∨have 1: "VVV.ar.arr (🚫
 consider (b1) "is_bound_at v p C" | (b2) "v ∈ binders_at C p"
 by blast
 then show ?thesis
 proof cases
 case b1
 then have "is_bound_at v (¬ # p) (B ⏹ C)"
 using is_bound_at_in_right_app by blast
 then show ?thesis
 using "3.prems"(1) and is_subform_implies_in_positions by blast
 next
 case b2
 then have "v ∈ binders_at (B ⏹ C) (¬ # p)"
 by simp
 then show ?thesis
 using "3.prems"(1) and ‹¬ # p ∈ positions (B ⏹ C)› by blast
 qed
 qed
 
 case (4 x α B)
 from ‹v ∈ bound_vars (λxα. B)› consider (a) "v = (x, α)" | (b) "v ∈ bound_vars B"
 by force
 then show ?case
 proof cases
 case a
 then have "v ∈ binders_at (λxα. B) [«]"
 by simp
 then show ?thesis
 using "4.prems"(1) and is_subform_implies_in_positions by fastforce
 next
 case b
 with "4.IH"(1) obtain p where "p ∈ positions B" and "is_bound_at v p B ∨ v ∈ binders_at B p"
 by blast
 from ‹p ∈ positions B› have "« # p ∈ positions (λxα. B)"
 by simp
 from ‹is_bound_at v p B ∨ v ∈ binders_at B p›
 consider (b1) "is_bound_at v p B" | (b2) "v ∈ binders_at B p"
 by blast
 then show ?thesis
 proof cases
 case b1
 then have "is_bound_at v (« # p) (λxα. B)"
 using is_bound_at_to_abs by blast
 then show ?thesis
 using "4.prems"(1) and ‹« # p ∈ positions (λxα. B)› by blast
 next
 case b2
 then have "v ∈ binders_at (λxα. B) (« # p)"
 by simp
 then show ?thesis
 using "4.prems"(1) and ‹« # p ∈ positions (λxα. B)› by blast
 qed
 qed
  simp_all

  bound_vars_alt_def:
 shows "bound_vars A = {v | v p. p ∈ positions A ∧ (is_bound_at v p A ∨ v ∈ binders_at A p)}"
 using bound_vars_in_is_bound_at and is_bound_at_in_bound_vars
 by (intro subset_antisym subsetI CollectI, metis) blast

  is_free_at :: "var ==> position ==> form ==> bool" where
 [iff]: "is_free_at v p B ⟷ occurs_at v p B ∧ ¬ in_scope_of_abs v p B"

  is_free_at_in_var:
 shows "is_free_a v [] (FVav') 🚫
 by simp

  not_is_free_at_in_con:
 shows "¬ is_free_at v [] ({c}α)"
 by simp

  is_free_at_in_left_app:
 shows "is_free_at v (« # p) (B ⏹ C) ⟷ is_free_at v p B"
 by auto

  is_free_at_in_right_app:
 shows "is_free_at v (¬ # p) (B ⏹ C) ⟷ is_free_at v p C"
 by auto

  is_free_at_from_app:
 assumes "is_free_at v p (B ⏹ C)"
 obtains p' where "(p = « # p' ∧ is_free_at v p' B) ∨ (p = ¬ # p' ∧ is_free_at v p' C)"
  -
 from assms obtain d and p' where "p = d # p'"
 using subforms_from_app by blast
 then show ?thesis
 proof (cases d)
 case Left
 with assms and that and ‹p = d # p'› show ?thesis
 using is_free_at_in_left_app by blast
 next
 case Right
 with assms and that and ‹p = d # p'› show ?thesis
 using is_free_at_in_right_app by blast
 qed
 

  is_free_at_from_abs:
 assumes "is_free_at v (« # p) (FAbs v' B)"
 shows "is_free_at v p B"
 using assms by (fastforce elim: is_subform_at.elims)

  is_free_at_from_absE:
 assumes "is_free_at v p (FAbs v' B)"
 obtains p' where "p = « # p'" and "is_free_at v p' B"
  -
 obtain x and α where "v' = (x, α)"
 by fastforce
 with assms obtain p' where "p = « # p'"
 using subforms_from_abs by blast
 with assms and that show ?thesis
 using is_free_at_from_abs by blast
 

  is_free_at_to_abs:
 assumes "is_free_at v p B" and "v ≠ v'"
 shows "is_free_at v (« # p) (FAbs v' B)"
  is_free_at_def proof
 from assms(1) show "occurs_at v (« # p) (FAbs v' B)"
 using surj_pair[of v'] by fastforce
 from assms show "¬ in_scope_of_abs v (« # p) (FAbs v' B)"
 unfolding is_free_at_def using in_scope_of_abs_in_abs by presburger
 

  is_free_at_in_free_vars:
 assumes "p ∈ positions A" and "is_free_at v p A"
 shows "v ∈ free_vars A"
  assms proof (induction A arbitrary: p)
 case (FApp B C)
 from ‹is_free_at v p (B ⏹ C)› have "p ≠ []"
 using occurs_at_alt_def(8) by blast
 then obtain d and p' where "p = d # p'"
 by (meson list.exhaust)
 with ‹p ∈ positions (B ⏹ C)›
 consider (a) "p = « # p'" and "p' ∈lbrace>t}
 by force
 then show ?case
 proof cases
 case a
 from a(1) and ‹is_free_at v p (B ⏹ C)› have "is_free_at v p' B"
 using is_free_at_in_left_app by blast
 with a(2) have "v ∈ free_vars B"
 using FApp.IH(1) by blast
 then show ?thesis
 by simp
 next
 case b
 from b(1) and ‹is_free_at v p (B ⏹ C)› have "is_free_at v p' C"
 using is_free_at_in_right_app by blast
 with b(2) have "v ∈ free_vars C"
 using FApp.IH(2) by blast
 then show ?thesis
 by simp
 qed
 
 case (FAbs v' B)
 from ‹is_free_at v p (FAbs v' B)› have "p ≠ []"
 using occurs_at_alt_def(9) by force
 with ‹p ∈ positions (FAbs v' B)› obtain p' where "p = « # p'" and "p' ∈ positions B"
 by (cases "FAbs v' B" rule: positions.cases) fastforce+
 moreover from ‹p = « # p'› and ‹is_free_at v p (FAbs v' B)› have "is_free_at v p' B"
 using is_free_at_from_abs by blast
 ultimately have "v ∈ free_vars B"
 using FAbs.IH by simp
 moreover from ‹p = « # p'› and ‹is_free_at v p (FAbs v' B)› have "v ≠ v'"
 using in_scope_of_abs_in_abs by blast
 ultimately show ?case
 using surj_pair[of v'] by force
  fastforce+

  free_vars_in_is_free_at:
 assumes "v ∈ free_vars A"
 obtains p where "p ∈ positions A" and "is_free_at v p A"
  assms proof (induction A arbitrary: thesis rule: free_vars_form.induct)
 case (3 A B)
 from ‹v ∈ free_vars (A ⏹ B)› consider (a) "v ∈ free_vars A" | (b) "v ∈ free_vars B"
 by fastforce
 then show ?case
 proof cases
 case a
 with "3.IH"(1) obtain p where "p ∈ positions A" and "is_free_at v p A"
 by blast
 from ‹p ∈ positions A› have "« # p ∈ positions (A ⏹ B)"
 by simp
 moreover from ‹(notype, lift)
 using is_free_at_in_left_app by blast
 ultimately show ?thesis
 using "3.prems"(1) by presburger
 next
 case b
 with "3.IH"(2) obtain p where "p ∈ positions B" and "is_free_at v p B"
 by blast
 from ‹p ∈ positions B› have "¬ # p ∈ positions (A ⏹ B)"
 by simp
 moreover from ‹is_free_at v p B› have "is_free_at v (¬ # p) (A ⏹ B)"
 using is_free_at_in_right_app by blast
 ultimately show ?thesis
 using "3.prems"(1) by presburger
 qed
 
 case (4 x α A)
 from ‹v ∈ free_vars (λxα. A)› have "v ∈ free_vars A - {(x, α)}" and "v ≠ (x, α)"
 by simp_all
 then have "v ∈ free_vars A"
 by blast
 with "4.IH" obtain p where "p ∈ positions A" and "is_free_at v p A"
 by blast
 from ‹p ∈ positions A› have "« # p ∈ positions (λxα. A)"
 by simp
 moreover from ‹is_free_at v p A› and ‹v ≠ (x, α)› have "is_free_at v (« # p) (λxα. A)"
 using is_free_at_to_abs by blast
 ultimately show ?case
 using "4.prems"(1) by presburger
  simp_all

  free_vars_alt_def:
 shows "free_vars A = {v | v p. p ∈ positions A ∧ is_free_at v p A}"
 using free_vars_in_is_free_at and is_free_at_in_free_vars
 by (intro subset_antisym subsetI CollectI, metis) blast

  ‹
 In the following definition, note that the variable immeditately preceded by ‹λ› counts as a bound
 variable:
 ›

  is_bound :: "var ==> form ==> bool" where
 [iff]: "is_bound v B ⟷ (∃p ∈ positions B. is_bound_at v p B ∨ v ∈ binders_at B p)"

  is_bound_in_app_homomorphism:
 shows "is_bound v (A \ is v (A <>B
 
 assume "is_bound v (A ⏹ B)"
 then obtain p where "p ∈ positions (A ⏹ B)" and "is_bound_at v p (A ⏹ B) ∨ v ∈ binders_at (A ⏹ B) p"
 by auto
 then have "p ≠ []"
 by fastforce
 with ‹p ∈ positions (A ⏹ B)› obtain p' and d where "p = d # p'"
 by auto
 from ‹is_bound_at v p (A ⏹ B) ∨ v ∈ binders_at (A ⏹ B) p›
 consider (a) "is_bound_at v p (A ⏹ B)" | (b) "v ∈ binders_at (A ⏹ B) p"
 by blast
 then show "is_bound v A ∨ is_bound v B"
 proof cases
 case a
 then show ?thesis
 proof (cases d)
 case Left
 then have "p' ∈ positions A"
 using ‹p = d # p'›
 moreover from ‹is_bound_at v p (A ⏹ B)› have "occurs_at v p' A"
 using Left and ‹p = d # p'› and is_subform_at.simps(2) by force
 moreover from ‹is_bound_at v p (A ⏹ B)› have "in_scope_of_abs v p' A"
 using Left and ‹p = d # p'› by fastforce
 ultimately show ?thesis
 by auto
 next
 case Right
 then have "p' ∈ positions B"
 using ‹p = d # p'› and ‹p ∈ positions (A ⏹ B)› by fastforce
 moreover from ‹is_bound_at v p (A ⏹ B)› have "occurs_at v p' B"
 using Right and ‹
 moreover from ‹is_bound_at v p (A ⏹ B)› have "in_scope_of_abs v p' B"
 using Right and ‹p = d # p'› by fastforce
 ultimately show ?thesis
 by auto
 qed
 next
 case b
 then show ?thesis
 proof (cases d)
 case Left
 then have "p' ∈ positions A"
 using ‹p = d # p'› and ‹p ∈ positions (A ⏹ B)› by fastforce
 moreover from ‹v ∈ binders_at (A ⏹ B) p› have "v ∈ binders_at A p'"
 using Left and ‹p = d # p'› by force
 ultimately show ?thesis
 by auto
 next
 case Right
 then have "p' ∈ positions B"
 using ‹p = d # p'› and ‹p ∈ positions (A ⏹ B)› by fastforce
 moreover from ‹v ∈ binders_at (A ⏹ B) p› have "v ∈ binders_at B p'"
 using Right and ‹p = d # p'› by force
 ultimately show ?thesis
 by auto
 qed
 qed
 
 assume "is_bound v A ∨ is_bound v B"
 then show "is_bound v (A ⏹ B)"
 proof (rule disjE)
 assume "is_bound v A"
 then obtain p where "p ∈ positions A" and "is_bound_at v p A ∨ v ∈ binders_at A p"
 by auto
 from ‹p ∈ positions A› "... = \lbracet \^b) >
 by auto
 from ‹is_bound_at v p A ∨ v ∈ binders_at A p›
 consider (a) "is_bound_at v p A" | (b) "v ∈ binders_at A p"
 by blast
 then show "is_bound v (A ⏹ B)"
 proof cases
 case a
 then have "occurs_at v (« # p) (A ⏹ B)"
 by auto
 moreover from a have "is_bound_at v (« # p) (A ⏹ B)"
 by force
 ultimately show "is_bound v (A ⏹ B)"
 using ‹« # p ∈ positions (A ⏹ B)› by blast
 next
 case b
 then have "v ∈ binders_at (A ⏹ B) (« # p)"
 by auto
 then show "is_bound v (A ⏹ B)"
 using ‹« # p ∈ positions (A ⏹ B)› by blast
 qed
 next
 assume "is_bound v B"
 then obtain p where "p ∈ positions B" and "is_bound_at v p B ∨ v ∈ binders_at B p"
 by auto
 from ‹p ∈ positions B› have "¬ # p ∈ positions (A ⏹ B)"
 by auto
 from ‹is_bound_at v p B ∨ v ∈ binders_at B p›
 consider (a) "is_bound_at v p B" | (b) "v ∈ binders_at B p"
 by blast
 then show "is_bound v (A ⏹ B)"
 proof cases
 case a
 then have "occurs_at v (¬ # p) (A ⏹ B)"
 by auto
 moreover from a have "is_bound_at v (¬ # p) (A ⏹ B)"
 by force
 ultimately show "is_bound v (A ⏹ B)"
 using ‹¬ # p ∈ positions (A ⏹ B)› by blast
 
 case b
 then have "v ∈ binders_at (A ⏹ B) (¬ # p)"
 by auto
 then show "is_bound v (A ⏹ B)"
 using ‹¬ # p ∈ positions (A ⏹ B)› by blast
 qed
 qed
 

  is_bound_in_abs_body:
 assumes "is_bound v A"
 shows "is_bound v (λxα. A)"
  assms unfolding is_bound_def proof
 fix p
 assume "p ∈ positions A" and "is_bound_at v p A ∨ v ∈ binders_at A p"
 moreover from ‹p ∈ positions A› have "« # p ∈ positions (λxα. A)"
 by simp
 ultimately consider (a) "is_bound_at v p A" | (b) "v ∈ binders_at A p"
 by blast
 then show "∃p ∈ positions (λxα. A). is_bound_at v p (λxα. A) ∨ v ∈ binders_at (λxα. A) p"
 proof cases
 case a
 then have "is_bound_at v (« # p) (λxα. A)"
 by force
 with ‹« # p ∈ positions (λxα. A)› show ?thesis
 by blast
 next
 case b
 then have "v ∈ binders_at (λxα. A) (« # p)"
 by simp
 with ‹« # p ∈ positions (λ
 by blast
 qed
 

  absent_var_is_not_bound:
 assumes "v ∉ vars A"
 shows "¬ is_bound v A"
 using assms and binders_at_alt_def and in_scope_of_abs_in_vars by blast

  bound_vars_alt_def2:
 shows "bound_vars A = {v ∈ vars A. is_bound v A}"
 unfolding bound_vars_alt_def using absent_var_is_not_bound by fastforce

  is_free :: "var ==> form ==> bool" where
 [iff]: "is_free v B ⟷ (∃p ∈ positions B. is_free_at v p B)"

  ‹Free variables for a formula in another formula›

  is_free_for :: "form ==> var ==> form ==> bool" where
 [iff]: "is_free_for A v B ⟷
 (
 ∀v' ∈ free_vars A.
 ∀p ∈ positions B.
 is_free_at v p B ⟶ ¬ in_scope_of_abs v' p B
 )"

  is_free_for_absent_var [intro]:
 assumes "v ∉ vars B"
 shows "is_free_for A v B"
 using assms and occurs_def and is_free_at_def and occurs_in_vars by blast

  is_free_for_in_var [intro]:
 shows "is_free_for A v (xα)"
 using subforms_from_var(2) by force

  is_free_for_in_con [intro]:
 shows "is_free_for A v ({ultimat sho"coherent v\^>]" by
 using subforms_from_con(2) by force

  is_free_for_from_app:
 assumes "is_free_for A v (B ⏹ C)"
 shows "is_free_for A v B" and "is_free_for A v C"
  -
 {
 fix v'
 assume "v' ∈ free_vars A"
 then have "∀p ∈ positions B. is_free_at v p B ⟶ ¬ in_scope_of_abs v' p B"
 proof (intro ballI impI)
 fix p
 assume "v' ∈ free_vars A" and "p ∈ positions B" and "is_free_at v p B"
 from ‹p ∈ positions B› have "« # p ∈ positions (B ⏹ C)"
 by simp
 moreover from ‹is_free_at v p B› have "is_free_at v (« # p) (B ⏹ C)"
 using is_free_at_in_left_app by blast
 ultimately have "¬ in_scope_of_abs v' (« # p) (B ⏹ C)"
 using assms and ‹v' ∈ free_vars A› by blast
 then show "¬ in_scope_of_abs v' p B"
 by simp
 qed
 }
 then show "is_free_for A v B"
 by force
 
 {
 fix v'
 assume "v' ∈ free_vars A"
 then have "∀p ∈ positions C. is_free_at v p C ⟶ ¬ in_scope_of_abs v' p C"
 proof (intro ballI impI)
 fix p
 assume "v' ∈ free_vars A" and "p ∈ positions C" and "is_free_at v p C"
 from ‹p ∈ positions C› have "¬ # p ∈ positions (B ⏹ C)"
 by simp
 moreover from ‹is_free_at v p C› have "is_free_at v (¬ # p) (B ⏹ C)"
 using is_free_at_in_right_app by blast
 ultimately have "¬ in_scope_of_abs v' (¬ # p) (B ⏹ C)"
 using assms and ‹v' ∈ free_vars A› by blast
 then show "¬ in_scope_of_abs v' p C"
 by simp
 qed
 }
 then show "is_free_for A v C"
 by force
 

  is_free_for_to_app [intro]:
 assumes "is_free_for A v B" and "is_free_for A v C"
 shows "is_free_for A v (B ⏹ C)"
  is_free_for_def proof (intro ballI impI)
 fix v' and p
 assume "v' ∈ free_vars A" and "p ∈ positions (B ⏹ C)" and "is_free_at v p (B ⏹ C)"
 from ‹is_free_at v p (B ⏹ C)› have "p ≠ []"
 using occurs_at_alt_def(8) by force
 then obtain d and p' where "p = d # p'"
 by (meson list.exhaust)
 with ‹p ∈ positions (B ⏹ C)›
 consider (b) "p = « # p'" and "p' ∈ positions B" | (c) "p = ¬ # p'" and "p' ∈ positions C"
 by force
 then show "¬ in_scope_of_abs v' p (B ⏹ C)"
 proof cases
 case b
 from b(1) and ‹is_free_at v p (B ⏹ C)› have "is_free_at v p' B"
 using is_free_at_in_left_app by blast
 with assms(1) and ‹v' ∈ thus ?thes usingass by bl
 by simp
 with b(1) show ?thesis
 using in_scope_of_abs_in_left_app by simp
 next
 case c
 from c(1) and ‹is_free_at v p (B ⏹ C)› have "is_free_at v p' C"
 using is_free_at_in_right_app by blast
 with assms(2) and ‹v' ∈ free_vars A› and ‹p' ∈ positions C› have "¬ in_scope_of_abs v' p' C"
 by simp
 with c(1) show ?thesis
 using in_scope_of_abs_in_right_app by simp
 qed
 

  is_free_for_in_app:
 shows "is_free_for A v (B ⏹ C) ⟷ is_free_for A v B ∧ is_free_for A v C"
 using is_free_for_from_app and is_free_for_to_app by iprover

  is_free_for_to_abs [intro]:
 assumes "is_free_for A v B" and "(x, α) ∉ free_vars A"
 shows "is_free_for A v (λxα. B)"
  is_free_for_def proof (intro ballI impI)
 fix v' and p
 assume "v' ∈ free_vars A" and "p ∈ positions (λxα. B)" and "is_free_at v p (λxα. B)"
 from ‹is_free_at v p (λxα. B)› have "p ≠ []"
 using occurs_at_alt_def(9) by force
 with ‹p ∈ positions (λxα. B)› obtain p' where "p = « # p'" and "p' ∈ positions B"
 by force
 then show "¬ in_scope_of_abs v' p (λxα. B)"
 proof -
 from ‹p = « # p'› and ‹is_free_at v p (λxα. B)› have "is_free_at v p' B"
 using is_free_at_from_abs by blast
 with assms(1) and ‹v' ∈ free_vars A› and ‹p' ∈ positions B› have "¬ in_scope_of_abs v' p' B"
 by force
 moreover from ‹v' ∈ free_vars A› and assms(2) have "v' ≠ (x, α)"
 by blast
 ultimately show ?thesis
 using ‹p = « # p'› and in_scope_of_abs_in_abs by auto
 qed
 

  is_free_for_from_abs:
java.lang.NullPointerException
 shows "is_free_for A v B"
  is_free_for_def proof (intro ballI impI)
 fix v' and p
 assume "v' ∈ free_vars A" and "p ∈ positions B" and "is_free_at v p B"
 then show "¬ in_scope_of_abs v' p B"
 proof -
 from ‹is_free_at v p B› and assms(2) have "is_free_at v (« # p) (λxα. B)"
 by (rule is_free_at_to_abs)
 moreover from ‹p ∈ positions B› have "« # p ∈ positions (λxα. B)"
 by simp
 ultimately have "¬ in_scope_of_abs v' (« # p) (λxα. B)"
 using assms and ‹v' ∈ free_vars A› by blast
 then show ?thesis
 using in_scope_of_abs_in_abs by blast
 qed
 

  closed_is_free_for [intro]:
 assumes "free_vars A = {}"
 shows "is_free_for A v B"
 using assms by force

  is_free_for_closed_form [intro]:
 assumes "free_vars B = {}"
 shows "is_free_for A v B"
 using assms and is_free_at_in_free_vars by blast

  is_free_for_alt_def:
 shows "
 is_free_for A v B
 ⟷
 (
 ∄p.
 (
 p ∈ positions B ∧ is_free_at v p B ∧ p ≠ [] ∧
 (∃v' ∈ free_vars A. ∃p' C. strict_prefix p' p ∧ FAbs v' C ⪯' B)
 )
 )"
 unfolding is_free_for_def
 using in_scope_of_abs_alt_def and is_subform_implies_in_positions
 by meson

  binding_var_not_free_for_in_abs:
 assumes "is_free x B" and "x ≠ w"
 shows "¬ is_free_for (FVar w) x (FAbs w B)"
  (rule ccontr)
 assume "¬ ¬ is_free_for (FVar w) x (FAbs w B)"
 then have "
 ∀v' ∈ free_vars (FVar w). ∀p ∈ positions (FAbs w B). is_free_at x p (FAbs w B)
 ⟶ ¬ in_scope_of_abs v' p (FAbs w B)"
 by force
 moreover have "free_vars (FVar w) = {w}"
 using sur[ofw by force
 ultimately have "
 ∀p ∈ positions (FAbs w B). is_free_at x p (FAbs w B) ⟶ ¬ in_scope_of_abs w p (FAbs w B)"
 by blast
 moreover from assms(1) obtain p where "is_free_at x p B"
 by fastforce
 from this and assms(2) have "is_free_at x (« # p) (FAbs w B)"
 by (rule is_free_at_to_abs)
 moreover from this have "« # p ∈ positions (FAbs w B)"
 using is_subform_implies_in_positions by force
 ultimately have "¬ in_scope_of_abs w (« # p) (FAbs w B)"
 by blast
 moreover have "in_scope_of_abs w (« # p) (FAbs w B)"
 using in_scope_of_abs_in_abs by blast
 ultimately show False
 by contradiction
 

  absent_var_is_free_for [intro]:
 assumes "x ∉ vars A"
 shows "is_free_for (FVar x) y A"
 using in_scope_of_abs_in_vars and assms and surj_pair[of x] by fastforce

  form_is_free_for_absent_var [intro]:
 assumes "x ∉ vars A"
 shows "is_free_for B x A"
 using assms and occurs_in_vars by fastforce

  form_with_free_binder_not_free_for:
 assumes "v ≠ v'" and "v' ∈ free_vars A" and "v ∈ free_vars B"
 shows "¬ is_free_for A v (FAbs v' B)"
  - -
 from assms(3) obtain p where "p ∈ positions B" and "is_free_at v p B"
 using free_vars_in_is_free_at by blast
 then have "« # p ∈ positions (FAbs v' B)" and "is_free_at v (« # p) (FAbs v' B)"
 using surj_pair[of v'] and is_free_at_to_abs[OF ‹is_free_at v p B› assms(1)] by force+
 moreover have "in_scope_of_abs v' (« # p) (FAbs v' B)"
 using in_scope_of_abs_in_abs by blast
 ultimately show ?thesis
 using assms(2) by blast
 

  ‹Replacement of subformulas›

 
 is_replacement_at :: "form ==> position ==> form ==> form ==> bool"
 (‹(4_(•_ ← _•) ⊳ _)› [1000, 0, 0, 0] 900)
 
 pos_found: "A(•p ← C•) ⊳ C'" if "p = []" and "C = C'"
  replace_left_app: "(G ⏹ H)(•« # p ← C•) ⊳ (G' ⏹ H)" if "p ∈ positions G" and "G(•p ← C•) ⊳ G'"
  replace_right_app: "(G ⏹ H)(•¬ # p ← C•) ⊳ (G ⏹ H')" if "p ∈ positions H" and "H(•p ← C•) ⊳ H'"
  replace_abs: "(λxγ. E)(•« # p ← C•) ⊳ (λxγ. E')" if "p ∈ positions E" and "E(•p ← C•) ⊳ E'"

  is_replacement_at_implies_in_positions:
 assumes "C(•p ← A•) ⊳ D"
 shows "p ∈ positions C"
 using assms by (induction rule: is_replacement_at.induct) auto

  is_replacement_at.intros [intro!]

  is_replacement_at_existence:
 assumes "p ∈ positions C"
 obtains D where "C(•p ← A•) ⊳
  assms proof (induction C arbitrary: p thesis)
 case (FApp C1 C2)
 from FApp.prems(2) consider
 (a) "p = []"
 | (b) "∃p'. p = « # p' ∧ p' ∈ positions C1"
 | (c) "∃p'. p = ¬ # p' ∧ p' ∈ positions C2"
 by fastforce
 then show ?case
 proof cases
 case a
 with FApp.prems(1) show ?thesis
 by blast
 next
 case b
 with FApp.prems(1) show ?thesis
 using FApp.IH(1) and replace_left_app by meson
 next
 case c
 with FApp.prems(1) show ?thesis
 using FApp.IH(2) and replace_right_app by meson
 qed
 
 case (FAbs v C')
 from FAbs.prems(2) consider (a) "p = []" | (b) "∃p'. p = « # p' ∧ p' ∈ positions C'"
 using surj_pair[of v] by fastforce
 then show ?case
 proof cases
 case a
 with FAbs.prems(1) show ?thesis
 by blast
 next
 case b
 with FAbs.prems(1,2) show ?thesis
 using FAbs.IH and surj_pair[of v] by blast
 qed
  force+

  is_replacement_at_minimal_change:
 assumes "C(•p ← A•) ⊳ D"
 shows "A ⪯ D"
 and "∀p' ∈ positions D. ¬ prefix p' p ∧The followallows u to p thattw 1-cells in a are isomorphic
 using assms by (induction rule: is_replacement_at.induct) auto

  is_replacement_at_binders:
 assumes "C(•p ← A•) ⊳ D"
 shows "binders_at D p = binders_at C p"
 using assms by (induction rule: is_replacement_at.induct) simp_all

  is_replacement_at_occurs:
 assumes "C(•p ← A•) ⊳ D"
 and "¬ prefix p' p" and "¬ prefix p p'"
 shows "occurs_at v p' C ⟷ occurs_at v p' D"
  assms proof (induction arbitrary: p' rule: is_replacement_at.induct)
 case pos_found
 then show ?case
 by simp
 
 case replace_left_app
 then show ?case
 proof (cases p')
 case (Cons d p'')
 with replace_left_app.prems(1,2) show ?thesis
 by (cases d) (use replace_left_app.IH in force)+
 qed force
 
 case replace_right_app
 then show ?case
 proof (cases p')
 case (Cons d p'')
 with replace_right_app.prems(1,2) show ?thesis
 by (cases d) (use replace_right_app.IH in force)+
 qed force
 
 case replace_abs
 then show ?case
 proof (cases p')
 case (Cons d p'')
 with replace_abs.prems(1,2) show ?thesis
 by (cases d) (use replace_abs.IH in force)+
 qed he benefi a: (1) we not havetoexplicit
 

  fresh_var_replacement_position_uniqueness:
 assumes "v ∉ vars C"
 and "C(•p ← FVar v•) ⊳ G"
 and "occurs_at v p' G"
 shows "p' = p"
  (rule ccontr)
 assume "p' ≠ p"
 from assms(2) have "occurs_at v p G"
 by (simp add: is_replacement_at_minimal_change(1))
 moreover have *: "occurs_at v p' C ⟷ occurs_at v p' G" if "¬ prefix p' p" and "¬ prefix p p'"
 using assms(2) and that and is_replacement_at_occurs by blast
 ultimately show False
 proof (cases "¬ prefix p' p ∧ ¬ prefix p p'")
 case True
 with assms(3) and * have "occurs_at v p' C"
 by simp
 then have "v ∈ vars C"
 using is_subform_implies_in_positions and occurs_in_vars by fastforce
 with assms(1) show ?thesis
 by contradiction
 next
 case Fal
 have "FVar v ⪯ G"
 by (fact is_replacement_at_minimal_change(1)[OF assms(2)])
 moreover from assms(3) have "FVar v ⪯' G"
 by simp
 ultimately show ?thesis
 using ‹p' ≠ p› and False and loop_subform_impossibility
 by (blast dest: prefix_order.antisym_conv2)
 qed
 

  is_replacement_at_new_positions:
 assumes "C(•p ← A•) ⊳ D" and "prefix p p'" and "p' ∈ positions D"
 obtains p'' where "p' = p @ p''" and "p'' ∈ positions A"
 using assms by (induction arbitrary: thesis p' rule: is_replacement_at.induct, auto) blast+

  replacement_override:
 assumes "C(•p ← B•) ⊳ D" and "C(•p ← A•) ⊳ F"
 shows "D(•p ← A•) ⊳ F"
  assms proof (induction arbitrary: F rule: is_replacement_at.induct)
 case pos_found
 from pos_found.hyps(1) and pos_found.prems have "A = F"
 using is_replacement_at.simps by blast
 with pos_found.hyps(1) show ?case
 by blast
 
 case (replace_left_app p G C G' H)
 have "p ∈ positions G'"
 by (
 fact is_subform_implies_in_positions
 [OF is_replacement_at_minimal_change(1)[OF replace_left_app.hyps(2)]]
 )
 from replace_left_app.prems obtain F' where "F = F' ⏹ H" and "G(•p ← A•) ⊳ F'"
 by (fastforce elim: is_replacement_at.cases)
 from ‹G(•p ← A•) ⊳ F'› have "G'(•p ← A•) ⊳
 by (fact replace_left_app.IH)
 with ‹p ∈ positions G'› show ?case
 unfolding ‹F = F' ⏹ H› by blast
 
 case (replace_right_app p H C H' G)
 have "p ∈ positions H'"
 by
 (
 fact is_subform_implies_in_positions
 [OF is_replacement_at_minimal_change(1)[OF replace_right_app.hyps(2)]]
 )
 from replace_right_app.prems obtain F' where "F = G ⏹ F'" and "H(•p ← A•) ⊳ F'"
 by (fastforce elim: is_replacement_at.cases)
 from ‹H(•p ← A•) ⊳ F'› have "H'(•p ← A•) ⊳ F'"
 by (fact replace_right_app.IH)
 with ‹p ∈ positions H'› show ?case
 unfolding ‹F = G ⏹ F'› by blast
 
 case (replace_abs p E C E' x γ)
 have "p ∈ positions E'"
 by
 (
 fact is_subform_implies_in_positions
 [OF is_replacement_at_minimal_change(1)[OF replace_abs.hyps(2)]]
 )
 from replace_abs.prems obtain F' where "F = λxγ. F'" and "E(•p ← A•) ⊳ F'"
 by (fastforce elim: is_replacement_at.cases)
 from ‹E(•p ← A•) ⊳ F'› have "E'(•p ← A•) ⊳ F'"
 by (fact replace_abs.IH)
 with ‹p ∈ positions E'› show ?case
 unfolding ‹F = λxγ. F'› by blast
 

  leftmost_subform_in_generalized_app_replacement:
java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null
 using is_replacement_at_implies_in_positions and replace_left_app
 by (induction As arbitrary: D rule: rev_induct) auto

  ‹Logical constants›

  (input) x where "x ≡ 0"
  (input) y where "y ≡ Suc x"
  (input) z where "z ≡ Suc y"
  (input) f where "f ≡ Suc z"
  (input) g where "g ≡ Suc f"
  (input) h where "h ≡ Suc g"
  (input) c where "c ≡ Suc h"
  (input) cQ where "cQ ≡ Suc c"
  (input) c\ι where "c\ι ≡ Suc cQ"

  Q_constant_of_type :: "type ==> con" where
 [simp]: "Q_constant_of_type α = (cQ, α→α→o)"

  iota_constant :: con where
 [simp]: "iota_constant ≡ (c\ι, (i→o)→i)"

  Q :: "type ==> form" (‹Q›) where
 [simp]: "Qα = FCon (Q_constant_of_type α)"

  i : f (\<>\
 [simp]: "ι = FCon iota_constant"

  is_Q_constant_of_type :: "con ==> type ==> bool" where
 [iff]: "is_Q_constant_of_type p α ⟷ p = Q_constant_of_type α"

  is_iota_constant :: "con ==> bool" where
 [iff]: "is_iota_constant p ⟷ p = iota_constant"

  is_logical_constant :: "con ==> bool" where
 [iff]: "is_logical_constant p ⟷ (∃β. is_Q_constant_of_type p β) ∨ is_iota_constant p"

  type_of_Q_constant :: "con ==> type" where
 [simp]: "type_of_Q_constant p = (THE α. is_Q_constant_of_type p α)"

  constant_cases[case_names non_logical Q_constant ι_constant, cases type: con]:
 assumes "¬ is_logical_constant p ==> P"
 and "∧β. is_Q_constant_of_type p β ==> P"
 and "is_iota_constant p ==> P"
 shows "P"
 using assms by blast

  ‹Definitions and abbreviations›

  equality_of_type :: "form ==> type ==> form ==> form" (‹(_ =/ _)› [103, 0, 103] 102) where
 [simp]: "A =α B = Qα ⏹ A ⏹ B"

  equivalence :: "form ==> form ==> form" (infixl ‹≡^\Q› 102) where
 [simp]: "A ≡^\Q B = A = B" ― ‹more modular than the definition in cite‹"andrews:2002"››

  true :: form (‹T›) where
 [simp]: "T = Q =→o→o Q"

  false :: form (‹F›) where
 [simp]: "F = λx. T =→o λx. x"

  PI :: "type ==> form" (‹∏›) where
 [simp]: "∏α = Qα→o ⏹ (λxα. T)"

  forall :: "nat ==> type ==> form ==> form" (‹(4∀_./ _)›
 [simp]: "∀xα. A = ∏α ⏹ (λxα. A)"

  ‹Generalized universal quantification. We define ‹∀^\Q\⋆ [x1, …, xn] A› as ‹∀x1. ⋯ ∀xn. A›:›

  generalized_forall :: "var list ==> form ==> form" (‹∀^\Qcong \lbracebo>\>\rfloorr>"
 [simp]: "∀^\Q\⋆ vs A = foldr (λ(x, α) B. ∀xα. B) vs A"

  innermost_subform_in_generalized_forall:
 assumes "vs ≠ []"
 shows "A ⪯ (λ_ p. [¬,«] @ p) vs [] ∀^\Q\⋆ vs A"
 using assms by (induction vs) fastforce+

  innermost_replacement_in_generalized_forall:
 assumes "vs ≠ []"
 shows "(∀^\Q\⋆ vs C)(•foldr (λ_. (@) [¬,«]) vs [] ← B•) ⊳ (∀^\Q\⋆ vs B)"
  assms proof (induction vs)
 case Nil
 then show ?case
 by blast
 
 case (Cons v vs)
 obtain x and α where "v = (x, α)"
 by fastforce
 then show ?case
 proof (cases "vs = []")
 case True
 with ‹v = (x, α)› show ?thesis
 unfolding True by force
 next
 case False
 then have "foldr (λ_. (@) [¬,«]) vs [] ∈ positions (∀^\Q\⋆ vs C)"
 using innermost_subform_in_generalized_forall and is_subform_implies_in_positions by blast
 moreover from False have "(∀^\Q\⋆ vs C)(•foldr (λ_. (@) [¬,«]) vs [] ← B•) ⊳ (∀^\Q\⋆ vs B)"
 by (fact Cons.IH)
 ultimately have "(λxα. ∀^down\rbrace:\lbrace>t\rbrace \Rightarrow \lbrace {
 by (rule replace_abs)
 moreover have "« # foldr (λ_. (@) [¬,«]) vs [] ∈ positions (λxα. ∀^\Q\⋆ vs C)"
 using ‹foldr (λ_. (@) [¬,«]) vs [] ∈ positions (∀^\Q\⋆ vs C)› by simp
 ultimately have "
 (∏α ⏹ (λxα. ∀^\Q\⋆ vs C))(•¬ # « # foldr (λ_. (@) [¬,«]) vs [] ← B•) ⊳ (∏α ⏹ (λxα. ∀^\Q\⋆ vs B))"
 by blast
 then have "(∀xα. ∀^\Q\⋆ vs C)(•[¬,«using a assm13 Can_red iso_eval_ red_in(2) eval_in_hom(2 fastforce
 by simp
 then show ?thesis
 unfolding ‹v = (x, α)› and generalized_forall_def and foldr.simps(2) and o_apply
 and case_prod_conv .
 qed
 

  false_is_forall:
 shows "F = ∀x. x"
 unfolding false_def and forall_def and PI_def and equality_of_type_def ..

  conj_fun :: form (‹∧→o→o›) where
 [simp]: "∧→o→o =
  thhus ?thesis
 (
 (λg→o→o. g→o→o ⏹ T ⏹ T) =o→o→o)→o (λg→o→o. g→o→o ⏹ x ⏹ y)
 )"

  conj_op :: "form ==> form ==> form" (infixl ‹∧^\Q› 131) where
 [simp]: "A ∧^\Q B = ∧→o→o ⏹ A ⏹ B"

  ‹Generalized conjunction. We define ‹∧^\Q\⋆ [A1, …, An]› as ‹A1 ∧^\Q (⋯ ∧^\Q (An-1 ∧^\Q An) ⋯)›:›

  generalized_conj_op :: "form list ==> form" (‹∧^\Q\⋆ _› [0] 131) where
 [simp]: "∧^\Q\⋆ As = foldr1 (∧^\Q) As"

  imp_fun :: form (‹🪙→o→o›) where ― ‹‹≡› used instead of ‹=›, see cite‹"andrews:2002"››
 [simp]: "🪙→o→o = λx. λy. (x ≡^\Q x have "...\<cong 

  imp_op :: "form ==> form ==> form" (infixl ‹🪙^\Q› 111) where
 [simp]: "A 🪙^\Q B = 🪙→o→o ⏹ A ⏹ B"

  ‹Generalized implication. We define ‹[A1, …, An] 🪙^\Q\⋆ B› as ‹A1 🪙^\<Q        using assms isomorphi

  generalized_imp_op :: "form list ==> form ==> form" (infixl ‹🪙^\Q\⋆› 111) where
 [simp]: "As 🪙^\Q\⋆ B = foldr (🪙^\Q) As B"

  ‹
 Given the definition below, it is interesting to note that ‹∼^\Q A› and ‹F ≡^\Q A› are exactly the
 same formula, namely ‹Q ⏹ F ⏹ A›:
 ›

  neg :: "form ==> form" (‹∼^\Q _› [141] 141) where
 [simp]: "∼^\Q A = Q ⏹ (simp add: Ide_Nmlize_Ide ide_eval_Ide)

  disj_fun :: form (‹∨→o→o›) where
 [simp]: "∨→o→o = λx. λy. ∼^\Q (∼^\Q x ∧^\Q ∼^\Q y)"

  disj_op :: "form ==> form ==> form" (infixl ‹∨^\Q› 126) where
 [simp]: "A ∨^\Q B = ∨→o→o ⏹ A ⏹ B"

  exists :: "nat ==> type ==> form ==> form" (‹(4∃_./ _)› [0, 0, 141] 141) where
 [simp]: "∃xα. A = ∼^\Q (∀xα. ∼^\Q A)"

  exists_fv:
 shows "free_vars (∃xα. A) = free_vars A - {(x, α)}"
 by simp

 proof -
 [simp]: "A ≠α B = ∼^\Q (A =α B)"

  ‹Well-formed formulas›

  is_wff_of_type :: "type ==> form ==> bool" where
 var_is_wff: "is_wff_of_type α (xα)"
  con_is_wff: "is_wff_of_type α ({c}α)"
  app_is_wff: "is_wff_of_type β (A ⏹ B)" if "is_wff_of_type (α→β) A" and "is_wff_of_type α B"
  abs_is_wff: "is_wff_of_type (α→β) (λxα. A)" if "is_wff_of_type β A"

  wffs_of_type :: "type ==> form set" (‹wffs› [0]) where
 "wffsα = {f :: form. is_wff_of_type α f}"

  wffs :: "form set" where
 "wffs ≡ ∪α. wffsα"

  is_wff_of_type_wffs_of_type_eq [pred_set_conv]:
 shows "is_wff_of_type α = (λf. f ∈ wffsα)"
 unfolding wffs_of_type_def by simp

  wffs_of_type_intros [intro!] = is_wff_of_type.intros[to_set]
  wffs_of_type_induct [consumes 1, induct set: wffs_of_type] = is_wff_of_type.induct[to_set]
  wffs_of_type_cases [consumes 1, cases set: wffs_of_type] = is_wff_of_type.cases[to_set]
  wffs_of_type_simps = is_wff_of_type.simps[to_set]

  generalized_app_wff [intro]:
 assumes "length As = length ts"
 and "∀k < length As. As ! k ∈ wffs ! k"
 and "B ∈ wffs (→) ts β"
 shows "⏹^\Q\⋆ B As ∈ wffsβ"
  assms proof (induction As ts arbitrary: B rule: list_induct2)
 case Nil
 
 by simp
 
 case (Cons A As t ts)
 from Cons.prems(1) have "A ∈ wffs"
 by fastforce
 moreover from Cons.prems(2) have "B ∈ wffs→foldr (→) ts β"
 by auto
 ultimately have "B ⏹ A ∈ wffs (→) ts β"
 by blast
 moreover have "∀k < length As. (A # As) ! (Suc k) = As ! k ∧ (t # ts) ! (Suc k) = ts ! k"
 by force
 with Cons.prems(1) have "∀k < length As. As ! k ∈ wffs ! k"
 by fastforce
 ultimately have "⏹^\Q\⋆ (B ⏹ A) As ∈ wffsβ"
 using Cons.IH by (simp only:)
 moreover have "⏹^\Q\⋆ B (A # As) = ⏹^\Q\⋆ (B ⏹ A) As"
 by simp
 ultimately show ?case
 by (simp only:)
 

  generalized_abs_wff [intro]:
 assumes "B ∈ wffsβ"
 shows "λ^\Q\⋆ vs B ∈ wffs (→) (map snd vs) β"
  assms proof (induction vs)
 case Nil
 then show ?case
 by simp
 
 case (Cons v vs)
 let ?δ = "foldr (→) (map snd vs) β"
 obtain x and α where "v = (x, α)"
 by fastforce
 then have "FVar v ∈ wffsα"
 by auto
 from Cons.prems have "λ^\Q\⋆ vs B ∈ wffsδ"
 by (fact Cons.IH)
 with ‹v = (x, α)› have "FAbs v (λ^\Q\⋆ vs B) ∈ wffsα→?δ"
 by blast
 moreover from ‹v = (x, α)› have "foldr (→) (map snd (v # vs)) β = α→?δ"
 by simp
 moreover have "λ^\Q\⋆ (v # vs) B = FAbs v (λ^\Q\⋆ vs B)"
 by simp
 ultimately show ?case by (simp only:)
 

  Q_wff [intro]:
 shows "Qα ∈ wffsα→α→o"
 by auto

  iota_wff [intro]:
 shows "ι ∈ wffsi→o)→i"
 by auto

  equality_wff [intro]:
java.lang.NullPointerException
 shows "A =α B ∈ wffs"
 using assms by auto

  equivalence_wff [intro]:
 assumes "A ∈ wffs" and "B ∈ wffs"
 shows "A ≡^\Q B ∈ wffs"
 using assms unfolding equivalence_def by blast

  true_wff [intro]:
 shows "T ∈ wffs"
 by force

  false_wff [intro]:
 shows "F ∈ wffs"
 by auto

  pi_wff [intro]:
 shows "∏α ∈ wffsα→o)→o"
 using PI_def by fastforce

  forall_wff [intro]:
 assumes "A ∈ wffs"
 shows "∀xα. A ∈ wffs"
 using assms and pi_wff unfolding forall_def by blast

  generalized_forall_wff [intro]:
 assumes "B ∈ wffs"
 shows "∀^\Q\⋆ vs B ∈ wffs"
  assms proof (induction vs)
 case (Cons v vs)
 then show ?case
 using surj_pair[of v] by force
  simp

  conj_fun_wff [intro]:
 shows "∧→o→o ∈ wffs→o→o"
 by auto

  conj_op_wff [intro]:
 assumes "A ∈ wffs" and "B ∈ wffs"
 shows "A ∧^\Q B ∈ wffs"
 using assms unfolding conj_op_def by blast

  imp_fun_wff [intro]:
 shows "🪙→o→o ∈ wffs→o→o"
 by auto

  imp_op_wff [intro]:
 assumes "A ∈ wffs" and "B ∈ wffs"
 shows "A 🪙^\Q B ∈ wffs
 using assms unfolding imp_op_def by blast

  neg_wff [intro]:
 assumes "A ∈ wffs"
 shows " ∼^\Q A ∈ wffs"
 using assms by fastforce

  disj_fun_wff [intro]:
 shows "∨→o→o ∈ wffs→o→o"
 by auto

  disj_op_wff [intro]:
 assumes "A ∈ wffs" and "B ∈ wffs"
 shows "A ∨^\Q B ∈ wffs"
 using assms by auto

  exists_wff [intro]:
 assumes "A ∈ wffs"
 shows "∃xα. A ∈ wffs"
 using assms by fastforce

  inequality_wff [intro]:
 assumes "A ∈ wffsα" and "B ∈ wffsα"
 shows "A ≠α B ∈ wffs"
 using assms by fastforce

  wffs_from_app:
 assumes "A ⏹ B ∈ wffsβ"
 obtains α where "A ∈ wffsα→β" and "B ∈ wffsα"
 using assms by (blast elim: wffs_of_type_cases)

  wffs_from_generalized_app:
 assumes "⏹^\Q\⋆ B As ∈ wffsβ"
 obtains ts
 where "length ts = length As"
 and "∀k < length As. As ! k ∈ wffs ! k"
 and "B ∈ wffs (→) ts β"
  assms proof (induction As arbitrary: B thesis)
 case Nil
 then show ?case
 by simp
 
 case (Cons A As)
 from Cons.prems have "⏹^\Q\⋆ (B ⏹ A) As ∈ wffsβ"
 by auto
 then obtain ts
 where "length ts = length As"
 and "∀k < length As. As ! k ∈ wffs ! k"
 and "B ⏹ A ∈ wffs (→) ts β"
 using Cons.IH by blast
 moreover
 from ‹
 by (elim wffs_from_app)
 moreover from ‹length ts = length As› have "length (t # ts) = length (A # As)"
 by simp
 moreover from ‹A ∈ wffs› and ‹∀k < length As. As ! k ∈ wffs ! k›
 have "∀k < length (A # As). (A # As) ! k ∈ wffst # ts) ! k"
 by (simp add: nth_Cons')
 moreover from ‹B ∈ wffs→foldr (→) ts β› have "B ∈ wffs (→) (t # ts) β"
 by simp
 ultimately show ?case
 using Cons.prems(1) by blast
 

  wffs_from_abs:
 assumes "λxα. A ∈ wffsγ"
 obtains β where "γ = α→β" and "A ∈ wffsβ"
 using assms by (blast elim: wffs_of_type_cases)

  wffs_from_equality:
 assumes "A =α B ∈ wffs"
 shows "A ∈ wffsα" and "B ∈ wffsα"
 using assms by (fastforce elim: wffs_of_type_cases)+

  wffs_from_equivalence:
 assumes "A ≡^\Q B ∈ wffs"
 shows "A ∈ wffs" and "B ∈ wffs"
 using assms unfolding equivalence_def by (fact wffs_from_equality)+

  wffs_from_forall:
 assumes "∀xα. A ∈ wffs"
 shows "A ∈ wffs"
 using assms unfolding forall_def and PI_def
 by (fold equality_of_type_def) (drule wffs_from_equality, blast elim: wffs_from_abs)

  wffs_from_conj_fun:
 assumes "∧→o→o ⏹ A ⏹ B ∈ wffs"
 shows "A ∈ wffs" and "B ∈ wffs"
 using assms by (auto elim: wffs_from_app wffs_from_abs)

  wffs_from_conj_op:
 assumes "A ∧^\Q B ∈ wffs"
 shows "A ∈ wffs" and "B ∈ wffs"
 using assms unfolding conj_op_def by (elim wffs_from_conj_fun)+

  wffs_from_imp_fun:
 assumes "🪙→o→o ⏹ A ⏹ B ∈ wffs"
 shows "A ∈ wffs" and "B ∈ wffs"
 using assms by (auto elim: wffs_from_app wffs_from_abs)

  wffs_from_imp_op:
 assumes "A 🪙^\Q B ∈ wffs"
 shows "A ∈ wffs" and "B ∈ wffs"
 using assms unfolding imp_op_def by (elim wffs_from_imp_fun)+

  wffs_from_neg:
 assumes "∼^\Q A ∈ wffs"
 shows "A ∈ wffs"
 using assms unfolding neg_def by (fold equality_of_type_def) (drule wffs_from_equality, blast)

  wffs_from_disj_fun:
 assumes "∨→o→o ⏹ A ⏹ B ∈ wffs"
 shows "A ∈ wffs" and "B ∈ wffs"
 using assms by (auto elim: wffs_from_app wffs_from_abs)

  wffs_from_disj_op:
 assumes "A ∨^\Q B ∈ wffs"
 shows "A ∈ wffs" and "B ∈ wffs"
 using assms and wffs_from_disj_fun unfolding disj_op_def by blast+

  wffs_from_exists:
 assumes "∃xα. A ∈ wffs"
 shows "A ∈ wffs"
 using assms unfolding exists_def using wffs_from_neg and wffs_from_forall by blast

  wffs_from_inequality:
 assumes "A ≠α B ∈ wffs"
 shows "A ∈ wffsα" and "B ∈ wffsα"
 using assms unfolding inequality_of_type_def using wffs_from_equality and wffs_from_neg by meson+

  wff_has_unique_type:
 assumes "A ∈ wffsα" and "A ∈ wffsβ"
 shows "α = β"
  assms proof (induction arbitrary: α β rule: form.induct)
 case (FVar v)
 obtain x and γ where "v = (x, γ)"
 by fastforce
 with FVar.prems have "α = γ" and "β = γ"
 by (blast elim: wffs_of_type_cases)+
 then show ?case ..
 
 case (FCon k)
 obtain x and γ where "k = (x, γ)"
 by fastforce
 with FCon.prems have "α = γ" and "β = γ"
 by (blast elim: wffs_of_type_cases)+
 then show ?case ..
 
 case (FApp A B)
 from FApp.prems obtain α' and β' where "A ∈ wffsα'→α" and "A ∈ wffsβ'→β"
 by (blast elim: wffs_from_app)
 with FApp.IH(1) show ?case
 by blast
 
 case (FAbs v A)
 obtain x and γ where "v = (x, γ)"
 by fastforce
 with FAbs.prems obtain α' and β'
 where "α = γ→α'" and "β = γ→β'" and "A ∈ wffsα'" and "A ∈ wffsβ'"
 by (blast elim: wffs_from_abs)
 with FAbs.IH show ?case
 by simp
 

  wffs_of_type_o_induct [consumes 1, case_names Var Con App]:
 assumes "A ∈ wffs"
 and "∧x. P (x)"
 and "∧c. P ({c})"
 and "∧A B α. A ∈ wffsα→o ==> B ∈ wffsα ==> P (A ⏹ B)"
 shows "P A"
 using assms by (cases rule: wffs_of_type_cases) simp_all

  diff_types_implies_diff_wffs:
 assumes "A ∈ wffsα" and "B ∈ wffsβ"
 and "α ≠ β"
 shows "A ≠ B"
 using assms and wff_has_unique_type by blast

  is_free_for_in_generalized_app [intro]:
 assumes "is_free_for A v B" and "∀C ∈ lset Cs. is_free_for A v C"
 shows "is_free_for A v (⏹^\Q\⋆ B Cs)"
  assms proof (induction Cs rule: rev_induct)
 case Nil
 then show ?case
 by simp
 
 case (snoc C Cs)
 from snoc.prems(2) have "is_free_for A v C" and "∀C ∈ lset Cs. is_free_for A v C"
 by simp_all
 with snoc.prems(1) have "is_free_for A v (⏹^\Q\⋆ B Cs)"
 using snoc.IH by simp
 with ‹is_free_for A v C› show ?case
 using is_free_for_to_app by simp
 

  is_free_for_in_equality [intro]:
 assumes "is_free_for A v B" and "is_free_for A v C"
 shows "is_free_for A v (B =α C)"
 using assms unfolding equality_of_type_def and Q_def and Q_constant_of_type_def
 by (intro is_free_for_to_app is_free_for_in_con)

  is_free_for_in_equivalence [intro]:
 assumes "is_free_for A v B" and "is_free_for A v C"
 shows "is_free_for A v (B ≡^\Q C)"
 using assms unfolding equivalence_def by (rule is_free_for_in_equality)

  is_free_for_in_true [intro]:
 shows "is_free_for A v (T)"
 by force

  is_free_for_in_false [intro]:
 shows "is_free_for A v (F)"
 unfolding false_def by (intro is_free_for_in_equality is_free_for_closed_form) simp_all

  is_free_for_in_forall [intro]:
 assumes "is_free_for A v B" and "(x, α) ∉ free_vars A"
 shows "is_free_for A v (∀xα. B)"
  forall_def and PI_def proof (fold equality_of_type_def)
 have "is_free_for A v (λxα. T)"
 using is_free_for_to_abs[OF is_free_for_in_true assms(2)] by fastforce
 moreover have "is_free_for A v (λxα. B)"
 by (fact is_free_for_to_abs[OF assms])
 ultimately show "is_free_for A v (λxα. T =α→o λxα. B)"
 by (iprover intro: assms(1) is_free_for_in_equality is_free_for_in_true is_free_for_to_abs)
 

  is_free_for_in_generalized_forall [intro]:
 assumes "is_free_for A v B" and "lset vs ∩ free_vars A = {}"
 shows "is_free_for A v (∀^\Q\⋆ vs B)"
  assms proof (induction vs)
 case Nil
 then show ?case
 by simp
 
 case (Cons v' vs)
 obtain x and α where "v' = (x, α)"
 by fastforce
 from Cons.prems(2) have "v' ∉ free_vars A" and "lset vs ∩ free_vars A = {}"
 by simp_all
 from Cons.prems(1) and ‹lset vs ∩ free_vars A = {}› have "is_free_for A v (∀^\Q\⋆ vs B)"
 by (fact Cons.IH)
 from this and ‹v' ∉ free_vars A›[unfolded ‹v' = (x, α)›] have "is_free_for A v (∀xα. ∀^\Q\⋆ vs B)"
 by (intro is_free_for_in_forall)
 with ‹v' = (x, α)› show ?case
 by simp
 

  is_free_for_in_conj [intro]:
 assumes "is_free_for A v B" and "is_free_for A v C"
 shows "is_free_for A v (B ∧^\Q C)"
  -
 have "free_vars ∧→o→o = {}"
 by force
 then have "is_free_for A v (∧→o→o)"
 using is_free_for_closed_form by fast
 with assms have "is_free_for A v (∧→o→o ⏹ B ⏹ C)"
 by (intro is_free_for_to_app)
 then show ?thesis
 by (fold conj_op_def)
 

  is_free_for_in_imp [intro]:
 assumes "is_free_for A v B" and "is_free_for A v C"
 shows "is_free_for A v (B 🪙^\Q C)"
  -
 have "free_vars 🪙→o→o = {}"
 by force
 then have "is_free_for A v (🪙→o→o)"
 using is_free_for_closed_form by fast
 with assms have "is_free_for A v (🪙→o→o ⏹ B ⏹ C)"
 by (intro is_free_for_to_app)
 then show ?thesis
 by (fold imp_op_def)
 

  is_free_for_in_neg [intro]:
 assumes "is_free_for A v B"
 shows "is_free_for A v (∼^\Q B)"
 using assms unfolding neg_def and Q_def and Q_constant_of_type_def
 by (intro is_free_for_to_app is_free_for_in_false is_free_for_in_con)

  is_free_for_in_disj [intro]:
 assumes "is_free_for A v B" and "is_free_for A v C"
 shows "is_free_for A v (B ∨^\Q C)"
  -
 have "free_vars ∨→o→o = {}"
 by force
 then have "is_free_for A v (∨→o→o)"
 using is_free_for_closed_form by fast
 with assms have "is_free_for A v (∨→o→o ⏹ B ⏹ C)"
 by (intro is_free_for_to_app)
 then show ?thesis
 by (fold disj_op_def)
 

  replacement_preserves_typing:
 assumes "C(•p ← B•) ⊳ D"
 and "A ⪯ C"
 and "A ∈ wffsα" and "B ∈ wffsα"
 shows "C ∈ wffsβ ⟷ D ∈ wffsβ"
  assms proof (induction arbitrary: β rule: is_replacement_at.induct)
 case (pos_found p C C' A)
 then show ?case
 using diff_types_implies_diff_wffs by auto
  (metis is_subform_at.simps(2,3,4) wffs_from_app wffs_from_abs wffs_of_type_simps)+

  replacement_preserves_typing':
 assumes "C(•p ← B•) ⊳ D"
 and "A ⪯ C"
 and "A ∈ wffsα" and "B ∈ wffsα"
 and "C ∈ wffsβ" and "D ∈ wffsγ"
 shows "β = γ"
 using assms and replacement_preserves_typing and wff_has_unique_type by simp

  ‹Closed formulas and sentences:›

  is_closed_wff_of_type :: "form ==> type ==> bool" where
 [iff]: "is_closed_wff_of_type A α ⟷ A ∈ wffsα ∧ free_vars A = {}"

  is_sentence :: "form ==> bool" where
 [iff]: "is_sentence A ⟷ is_closed_wff_of_type A o"

  ‹Substitutions›

  substitution = "(var, form) fmap"

  is_substitution :: "substitution ==> bool" where
 [iff]: "is_substitution θ ⟷ (∀(x, α) ∈ fmdom' θ. θ $$! (x, α) ∈ wffsα)"

  substitute :: "substitution ==> form ==> form" (‹S _ _› [51, 51]) where
 "S θ (xα) = (case θ $$ (x, α) of None ==> xα | Some A ==> A)"
  "S θ ({c}α) = {c}α"
  "S θ (A ⏹ B) = (S θ A) ⏹ (S θ B)"
  "S θ (λxα. A) = (if (x, α) ∉ fmdom' θ then λxα. S θ A else λxα. S (fmdrop (x, α) θ) A)"

  empty_substitution_neutrality:
 shows "S {$$} A = A"
 by (induction A) auto

  substitution_preserves_typing:
 assumes "is_substitution θ"
 and "A ∈ wffsα"
 shows "S θ A ∈ wffsα"
  assms(2) and assms(1)[unfolded is_substitution_def] proof (induction arbitrary: θ)
 case (var_is_wff α x)
 then show ?case
 by (cases "(x, α) ∈ fmdom' θ") (use fmdom'_notI in ‹force+›)
 
 case (abs_is_wff β A α x)
 then show ?case
 proof (cases "(x, α) ∈ fmdom' θ")
 case True
 then have "S θ (λxα. A) = λxα. S (fmdrop (x, α) θ) A"
 by simp
 moreover from abs_is_wff.prems have "is_substitution (fmdrop (x, α) θ)"
 by fastforce
 with abs_is_wff.IH have "S (fmdrop (x, α) θ) A ∈ wffsβ"
 by simp
 ultimately show ?thesis
 by auto
 next
 case False
 then have "S θ (λxα. A) = λxα. S θ A"
 by simp
 moreover from abs_is_wff.IH have "S θ A ∈ wffsβ"
 using abs_is_wff.prems by blast
 ultimately show ?thesis
 by fastforce
 qed
  force+

  derived_substitution_simps:
 shows "S θ T = T"
 and "S θ F = F"
 and "S θ (∏α) = ∏α"
 and "S θ (∼^\Q B) = ∼^\Q (S θ B)"
 and "S θ (B =α C) = (S θ B) =α (S θ C)"
 and "S θ (B ∧^\Q C) = (S θ B) ∧^\Q (S θ C)"
 and "S θ (B ∨^\Q C) = (S θ B) ∨^\Q (S θ C)"
 and "S θ (B 🪙^\Q C) = (S θ B) 🪙^\Q (S θ C)"
 and "S θ (B ≡^\Q C) = (S θ B) ≡^\Q (S θ C)"
 and "S θ (B ≠α C) = (S θ B) ≠α (S θ C)"
 and "S θ (∀xα. B) = (if (x, α) ∉ fmdom' θ then ∀xα. S θ B else ∀xα. S (fmdrop (x, α) θ) B)"
 and "S θ (∃xα. B) = (if (x, α) ∉ fmdom' θ then ∃xα. S θ B else ∃xα. S (fmdrop (x, α) θ) B)"
 by auto

  generalized_app_substitution:
 shows "S θ (⏹^\Q\⋆ A Bs) = ⏹^\Q\⋆ (S θ A) (map (λB. S θ B) Bs)"
 by (induction Bs arbitrary: A) simp_all

  generalized_abs_substitution:
 shows "S θ (λ^\Q\⋆ vs A) = λ^\Q\⋆ vs (S (fmdrop_set (fmdom' θ ∩ lset vs) θ) A)"
  (induction vs arbitrary: θ)
 case Nil
 then show ?case
 by simp
 
 case (Cons v vs)
 obtain x and α where "v = (x, α)"
 by fastforce
 then show ?case
 proof (cases "v ∉ fmdom' θ")
 case True
 then have *: "fmdom' θ ∩ lset (v # vs) = fmdom' θ ∩ lset vs"
 by simp
 from True have "S θ (λ^\Q\⋆ (v # vs) A) = λxα. S θ (λ^\Q\⋆ vs A)"
 using ‹v = (x, α)› by auto
 also have "… = λxα. λ^\Q\⋆ vs (S (fmdrop_set (fmdom' θ ∩ lset vs) θ) A)"
 using Cons.IH by (simp only:)
 also have "… = λ^\Q\⋆ (v # vs) (S (fmdrop_set (fmdom' θ ∩ lset (v # vs)) θ) A)"
 using ‹v = (x, α)› and * by auto
 finally show ?thesis .
 next
 case False
 let ?θ' = "fmdrop v θ"
 have *: "fmdrop_set (fmdom' θ ∩ lset (v # vs)) θ = fmdrop_set (fmdom' ?θ' ∩ lset vs) ?θ'"
 using False by clarsimp (metis Int_Diff Int_commute fmdrop_set_insert insert_Diff_single)
 from False have "S θ (λ^\Q\⋆ (v # vs) A) = λxα. S ?θ' (λ^\Q\⋆ vs A)"
 using ‹v = (x, α)› by auto
 also have "… = λxα. λ^\Q\⋆ vs (S (fmdrop_set (fmdom' ?θ' ∩ lset vs) ?θ') A)"
 using Cons.IH by (simp only:)
 also have "… = λ^\Q\⋆ (v # vs) (S (fmdrop_set (fmdom' θ ∩ lset (v # vs)) θ) A)"
 using ‹v = (x, α)› and * by auto
 finally show ?thesis .
 qed
 

  generalized_forall_substitution:
 shows "S θ (∀^\Q\⋆ vs A) = ∀^\Q\⋆ vs (S (fmdrop_set (fmdom' θ ∩ lset vs) θ) A)"
  (induction vs arbitrary: θ)
 case Nil
 then show ?case
 by simp
 
 case (Cons v vs)
 obtain x and α where "v = (x, α)"
 by fastforce
 then show ?case
 proof (cases "v ∉ fmdom' θ")
 case True
 then have *: "fmdom' θ ∩ lset (v # vs) = fmdom' θ ∩ lset vs"
 by simp
 from True have "S θ (∀^\Q\⋆ (v # vs) A) = ∀xα. S θ (∀^\Q\⋆ vs A)"
 using ‹v = (x, α)› by auto
 also have "… = ∀xα. ∀^\Q\⋆ vs (S (fmdrop_set (fmdom' θ ∩ lset vs) θ) A)"
 using Cons.IH by (simp only:)
 also have "… = ∀^\Q\⋆ (v # vs) (S (fmdrop_set (fmdom' θ ∩ lset (v # vs)) θ) A)"
 using ‹v = (x, α)› and * by auto
 finally show ?thesis .
 next
 case False
 let ?θ' = "fmdrop v θ"
 have *: "fmdrop_set (fmdom' θ ∩ lset (v # vs)) θ = fmdrop_set (fmdom' ?θ' ∩ lset vs) ?θ'"
 using False by clarsimp (metis Int_Diff Int_commute fmdrop_set_insert insert_Diff_single)
 from False have "S θ (∀^\Q\⋆ (v # vs) A) = ∀xα. S ?θ' (∀^\Q\⋆ vs A)"
 using ‹v = (x, α)› by auto
 also have "… = ∀xα. ∀^\Q\⋆ vs (S (fmdrop_set (fmdom' ?θ' ∩ lset vs) ?θ') A)"
 using Cons.IH by (simp only:)
 also have "… = ∀^\Q\⋆ (v # vs) (S (fmdrop_set (fmdom' θ ∩ lset (v # vs)) θ) A)"
 using ‹v = (x, α)› and * by auto
 finally show ?thesis .
 qed
 

  singleton_substitution_simps:
 shows "S {(x, α) 🍋 A} (yβ) = (if (x, α) ≠ (y, β) then yβ else A)"
 and "S {(x, α) 🍋 A} ({c}α) = {c}α"
 and "S {(x, α) 🍋 A} (B ⏹ C) = (S {(x, α) 🍋 A} B) ⏹ (S {(x, α) 🍋 A} C)"
 and "S {(x, α) 🍋 A} (λyβ. B) = λyβ. (if (x, α) = (y, β) then B else S {(x, α) 🍋 A} B)"
 by (simp_all add: empty_substitution_neutrality fmdrop_fmupd_same)

  substitution_preserves_freeness:
 assumes "y ∉ free_vars A" and "y ≠ z"
 shows "y ∉ free_vars S {x 🍋 FVar z} A"
  assms(1) proof (induction A rule: free_vars_form.induct)
 case (1 x' α)
 with assms(2) show ?case
 using surj_pair[of z] by (cases "x = (x', α)") force+
 
 case (4 x' α A)
 then show ?case
 using surj_pair[of z]
 by (cases "x = (x', α)") (use singleton_substitution_simps(4) in presburger, auto)
  auto

  renaming_substitution_minimal_change:
 assumes "y ∉ vars A" and "y ≠ z"
 shows "y ∉ vars (S {x 🍋 FVar z} A)"
  assms(1) proof (induction A rule: vars_form.induct)
 case (1 x' α)
 with assms(2) show ?case
 using surj_pair[of z] by (cases "x = (x', α)") force+
 
 case (4 x' α A)
 then show ?case
 using surj_pair[of z]
 by (cases "x = (x', α)") (use singleton_substitution_simps(4) in presburger, auto)
  auto

  free_var_singleton_substitution_neutrality:
 assumes "v ∉ free_vars A"
 shows "S {v 🍋 B} A = A"
 using assms
 by
 (induction A rule: free_vars_form.induct)
 (simp_all, metis empty_substitution_neutrality fmdrop_empty fmdrop_fmupd_same)

  identity_singleton_substitution_neutrality:
 shows "S {v 🍋 FVar v} A = A"
 by
 (induction A rule: free_vars_form.induct)
 (simp_all add: empty_substitution_neutrality fmdrop_fmupd_same)

  free_var_in_renaming_substitution:
 assumes "x ≠ y"
 shows "(x, α) ∉ free_vars (S {(x, α) 🍋 yα} B)"
 using assms by (induction B rule: free_vars_form.induct) simp_all

  renaming_substitution_preserves_form_size:
 shows "form_size (S {v 🍋 FVar v'} A) = form_size A"
  (induction A rule: form_size.induct)
 case (1 x α)
 then show ?case
 using form_size.elims by auto
 
 case (4 x α A)
 then show ?case
 by (cases "v = (x, α)") (use singleton_substitution_simps(4) in presburger, auto)
  simp_all

  ‹The following lemma corresponds to X5100 in cite‹"andrews:2002"›:›

  substitution_composability:
 assumes "v' ∉ vars B"
 shows "S {v' 🍋 A} S {v 🍋 FVar v'} B = S {v 🍋 A} B"
  assms proof (induction B arbitrary: v')
 case (FAbs w C)
 then show ?case
 proof (cases "v = w")
 case True
 from ‹v' ∉ vars (FAbs w C)› have "v' ∉ free_vars (FAbs w C)"
 using free_vars_in_all_vars by blast
 then have "S {v' 🍋 A} (FAbs w C) = FAbs w C"
 by (rule free_var_singleton_substitution_neutrality)
 from ‹v = w› have "v ∉ free_vars (FAbs w C)"
 using surj_pair[of w] by fastforce
 then have "S {v 🍋 A} (FAbs w C) = FAbs w C"
 by (fact free_var_singleton_substitution_neutrality)
 also from ‹S {v' 🍋 A} (FAbs w C) = FAbs w C› have "… = S {v' 🍋 A} (FAbs w C)"
 by (simp only:)
 also from ‹v = w› have "… = S {v' 🍋 A} S {v 🍋 FVar v'} (FAbs w C)"
 using free_var_singleton_substitution_neutrality[OF ‹v ∉ free_vars (FAbs w C)›] by (simp only:)
 finally show ?thesis ..
 next
 case False
 from FAbs.prems have "v' ∉ vars C"
 using surj_pair[of w] by fastforce
 then show ?thesis
 proof (cases "v' = w")
 case True
 with FAbs.prems show ?thesis
 using vars_form.elims by auto
 next
 case False
 from ‹v ≠ w› have "S {v 🍋 A} (FAbs w C) = FAbs w (S {v 🍋 A} C)"
 using surj_pair[of w] by fastforce
 also from FAbs.IH have "… = FAbs w (S {v' 🍋 A} S {v 🍋 FVar v'} C)"
 using ‹v' ∉ vars C› by simp
 also from ‹v' ≠ w› have "… = S {v' 🍋 A} (FAbs w (S {v 🍋 FVar v'} C))"
 using surj_pair[of w] by fastforce
 also from ‹v ≠ w› have "… = S {v' 🍋 A} S {v 🍋 FVar v'} (FAbs w C)"
 using surj_pair[of w] by fastforce
 finally show ?thesis ..
 qed
 qed
  auto

  ‹The following lemma corresponds to X5101 in cite‹"andrews:2002"›:›

  renaming_substitution_composability:
 assumes "z ∉ free_vars A" and "is_free_for (FVar z) x A"
 shows "S {z 🍋 FVar y} S {x 🍋 FVar z} A = S {x 🍋 FVar y} A"
  assms proof (induction A arbitrary: z)
 case (FVar v)
 then show ?case
 using surj_pair[of v] and surj_pair[of z] by fastforce
 
 case (FCon k)
 then show ?case
 using surj_pair[of k] by fastforce
 
 case (FApp B C)
 let ?θzy = "{z 🍋 FVar y}" and ?θxz = "{x 🍋 FVar z}" and ?θxy = "{x 🍋 FVar y}"
 from ‹is_free_for (FVar z) x (B ⏹ C)› have "is_free_for (FVar z) x B" and "is_free_for (FVar z) x C"
 using is_free_for_from_app by iprover+
 moreover from ‹z ∉ free_vars (B ⏹ C)› have "z ∉ free_vars B" and "z ∉ free_vars C"
 by simp_all
 ultimately have *: "S ?θzy S ?θxz B = S ?θxy B" and **: "S ?θzy S ?θxz C = S ?θxy C"
 using FApp.IH by simp_all
 have "S ?θzy S ?θxz (B ⏹ C) = (S ?θzy S ?θxz B) ⏹ (S ?θzy S ?θxz C)"
 by simp
 also from * and ** have "… = (S ?θxy B) ⏹ (S ?θxy C)"
 by (simp only:)
 also have "… = S ?θxy (B ⏹ C)"
 by simp
 finally show ?case .
 
 case (FAbs w B)
 let ?θzy = "{z 🍋 FVar y}" and ?θxz = "{x 🍋 FVar z}" and ?θxy = "{x 🍋 FVar y}"
 show ?case
 proof (cases "x = w")
 case True
 then show ?thesis
 proof (cases "z = w")
 case True
 with ‹x = w› have "x ∉ free_vars (FAbs w B)" and "z ∉ free_vars (FAbs w B)"
 using surj_pair[of w] by fastforce+
 from ‹x ∉ free_vars (FAbs w B)› have "S ?θxy (FAbs w B) = FAbs w B"
 by (fact free_var_singleton_substitution_neutrality)
 also from ‹z ∉ free_vars (FAbs w B)› have "… = S ?θzy (FAbs w B)"
 by (fact free_var_singleton_substitution_neutrality[symmetric])
 also from ‹x ∉ free_vars (FAbs w B)› have "… = S ?θzy S ?θxz (FAbs w B)"
 using free_var_singleton_substitution_neutrality by simp
 finally show ?thesis ..
 next
 case False
 with ‹x = w› have "z ∉ free_vars B" and "x ∉ free_vars (FAbs w B)"
 using ‹z ∉ free_vars (FAbs w B)› and surj_pair[of w] by fastforce+
 from ‹z ∉ free_vars B› have "S ?θzy B = B"
 by (fact free_var_singleton_substitution_neutrality)
 from ‹x ∉ free_vars (FAbs w B)› have "S ?θxy (FAbs w B) = FAbs w B"
 by (fact free_var_singleton_substitution_neutrality)
 also from ‹S ?θzy B = B› have "… = FAbs w (S ?θzy B)"
 by (simp only:)
 also from ‹z ∉ free_vars (FAbs w B)› have "… = S ?θzy (FAbs w B)"
 by (simp add: ‹FAbs w B = FAbs w (S ?θzy B)› free_var_singleton_substitution_neutrality)
 also from ‹x ∉ free_vars (FAbs w B)› have "… = S ?θzy S ?θxz (FAbs w B)"
 using free_var_singleton_substitution_neutrality by simp
 finally show ?thesis ..
 qed
 next
 case False
 then show ?thesis
 proof (cases "z = w")
 case True
 have "x ∉ free_vars B"
 proof (rule ccontr)
 assume "¬ x ∉ free_vars B"
 with ‹x ≠ w› have "x ∈ free_vars (FAbs w B)"
 using surj_pair[of w] by fastforce
 then obtain p where "p ∈ positions (FAbs w B)" and "is_free_at x p (FAbs w B)"
 using free_vars_in_is_free_at by blast
 with ‹is_free_for (FVar z) x (FAbs w B)› have "¬ in_scope_of_abs z p (FAbs w B)"
 by (meson empty_is_position is_free_at_in_free_vars is_free_at_in_var is_free_for_def)
 moreover obtain p' where "p = « # p'"
 using is_free_at_from_absE[OF ‹is_free_at x p (FAbs w B)›] by blast
 ultimately have "z ≠ w"
 using in_scope_of_abs_in_abs by blast
 with ‹z = w› show False
 by contradiction
 qed
 then have *: "S ?θxy B = S ?θxz B"
 using free_var_singleton_substitution_neutrality by auto
 from ‹x ≠ w› have "S ?θxy (FAbs w B) = FAbs w (S ?θxy B)"
 using surj_pair[of w] by fastforce
 also from * have "… = FAbs w (S ?θxz B)"
 by (simp only:)
 also from FAbs.prems(1) have "… = S ?θzy (FAbs w (S ?θxz B))"
 using ‹x ∉ free_vars B› and free_var_singleton_substitution_neutrality by auto
 also from ‹x ≠ w› have "… = S ?θzy S ?θxz (FAbs w B)"
 using surj_pair[of w] by fastforce
 finally show ?thesis ..
 next
 case False
 obtain vw and α where "w = (vw, α)"
 by fastforce
 with ‹is_free_for (FVar z) x (FAbs w B)› and ‹x ≠ w› have "is_free_for (FVar z) x B"
 using is_free_for_from_abs by iprover
 moreover from ‹z ∉ free_vars (FAbs w B)› and ‹z ≠ w› and ‹w = (vw, α)› have "z ∉ free_vars B"
 by simp
 ultimately have *: "S ?θzy S ?θxz B = S ?θxy B"
 using FAbs.IH by simp
 from ‹x ≠ w› have "S ?θxy (FAbs w B) = FAbs w (S ?θxy B)"
 using ‹w = (vw, α)› and free_var_singleton_substitution_neutrality by simp
 also from * have "… = FAbs w (S ?θzy S ?θxz B)"
 by (simp only:)
 also from ‹z ≠ w› have "… = S ?θzy (FAbs w (S ?θxz B))"
 using ‹w = (vw, α)› and free_var_singleton_substitution_neutrality by simp
 also from ‹x ≠ w› have "… = S ?θzy S ?θxz (FAbs w B)"
 using ‹w = (vw, α)› and free_var_singleton_substitution_neutrality by simp
 finally show ?thesis ..
 qed
 qed
 

  absent_vars_substitution_preservation:
 assumes "v ∉ vars A"
 and "∀v' ∈ fmdom' θ. v ∉ vars (θ $$! v')"
 shows "v ∉ vars (S θ A)"
  assms proof (induction A arbitrary: θ)
 case (FVar v')
 then show ?case
 using surj_pair[of v'] by (cases "v' ∈ fmdom' θ") (use fmlookup_dom'_iff in force)+
 
 case (FCon k)
 then show ?case
 using surj_pair[of k] by fastforce
 
 case FApp
 then show ?case
 by simp
 
 case (FAbs w B)
 from FAbs.prems(1) have "v ∉ vars B"
 using vars_form.elims by auto
 then show ?case
 proof (cases "w ∈ fmdom' θ")
 case True
 from FAbs.prems(2) have "∀v' ∈ fmdom' (fmdrop w θ). v ∉ vars ((fmdrop w θ) $$! v')"
 by auto
 with ‹v ∉ vars B› have "v ∉ vars (S (fmdrop w θ) B)"
 by (fact FAbs.IH)
 with FAbs.prems(1) have "v ∉ vars (FAbs w (S (fmdrop w θ) B))"
 using surj_pair[of w] by fastforce
 moreover from True have "S θ (FAbs w B) = FAbs w (S (fmdrop w θ) B)"
 using surj_pair[of w] by fastforce
 ultimately show ?thesis
  simp
 next
 case False
  show ?thesis
 Hbpemsdsr_p[f ae
 qed
 

 _oin
  "🚫
  lat:"na \Rightarrow int ==> int" where
  assms proof (induction B arbitrary: θ)
 case (FAbs w B)
 
 proof (cases "v ≠"n it<> as. ∣as!i∣
 case True
 with FAbs.
 using surj_pair[of w] by fastforce
 then show ?thesis
 proof (cases "w ∈i. b5 i 1M )"
 case True
java.lang.NullPointerException
 using surj_pair[of w] by fastforce
 <>  A} ++fdro w <heta)as. ∣as!i∣
 addfo_fm
java.lang.NullPointerException
 
 also Tue ae \dots= S θ
 using surj_pair[of w] by fastforce
java.lang.StringIndexOutOfBoundsException: Index 28 out of bounds for length 28
 next
 case False
 with -
 ng \<envas - 1]"
 also frm Asprs1 ad open>v \notin> free_vars B› hav = FAbs w ()
 usingsI by im
 also from False have "…as - 1]) =
 usingigsur_pair[f ] byfatfoce
 finally show ?thesi concat (p(\>_t asiM [0.i])
 qed
 next
 case False
 then have "fmdrop w ({v 🍋 A} ++f θ) = fmdrop w θ"
 by (simp add: fmdrop_fmupd_same)
 then show ?thesis
 using surj_pair[of w] by (metis (no_types, lifting) fmdrop_idle' substitute.simps(4))
 qed
  fastforce+

  substitution_absorption:
 assumes "θ $$ v = None" and "v ∉ vars B"
 shows "S ({v 🍋 A} ++f θ) B = S θ B"
 using assms by (meson free_vars_in_all_vars in_mono substitution_free_absorption)

  is_free_for_with_renaming_substitution:
 assumes "is_free_for A x B"
 and "y ∉ vars B"
 and "x ∉ fmdom' θ"
 and "∀v ∈ fmdom' θ. y ∉ vars (θ $$! v)"
 and "∀v ∈ fmdom' θ. is_free_for (θ $$! v) v B"
 shows "is_free_for A y (\<^       (

  b j u sslnthl
 then
 proof (cases "w = x")
 aseu
 with FVar.prems(3) have " Vry +) (ar Far "
 using
 then show ?ths
 using self_subform_is_at_top by fastforce
 next
 casebentbls_ast,utle_ont_p__is,uo
 then show ?thesis
 proof (cases "w ∈
 how ?case ns
 from False have "\<^then 
 using substitution_absorption and surj_pair[of oc
 also from True have "…
  (metis fmdom'_notI option.case_eq_if substitute.simps(1))
 finally def weM \<><length as. ∣as ! i∣) + 1)"
 
 by blast
 
 is_free_for_absent_varp
 next
 
 havenpltcncmp(l>i. if i<>hen adxe_da"icx ngh 1
 using surj_pair[of w] by fastforce
 with FVar.prems(2) show ?thesis
 using form_is_free_for_absent_var by prsugr
 qed
 qed
 
 case (FCon k)
 then show ?case
 using surj_pair[of k] by fastfrc
 
 i. if i∈i. [(if i∈I then plus_minus!1 else minus_plus!1),
 pm)hv"\notin vars C" and "y ∉
 by simp_all
 or"ifefoAx"
 using is_free_for_from_app by iprover+
 v ∈ !vv an> is_free_for (θ $$! v) v D"
 proof (rule ballI)
 fix
 assume "v ∈?teuodin car t_pedenth_ifuig \open🪙by auto
  App.prem() hav "s_fefor \theta $$! v) v (C ⏹ D)"
 by blast
 owsfeor(the $! v) v C ∧ is_free_for (θ $$! v) v D"
 using is_free_for_from_app by iprover+
 qed
 then have
 *: "∀
 (b1+) M(a!) (b (+1M -( (i+) )" f "<>I
java.lang.NullPointerException
 by simp
 moreoverapplbst ge_hl_2of i ],stforc)
 by (rule FApp.IH(1)[OF ‹
  have "is_free_for A y (S ({x 🍋f θ
 by (rule FApp.IH(2)[OF ‹
 ultimately show ?case
 M_def plus_minsdf mn_xdef
 
 \=0..<5.
 obtain x\w, αw)"
 
 from pply (sbsxho ], fatfore astfoce)
 using vars_form.elims b qed
 then show ?case
 proof (cases "w = x")
 case True
 from True and ‹length a > 0›
 using ‹
 with True have "S ({x 🍋 FVar y} ++S θ (FAbs w B)"
 using substitution_free_absorption by bl gen_a $ (()* x $n-15
 also have "\<    also unfolding n_def
 using ‹w)›w ∉ fmdom' θ›
 last3of ,OF\openlength a > 0›])
 moreover from ‹S θ B)› vas FAb (\^S θ B))"
 usingq
 ultimately shw e
 using is_free_for_absent_var by (simp only:)
 next
 case False
  (\Sum5..<).
java.lang.StringIndexOutOfBoundsException: Index 29 out of bounds for length 18
 from FAbs.prems(1) and ‹w ≠ and ‹ have "is_free_for A x B"
 using is_free_for_from_abs by iprover
 then show ?thesis
 proof (cases "w ∈ fmdom' θ
 case True
 then have "Sumi∈I-{n-1}. f i) + (\<Sumi} fi
 using ‹w)›
 also from ‹
 by (simp add: fmdrop_fmupd)
 lly
 have *: "j = 0..<4.i∈
 have "∀Su>i\in>I-{n-1 (1i+1)M a -( (+) )-(b (+) M)
 proof
 fix v
java.lang.StringIndexOutOfBoundsException: Index 51 out of bounds for length 51
 rd <>!- _anMa n 1 5 n
 by auto
 dropw\thetaclose> have "v ≠ w"
 proof
 ultimately show "is_free_fo{n-1} M * (4i4*4 M * ^(4*i+4)) +
 folding ‹w)›
 
 moreover from FAbs.prems(3) have "x ∉
 stbmmeri]
 moreover from FAbs.prems(4) have "∀ fmdom' (fmdrop w θ vars (fmdrop w θ $$! v)"
 by simp
 ultimately have "is_free_for A y (finite I›)
 using ‹y ∉ vars B› pror
 then show ?thesis
 proof (cases 0..<4.1) M))
 case True(a!(n-1-)) (b2s ) -(5nM)"
 have "y ∉i∈I--1.(1(+1 M a!i)) -b2(i) )- (b (i+) M) "
 proof -
 have "S ({x 🍋laby auto
 using * .
 lso <>\ \>= FAbs w ()B"
 (*5^*(i+)) fiin>>0..<n}
 finally have "nv_difftr)
 with FAbs.prems(2) and ‹ = (∑{0..<n}-I-{n-1}. (a!i)) + (∑} -!i)
 using absent_vars_substitution_preservation by auto
 qed
 then show ?thesis
 using is_fre = 0..<n.
 
 case False
 have "w ∉
 proof (rule ccontr)
 assume "¬ free_vars A"
 with asean ‹ have "¬ wB)"
 using form_with_fqed
 with

 qed
 with ‹0 < length\close)
 have "is_free_for A y (FAbs w (\<      qed{0..<n}
 unfolding ‹0 < length a›
 with * show ?thesis
 
 qed
 next
 case False
 have "∀ fmdom' θ. is_free_for (θ
 proof (rule ballI)
 fix v
 assume "v ∈fmom' \theta>"
 with FAbs.prems(5) have "is_free_for (θ $$! v) v (FAbs w B)"
 by blast
 moreover from ‹length a > 0›arith
 by blast
 imatelyshow"sfreefr (\theta>$! v) v B"
 unfolding ‹
 qed
 with ‹x∥∞≤
java.lang.NullPointerException
 ver
 thenshw ?thesis
 proof (cases "x ∉ free_vars B")
 case True
 have "y ∉ vars (S ({x 🍋 FVar y} ++f θ) (FAbs w B))"
 proof -
 from False and ‹w = (vwαw)›w ≠ x›
 have "S ({x 🍋f θ) (FAbs w B) = FAbs w (\<^ld(to
 by auto
java.lang.NullPointerException
 sing substitution_free_absorption y (simpimp add: fmom'_notD)
 finally have "\in> bhle"
 with FAbs.prems(2,4) and ‹w = (vw, αw)› show ?thesis
 using absent_vars_substitution_preservation by auto
 qed
 then show ?thesis
 using is_free_for_absent_var by simp
 next
 case False
 have "w ∉ free_vars A"
 proof (rule ccontr)
 assume "¬ w ∉ free_vars A"
 with False and ‹w ≠ x› have "¬ is_free_for A x (FAbs w B)"
 using form_with_free_binder_not_free_for by simp
 with FAbs.prems(1) show False
 by contradiction
 qed
 with ‹is_free_for A y (S ({x 🍋 FVar y} ++f θ) B)›
 have "is_free_for A y (FAbs w (S ({x 🍋 FVar y} ++f θ) B))"
 unfolding ‹w = (vw, αw)› partition_problem_nonzero"
 moreover from case (1 x)
java.lang.NullPointerException
 using surj_pair[of w] by fastforce
 
 by simp only:)
 qed
 qed
 qed
 

  ‹,} then a!(i div 5) else 0)"
 he following lemma allows us to fuse a singleton substitution and a simultaneous substitution,
 as long as the variable of the former does not occur anywhere in the latter:
 ›

java.lang.StringIndexOutOfBoundsException: Index 97 out of bounds for length 97
 assumes "is_substitution θ" and "is_substitution {v 🍋
 and "θe4t div 5 +1) M (a!(i div 5))))"
 shows "=1then n ?P1 i elels
  assms(1,3,4) proof (induction B arbitrary: θ)
 FVar v')v')
 then show ?case
 notin> fmdom' θ fmdom' θ
 case True
 then show ?thesis
 using surj_pair[of v'] by fastforce
 next
 case False
 then obtain A' where<> 
 by (meson fmlookup_dom'_iff)
 with False and FVar.prems(3) have "v ∉ vars A'"
 by fastforce
 then have "(n-1)" by auto
 using free_var_singleton_substitution_neutrality and free_vars_in_all_vars by blast
 from ‹ $$ v' = Some A'›S {v 🍋S θS {v 🍋
 using surj_pair[of v'] by fastforce
 also from ‹of a M "i "i div 5""]
 by (simp only:)
 also from ‹also have "…
 using surj_pair[of v'] by fastforce
 finally show ?thesis .
 qed
 
 case (FCon k)
 then show ?case
 using surj_pair[of k] by fastforce
 
 case (FApp C D)
 have " A} C \<>D A} ((<>S θ D))"
 by auto
 also have "…S {v 🍋S θ C) ⏹S {v 🍋S θ
 by simp
java.lang.NullPointerException
 using FApp.prems(1,2,3) by presburger
 also have "… = A} ++ D)"
 by simp
 finally show ?case .
 
 case (FAbs w C)
 btainvw, α)"
 by fastforce
 then show ?case
 proof (cases "v ≠ w")
  True
 show ?thesis
 proof (cases "w ∉)
 case True
 then have " A} S θFAbs w C) = A} (FAbs w (S θ"
 by (simp add: ‹w = (vw, α)›)
 also from ‹
 by (simp add: ‹)
 also from FAbs.IH have "…i<5*) < M
 using FAbs.prems(1,2,3) by blast
 also from ‹ and True have "…S ({v 🍋>f θ) (FAbs w C)"
 by (simp add: ‹
 finally show ?thesis .
 next
 case False
 then have "S {v 🍋 A} S θ (FAbs w C) = S {v 🍋 A} (FAbs w (S (fmdrop w θ) C))"
 by (simp add: ‹w = (vw, α)›)
 also from ‹v ≠ w› have "… = FAbs w (S {v 🍋 A} S (fmdrop w θ) C)"
 by (simp add: ‹w = (vw, α)›)
 also have "…
 "(∑
 from ‹(5*n-1)\<> 
 by fastforce
 moreover from ‹θ $$ v = None› have "(fmdrop w θ) $$ v = None"
 by force
 moreover from FAbs.prems(3) have "∀v' ∈ fmdom' (fmdrop w θ). v ∉ vars ((fmdrop w θ) $$! v')"
 by force
 ultimately show ?thesis
 using FAbs.IH by blast
 qed
 also from ‹v ≠ w› have "…[of "(🚫
 by (simp add: ‹w = (vlessThan_Sucof "(λ5* n - 4"]
 finally show ?thesis .
 qed
 next
 case False
 then show ?thesis
 proof (cases "w ∉ fmdom' θ")
 case True
 then have "S {v 🍋 A} S θ (FAbs w C) = S {v 🍋 A} (FAbs w (S θ C))"
 by (simp add: ‹w = (vw, αad: Suc3_eq_add_ ad.co
 
 using ‹w = (vw, α)› and singleton_substitution_simps(4) by presburger
 also from ‹¬ v ≠ w› and True have "… = FAbs w (S (fmdrop w ({v 🍋 A} ++f θ)) C)"
 by (simp add: fmdrop_fmupd_same fmdrop_idle')
 also from ‹¬ v ≠ w› have "… = S ({v 🍋?tesis using \openn-5= 5(n-1)›
java.lang.NullPointerException
 finally show ?thesis .
 next
 case False
 then have "S {v 🍋 A} S θ (FAbs w C) = S {v 🍋 A} (FAbs w (of\lambdai. <> 
 by (simp add: ‹ \dots=(\<><
 also from ‹¬ v ≠ w› have "… = FAbs w (S (fmdrop w θ) C)"
 using ‹θ $$ v = None›
 also from ‹¬. (∑
 by (simp add: fmdrop_fmupd_same)
 also from ‹¬ v ≠ w› and False and ‹} then a i else 00∣
 by (simp add: fmdom'_notI)
 finally show ?thesis .
 qed
 qed
 

  updated_substitution_is_substitution:
 assumes "v ∉ fmdom' θ" and "is_substitution (θ(v 🍋 A))"
 shows "is_substitution θ"
  is_substitution_def proof (intro ballI)
 fix v' :: var
 obtain x and α
 by fastforce
 assume "v' ∈ fmdom' θ"
 with assms(2)[unfolded is_substitution_def] have "v' ∈ fmdom' (θ(v 🍋 A))"
 by simp
 with assms(2)[unfolded is_substitution_def] have "θ(v 🍋 A) $$! (x, α) ∈ wffsα"
 using ‹
 with assms(1) and ‹
 by (metis fmupd_lookup)
 then show "case v' of (x, α) ==> θ $$! (x, α) ∈ wffsα"
 by (simp add: ‹
 

  is_renaming_substitution where
 [iff]: "is_renaming_substitution θ ⟷ is_substitution θ ∧ fmpred (λ_ A. ∃v. A = FVar v) θ"

  ‹
 The following lemma proves that $
 \d{\textsf{S}}\;^{x^1_{\alpha_1}\;\dots\;x^n_{\alpha_n}}_{y^1_{\alpha_1}\;\dots\;y^n_{\alpha_n}} B
 =
 \d{\textsf{S}}\;^{x^1_{\alpha_1}}_{y^1_{\alpha_1}}\;\cdots\;
 \d{\textsf{S}}\;^{x^n_{\alpha_n}}_{y^n_{\alpha_n}} B$ provided that

 x^1{\alpha_1;\\;x^n_{\alpha_n$ are distinct variables

 ▪ $y^1_{\alpha_1}\;\dots\;y^n_{\alpha_n}$ are distinct variables, distinct from
 $x^1_{\alpha_1}\;\dots\;x^n_{\alpha_n}$ and from all variables in ‹B› (i.e., they are fresh
 variables)

 In other words, simultaneously renaming distinct variables with fresh ones is equivalent to
 renaming each variable one at a time.
 ›

  fresh_vars_substitution_unfolding:
 fixes ps :: "(var × form) list"
 assumes "θ = fmap_of_list ps" and "is_renaming_substitution θ"
 and "distinct (map fst ps)" and "distinct (map snd ps)"
 and "vars (fmran' θ) ∩ (fmdom' θ ∪ ordertran vec_index_le_linf_no)
 shows "S θ B = foldr (λ(x, y) C. S {x 🍋 y} C) ps B"
  assms proof (induction ps arbitrary: θ)
 case Nil
 then have "θ = {$$}"
 by simp
 then have "S θ B = B"
 using empty_substitution_neutrality by (simp only:)
 with Nil show ?case
 proof
 
 case (Cons p ps)
 from Cons.prems(1,2) obtain x and y where "θ $$ (fst p) = Some (FVar y)" and "p = (x, FVar y)"
 using surj_pair[of p] by fastforce
 let ?θ' = "fmap_of_list ps"
 from Cons.prems(1) and ‹p = (x, FVar y)› have "θ = fmupd x (FVar y) ?θ'"
 by simp
 moreover from Cons.prems(3) and ‹p = (x, FVar y)› have "x ∉ fmdom' ?θ'"
 by simp
 ultimately have "θ = {x 🍋
 using fmap_singleton_comm by fastforce
 with Cons.prems(2) and ‹x ∉ fmdom' ?θ'›..<i5
 unfolding is_renaming_substitution_def and ‹θ = fmupd x (FVar y) ?θ'›
  uupda by (metis fmdiff_fmu fmdo'_not fm)
 from Cons.prems(2) and ‹θ = fmupd x (FVar y) ?θ'› have "is_renaming_substitution {x 🍋 FVar y}"
 by auto
 have "
 oldr (🚫
 =
 S {x 🍋
 by (simp add: ‹p = (x, FVar y)›)
 also have "… = S {x 🍋 FVar y} S ?θ' B"
 -
 from Cons.prems(3,4) have "distinct (map fst ps)" and "distinct (map snd ps)"
 by fastforce+
 moreover have "vars (fmran' ?θ') ∩ (fmdom' ?θ' ∪ vars B) = {}"
 proof -
 have "vars (fmran' θ) = vars ({FVar y} ∪n-1+4. x $ j * a0 j = ?h (n-1)"
 using ‹θ = fmupd x (FVar y) ?θ'› and ‹x ∉ fmdom' ?θ'› by (metis fmdom'_notD fmran'_fmupd)
 then have "vars (fmran' θ) = {y} ∪ vars (fmran' ?θ')"
 using single
 moreover have "fmdom' θ = {x} ∪ fmdom' ?θ'"
 by (simp add: ‹θ = {x 🍋 FVar y} ++f ?θ'›)
 ultimately show ?thesis
 using Cons.prems(5) by auto
 qed
 ultimately show ?thesis
 using Cons.IH and ‹is_renaming_substitution ?θ'› by simp
 qed
java.lang.NullPointerException
 proof (rule substitution_fusion)
 show "is_substitution ?θ'"
 using ‹is_renaming_substitution ?θ'› by simp
 show "is_substitution {x 🍋 FVar y}"
 using ‹?g ((n - 1 * 5 5 + xa) =
 show "?θ' $$ x = None"
 using \openx ∉
 show "∀v' ∈ fmdom' ?θ'. x ∉ vars (?θ' $$! v')"
 proof -
 have "x ∈ fmdom' θ"
 using ‹θ = {x 🍋 FVar y} ++f ?θ'› by simp
 then have "x ∉ vars (fmran' θ)"
 show ?thesis
 moreover have "{?θof "n-1" 4] div_rule
 unfolding \open🚫
 by (auto simp add: fmlookup_of_list fmlookup_dom'_iff fmran'I weak_map_of_SomeI)
 ultimately show ?thesis
 by force
java.lang.StringIndexOutOfBoundsException: Index 67 out of bounds for length 7
 
 
 by (simp only:)
 finally show ?case ..
 

  free_vars_agreement_substitution_equality:
 assumes "fmdom' θ = fmdom' θ'"
 and "∀v ∈ free_vars A ∩ fmdom' θ. θ $$! v = θ' $$! v"
 shows "S θ A = S θ' A"
  aasassms proof(induc A arbitr: θ
 caseshow?th
 have "free_vars (FVar v) = {v}"
 using surj_pair[of v] by fastforce
 with FVar have "θ $$! v = θ' $$! v"
 by force
 with FVar.prems(1) show ?case
 using surj_pair[of v] by (metis fmdom'_notD fmdom'_notI option.collapse substitute.simps(1))
 
 case FCon
 then show ?case
 by (metis prod.exhaust_sel substitute.simps(2))
 
 case (FApp B C)
 have "S θ
 by simp
 also have "… = (i. x$(i*5) + (if i<n-
 proof -
 have "∀v ∈)"
 and "∀v ∈k.
 using F = 0 ten d5(-+ d10 else ( (k div 4)5 k div -1))) ele
 with FApp.IH(1,2) and FApp.prems(1) show ?thesis
 by blast
 qed
 finally show ?case
 by simp
 
 case (FAbs w B)
 from bms(1,2) hae *: "∀ free_vars B - {w} ∩θ' $$! v"
 using surj_pair[of w] by fastforce
  cse
 proof (cases "w ∈ {1, 2} then if i < nunfong f1_def by aauto
 case True
 then have " * i +1)+(iif i < n
 using surj_pair[of w] by fastforce
 also have "…S (fmdrop w θ') B)"
 proof -
 from * have "∀v ∈ fmdom' (fmdrop w θ). (fmdrop w θ') $$! v"
 by simp
 moreover have "fmdom' (fmdrop w θ
 by (simp add: FAbs.prems(1))
 ultimately show ?thesis
 using FAbs.IH by blast
 qed
 inally ly show ?hesis
 using FAbs.prems(1) and True and surj_pair[of w] by fastforce
 next
 case False
 then have "S θ (FAbs w B) = FAbs w ( = f3 i" unfolding f3_def d1_def d2_def d3_def d4_def d5_def using True
 _i[of w] by by fastfore
 also have "…
 proof -
 from * have "∀v ∈ free_vars B x $ (i * + ) * 5 ^ (44 * i + 1 + x $(i * 5 +1) +
 using False by blast
 with FAbs.prems(1) show ?thesis
 using FAbs.IH by blast
 qed
 finally show ?thesis
 using FAbs.prems(1) and False and surj_pair[of w] by fastforce
 qed
 

  ‹ - 1)" using ‹ by auto
 The following lemma proves that $
 \d{\textsf{S}}\;^{x_\alpha}_{A_\alpha}\;
 \d{\textsf{S}}\;^{x^1_ unfolding ‹
 =
 \d{\textsf{S}}\;{
 \begingroupately show ?thesis
 \scriptstyle{x_\alpha} & \scriptstyle{x^1_{\alpha_1}} & \scriptstyle{\dots} & \scriptstyle{x^n_{\alpha_n}} \\
 \scriptstyle{A_\alpha} & \scriptstyle{\d{\small{\textsf{S}}}\;^{x_\alpha}_{A_\alpha} A^1_{\alpha_1}}
 & \scriptstyle{\dots} & \scriptstyle{\d{\small{\textsf{S}}}\;^{x_\alpha}_{A_\alpha} A^n_{\alpha_n}}
 \end{matrix} \endgroup} B$ provided that $x_\alpha$ is distinct from $x^1_{\alpha_1ha_1}, \dots^n{\\alp}$
 and $A^\} is s freee f $x^i_{\alpha_iin $B$:
 ›ig atL0LsTan b auto

  substitution_consolidation:
 assumes "v ∉ fmdom' θ"
 and "∀v' ∈ fmdom' θ. is_free_for (θ $$! v') v' B"
 shows "S {v 🍋S θ B = A} ++A'. }' \>) B"
  )
 case (FApp B C)
 have "∀v' ff a0_rest_def f a0_r'_def a0_lasst_def
  a1_def a1_last_def a2_def _def a3_last_def a4_def a5_def 
 fix v'
 assume "v' ∈ auo)
 with FApp.prems(2) have "is_free_for (θ
 by blast
 then show "is_free_for (θ $$! v') v' B ∧have "\dots= (∑i<n.
  case (1(1 i)
 qed
 with FApp.IH and FApp.prems(1) show ?case
 by simp
 
 case (FAbs w B)
 let ?θ' = "fmmap (λA'. <(i * 5 + j) 1 ij
 show ?case
 proof (cases "w ∈ fmdom' θ")
 case True
 then have "w ∈ fmdom' ?θ'"
 by simp
 with True and FAbs.prems have "v ≠ w"
 by blast
 from True have "S {v 🍋S θ (FAbs w B) = {v 🍋S (fmdrop w θ) B))"
 using surj_pair[of w] by fastforce
 also from ‹
 using surj_pair[of w] by fastforce
 also have "…> (fmdrop w ({v 🍋f ?θ')) B)"
 proof -
 obtain xn>0› by auto
 by fastfastforce
 have "∀v' ∈ fmdom' (fmdrop w θunfng f1_def x_paddf using \<openn>0› by auto
 proof
 fix v'
 assume "v' ∈
 (e"isfree_for (\<thetatheta(FAbs wB)"
 
java.lang.StringIndexOutOfBoundsException: Index 11 out of bounds for length 11
 have "is_free_for (θ $$! v') v' (λw (xw)"
 by auto
 then have "is_free_for (θn-1] \<>lengthauto›)
  is_fre_for_from_abby presburger
java.lang.NullPointerException
 by simp
 qed
 moreover have "v ∈
 by (simp add: FAbs.prems(1))
 ultimately show ?thesis
 using FAbs.IH and ‹ by (simp add: fmdrop_fmupd)
 qed
 finally show ?thesis
 using ‹i<n.
 next
 case False
 then have "w ∉ fmdom' ?θ'"
 by simp
 from FAbs.prems have "vusing \open0 < length n_def by force
 by si
 from False have *: "S {v 🍋S θ (FAbs w B) = A} (FAbs w ( B))"
 using surj_pa "(🚫
 then show ?thesis
 proof (cases "v ≠ w")
 case True
 then have "S {v 🍋 (∑
 using surj_pair[of w] by fastforce
 also have "… = FAbs w (i. d5 i * 5 ^ (4 * (i + 1)))" "{..<n-
 proof -
java.lang.NullPointerException
 by fastforce
 have "∀ fmdom' θ $$! v') v' B"
 proof
 fix v'
 assume "v' ∈ fmdom' θ"
 with FAbs.prems(2) have "is_free_for (θ $$! v') v' (FAbs w B)"
 by auto
 with ‹
 have "is_free_for (θ $$! v') v' (λx0<length ,
 by fastforce+
 then have "is_free_for (θi<5*in.
 using is_free_for_from_abs by presburger
 with ‹v' ≠ (xw, αw)› and ‹w = (xw, αw)› show "is_free_for (θ $$! v') v' B"
 by simp
 qed
 with FAbs.IH show ?thesis
 using FAbs.prems(1) by blast
 qed
 finally show ?thesis
 proof -
 assume "
 S {v 🍋 A} (FAbs w (S θ B)) = FAbs w (S ({v 🍋 A} ++f fmmap (substitute {v 🍋 A}) θ) B)"
 moreover have "w ∉ fmdom' ({v 🍋 A} ++f fmmap (substitute {v 🍋 i then dn 1)+ 0 ele d1 + d5 (i ) * 5 ^ (4 i) +
 using False and True by auto
 ultimately show ?thesis
 using * and surj_pair[of w] by fastforce
 qed
 next
 case False
 then have "v ∉ free_vars (FAbs w (S θ B))"
 using surj_pair[of w] by fastforce
 then have **: "S {v 🍋
 using free_var_singletoto
 also have "… = FAbs w (S ?θ meti ad.comme addrgt_eutrdiv_mult__self3 mod_Suc mod_div_div_rivial
 proof -
 {
 fix v'
 assume "v' ∈ fmdom' θ"
 with FAbs.prems(1) have "v' ≠ut sip d: mult.cmmutete)
  = (∑n. d k * 5^k)"
 assume "v ∈ free_vars ( (θ$$! v')" and "v' ∈ free_vars B"
 with ‹
 using form_with_free_binder_not_free_for by blast
 with FAbs.prems(2) and ‹Some helping lemmas to get equations.›
 
 }
 then have "∀ fmdom' θ. \notin free_vars (θ $$! v') ∨ free_vars B"
 
 then have "∀ fmdom' θ free_vars B ⟶S {v 🍋 $$! '<> 
 using free_var_singleton_substitution_neutrality by blast
 then have "∀if_xi__le_: "\<barif - 1 then x $ (i * 5 + 4) else 0)∣ e
 
 then have "S θ B = Shave prec_0: "i * 5 < x
 using free_vars_agreement_substitution_equality by (metis IntD1 fmdom'_map)
 then show ?thesis
 by simp
 qed
 also from False and FAbs.prems(1) have "…
 by (simp add: fmdrop_fmupd_same fmdrop_idle')
 also from False have "…S ({v 🍋f ?θ') (FAbs w B)"
 using surj_pair[of w] by fastforce
 finally show ?thesis
 using * a"∣≤
 qed
 qed
  force+

  vars_range_subtiuon
 assumes "is_substitution θ"
 and "v ∉
 shows "v ∉ vars (fmran' (fmdrop w θ))"
  assms proof (induction θ)
 case fmempty
 then show ?case
 by simp
 
 case (fmupd v' A θ
 from fmdom'_notI[OF fmupd.hyps]] n mdpemss(1 hav "is_subtittion \<theta"
 by (rule updated_substitution_is_substitution)
 moreover from fmupd.prems(2) and fmupd.hyps have "v ∉ vars (fmran' θ)"
 by simp
 ultimately have "v ∉
 by (rule fmupd.IH)
 sadfupdprms(2 show ?case
 by (simp add: fmdrop_fmupd)
 

  excluded_var_from_substitution:
 assumes "is_substitution θ"
 and "v ∉ fmdom' θ"
 and "v ∉ vas (ma' θ
 and "v ∉ vars A"
 shows "v \<       "
  assms proof (induction A arbitrary: θ)
 case (FVar v')
 then show ?case
 proof (cases "v' ∈ fmdom' θ{0..<n}
 
 then have "θ $$! v' ∈ fmran' θ"
 by (simp add: fmlookup_dom'_iff fmran'I)
 with FVar(3) have "v ∉ vars (θ(4 * +2) ddiv 4 = i" uto
 by simp
 with True show ?thesis
 using surj_pair[of v'] and fmdom'_notI by force
 next
 case False
 with FVar.prems(4) show ?thesis
 _pa[of v']by force 
 qed
 
 case (FCon k)
 then show ?case
 using surj_pair[of k] by force
 
 case (FApp B C)
 then show ?case
 by auto
 
 case (FAbs w B)
 haveve eq_ eq_1': "x$(i*5) + (if i<n-
 using surj_pair[of w] and FAbs.prems(4) by fastforce+
 then show ?case
 proof (cases "w ∉)
 case True
 then have "S θ (FAbs w B) = FAbs w (S θ B)"
 using surj_pair[of w] by fastforce
 moreover from FAbs.IH have "v ∉ vars (S θ B)"
 using FAbs.prems(1-3) and ‹v ∉ vars B›This defines the weight of the solution, since $x_{i,0} + x_{i,4}$ does not depend on
 ultimately show ?thesis
 using ‹v ≠ w›
 next
 case False
 then have "1 then x$(i*5+4) else 0)" if "i∈
 using surj_pair[of w] by fastforce
 moreover have "v ∉ vars (🚫
 proof -
 from FAbs.prems(1) have "is_substitution (fmdrop w θ)"
 by fastforce
 moreover from FAbs.prems(2) have "v ∉ fmdom' (fmdrop w
 by simp
 moreover from FAbs..prems(1,3) ve "v ∉ (fmran' (fmdrop w θ))"
 by (fact vars_range_substitution)
 ultimately show ?thesis
 using FAbs.IH and ‹
 qed
 imatelyshow ?thesis
 using ‹v ≠ if ∈.<n}" for i
 qed
 

  ‹Renaming of bound variabls have p_zero: "x$(i*5) = 0" if "i<n" i

  rename_bound_var :: "var ==> nat ==> form ==> form" where
 "rename_bound_var v y (xαα
java.lang.NullPointerException
  "rename_bound_var v y (B ⏹ C) = rename_bound_v
  "rename_bound_var v y (λ 0"
 (
 if (x, α) = v then
 λyS {(x, α 🍋} (rename_bound_var v y B)
 else
 λxα. (rename_bound_var v y B)
 )"

  rename_bound_var_preserves_typing:
 assumes "A ∈α
 shows "rename_bound_var (y, γ) z A ∈ wffs*5 = j›[symmetric] using p_zero[OF ‹
  assms proof (induction A)
 case (abs_is_wff β A δ x)
 then show ?case
 proof (cases "(x, δ) = (y, γ)")
 case True
java.lang.NullPointerException
 using substitution_preserves_typing by (simp add: wffs_of_type_intros(1))
 then have "λzγ. thesissis unfolding \ i*5+1 = j›[symmetric] using p_one[OF ‹
 by blast
 with True show ?thesis
 by simp
 next
 case False
 from abs_is_wff.IH have "λx rename_bound_var (y, γ) z A ∈δβ"
 by (metis add.soc add.commute less_Suc_eq lesdiff__conv less_mut_imp_div_lss
 with False show ?thesis
 by auto
 qed
  auto

  old_bound_var_not_free_in_abs_after_renaming:
 assumes "A ∈α
java.lang.NullPointerException
 and "(z, γ) ∉ vars A"
 shows "(y, γ free_vars (rename_bound_var (y, γ z (λγ
 using assms and free_var_in_renaming_substitution by (induction A) auto

  rename_bound_var_free_vars:
 assumes "A ∈ wffs
java.lang.NullPointerException
 and "(z, γ) ∉ vars A"
 shows "(z, γ
 using assms by (induction A) auto

  old_bound_var_not_free_after_renaming:
 assumes "A ∈ wffsα"
 and "z≠γ"
 and "(z, γ) ∉
 and "(y, γ) ∉ free_vars A"
 shows "(y, γ) ∉
  assms proof induction
 case (abs_is_wff βusing mod_5_chices[of"(λ
 then show ?case
 proof (cases "(x, α) = (y, γ)")
 case True
 with abs_is_wff.hyps and abs_is_wff.prems(2) show ?thesis
 usingold_bobound_var_not_free_in_aabs_fter_renaming by auto
 next
 case False
 with abs_is_wff.prems(2,3) and assms(2) show ?thesis
 using abs_is_wff.IH by force
 qed
 astforce+

  old_bound_vr_n_currn_afteterenaming:
 assumes "A ∈ wffs)"$(i*5) = 1
java.lang.NullPointerException
 shows "¬) p ( z (rename_bound_var (y, γ
  assms(1) proof (induction A arbitrary: p)
 case (var_is_wff α x)
 from assms(2) show ?case
 using subform_size_decrease by (cases "(x, α) = (y, γ)") fastforce+
 
 case (con_is_wff α c)
 then show ?case
 using occurs_at_alt_def(2) by auto
 
 case (app_is_wff α β A B)
 then show ?case
 f (cases p)
 case (Cons d p')
 then show ?thesis
 by (cases d) (use) = 1" if "i∈
 qed simp
 
 case (abs_is_wff β)
 then show ?case
 proof (cases p)
 case (Cons d p')
 then show ?thesis
  es d)
 case Left
 have *: "¬ymmetric]
 for x and α
 using Left and Cons and abs_is_wff.IH by simp
 then show ?thesis
 proof (cases "(x, α) = (y, γ)")
 case True
 with assms(2) have "
 S {(y, γ) 🍋i=n-1›
 =
 λz z
 using free_var_in_renaming_substitution and free_var_singleton_substitution_neutrality
 by simp
 moreover have "¬ occurs_at (y, γes "i<n-)
 using Left and Cons and * by simp
 ultimately show ?thesis
 by simp
 next
 case False
 with assms(2) have "
 then show ? ?thesis usi‹I›
 =
 λxαproof caes n1")
 by simp
 moreover have "¬ occurs_at (y, γ) p (λximadd: mult.commute)
 using Left and Cons and * by simp
 ultimately show ?thesis
 by simp
 qed
 qed (simp add: Cons)
 qed simp
 

  ‹set_diff[_diff[of I]) (auto simp add I_def n_deflessTan_atLasst0)
 The following lemma states that the result of term
 occurrences of the renamed variable:
 ›

  rename_bound_var_not_bound_occurrences:
 assumes "A ∈ wffsx$(i*5+4) = -1) ∨\and x$(i*5+4) = 0)" if "i<n-
 and "zx" using that ‹
 and "(z, γ) ∉
 and "occurs_at (y, γ) p (rename_bound_var (y, γ) z A)"
 shows "¬ in_scope_of_abs (z, γ) p (rename_bound_var (y, γ) z A)"
  assms(1,3,4) proof (induction arbitrary: p)
 case (var_is_wff α x)
 then show ?case
 by (simp add: subforms_from_var(2))
 
 case (con_is_wff α c)
 then show ?case
 using occurs_at_alt_def(2) by auto
 
 case (app_is_wff αnext
 from app_is_wff.prems(1) have "(z, γ) ∉ vars B" and "(z, γ) ∉w=-1› by auto
 by simp_all
 from app_is_wff.prems(2)
 I" using w_def unfolding ‹n>0› mult.commute)
 by simp
 then consider
 (a) "∃p'. p = « # p' ∧
 | (b) "∃p'. p = ¬ # p' ∧ oc by (simp add: mult.com.comute)
 using subforms_from_app by force
 then show ?case
 proof cases
 case a
 then obtain p' where "p = « # p'" and "occurs_at (y, γ) p' (rename_bound_var (y, γ) z B)"
 by blast
 then have "¬
 using app_is_wff.IH(1)[OF ‹
 then have "¬
 using ‹p = «y autoto
 then show ?thesis
 by blast
 next
 case b
 then obtain p' where "p = ¬d "occursurs_at (, gamma>) p' (rename_bound_var (y, γ) z C)"
 by blast
 then have "¬ in_scope_of_abs (z, γ) p' (rename_bound_var (y, γ) z C)"
 using app_is_wff.IH(2)[OF ‹
 then have "¬ in_scope_of_abs (z, γ) p (rename_bound_var (y, γ) z (B ⏹ C))" for B
 using ‹p = ¬proof (cases "i<n-
 then show ?thesis
 by blast
 qed
 
 case (abs_is_wff β A α x)
 from abs_is_wff.prems(1) have "(z, γ vars A" and "(z, γ) ≠ (x, α)"
 by fastforce+
 then show ?case
 proof (cases "(y, γ) = (x, α)")
 case True
 then have "occurs_at (y, \<then 
 using abs_is_wff.prems(2) by simp
 moreover have "¬ occurs_at (y, γ) p (λo
 using old_bound_var_not_ocurring_after_renaming[OF abs_is_wff.hyps assms(2)] and subforms_from_abs
 by fastforce
 ultimately show ?thesis
 by contradiction
 ext
  unfolding eq_0[symmet
 then have *: "rename_bound_var (y, γ) z (λxαI" for i
 by auto
 with abs_is_wff.prems(2) have "occurs_at (y, γ) p (λxαtI_2that by y auto
 by auto
 then obtain p' where "p = « # p'" and "occurs_at (y, γ) p' (rename_bound_var (y, γ) z A)"
 using subforms_from_abs by fastforce
 then have "¬ in_scope_of_abs (z, γ) p' (rename_bound_var (y, γ) z A)"
 using abs_is_wff.IH[OF ‹) ∉] by blast
 then have "¬ in_scope_of_abs (z, γ
 using ‹
 then show ?thesis
 using * and ‹
 qed
 

  is_free_for_in_rename_bound_var:
 assumes "A ∈ wffsα
 and "zγ ≠ yγ"
 and "(z, γ) ∉ vars A"
 shows "is_free_for (zγ) (y, γ) (rename_bound_var (y, γ) z A)"
  (rule ccontr)
 assume "¬ is_free_for (zγ) (y, γ) (rename_bound_var (y, γ) z A)"
 then obtain p
 where "is_free_at (y, γ) p (rename_bound_var (y, γ) z A)"
 and "in_scope_of_abs (z, γ) p (rename_bound_var (y, γ) z A)"
 by force
 then show False
 using rename_bound_var_not_bound_occurrences[OF assms] by fastforce
 

  renaming_substitution_preserves_bound_vars:
 shows "bound_vars (S {(y, γ) 🍋 zγ} A) = bound_vars A"
  (induction A)
 case (FAbs v A)
 then show ?case
 using singleton_substitution_simps(4) and surj_pair[of v]
 by (cases "v = (y, γ)") (presburger, force)
  force+

  rename_bound_var_bound_vars:
 assumes "A ∈ wffsα"
 and "zγ ≠ yγ"
 shows "(y, γ) ∉ bound_vars (rename_bound_var (y, γ) z A)"
 using assms and renaming_substitution_preserves_bound_vars by (induction A) auto

  old_var_not_free_not_occurring_after_rename:
 assumes "A ∈ wffsα"
 and "zγ ≠ yγ"
 and "(y, γ) ∉ free_vars A"
 and "(z, γ) ∉ vars A"
 shows "(y, γ) ∉ vars (rename_bound_var (y, γ) z A)"
 using assms and rename_bound_var_bound_vars[OF assms(1,2)]
 and old_bound_var_not_free_after_renaming and vars_is_free_and_bound_vars by blast</sub>