Impressum IVSubst.thy

(*<*)
theory IVSubst
  imports  Syntax
begin
  (*>*)

chapter ‹Immutable Variable Substitution›

text ‹Substitution involving immutable variables. We define a class and instances for all
  the term forms›

section ‹Class›

class has_subst_v = fs +
  fixes subst_v :: "'a::fs ==> x ==>(*<*)
  assumes fresh_subst_v_if: "y ♯ (subst_v a x v)  ⟷ (atom x ♯ a ∧ y ♯ a) ∨ (y ♯ v ∧ (y ♯ a ∨ y = atom x))"
    and forget_subst_v[simp]: "atom x ♯ a ==> subst_v a  x v = a"
    and subst_v_id[simp]: "subst_v a x (V_var x) = a"
    and eqvt[simp,eqvt]: "(p::perm) ∙ (subst_v a x v) = (subst_v  (p ∙ a) (p ∙x) (p ∙v))"
    and flip_subst_v[simp]: "atom x ♯ c ==> ((x ↔ z) ∙ c) = c[z::=[x]^v]_v"
    and subst_v_simple_commute[simp]: "atom x ♯ c ==>(c[z::=[x]^v]_v)[x::=b]_v = c[z::=b]_v"
begin

lemma subst_v_flip_eq_one:
  fixes z1::x and z2::x and x1::x and x2::x
  assumes "[[atom z1]]lst. c1 = [[atom z2]]lst. c2"
    and "atom x1 ♯ (z1,z2,c1,c2)"
  shows "(c1[z1:=[x1<^upv]^sub) = (c2[z2::=[x1]^v]_v)"
proof -
  have "(c1[z1::=[x1<^sup>v] z1) ∙v auto
  moreover have  "(c2[z2::=[x1]^<oen>Imutable Variable Substitution›
  ultimately show ?thesis using Abs1_eq_iff_all(3)[of z1 c1 z2 c2 z1] assms
    by (metis Abs1_eq_iff_fresh(3) flip_commute)
qed

lemma subst_v_flip_eq_two:
  fixes z1::x and z2::x and x1::x and x2::x
  assumes "atom m].c2
  shows "(c1[z1::=b]_the erm frms\>
proof -
  obtain x::x where *:"atom x ♯ (z1,z2,c1,c2)" using obtain_fresh by metis
  hence "(c1[z1::=[x]^v]_v) = (c2[z2::=[x]^v]_v)" using subst_v_flip_eq_one[OF assms, of x] by metis
  hence "(c1[z1::=[x]^v]_v)[x::=b]_v = (c2[z2::=[x]^v]_v)[x::=b]_v" by auto
  thus ?thesis using subst_v_simple_commute * fresh_prod4 by metis
qed

lemma subst_v_flip_eq_three:
  assumes "[[atom z1]]lst. c1 = [[atom z1']]lst. c1'" and "atom x ♯ c1" and "atom
  shows   java.lang.NullPointerException
proof -
  have "atom x' ♯v]<subs fresh_subst_v_if
  hence "(x ↔ x') ∙ (subst_v a x v) ⟷ (atom x ♯> a) ∨ (y 🚫v))"
  also have. =c1::=[x']\^supv]_usingsingmple_commute_4assmsms
  also have "... = c1'[z1'::=[x'] c ==>[::==[]\<^>]v)[x::=b]_v" 
  nallyisto and2:
qed

end

section <openopen›v]_\upv)"

nominal_functionhave "(c1[z1::=[x1]^v) = (x1 ↔ c1" using assms flip_subst_v by auto
  subst_vv :: "v ==> v ==>
  t_vvV_litlit
| "subst_vv (V_|by mtsAs1eq_iff_fr_frsh(3 f
| "subst_vv ( tyidV_consbst_vv
| "subst_vv (V_consp ty -
| "subst_vv (V_pair v1 v2) x v = V_pair (subst_vv v1 x v ) (subst_vv v2 x v )"
  by(autosm: eqqtdfsst_vgah_aux_def etis v.stronehut
nominal_termination (eqvt) by lexicographic_order

abbreviation
  subst_vv_abbrev :: "v ==> v ==>_[_::=_]_vv›
  here
    "v[x::=v']_vv ≡ subst_vv v x v'" 

lemma fresh_subst_vv_if [simp]:
  "j ♯ t[i::=x]_vv = ((atom i ♯ t ∧ j ♯ t) ∨ (j ♯ x ∧ (j ♯ t ∨ j = atom i)))"
  using supp_l_empty apply (induct t rule: v.induct,auto simp add: subst_vv.simps fresh_def, auto)
  by (simp add: supp_at_base |metis b.supp supp_b_empty  )+

lemma forget_subst_vv [simp]: "atom a ♯ tm ==> tm[a::=x]_vv = tm"
  by (induct tm rule: v.induct) (simp_all add: fresh_at_base)

lemma subst_vv_id [simp]: "tm[a::=V_var a]_vv = tm"
  by (induct tm rule: v.induct) simp_all

lemma subst_vv_commute [simp]:
  "atom j ♯ tm ==> tm[i::=t]_vv[j::=u]_vv = tm[i::=t[j::=u]_vv]_vv "
  by (induct tm rule(utoPair

lemma subst_vv_commute_full [simp]:
  "shows ( <> x') \<llettv" 
  by (induct tm rulejava.lang.StringIndexOutOfBoundsException: Index 7 out of bounds for length 7

lemmasubst_vv_var_flip
  fixes v::v
  assumes "atom y ♯ v"
  shows "(y ↔x) \bulletv = v [x::=V_var y]_vv] usn ubst_v_flipeq__oe[of 1c1 1' 1 x'] usi assm b uto
  using asassmspl(dc ueviducct)
      apply auto
  using l.fresh l.perm_simps l.strong_exhaust supp_l_empty permute_pure permute_list.simps fresh_def flip_fresh_fresh apply fastforce
  using permute_pure apply blast+
  done

instantiation v :: has_subst_v
begin

definition
  "subst_v

instance proof
  fix
  show"(j ♯ subst_v t i x) = ((atom i ♯ t ∧ j ♯ t) ∨ (j ♯ x ∧ (j ♯ t ∨ j = atom i)))"
    using fresh_subst_vv_if[of j t i x] subst_v_v_def by metis

  fix a::x and tm::v and x::v
  show='^sub_v   subst_vv v x v'"
    using forget_subst_vv s fresh_subst_v_if sim

  fix a::x and tm::v
  show "subst_v tmemptyct. sh_def

  fix p::perm
  how <bullet subst_v t1 x1 v  = subst_v  (p ∙ x1) (p ∙
    using   subst_v_v_def by simp

  fix x::x and subst_vv_commute
  show java.lang.NullPointerException
    using subst_v_v_def b (inductt tmrul:.nut)(auo simp: frsh_Pir)

  fix x::x and c:vand z:
  show "atom java.lang.NullPointerException
    using subst_v_v_def by simp
qed

end

section ‹

nominal_functionev :: "\Rightarrowx \<Rightarrow> v  \<Rightarrow> e" where
  l 'E_valsubst_vv x v))"
| "subst_ev  ( (AE_app  showow tom\<sharp>m\<Longrightarrowsubst_v tm a x  = tm"
| "subst_evappPP  ) =(AE_appPppP (vvv)   
| "subst_ev  ( (AE_op opp v1 v2) ) x v  = ( (AE_op opp (subst_vv v1 x v ) (subst_vv2   java.lang.StringIndexOutOfBoundsException: Index 96 out of bounds for length 96
| "subst_ev  [#1 v']\<^sup>  #_v )supe
| "subst_ev  [#2 v'<sup>x[2 subst_vv v\^>"
| "bst_evE_mvar u x=E_mvar"
| "subst_ev  [| v' byuto
| "subst_ev  ( AE_concat v1 v2) x v = AE_concat (subst_vv v1 x v ) (subst_vv v2 x v )"
| "subst_ev  ( AE_split v1 v2) x v = AE_split (subst_vv v1 x v ) (subst_vv v2 x v )"
  by(simp add: eqvt_def subst_ev_graph_aux_def,auto)(meson e.strong_exhaust)

nominal_termination (eqvt) by

abbreviation 
  subst_ev_abbrev :: "e \<Rightarrow> xRightarrow> v \<_[_::=_]\<^sub>e\<^sub>v\<close> [1000,50,50] 500)
  where 
    "e[x::=v']\<^sub>e\<^sub>v  \<equiv> subst_ev e x v' " 

lemma size_subst_ev [simp]: "size ( subst_ev A i x) = size A"
  apply (nominal_induct A avoiding: i x rule: e.strong_induct) 
  by auto

lemma forget_subst_ev [simp]: "atom a 
  apply (nominal_induct A avoiding: a x rule: e.strong_induct) 
  by (auto simp: fresh_at_base)

lemma subst_ev_id [simp]: "subst_ev A a (V_var a)  = A"
  by(ductvoidingding  rule e.strong_inductrong_inductg_inductnductt(autosimpresh_at_base

lemma fresh_subst_ev_if [simp]:
  "j \<sharp> (subst_ev A i x ) = ((atom i \<sharp> A<and>  sharp A) \<or> (j \<sharp> x \<and> (j \<sharp> A \<or> j = atom i)))"
ductAe.uct
  unfolding subst_ev.simps fresh_subst_vv_ifyftom \< v1 \<and> atom y \<sharp> v2" using ce.fresh byblastast
  using pure_fresh fresh_opp_all    usingopperm_simpsceperm_simps_purereshppstrong_exhaustesburger
  done

lemma subst_ev_commute [simp]:
  "atom j \<sharp> A \<Longrightarrow> by etisll_typesypess
  by (nominal_induct avoiding: i j t  rulele .ong_inductutosimpmp:esh_at_base_e)

lemma subst_ev_var_flip[simp]:
  fixes e:: nd : andxx
  assumes "atom y \<sharp> e"
  ows y<leftrightarrow> \>e ::varry]\sube\<^sub>v"
  using assms apply(nominal_induct e rule:e.strong_induct)
           apply (simp add: subst_v_v_def)  
          metis(o_tagsagsifting) eq_iff.erm_simps_imps freshsh.perm_simpsip_b_id _simps_var_flip
         apply (metis (mono_tags, lifting) b.eq_iff b.perm_simps e.fresh e.perm_simps flip_b_id subst_ev.simps subst_vv_var_flip
  subgoal
    apply ubst_v_ce_def_def
  subst_vv_var_flip flip_def by (simp add: flip_def permute_pure)+
  using  subst_vv_var_flip flip_def by (simp add: flip_def permute_pure)+

lemma subst_ev_flip:
  fixes e::e and ea::e and c::x
  assumes "atom c \  ee
  shows ":v<sub\^>v = ea[xa::v\^e\<^sub>v"
proof -
  have "e[x::=v']\<^sub>e\<^sub>v = (e[x::=V_var c]\<^sub>e\<^sub>v)[c::=v']\<^sub>e\<^sub>v" using subst_ev_commute assms by simp
  also have "...  = ((c \<leftrightarrow> x) \<bullet> e)[c::=v']\<^sub>e\<^sub>v" using subst_ev_var_flip assms by simp
  also  subst_cv_commutemp:
  also ave".. eaxa:=v\^sub>\<^sub>v"  using subst_ev_var_flip assms  by simp
  finally show ?thesis by autousingassmsduct uleestrong_inductmp:flip_subst_vubst_v_ce_defce_deffjava.lang.StringIndexOutOfBoundsException: Index 96 out of bounds for length 96
qed

subst_ev_vart_ev_varv_var[mp]java.lang.StringIndexOutOfBoundsException: Index 25 out of bounds for length 25
  "(fix p:ermanddx1:xndd1c
  by auto

instantiation e :: has_subst_v
begin

definition 
  "subst_v = subst_ev  fix x::x and:canddzx

instance proof
  fix j::atom and i::x and  x:
  show  "(j \<sharp> subst_v t i x) = ((atom i \arptand>j \<sharp> t) \<or> (j \<sharp> x \<and> (j \<sharp> t \<or> j = atom i)))"
    using fresh_subst_ev_ifofj i]ubst_v_e_defy etis

  fix a::x and tm::aseC_eq_eqe2)
  show "atom a \<sharp> tm \<Longrightarrow> subst_v tm a x  tm
    using forget_subst_ev subst_v_e_def by simp

  fix a::x and tm::e
 showubst_va_ar =tmusingsubst_ev_id subst_v_e_defysimp

  fix p::perm and x1::x and v::v and t1::e
  show "p \<bullet> subst_v t1 x1 v  = subst_v  (p \<bullet>(goal_cases
    using subst_ev_commute  subst_v_e_def by simp

  fix x::x and  size_subst_gv subst_gv<lesize G"
  show "atom x \<sharp> c java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
    using  subst_v_e_def by simp

  fix x::x and c::e and z::x
  x=<subv = c[z::=v]\<^sub>v"
    using  subst_v_e_def byimpp
qed
end

lemma subst_ev_commute_full:
  fixes: and:  :and<Gamma>:\<Gamma>
  assumes z<sharp> vand atomom  sharp w" and "x \<noteq> z"
  shows "subst_ev  (e[z::=w]\<^sub>e\<^sub>v) x v = subst_ev  (e[x::=v\sub>\<^sub>v) z w" 
  using assms by(nominal_induct rulestrong_inductimpjava.lang.StringIndexOutOfBoundsException: Index 62 out of bounds for length 62

lemma subst_ev_v_flip1    substlip_fresh_fresh imp
  fixes e::e
  assumes "atom z1 \<sharp> (z,e)" and "atom z1' \<sharp> (,java.lang.StringIndexOutOfBoundsException: Index 64 out of bounds for length 64
  shows"(z1 \<leftrightarrow
  using assms proof(nominal_induct eeong_inductt
qed  (simp add: flip_def fresh_Pair swap_fresh_fresh)+

section \<open>Expressions in Constraintssubgoalaajava.lang.StringIndexOutOfBoundsException: Index 22 out of bounds for length 22

nominal_function subst_cev :: "ce \<Rightarrow> x \<Rightarrow> v  \<Rightarrow> ce" where
  "subst_cev ( (CE_val v') ) x v = ( (CE_val (subst_vvv  )
|cevE_oppp v1 x(CE_opsubst_cevv1 v(bst_cev xv)"
| "subst_cev ( (CE_fst v') v CE_fstsubst_cev'vjava.lang.StringIndexOutOfBoundsException: Index 62 out of bounds for length 62
| "subst_cev ( (CE_snd v')) x v = CE_snd (subst_cev  v' x v )"
| "subst_cev ( (CE_len vproofminal_inductnductductAavoidingxule<tau>strong_induct)
|
                      apply.strong_induct) (automp esh_at_base
  by (meson ce.rong_exhaust

nominal_termination (eqvt) "\<>  \<Longrightarrow> (\<tau>[x::= \\<tau>\<^sub>v)[y::=v]\<^sub>\<au>\^> = \<tau>[x::= t[y::=v]\<^sub>v\<^sub>v]\<^><\<^sub>v "

breviation
  subst_cev_abbrev :: "ce \<Rightarrow> x<>\>ce" (\<open>_[_::=_^>\<^sub>e\<^sub>v\<close> [1000,5050500

    "e[x::=java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0

lemma size_subst_cev [simp]:usingubst_v_c_defet_subst_vsubst_vst_tvmpssubst_v_tau_def fresh_Pair by simp
  by (nominal_induct Axand :and 1\<>

lemma forget_subst_cev [simp]: "atom a \<sharp> A \<Longrightarrow> subst_cev A a x  = A"
  by (nominal_induct A avoiding: a x rule: ce.strong_induct, auto simp: fresh_at_base)

lemma subst_cev_id [simp]: "subst_cev A a (V_var a)  = A"
  by (nominal_induct A avoiding: a rule: ce.strong_induct utopfresh_at_base)

lemma fresh_subst_cev_ifshowtom< c \<Longrightarrow> ((x \<leftrightarrow> z) \<bullet> c) = c[z::=[x]\<supsubv" 
  "j \<sharp> (subst_cev A i x ) = ((atom i \<sharp> A \<and> j \<sharp> A) \<or>(j\<sharp x \<and> (j \<sharp> A \<or> j = atom i)))"
strong_induct
  case (CE_op opp v1 v2)
  then w   fresh_subst_vv_if ubst_evimps supp re_freshesh.sh
      fresh_e_opp 
    using fresh_opp_all by auto
qed  )

lemma
  "casec1)
  

lemma subst_cev_var_flip[simp]shows lbrace> x : b | c \<rbrace"
  fixes ceyandx
  sharp e"
  shows "(
  using assms proof(nominal_induct e rule:ce.strong_induct)
  case (CE_val v)
  then show ?case using subst_vv_var_flip by auto
ext
  case (CE_op   tbjava.lang.StringIndexOutOfBoundsException: Index 19 out of bounds for length 19
  hence\> 1and atom y \<sharp> v2" using ce.freshblast
  have " (y obtainnd z z' : b_of t rbrace\<and> atom z' \<sharp> (x,z)" using obtain_fresh_z_c_of by metis
usingm_simps ermute_pureure .shprong_exhaustustbysburger
  
    by (simp add: CE_op.hypsfixes
  finally show ?case using subst_cev.  pppst

qedutodd te_purebst_vv_var_flipip

lemma subst_cev_flip:
  fixes e::ce and ea::ce:
   sharp> (e, ea)" and "atom c \<sharp>xa,nd(<>c\bullete = (xa \<leftrightarrow> c) \<bullet> ea" 
  shows "e[x::=v]<c\<^sub>e\<^sub>v = ea[xa::=v']<c^e\<^sub>v"

    1\leftrightarrow z2) \>c2" by auto
  ove( <eftrightarrow x) \<bullet> e)[c::=v']\<^sub>c\<^sub>e\<^sub>v" using subst_ev_var_flip assms by simp
  also have ".. java.lang.StringIndexOutOfBoundsException: Index 24 out of bounds for length 24
  also have "shows [:1^c\<^sub>v" and "b1=b2"
  finally show ?thesis by auto
qed

lemma subst_cev_varlemma 
xes
  showsbyeq_subst_eq
  by lemma 

 v
begin

definition 
  "subst_v = subst_cev"

instance proof
  fix j::atom and:
  show  "(j \<harpbst_v =om<>\>j \<sharp> t) \<or> (j  x \<and> (j \<sharp> t \<>jom)
    using fresh_subst_cev_if[of j t i x] subst_v_ce_defetisctbst_tvcases)

  
  show "atom a \<sharp> tm \<Longrightarrow> st_vxm
    using forget_subst_cev subst_v_ce_def by 


  show "subst_v tm a (V_var st_tv_tid

  fix p::perm and x1::x and v::v and t1::ce
   subst_v t1 x1 v  = ubst_v(\bullett1) (p \<bullet> x1) (p \<bullet> v)" 
     '[x::=vsub><tau>\<^sub>=" and sharp (v,\<tau>)" and \> (v,\<tau>)"

  fix x::x and bst_cv_true
  show "atom x \<sharp Longrightarrow ((x \<leftrightarrow> z)\ c) = c [z::=V_var x]\<^sub>
    using  subst_v_ce_def by simp

  fix x::x thesisgo
  show  " <> <>c [z:=var\^>v[x::=v]\<^sub>v = c[z::=v]\<^sub>v"
    _fsimp
ed

end

lemma  < cc"
  cev:
  assumessharp v" and "atom x \<sharpw   z"
ubst_cevsubc\<^sub>e\<^sub>v) x v  = subst_cev (e[x=<e\<^sub>v) z w " 
sing  eng_inductt,mp)


lemmalip1
  fixes e:java.lang.StringIndexOutOfBoundsException: Index 13 out of bounds for length 13
  tom\>(z,e)" and "atom z1' \<sharp> (z,e)"
shows z1') \<lletz]>\<^sub>e\^sub>   [ \>z1' <ullet\<^sub>e\<^sub>v
uctng_inductct)
  by (simp addapplyd _onsfresh_DConsjava.lang.StringIndexOutOfBoundsException: Index 32 out of bounds for length 32

sectionp_subst_v](taux=^\<<sub\>setD (\<Delta>[x::=<>Delta\<ub


  "  e
|subst_cv (C_false) x v = C_false"
|ultimately show ?thesis using Abs1_eq_iff_all  
|bst_cvvdisj2 disjt_cvvc2 v)
 C_impp bst_cvcv1)2 "
|  "subst_cv (e1 =e2 t_cev)bst_cev x java.lang.StringIndexOutOfBoundsException: Index 75 out of bounds for length 75
|  "subst_cv (C_not c) x v = C_not (ubst_cv 
                     apply (simp addqvt_def_eft_cv_graph_aux_def
  
nominal_terminationbyraphic_orderingms ofuct \_duct

   
ubst_cv_abbrev x \<Rightarrow> vjava.lang.StringIndexOutOfBoundsException: Index 3 out of bounds for length 3
  where 
    c=]sub\^>v  \<equiv> subst_cv c x v'" 

lemma_mpze_nominal_functioncase_sumum< Inl undefined case_sume_sum\lambdax  undefined) x. Inrfined


instance
yl_inducttidinggeng_inductuct ofresh_at_base

emma(fs2vAS_ifsubst_vvt_vvxsubst_sv t_sv java.lang.StringIndexOutOfBoundsException: Index 107 out of bounds for length 107
  bysvsertsssert_x subst_sv )java.lang.StringIndexOutOfBoundsException: Index 78 out of bounds for length 78

_
     _r mvar
  minal_inductidingg rule trong_inductg_inductucto  _h


  "apply1 (ubst_sv_subst_branchv_subst_branchlv_graph"
 ulecto:sh_at_base

lemmast_ev_id 
  apply
            
  done

lemmaresh_simpsp_b_id bst_evsimpssubst_vv_var_flip   caseldsaa java.lang.StringIndexOutOfBoundsException: Index 30 out of bounds for length 30
c
then ssinggInl1branch_s_branch_listnch_listlisttrong_exhauststesh_star_insertsertetisjava.lang.StringIndexOutOfBoundsException: Index 109 out of bounds for length 109
s\eftrightarrowrightarrowrow< c = c[x::=V_var y]\<^sub>c\<^sub>
  using assms by(nominal_induct c rule    sing

instantiation
begin

java.lang.StringIndexOutOfBoundsException: Index 71 out of bounds for length 11
" bst_cv

instancefixjava.lang.StringIndexOutOfBoundsException: Index 2 out of bounds for length 0
 andand:tjava.lang.StringIndexOutOfBoundsException: Index 41 out of bounds for length 41
  show  "(jusingmsy    <b\>ubst_sv_ java.lang.StringIndexOutOfBoundsException: Index 56 out of bounds for length 56
    using fresh_subst_cv_if[of j t i x] subst_v_c_def by metis

ix  d
  |st_cev(nn'x=E_len bst_cevevv"
    gget_subst_cvvddingarule:_h_s_branch_listranch_listch_listlisttg_inductinduct)

  java.lang.StringIndexOutOfBoundsException: Index 14 out of bounds for length 4
 bst_v_a= _dsubst_v_c_def__efby p

  (
  show "p \bullet  t1 1=st_v(<>1<1(p>v)"
    using subst_cv_commute  subst_v_c_def by simp

  fix x:nd: z
ightarrowrow\bulletcc:[v]\<^sub>v"
     qed(tompadddpermute_purete_purepurebst_vv_var_flip)

  ":]< '_ susingsubst_svst_svp
    "atom x \<sharp> c \<Longrightarrow> then  sissusingTrueeylast
    using subst_cv_var_flip subst_v_c_def bysimp


endshow

lemmabst_cev_commutecommutete  __  mpjava.lang.StringIndexOutOfBoundsException: Index 51 out of bounds for length 51
  fixes c::c
   java.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 6
ftrightarrow c c\<^sub>v"
   resh_subst_tv_ifbst_tv_ifv_ififlisttscI.sesjava.lang.StringIndexOutOfBoundsException: Index 101 out of bounds for length 101
  sms

lemma subst_cv_v_flip3[simp]:
fixesc
  assumes "atom z1 \assmsauto+
  shows"  :vjava.lang.StringIndexOutOfBoundsException: Index 21 out of bounds for length 21
proof - isj_ xubst_cv x )
  '=ingh_subst_sv_if_lr_v_if_lr resh_subst_sv_if_rlbst_sv_if_rlbytis
  then show ?thesis proof(cases)
    case 1
    then show ?thesis using 1 assms by auto
  next
    case 2
    rget_subst_cvimp"a\>A \<Longrightarrow> subst_cv A a x  = A"
    <byautoopresh_at_baset_basese
     
    then show  ngby
  
qed

shows x) \<bullet>showsx]<sub>sub>  sa[xa::=v']\<^sub>s\<^sub>v"
  fixes c::c
  assumes var "singdt_v_c_deflsoave. xaleftrightarrowc) \<bullet c) \<bullet>:(>c) < v^s\<^sub>v" using assmsresburger
  <>\bullet> c)[x::<c^>v  :v]\^>c\<^subjava.lang.StringIndexOutOfBoundsException: Index 98 out of bounds for length 98
  efto

lemmammute_full
  case
  assumes "atom z \    thenngbyto
  "[:]<sub>c^ubv)[x::=v]\<^sub>c\<^sub>v = (c[x::=v]\<^sub>c\<^sub>v)[z::=w]\<^>subv" 
  
   
  then where
qedlemma v  le    

lemma
 > 
  shows "(CE_val  

  have "?A = (((CE_val (
  < xa) \<bullet>  (c< "atoma\sharptm \<Longrightarrow> subst_v tm a x   "
qedave:\sub\<^usingsubst_sv_commute by simp

nominal_function 

textThe idea usingsubst_sv_var_flip by 
that   xandza:dad:  x

nominal_function subst_gv"<p)\c\<^sub>v t[x::=v]\<^sub\tau<^sub>v s[x=\sub>subv"

 :est_tv ize
ases
  (pjava.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4
thenbympddefubst_gv_graph_aux_defraph_aux_defux_def_f
next

   asemetisneq_GNil_convl_convrod_cases3es3
qedfast+)
nominal_termination (eqvt) by lexicographic_order

 
ubst_gv_abbrev .mpsyimpddflip_fresh_freshresh_freshfreshjava.lang.StringIndexOutOfBoundsException: Index 73 out of bounds for length 73
where
    "    sh_PairDirD( java.lang.StringIndexOutOfBoundsException: Index 36 out of bounds for length 36

lemmasize_subst_gv [simp: " v le size G"
  by fun_typ_reshpplyyimp

lemma forget_subst_gv [simp]: "  subst_vvm _ahtarrowrrow>subst_v  m
    tautoutojava.lang.StringIndexOutOfBoundsException: Index 25 out of bounds for length 25
     st_vm_)"
   apply (simpddfresh_GCons
  done

lemma
proof    x<>cLongrightarrow c[z:  showp \letsubst_vt11  =v < 1p\>x1) (p <> v) 
eubst_tv_commute_full
  then show ?fixx:xandc:_ d:
next
  case (GCons xbcapplycaserefined_typeed_typeype 12 3java.lang.StringIndexOutOfBoundsException: Index 35 out of bounds for length 35
obtain  b'and here:cx''ingrod_cases3ses33yst
  show ?case proof(cases "x    by (auto simp :bst_v_c_defc_defbst_v_s_defst_v_<tau_ subst_v_fun_typ_def )
    case case
vetomsharp"usingGCons fresh_GCons by 
     esissingsubst_gvimps2[  nominal_inductinductctavoidingdingxle__rong_inductnduct,)
       o_typess)_t_v_ift_v_fun_typ_deffun_typ_defyp_def_efjava.lang.StringIndexOutOfBoundsException: Index 63 out of bounds for length 63
    aseFalse
    showthesis subst_gvsimps2[  G Falseh_GConsbymp
  qed
qed

a
   :x xa:  :xandc:  <amma:\Gamma>
  "om<>(x, b, c[z::=[x]\<^upv]\<^sub^subv) #\<^sub>\<Gamma> \<ammaaand" <harp<> om sharp<>"and >(z, c)" and "atom xa \<sharp 
  "<>"
proof -
  have  "(x \<leftrightarrow> xa) \<bullet>  ((x, b, c[z
   tns_eqvtvtp_fresh_freshsh_freshhsingcons_fliplip  p
  x\>toSet \<Gamma>" and "atom x\ atom_dom \<Gamma
  z11 = (\<lbrace> :| rbrace and "atom  c2" 
  also have "... = (a,c:^ub>\<^subcase
  finallyshow1:]<subb\^sub
qed

on\><>

 < <> where
bst_tv\<lbrace> z : b |  racex <>z:b [subc\<^sub>v \<rbrace>"
f )

  subgoal for P   ow1:\^><sub [2=]<^b<> ype_eq_subst_eq__ssmsby t
    apply(rule_tac y=a and c="(aa,b)" in \<tau>.java.lang.StringIndexOutOfBoundsException: Index 63 out of bounds for length 63
    by (auto simp: eqvt_at_deffresh_star_defeffresh_Pairesh_at_baset_basejava.lang.StringIndexOutOfBoundsException: Index 72 out of bounds for length 72
  apply (auto simp: eqvt_at_def fresh_star_def fresh_Pairshows java.lang.StringIndexOutOfBoundsException: Index 24 out of bounds for length 24
proof -
  java.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4

  assume a4: "atom cb \<sharp> c" and a5" \<sharp ca" and  <> z" and a7: "cb \<noteq> zandm\sharp a"noteqxa" and a9:  noteq xa"
    java.lang.StringIndexOutOfBoundsException: Index 68 out of bounds for length 68
  note assms = a10  7 a3

  have "c[z::=b<sub<ub [:r]\<\>" using assms  by auto
  hence "c[z::=V_var cb]\<^sub>c\<^sub>v[xa::=va]\<^sub>c
  moreover[=^c\<^sub>v[xa:c\<^sub>v = c[xa::=va]\<^<^ub[z::=V_var cb]\<^sub>c\<^sub>v" singsubst_cv_commute_fullacbresh_def v stforce
avec\<^sub>vxa:va<sub\<^sub>v = ca[xa::=va]\<^sub>c\<^sub>v[za::=V_var cb]\<^sub><"
   bsh_def stforce

  ultimately show "c[xa:java.lang.StringIndexOutOfBoundsException: Index 3 out of bounds for length 3
qed

nominal_termination (eqvt) bycographic_orderhic_orderr

abbreviation
  subst_tv_abbrev :: "\<taushows-tom}supp
  
    "t[x::=v]><tau>\<^sub>v  \<equiv> subst_tv t x v" 

   supp b = supp cc - {atom supp b" using \<tau> 
proofoidingrule>strong_induct)
  case (T_refined_type x' b' c')
  thenase 
qed

m a \<sharp> <>subst_tvv A
  apply (nominal_induct A avoiding: a "Nil  DNil
  apply(        (simp :qvt_def_fmap_graph_aux_defo
  done

lemma subst_tv_id [simp"subst_tv AV_vara"
 ctiding<>strong_induct) (auto simpfresh_at_basee

lemma fresh_subst_tv_if [simp
  "j\sharp (subst_tv A i x ) \<longleftrightarrow> (atom i <rp \ j \<sharp> A) or (j \<sharp> x \<andj< A \<or> j = atom i))"
  apply (nominal_induct ingle.strong_induct)
  using fresh_def supp_b_empty x_fresh_b by auto

lemma)
   \<tau> \<Longrightarrow> (tau[^\<tau>\<^sub>v)[y::=v]\<^sub>\<tau>\> = \<tau>[x::= t[y::=v]<ub\v]\<^sub>\<tau>\<^sub> 
     eqvt_at_proj< s xa va . eqvt_at subst_sv_subst_branchv_subst_branchlv_sumC (Inl (,,)< 

lemma

  
  shows         
proof - 
  obtain z::xthenwhesisusingrnr2r_insert
    
  hencem<>upp atom}ng<ppb esh_def_mptysms
    by  auto
  moreover have "xa \<noteq
  ultimately have:asharpc" using fresh_def by auto
  have "(x \<leftrightarrow> xa) \<bullet> \<tau  <brace z : b | (x \<leftrightarrow> xa) \<bullet> c \<rbrace>" 
    by (metis \ shows <sharp>  <>ubst_sv""ma<\>t_branchvchv  =and"m C \<Longrightarrow> subst_branchlv C a x  = C"
  also have "... =  \<lbrace> z : b | c[x::=V_var xa]\<^sub>c\<^sub>v \<rbrace>"  using subst_cv_v_flip xaf  
    by (metis permute_flip_cancel permute_flip_cancel2 subst_cv_var_flip)
nallysingsubst_tvt_tvimpsbc 
    using fresh_PairD(1) not_self_fresh by force
qed

instantiation \<tau> :: has_subst_v
begin

definition 
  "subst_v qed

instance proof
  fix j::atom and next
how subst_v t i x) = ((atom i \<harp\ j \<sharp>   (j \<sharp> x \<and>( < t \<or> j = atom i)))

  proof(nominal_induct t avoiding: i x rule:\<tau>.strong_induct)
   efined_typec
    hence " j \<sharp> \<lbrace> z : b  | c \<    "j\> B \<Longrightarrow> (subst_branchv  (subst_branchv B i t ) j u )  _chvB i (bst_vv andnd
    also have "...shows s=\subs\<^sub>v = sa[xa::=v']\<^sub>s\<^sub>v"
       tau.fresh using subst_v_c_defsh_subst_v_ifsubst_v_ift_v_ifif 
      using T_refined_type.hyps(1) T_refined_type.hyps(2) x_fresh_b by auto
    finally show ?case by auto
  qed

  fix a::x and tm::\<tau> and  :'<supv<>\<^sub>v  \<rbrace>) = \<lbrace> z1 : ba  | CE_val v  ==  CE_val (V_lit ll) IMP  ca[za::=[z1]\<^sup>v]\<^sub>c>  \<rbrace>"

    apply(nominal_induct tm avoiding: a xule<>strong_induct)
    using subst_v_c_deforget_subst_vt_tvsubst_v__\_def fresh_Pair by simp

   a::x and tm::\<tau
  show "subst_v tm a (V_var)=m       
    apply(nominal_induct tm avoiding: subst, perm *)
    using subst_v_c_def forget_subst_v subst_tv.simps subst_v_\<tau>_def fresh_Pair by subst_v_<>_def subst_v_v_def subst_vv_var_flipsubst_v_e_def pure_freshapply auto 

  fix   ( : flip_fresh_fresh
  show "p \<bullet> subst_v t1 x1 v  = subst_v  (p \<bullet> t1instantiation s :: has_subst_v
    apply(nominal_induct tm voiding  ule>strong_induct)
    using  tm \<Longrightarrow> subst_v tm a x  = 

  fix x::   p::perm and x1:xand:vandt1:
  show "atom x \<sharp     subst_sv_commute  subst_v_s_def bysimp
    duct avoidingrule<au>.strong_induct)
    using subst_v_c_def :

   x: c\>and:
  show  "atom java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
   inal_inductductcing rule\tautrong_induct
    using subst_v_c_def  subst_tv.simps subst_v_\<tau>    lyimpun_typ.ng_exhaust
    by (metis flip_commute subst_tv_commute subst_tv_var_flip subst_v_\<tau>_def subst_vv.simps(2)
qed
    c= \]<sub>c\<^sub>v[xa::=va]\<^sub>v = ca[za::=[ cb ]\<^supc\<^sub>v[xa::=va]\<^sub<v" by auto
end

lemma subst_tv_commute_full:
  fixes c::\<tau>
   "atom z \<sharp> " and "atom x <sharp> w"and"x\<>z
  (z::w\^><>\<subv[:=]<sub\tau\^sub>v=([:=]<sub\<tau>\<^sub>v)[z::=w]\<^sub>\<>\^>v" 
  using  (nominal_induct 
  3
  
qed

lemma type_eq_subst_eq
  fixes v::
  assumes "\<lbrace  show  "j <> subst_v   ) (( i\sharp  <>j\sharp> t)\or j\sharp  < j\<sharp  <>j=atom i)
  shows "c1[z1::=v]\<^sub>c\<^sub>v = c2[z2::=v]\<^sub>c\<^sub>v"
  casedingubst_ft_v_impsubst_v_fun_typ_deftyp.reshsingget_subst_vt_subst_vbst_ft_vmps ubst_v_c_def__efforget_subst_svst_v__<tau>_defyastforcestforce

text AF_fun_typ x1a x2a x3a x5a)
 - types give different answers \<close

nominal_function c_of :: "\<tau> show atomx\sharp c \<Longrightarrow>(x <> z <>c  [:=]<>v]<subvjava.lang.StringIndexOutOfBoundsException: Index 111 out of bounds for length 111
  "atom z \    (simpddubst_v_c_deft_v_c_defst_v_s_defst_v_<>def 
proof(goal_cases)
  case 1
  then show ?case using eqvt_def c_of_graph_aux_def by force
next
  case (2 x y)
  then show ?case using eqvt_def c_of_graph_aux_def by force
next
  case3 Px
thenobtain::tau and x2x *x1)byforce
  obtain z' and b' and c' where "x1 = \<lbrace> z' : b' | c' \<rbrace> \<and> atom z' 
  then show ?case  using    byautosimpadd: subst_v_fun_typ_defsubst_v_s_def \tau>_  fresh_subst_v_if   
xt
  case (4 z1 x1 b1 c1 z2 x2 b2 c2)
  then show ?case using subst_v_flip_eq_two \<tau>.eq_iff   by (metis prod.inject type_eq_subst_eq)
qed

nominal_termination (eqvt) by lexicographic_order

lemma c_of_eq:
  shows  "c_of \<lbrace> x : b | c "<>c\Longrightarrowc[z::=[x]\<^sup>v]\<^sub>v[x::=v]\<^sub>v = c[z::=v]\<^sub>v"
proof(nominal_induct "\<lbrace> x 
  case (x',b'c')\in  \<Gamma>"and atom  \notin tom_dom<> 
  moreover hence "c_of \<lbrace> x' : b | c' \<rbrace> x = c'[x'::=V_var x]\<^sub>c\<^sub>v" using c_of.simps by auto
  moreover have "\<lbrace> x' : b  | c' \<rbrace>      caseTrue
moreover have "c'[x'::=V_var x]\<^sub>c\<^sub>v = c" using efined_typed_type1_ ip_subst_vsubst_v_c_def
    by (metis subst_cv_id)
  ultimately show ?case by      moreovereatom x \notin atom_dom\<Gamma' usingresh_GConsGConsnsConsdommpsoSetmps 
qed

lemma obtain_fresh_z_c_of:
  fixes t::"'b::fs"
  obtains z  where "atom z \<sharp> t \<and> \<tau> = \<lbrace> z : b_of \<tau> | c_of \<tau> z \<rbrace>"
proof
obtain <>tau = \<lbrace> z of | c " using obtain_fresh_z2 by metis
  moreover hence "c = c_of 
  ultimately show ?thesis 
     that  auto
qed

lemma c_of_fresh:
  fixes  " <> x'"

  shows "atom x \<sharp> c_of t z" 
proof -
  obtain z' and c' where z:"t = \<lbrace> z' : b_of t | c' \<rbrace> \<and> atom z' \<sharp> (x,z)" using obtain_fresh_z_c_of by metis
  hence *:"c_of t z = c'[z'::=V_var z]\<^sub>c\<^sub>v" using c_of.simps fresh_Pair by metis
  have "(atom x \<sharp> c' \<or> atom x \<in> set [atom z']) \<and> atom x \<sharp> b_of t" using \<tau>.fresh assms z fresh_Pair by metis
  hence "atom x \<sharp> c'" using fresh_Pair z fresh_at_base(2) by fastforce
  moreover have "atom x \<sharp> V_var z" using assms fresh_Pair v.fresh by metis
  ultimately show ?thesis using assms fresh_subst_v_if[of "atom x" c' z' "V_var z"] subst_v_c_def * by metis
qed

lemma c_of_switch:
  fixes z::x
  assumes "atom z \<sharp> t" 
  shows "(c_of t z)[z::=V_var x]\<^sub>c\<^sub>v = c_of t x"
proof -  
  obtain z' and c' where z:"t = \<lbrace> z' : b_of t | c' \<rbrace> \<and> atom z' \<sharp> (x,z)" using obtain_fresh_z_c_of by metis
  hence "(atom z \<sharp> c' \<or> atom z \<in> set [atom z']) \<and> atom z \<sharp> b_of t" using \<tau>.fresh[of "atom z" z' "b_of t" c'] assms by metis
  moreover have " atom z \<notin> set [atom z']" using z fresh_Pair by force
  ultimately have  **:"atom z \<sharp> c'" using fresh_Pair z fresh_at_base(2) by metis

  have "(c_of t z)[z::=V_var x]\<^sub>c\<^sub>v = c'[z'::=V_var z]\<^sub>c\<^sub>v[z::=V_var x]\<^sub>c\<^sub>v"  using c_of.simps fresh_Pair  z by metis
  also have "... = c'[z'::=V_var x]\<^sub>c\<^sub>v"  using subst_v_simple_commute subst_v_c_def assms c_of.simps z  ** by metis
  finally show ?thesis using c_of.simps[of z' x "b_of t" c']  fresh_Pair z by metis
qed

lemma type_eq_subst_eq1:
  fixes v::v and c1::c
  assumes "\<lbrace> z1 : b1  |  c1 \<rbrace> = (\<lbrace> z2 : b2  |  c2 \<rbrace>)" and "atom z1 \<sharp> c2" 
  shows "c1[z1::=v]\<^sub>c\<^sub>v = c2[z2::=v]\<^sub>c\<^sub>v" and "b1=b2" and " c1 = (z1 \<leftrightarrow> z2) \<bullet> c2"
proof -
  show "c1[z1::=v]\<^sub>c\<^sub>v = c2[z2::=v]\<^sub>c\<^sub>v" using type_eq_subst_eq assms by blast
  show "b1=b2" using \<tau>.eq_iff assms by blast
  have "z1 = z2 \<and> c1 = c2 \<or> z1 \<noteq> z2 \<and> c1 = (z1 \<leftrightarrow> z2) \<bullet> c2 \<and> atom z1 \<sharp> c2" 
    using \<tau>.eq_iff Abs1_eq_iff[of z1 c1 z2 c2] assms by blast 
  thus  "c1 = (z1 \<leftrightarrow> z2) \<bullet> c2" by auto
qed

lemma type_eq_subst_eq2:
  fixes v::v and c1::c
  assumes "\<lbrace> z1 : b1  |  c1 \<rbrace> = (\<lbrace> z2 : b2  |  c2 \<rbrace>)" 
  shows "c1[z1::=v]\<^sub>c\<^sub>v = c2[z2::=v]\<^sub>c\<^sub>v" and "b1=b2" and "[[atom z1]]lst. c1 = [[atom z2]]lst. c2"
proof -
  show "c1[z1::=v]\<^sub>c\<^sub>v = c2[z2::=v]\<^sub>c\<^sub>v" using type_eq_subst_eq assms by blast
  show "b1=b2" using \<tau>.eq_iff assms by blast
  show  "[[atom z1]]lst. c1 = [[atom z2]]lst. c2" 
    using \<tau>.eq_iff assms by auto
qed

lemma type_eq_subst_eq3:
  fixes v::v and c1::c
  assumes "\<lbrace> z1 : b1  |  c1 \<rbrace> = (\<lbrace> z2 : b2  |  c2 \<rbrace>)" and "atom z1 \<sharp> c2" 
  shows "c1 = c2[z2::=V_var z1]\<^sub>c\<^sub>v" and "b1=b2"
  using type_eq_subst_eq1 assms  subst_v_c_def 
  by (metis subst_cv_var_flip)+

lemma type_eq_flip:
  assumes "atom x \<sharp> c"
  shows "\<lbrace> z : b  | c \<rbrace> = \<lbrace> x : b | (x \<leftrightarrow> z ) \<bullet> c \<rbrace>"
  using \<tau>.eq_iff Abs1_eq_iff assms 
  by (metis (no_types, lifting) flip_fresh_fresh)

lemma c_of_true:
  "c_of \<lbrace> z' : B_bool  | TRUE \<rbrace> x = C_true"
proof(nominal_induct "\<lbrace> z' : B_bool  | TRUE \<rbrace>" avoiding: x rule:\<tau>.strong_induct)
  case (T_refined_type x1a x3a)
  hence "\<lbrace> z' : B_bool  | TRUE \<rbrace> = \<lbrace> x1a : B_bool  | x3a \<rbrace>" using \<tau>.eq_iff by metis
  then show ?case using subst_cv.simps c_of.simps T_refined_type 
      type_eq_subst_eq3 
    by (metis type_eq_subst_eq)
qed

lemma type_eq_subst:
  assumes "atom x \<sharp> c"
  shows "\<lbrace> z : b  | c \<rbrace> = \<lbrace> x : b | c[z::=[x]\<^sup>v]\<^sub>c\<^sub>v \<rbrace>"
  using \<tau>.eq_iff Abs1_eq_iff assms 
  using subst_cv_var_flip type_eq_flip by auto

lemma type_e_subst_fresh:
  fixes x::x and z::x
  assumes "atom z \<sharp> (x,v)" and "atom x \<sharp> e" 
  shows "\<lbrace> z : b  | CE_val (V_var z)  ==  e  \<rbrace>[x::=v]\<^sub>\<tau>\<^sub>v = \<lbrace> z : b  | CE_val (V_var z)  ==  e  \<rbrace>"
  using assms subst_tv.simps subst_cv.simps forget_subst_cev by simp

lemma type_v_subst_fresh:
  fixes x::x and z::x
  assumes "atom z \<sharp> (x,v)" and "atom x \<sharp> v'" 
  shows "\<lbrace> z : b  | CE_val (V_var z)  ==  CE_val v'  \<rbrace>[x::=v]\<^sub>\<tau>\<^sub>v = \<lbrace> z : b  | CE_val (V_var z)  ==  CE_val v'  \<rbrace>"
  using assms subst_tv.simps subst_cv.simps  by simp

lemma subst_tbase_eq:
  "b_of \<tau> = b_of \<tau>[x::=v]\<^sub>\<tau>\<^sub>v"
proof -
  obtain z and b and c where zbc: "\<tau> = \<lbrace> z:b|c\<rbrace> \<and> atom z \<sharp> (x,v)" using \<tau>.exhaust
    by (metis prod.inject subst_tv.cases)
  hence "b_of \<lbrace> z:b|c\<rbrace> = b_of \<lbrace> z:b|c\<rbrace>[x::=v]\<^sub>\<tau>\<^sub>v" using subst_tv.simps by simp
  thus ?thesis using zbc by blast
qed

lemma subst_tv_if:
  assumes "atom z1 \<sharp> (x,v)" and "atom z' \<sharp> (x,v)" 
  shows "\<lbrace> z1 : b  | CE_val (v'[x::=v]\<^sub>v\<^sub>v)  ==  CE_val (V_lit l)   IMP  (c'[x::=v]\<^sub>c\<^sub>v)[z'::=[z1]\<^sup>v]\<^sub>c\<^sub>v  \<rbrace> = 
         \<lbrace> z1 : b  | CE_val v'           ==  CE_val (V_lit l)   IMP  c'[z'::=[z1]\<^sup>v]\<^sub>c\<^sub>v  \<rbrace>[x::=v]\<^sub>\<tau>\<^sub>v" 
  using subst_cv_commute_full[of z' v x "V_var z1" c']  subst_tv.simps subst_vv.simps(1) subst_ev.simps  subst_cv.simps assms 
  by simp

lemma subst_tv_tid:
  assumes "atom za \<sharp> (x,v)"
  shows "\<lbrace> za : B_id tid  | TRUE \<rbrace> = \<lbrace> za : B_id tid   | TRUE \<rbrace>[x::=v]\<^sub>\<tau>\<^sub>v"
  using assms subst_tv.simps subst_cv.simps by presburger


lemma b_of_subst:
  "b_of (\<tau>[x::=v]\<^sub>\<tau>\<^sub>v) = b_of \<tau>"
proof -
  obtain z b c where *:"\<tau> = \<lbrace> z : b | c \<rbrace> \<and> atom z \<sharp> (x,v)" using obtain_fresh_z by metis
  thus ?thesis  using subst_tv.simps * by auto 
qed

lemma subst_tv_flip:
  assumes "\<tau>'[x::=v]\<^sub>\<tau>\<^sub>v = \<tau>" and "atom x \<sharp> (v,\<tau>)" and "atom x' \<sharp> (v,\<tau>)"
  shows "((x' \<leftrightarrow> x) \<bullet> \<tau>')[x'::=v]\<^sub>\<tau>\<^sub>v = \<tau>"
proof -
  have "(x' \<leftrightarrow> x) \<bullet> v = v \<and> (x' \<leftrightarrow> x) \<bullet> \<tau> = \<tau>" using assms flip_fresh_fresh by auto
  thus ?thesis using subst_tv.eqvt[of  "(x' \<leftrightarrow> x)"  \<tau>' x v ] assms by auto
qed

lemma subst_cv_true:
  "\<lbrace> z : B_id tid  | TRUE \<rbrace> = \<lbrace> z : B_id tid  | TRUE \<rbrace>[x::=v]\<^sub>\<tau>\<^sub>v" 
proof -
  obtain za::x where "atom za \<sharp> (x,v)" using obtain_fresh by auto
  hence "\<lbrace> z : B_id tid   | TRUE \<rbrace> = \<lbrace> za: B_id tid | TRUE \<rbrace>" using \<tau>.eq_iff Abs1_eq_iff by fastforce
  moreover have  "\<lbrace> za : B_id tid   | TRUE \<rbrace> = \<lbrace> za : B_id tid   | TRUE \<rbrace>[x::=v]\<^sub>\<tau>\<^sub>v"  
    using subst_cv.simps subst_tv.simps  by (simp add: \<open>atom za \<sharp> (x, v)\<close>)
  ultimately show ?thesis by argo
qed

lemma t_eq_supp:
  assumes "(\<lbrace> z : b | c \<rbrace>) = (\<lbrace>  z1 : b1 | c1 \<rbrace>)"
  shows "supp c - { atom z } = supp c1 - { atom z1 }"
proof - 
  have "supp c - { atom z } \<union> supp b = supp c1 - { atom z1 } \<union> supp b1" using \<tau>.supp assms
    by (metis list.set(1) list.simps(15) sup_bot.right_neutral supp_b_empty)
  moreover have "supp b = supp b1" using assms  \<tau>.eq_iff by simp
  moreover have "atom z1 \<notin> supp b1 \<and> atom z \<notin> supp b" using  supp_b_empty by simp
  ultimately show ?thesis
    by (metis \<tau>.eq_iff \<tau>.supp assms b.supp(1) list.set(1) list.set(2) sup_bot.right_neutral)
qed

lemma fresh_t_eq: 
  fixes x::x
  assumes  "(\<lbrace> z : b  | c \<rbrace>) = (\<lbrace> zz : b | cc \<rbrace>)" and "atom x \<sharp> c" and "x \<noteq> zz"
  shows "atom x \<sharp> cc"
proof - 
  have "supp c - { atom z } \<union> supp b = supp cc - { atom zz } \<union> supp b" using \<tau>.supp assms
    by (metis list.set(1) list.simps(15) sup_bot.right_neutral supp_b_empty)
  moreover have "atom x \<notin> supp c" using assms fresh_def by blast
  ultimately have "atom x \<notin> supp cc - { atom zz } \<union> supp b" by force
  hence "atom x \<notin> supp cc" using assms by simp
  thus ?thesis using fresh_def by auto
qed

section \<open>Mutable Variable Context\<close>

nominal_function subst_dv :: "\<Delta> \<Rightarrow> x \<Rightarrow> v \<Rightarrow> \<Delta>" where
  "subst_dv  DNil x v = DNil"
| "subst_dv ((u,t) #\<^sub>\<Delta> \<Delta>) x v  = ((u,t[x::=v]\<^sub>\<tau>\<^sub>v) #\<^sub>\<Delta> (subst_dv \<Delta> x v ))"
       apply (simp add: eqvt_def subst_dv_graph_aux_def,auto )
  using delete_aux.elims by (metis \<Delta>.exhaust surj_pair)
nominal_termination (eqvt) by lexicographic_order

abbreviation 
  subst_dv_abbrev :: "\<Delta> \<Rightarrow> x \<Rightarrow> v \<Rightarrow> \<Delta>" (\<open>_[_::=_]\<^sub>\<Delta>\<^sub>v\<close> [1000,50,50] 1000)
  where 
    "\<Delta>[x::=v]\<^sub>\<Delta>\<^sub>v  \<equiv> subst_dv \<Delta> x v " 

nominal_function dmap :: "(u*\<tau> \<Rightarrow> u*\<tau>) \<Rightarrow> \<Delta> \<Rightarrow> \<Delta>" where
  "dmap f DNil  = DNil"
| "dmap  f ((u,t)#\<^sub>\<Delta>\<Delta>)  = (f (u,t) #\<^sub>\<Delta> (dmap f \<Delta> ))"
       apply (simp add: eqvt_def dmap_graph_aux_def,auto )
  using delete_aux.elims by (metis \<Delta>.exhaust surj_pair)
nominal_termination (eqvt) by lexicographic_order

lemma subst_dv_iff:
  "\<Delta>[x::=v]\<^sub>\<Delta>\<^sub>v = dmap (\<lambda>(u,t). (u, t[x::=v]\<^sub>\<tau>\<^sub>v)) \<Delta>"
  by(induct \<Delta>, auto)

lemma size_subst_dv [simp]: "size ( subst_dv G i x) \<le> size G"
  by (induct G,auto) 

lemma forget_subst_dv [simp]: "atom a \<sharp> G \<Longrightarrow> subst_dv G a x = G"
  apply (induct G ,auto) 
  using fresh_DCons fresh_PairD(1) not_self_fresh apply fastforce
  apply (simp add: fresh_DCons)+
  done

lemma subst_dv_member:
  assumes "(u,\<tau>) \<in> setD \<Delta>"
  shows  "(u, \<tau>[x::=v]\<^sub>\<tau>\<^sub>v) \<in> setD (\<Delta>[x::=v]\<^sub>\<Delta>\<^sub>v)"
  using assms  by(induct \<Delta> rule: \<Delta>_induct,auto)

lemma fresh_subst_dv:
  fixes x::x
  assumes "atom xa \<sharp> \<Delta>" and "atom xa \<sharp> v"
  shows "atom xa \<sharp>\<Delta>[x::=v]\<^sub>\<Delta>\<^sub>v" 
  using assms proof(induct \<Delta> rule:\<Delta>_induct)
  case DNil
  then show ?case by auto
next
  case (DCons u t  \<Delta>)
  then show ?case using subst_dv.simps  subst_v_\<tau>_def fresh_DCons fresh_Pair by simp
qed

lemma fresh_subst_dv_if:
  fixes j::atom and i::x and  x::v and t::\<Delta>
  assumes "j \<sharp> t \<and> j \<sharp> x" 
  shows  "(j \<sharp> subst_dv t i x)"
  using assms proof(induct t rule: \<Delta>_induct)
  case DNil
  then show ?case using subst_gv.simps fresh_GNil by auto
next
  case (DCons u' t'  D')
  then show ?case unfolding subst_dv.simps using fresh_DCons fresh_subst_tv_if fresh_Pair by metis
qed

section \<open>Statements\<close>

text \<open> Using ideas from proofs at top of AFP/Launchbury/Substitution.thy.
       Subproofs borrowed from there; hence the apply style proofs. \<close>

nominal_function (default "case_sum (\<lambda>x. Inl undefined) (case_sum (\<lambda>x. Inl undefined) (\<lambda>x. Inr undefined))")
  subst_sv :: "s \<Rightarrow> x \<Rightarrow> v  \<Rightarrow> s"
  and subst_branchv :: "branch_s \<Rightarrow> x \<Rightarrow> v  \<Rightarrow> branch_s" 
  and subst_branchlv :: "branch_list \<Rightarrow> x \<Rightarrow> v \<Rightarrow> branch_list" where
  "subst_sv ( (AS_val v') ) x v = (AS_val (subst_vv v' x v  ))"
| "atom y \<sharp> (x,v) \<Longrightarrow> subst_sv  (AS_let y  e s) x v = (AS_let y  (e[x::=v]\<^sub>e\<^sub>v) (subst_sv s x v ))"  
| "atom y \<sharp> (x,v) \<Longrightarrow> subst_sv (AS_let2 y t s1 s2) x v = (AS_let2 y (t[x::=v]\<^sub>\<tau>\<^sub>v) (subst_sv s1 x v ) (subst_sv s2 x v ))"  
| " subst_sv (AS_match v'  cs) x v = AS_match  (v'[x::=v]\<^sub>v\<^sub>v)  (subst_branchlv cs x v )"
| "subst_sv (AS_assign y v') x v = AS_assign y (subst_vv v' x v )"
| "subst_sv ( (AS_if v' s1 s2) ) x v = (AS_if (subst_vv v' x v ) (subst_sv s1 x v ) (subst_sv s2 x v ) )"  
| "atom u \<sharp> (x,v) \<Longrightarrow> subst_sv (AS_var u \<tau> v' s) x v = AS_var u (subst_tv \<tau> x v ) (subst_vv v' x v ) (subst_sv s x v ) "
| "subst_sv (AS_while s1 s2) x v = AS_while (subst_sv s1 x v ) (subst_sv s2 x v )"
| "subst_sv (AS_seq s1 s2) x v = AS_seq (subst_sv s1 x v ) (subst_sv s2 x v )" 
| "subst_sv (AS_assert c s) x v = AS_assert (subst_cv c x v) (subst_sv s x v)"
| "atom x1 \<sharp> (x,v) \<Longrightarrow>  subst_branchv (AS_branch dc x1 s1 ) x v  = AS_branch dc x1 (subst_sv s1 x v )" 

| "subst_branchlv (AS_final cs) x v = AS_final (subst_branchv  cs x v )"
| "subst_branchlv (AS_cons cs css) x v = AS_cons (subst_branchv cs x v ) (subst_branchlv css x v )"
                      apply (auto,simp add: eqvt_def subst_sv_subst_branchv_subst_branchlv_graph_aux_def )
proof(goal_cases)

  have eqvt_at_proj: "\<And> s xa va . eqvt_at subst_sv_subst_branchv_subst_branchlv_sumC (Inl (s, xa, va)) \<Longrightarrow> 
           eqvt_at (\<lambda>a. projl (subst_sv_subst_branchv_subst_branchlv_sumC (Inl a))) (s, xa, va)"
    apply(simp add: eqvt_at_def)
    apply(rule)
    apply(subst Projl_permute)
     apply(thin_tac _)+
     apply (simp add: subst_sv_subst_branchv_subst_branchlv_sumC_def)
     apply (simp add: THE_default_def)
     apply (case_tac "Ex1 (subst_sv_subst_branchv_subst_branchlv_graph (Inl (s,xa,va)))")
      apply simp
      apply(auto)[1]
      apply (erule_tac x="x" in allE)
      apply simp
      apply(cases rule: subst_sv_subst_branchv_subst_branchlv_graph.cases)    
                   apply(assumption)
                  apply(rule_tac x="Sum_Type.projl x" in exI,clarify,rule the1_equality,blast,simp (no_asm) only: sum.sel)+
        apply blast +

    apply(simp)+      
    done

  {
    case (1 P x')    
    then show ?case proof(cases x')
      case (Inl a) thus P 
      proof(cases a)
        case (fields aa bb cc)
        thus P using Inl 1 s_branch_s_branch_list.strong_exhaust fresh_star_insert by metis
      qed
    next
      case (Inr b) thus P
      proof(cases b)
        case (Inl a) thus P proof(cases a)
          case (fields aa bb cc)
          then show ?thesis  using Inr Inl 1 s_branch_s_branch_list.strong_exhaust fresh_star_insert by metis
        qed
      next
        case Inr2: (Inr b) thus P proof(cases b)
          case (fields aa bb cc)
          then show ?thesis  using Inr Inr2 1 s_branch_s_branch_list.strong_exhaust fresh_star_insert by metis
        qed
      qed
    qed
  next
    case (2 y s ya xa va sa c)
    thus ?case using eqvt_triple eqvt_at_proj by blast
  next
    case (3 y s2 ya xa va s1a s2a c)
    thus ?case using eqvt_triple eqvt_at_proj by blast
  next
    case (4 u xa va s ua sa c)
    moreover have "atom u \<sharp> (xa, va) \<and> atom ua \<sharp> (xa, va)" 
      using fresh_Pair u_fresh_xv by auto
    ultimately show ?case using eqvt_triple[of u xa va ua s sa]  subst_sv_def eqvt_at_proj by metis
  next
    case (5 x1 s1 x1a xa va s1a c)
    thus ?case using eqvt_triple eqvt_at_proj by blast
  }
qed
nominal_termination (eqvt) by lexicographic_order

abbreviation 
  subst_sv_abbrev :: "s \<Rightarrow> x \<Rightarrow> v \<Rightarrow> s" (\<open>_[_::=_]\<^sub>s\<^sub>v\<close> [1000,50,50] 1000)
  where 
    "s[x::=v]\<^sub>s\<^sub>v  \<equiv> subst_sv s x v" 

abbreviation 
  subst_branchv_abbrev :: "branch_s \<Rightarrow> x \<Rightarrow> v \<Rightarrow> branch_s" (\<open>_[_::=_]\<^sub>s\<^sub>v\<close> [1000,50,50] 1000)
  where 
    "s[x::=v]\<^sub>s\<^sub>v  \<equiv> subst_branchv s x v" 

lemma size_subst_sv [simp]:  "size (subst_sv A i x ) = size A" and  "size (subst_branchv B i x ) = size B"  and  "size (subst_branchlv C i x ) = size C"
  by(nominal_induct A and B and C avoiding: i x rule: s_branch_s_branch_list.strong_induct,auto)

lemma forget_subst_sv [simp]: shows  "atom a \<sharp> A \<Longrightarrow> subst_sv A a x = A" and "atom a \<sharp> B \<Longrightarrow> subst_branchv B a x = B" and "atom a \<sharp> C \<Longrightarrow> subst_branchlv C a x  = C"
  by (nominal_induct A and B and C avoiding: a x rule: s_branch_s_branch_list.strong_induct,auto simp: fresh_at_base)

lemma subst_sv_id [simp]: "subst_sv A a (V_var a) = A" and "subst_branchv B a (V_var a) = B" and  "subst_branchlv C a (V_var a)  = C"
proof(nominal_induct A and B and C avoiding: a  rule: s_branch_s_branch_list.strong_induct) 
  case (AS_let x option e s)
  then show ?case 
    by (metis (no_types, lifting) fresh_Pair not_None_eq subst_ev_id subst_sv.simps(2) subst_sv.simps(3) subst_tv_id v.fresh(2))
next
  case (AS_match v branch_s)
  then show ?case using fresh_Pair not_None_eq subst_ev_id subst_sv.simps subst_sv.simps subst_tv_id v.fresh subst_vv_id
    by metis 
qed(auto)+ 

lemma fresh_subst_sv_if_rl:
  shows 
    "(atom x \<sharp> s \<and> j \<sharp> s) \<or> (j \<sharp> v \<and> (j \<sharp> s \<or> j = atom x)) \<Longrightarrow> j \<sharp> (subst_sv s x v )" and
    "(atom x \<sharp> cs \<and> j \<sharp> cs) \<or> (j \<sharp> v \<and> (j \<sharp> cs \<or> j = atom x)) \<Longrightarrow> j \<sharp> (subst_branchv cs x v)" and
    "(atom x \<sharp> css \<and> j \<sharp> css) \<or> (j \<sharp> v \<and> (j \<sharp> css \<or> j = atom x)) \<Longrightarrow> j \<sharp> (subst_branchlv css x v )" 
    apply(nominal_induct s and cs and css avoiding: v x rule: s_branch_s_branch_list.strong_induct)
  using pure_fresh by force+

lemma fresh_subst_sv_if_lr:
  shows  "j \<sharp> (subst_sv s x v) \<Longrightarrow> (atom x \<sharp> s \<and> j \<sharp> s) \<or> (j \<sharp> v \<and> (j \<sharp> s \<or> j = atom x))" and
    "j \<sharp> (subst_branchv cs x v) \<Longrightarrow> (atom x \<sharp> cs \<and> j \<sharp> cs) \<or> (j \<sharp> v \<and> (j \<sharp> cs \<or> j = atom x))" and       
    "j \<sharp> (subst_branchlv css x v ) \<Longrightarrow> (atom x \<sharp> css \<and> j \<sharp> css) \<or> (j \<sharp> v \<and> (j \<sharp> css \<or> j = atom x))"
proof(nominal_induct s and cs and css avoiding: v x rule: s_branch_s_branch_list.strong_induct)
  case (AS_branch list x s )
  then show ?case using s_branch_s_branch_list.fresh fresh_Pair list.distinct(1) list.set_cases pure_fresh set_ConsD subst_branchv.simps by metis
next
  case (AS_let y e s')
  thus ?case proof(cases "atom x \<sharp>  (AS_let y e s')")
    case True
    hence "subst_sv (AS_let y  e s') x v  =  (AS_let y e s')" using forget_subst_sv by simp
    hence "j \<sharp>  (AS_let y  e s')" using AS_let by argo
    then show ?thesis using True by blast
  next
    case False
    have "subst_sv (AS_let y  e s') x v  = AS_let y  (e[x::=v]\<^sub>e\<^sub>v) (s'[x::=v]\<^sub>s\<^sub>v)" using subst_sv.simps(2) AS_let by force
    hence "((j \<sharp> s'[x::=v]\<^sub>s\<^sub>v \<or> j \<in> set [atom y]) \<and> j \<sharp> None \<and> j \<sharp> e[x::=v]\<^sub>e\<^sub>v)" using s_branch_s_branch_list.fresh AS_let 
      by (simp add: fresh_None)
    then show ?thesis using  AS_let  fresh_None fresh_subst_ev_if list.discI list.set_cases s_branch_s_branch_list.fresh set_ConsD 
      by metis
  qed
next
  case (AS_let2 y \<tau> s1 s2)
  thus ?case proof(cases "atom x \<sharp>  (AS_let2 y \<tau> s1 s2)")
    case True
    hence "subst_sv  (AS_let2 y \<tau> s1 s2)  x v =  (AS_let2 y \<tau> s1 s2)" using forget_subst_sv by simp
    hence "j \<sharp>  (AS_let2 y \<tau> s1 s2)" using AS_let2 by argo
    then show ?thesis using True by blast
  next
    case False
    have "subst_sv (AS_let2 y \<tau> s1 s2) x v  = AS_let2 y (\<tau>[x::=v]\<^sub>\<tau>\<^sub>v) (s1[x::=v]\<^sub>s\<^sub>v) (s2[x::=v]\<^sub>s\<^sub>v)" using subst_sv.simps AS_let2 by force
    then show ?thesis using  AS_let2
        fresh_subst_tv_if list.discI list.set_cases s_branch_s_branch_list.fresh(4) set_ConsD by auto
  qed
qed(auto)+

lemma fresh_subst_sv_if[simp]:
  fixes x::x and v::v
  shows "j \<sharp> (subst_sv s x v) \<longleftrightarrow> (atom x \<sharp> s \<and> j \<sharp> s) \<or> (j \<sharp> v \<and> (j \<sharp> s \<or> j = atom x))" and
    "j \<sharp> (subst_branchv cs x v) \<longleftrightarrow> (atom x \<sharp> cs \<and> j \<sharp> cs) \<or> (j \<sharp> v \<and> (j \<sharp> cs \<or> j = atom x))"
  using fresh_subst_sv_if_lr fresh_subst_sv_if_rl by metis+

lemma subst_sv_commute [simp]:
  fixes A::s and t::v and j::x and i::x
  shows  "atom j \<sharp> A \<Longrightarrow> (subst_sv (subst_sv A i t)  j u ) = subst_sv A i (subst_vv t j u )" and
    "atom j \<sharp> B \<Longrightarrow> (subst_branchv  (subst_branchv B i t ) j u ) = subst_branchv B i (subst_vv t j u )" and
    "atom j \<sharp> C \<Longrightarrow> (subst_branchlv  (subst_branchlv C i t) j u ) = subst_branchlv C i (subst_vv t j u   ) "
    apply(nominal_induct A and B and C avoiding: i j t u rule: s_branch_s_branch_list.strong_induct) 
  by(auto simp: fresh_at_base)

lemma c_eq_perm:
  assumes "( (atom z)  \<rightleftharpoons> (atom z') )  \<bullet> c = c'" and "atom z'  \<sharp> c"
  shows "\<lbrace> z : b | c \<rbrace> = \<lbrace> z' : b | c' \<rbrace>"
  using \<tau>.eq_iff Abs1_eq_iff(3) 
  by (metis Nominal2_Base.swap_commute assms(1) assms(2) flip_def swap_fresh_fresh)

lemma subst_sv_flip:
  fixes s::s and sa::s and v'::v
  assumes "atom c \<sharp> (s, sa)" and "atom c \<sharp> (v',x, xa, s, sa)" "atom x \<sharp> v'" and "atom xa \<sharp> v'" and "(x \<leftrightarrow> c) \<bullet> s = (xa \<leftrightarrow> c) \<bullet> sa" 
  shows "s[x::=v']\<^sub>s\<^sub>v = sa[xa::=v']\<^sub>s\<^sub>v"
proof - 
  have "atom x \<sharp> (s[x::=v']\<^sub>s\<^sub>v)" and xafr: "atom xa \<sharp> (sa[xa::=v']\<^sub>s\<^sub>v)" 
    and  "atom c \<sharp> ( s[x::=v']\<^sub>s\<^sub>v, sa[xa::=v']\<^sub>s\<^sub>v)" using assms using  fresh_subst_sv_if assms  by( blast+ ,force)

  hence "s[x::=v']\<^sub>s\<^sub>v = (x \<leftrightarrow> c) \<bullet> (s[x::=v']\<^sub>s\<^sub>v)"  by (simp add: flip_fresh_fresh fresh_Pair)
  also have " ... = ((x \<leftrightarrow> c) \<bullet> s)[ ((x \<leftrightarrow> c) \<bullet> x) ::= ((x \<leftrightarrow> c) \<bullet> v') ]\<^sub>s\<^sub>v" using subst_sv_subst_branchv_subst_branchlv.eqvt  by blast
  also have "... = ((xa \<leftrightarrow> c) \<bullet> sa)[ ((x \<leftrightarrow> c) \<bullet> x) ::= ((x \<leftrightarrow> c) \<bullet> v') ]\<^sub>s\<^sub>v" using assms by presburger
  also have "... = ((xa \<leftrightarrow> c) \<bullet> sa)[ ((xa \<leftrightarrow> c) \<bullet> xa) ::= ((xa \<leftrightarrow> c) \<bullet> v') ]\<^sub>s\<^sub>v" using assms 
    by (metis flip_at_simps(1) flip_fresh_fresh fresh_PairD(1))
  also have "... =  (xa \<leftrightarrow> c) \<bullet> (sa[xa::=v']\<^sub>s\<^sub>v)" using subst_sv_subst_branchv_subst_branchlv.eqvt  by presburger
  also have "... = sa[xa::=v']\<^sub>s\<^sub>v" using xafr assms by (simp add: flip_fresh_fresh fresh_Pair)
  finally show ?thesis by simp
qed

lemma if_type_eq:
  fixes \<Gamma>::\<Gamma> and v::v and z1::x
  assumes "atom z1' \<sharp> (v, ca, (x, b, c) #\<^sub>\<Gamma> \<Gamma>,  (CE_val v  ==  CE_val (V_lit ll) IMP  ca[za::=[z1]\<^sup>v]\<^sub>c\<^sub>v ))" and "atom z1 \<sharp> v" 
    and "atom z1 \<sharp> (za,ca)" and "atom z1' \<sharp> (za,ca)"
  shows "(\<lbrace> z1' : ba  | CE_val v  ==  CE_val (V_lit ll)   IMP  ca[za::=[z1']\<^sup>v]\<^sub>c\<^sub>v  \<rbrace>) = \<lbrace> z1 : ba  | CE_val v  ==  CE_val (V_lit ll) IMP  ca[za::=[z1]\<^sup>v]\<^sub>c\<^sub>v  \<rbrace>"
proof -
  have "atom z1' \<sharp> (CE_val v  ==  CE_val (V_lit ll) IMP  ca[za::=[z1]\<^sup>v]\<^sub>c\<^sub>v )" using assms fresh_prod4 by blast
  moreover hence "(CE_val v  ==  CE_val (V_lit ll)   IMP  ca[za::=[z1']\<^sup>v]\<^sub>c\<^sub>v) = (z1' \<leftrightarrow> z1) \<bullet> (CE_val v  ==  CE_val (V_lit ll)   IMP  ca[za::=[z1]\<^sup>v]\<^sub>c\<^sub>v )"
  proof -
    have "(z1' \<leftrightarrow> z1) \<bullet> (CE_val v  ==  CE_val (V_lit ll)   IMP  ca[za::=[z1]\<^sup>v]\<^sub>c\<^sub>v ) = ( (z1' \<leftrightarrow> z1) \<bullet> (CE_val v  ==  CE_val (V_lit ll)) IMP  ((z1' \<leftrightarrow> z1) \<bullet> ca[za::=[z1]\<^sup>v]\<^sub>c\<^sub>v ))"
      by auto
    also have "... = ((CE_val v  ==  CE_val (V_lit ll))   IMP  ((z1' \<leftrightarrow> z1) \<bullet> ca[za::=[z1]\<^sup>v]\<^sub>c\<^sub>v ))"
      using \<open>atom z1 \<sharp> v\<close> assms 
      by (metis (mono_tags) \<open>atom z1' \<sharp> (CE_val v == CE_val (V_lit ll) IMP ca[za::=[z1]\<^sup>v]\<^sub>c\<^sub>v )\<close> c.fresh(6) c.fresh(7) ce.fresh(1) flip_at_simps(2) flip_fresh_fresh fresh_at_base_permute_iff fresh_def supp_l_empty v.fresh(1))
    also have "... =  ((CE_val v  ==  CE_val (V_lit ll))   IMP  (ca[za::=[z1']\<^sup>v]\<^sub>c\<^sub>v ))"
      using assms   by fastforce
    finally show ?thesis by auto
  qed
  ultimately show ?thesis    
    using \<tau>.eq_iff Abs1_eq_iff(3)[of z1' "CE_val v  ==  CE_val (V_lit ll) IMP  ca[za::=[z1']\<^sup>v]\<^sub>c\<^sub>v" 
        z1 "CE_val v  ==  CE_val (V_lit ll)   IMP ca[za::=[z1]\<^sup>v]\<^sub>c\<^sub>v"] by blast
qed 

lemma subst_sv_var_flip:
  fixes x::x and s::s and z::x
  shows "atom x \<sharp> s \<Longrightarrow> ((x \<leftrightarrow> z) \<bullet> s) = s[z::=[x]\<^sup>v]\<^sub>s\<^sub>v" and 
    "atom x \<sharp> cs \<Longrightarrow> ((x \<leftrightarrow> z) \<bullet> cs) = subst_branchv cs z [x]\<^sup>v" and
    "atom x \<sharp> css \<Longrightarrow> ((x \<leftrightarrow> z) \<bullet> css) = subst_branchlv css z [x]\<^sup>v"
    apply(nominal_induct s and cs and css avoiding: z x rule: s_branch_s_branch_list.strong_induct)
  using [[simproc del: alpha_lst]]
              apply (auto  ) (* This unpacks subst, perm *)
  using  subst_tv_var_flip  flip_fresh_fresh v.fresh s_branch_s_branch_list.fresh 
    subst_v_τ_def subst_v_v_def subst_vv_var_flip subst_v_e_def subst_ev_var_flip pure_fresh   apply auto 
     defer 1 (* Sometimes defering hard goals to the end makes it easier to finish *)
  using x_fresh_u   apply blast (* Next two involve u and flipping with x *)
    defer 1
  using x_fresh_u   apply blast
   defer 1
  using x_fresh_u Abs1_eq_iff'(3) flip_fresh_fresh 
   apply (simp add: subst_v_c_def)
  using x_fresh_u Abs1_eq_iff'(3) flip_fresh_fresh  
  by (simp add: flip_fresh_fresh)

instantiation s :: has_subst_v
begin

definition 
  "subst_v = subst_sv"

instance proof
  fix j::atom and i::x and  x::v and t::s
  show  "(j ♯ subst_v t i x) = ((atom i ♯ t ∧ j ♯ t) ∨ (j ♯ x ∧ (j ♯ t ∨ j = atom i)))"
    using fresh_subst_sv_if subst_v_s_def by auto

  fix a::x and tm::s and x::v
  show "atom a ♯ tm ==> subst_v tm a x = tm"
    using forget_subst_sv subst_v_s_def by simp

  fix a::x and tm::s
  show "subst_v tm a (V_var a) = tm" using subst_sv_id  subst_v_s_def by simp

  fix p::perm and x1::x and v::v and t1::s
  show "p ∙ subst_v t1 x1 v = subst_v (p ∙ t1) (p ∙ x1) (p ∙ v)" 
    using subst_sv_commute  subst_v_s_def by simp

  fix x::x and c::s and z::x
  show "atom x ♯ c ==> ((x ↔ z) ∙ c) = c[z::=[x]^v]_v"
    using subst_sv_var_flip subst_v_s_def by simp

  fix x::x and c::s and z::x
  show  "atom x ♯ c ==> c[z::=[x]^v]_v[x::=v]_v = c[z::=v]_v"
    using subst_sv_var_flip subst_v_s_def by simp
qed
end

section ‹Type Definition›

nominal_function subst_ft_v :: "fun_typ ==> x ==> v ==> fun_typ" where
  "atom z ♯ (x,v) ==> subst_ft_v ( AF_fun_typ z b c t (s::s)) x v = AF_fun_typ z b c[x::=v]_cv t[x::=v]_\<tau>_v s[x::=v]_sv"
     apply(simp add: eqvt_def subst_ft_v_graph_aux_def )
    apply(simp add:fun_typ.strong_exhaust )
   apply(auto) 
    apply(rule_tac y=a and c="(aa,b)" in fun_typ.strong_exhaust)
    apply (auto simp: eqvt_at_def fresh_star_def fresh_Pair fresh_at_base)

proof(goal_cases)
  case (1 z xa va c t s za ca ta sa cb)
  hence  "c[z::=[ cb ]^v]_cv = ca[za::=[ cb ]^v]_cv" 
    by (metis flip_commute subst_cv_var_flip)
  hence  "c[z::=[ cb ]^v]_cv[xa::=va]_cv = ca[za::=[ cb ]^v]_cv[xa::=va]_cv" by auto
  then show ?case using subst_cv_commute atom_eq_iff fresh_atom fresh_atom_at_base subst_cv_commute_full v.fresh 
    using 1 subst_cv_var_flip  flip_commute by metis
next
  case (2 z xa va c t s za ca ta sa cb)
  hence  "t[z::=[ cb ]^v]_\<tau>_v = ta[za::=[ cb ]^v]_\<tau>_v" by metis
  hence  "t[z::=[ cb ]^v]_\<tau>_v[xa::=va]_\<tau>_v = ta[za::=[ cb ]^v]_\<tau>_v[xa::=va]_\<tau>_v" by auto
  then show ?case using subst_tv_commute_full 2 
    by (metis atom_eq_iff fresh_atom fresh_atom_at_base v.fresh(2))
qed

nominal_termination (eqvt) by lexicographic_order

nominal_function subst_ftq_v :: "fun_typ_q ==> x ==> v ==> fun_typ_q" where
  "atom bv ♯ (x,v) ==> subst_ftq_v (AF_fun_typ_some bv ft) x v = (AF_fun_typ_some bv (subst_ft_v ft x v))" 
|  "subst_ftq_v (AF_fun_typ_none ft) x v = (AF_fun_typ_none (subst_ft_v ft x v))" 
       apply(simp add: eqvt_def subst_ftq_v_graph_aux_def )
      apply(simp add:fun_typ_q.strong_exhaust )
     apply(auto) 
   apply(rule_tac y=a and c="(aa,b)" in fun_typ_q.strong_exhaust)
    apply (auto simp: eqvt_at_def fresh_star_def fresh_Pair fresh_at_base)
proof(goal_cases)
  case (1 bv ft bva fta xa va c)
  then show ?case using subst_ft_v.simps  by (simp add: flip_fresh_fresh)
qed
nominal_termination (eqvt) by lexicographic_order

lemma size_subst_ft[simp]:  "size (subst_ft_v A x v) = size A" 
  by(nominal_induct A  avoiding: x v rule: fun_typ.strong_induct,auto)

lemma forget_subst_ft [simp]: shows  "atom x ♯ A ==> subst_ft_v A x a = A" 
  by (nominal_induct A  avoiding: a x rule: fun_typ.strong_induct,auto simp: fresh_at_base)

lemma subst_ft_id [simp]: "subst_ft_v A a (V_var a) = A"
  by(nominal_induct A  avoiding: a  rule: fun_typ.strong_induct,auto) 

instantiation fun_typ :: has_subst_v
begin

definition 
  "subst_v = subst_ft_v"

instance proof

  fix j::atom and i::x and  x::v and t::fun_typ
  show  "(j ♯ subst_v t i x) = ((atom i ♯ t ∧ j ♯ t) ∨ (j ♯ x ∧ (j ♯ t ∨ j = atom i)))"
    apply(nominal_induct t avoiding: i x rule:fun_typ.strong_induct)
    apply(simp only: subst_v_fun_typ_def subst_ft_v.simps )
    using fun_typ.fresh fresh_subst_v_if apply simp
    by auto

  fix a::x and tm::fun_typ and x::v
  show "atom a ♯ tm ==> subst_v tm a x = tm"
  proof(nominal_induct tm avoiding: a x rule:fun_typ.strong_induct)
    case (AF_fun_typ x1a x2a x3a x4a x5a)
    then show ?case unfolding subst_ft_v.simps subst_v_fun_typ_def fun_typ.fresh  using forget_subst_v subst_ft_v.simps subst_v_c_def forget_subst_sv subst_v_τ_def by fastforce
  qed

  fix a::x and tm::fun_typ
  show "subst_v tm a (V_var a) = tm" 
  proof(nominal_induct tm avoiding: a x rule:fun_typ.strong_induct)
    case (AF_fun_typ x1a x2a x3a x4a x5a)
    then show ?case unfolding subst_ft_v.simps subst_v_fun_typ_def fun_typ.fresh  using forget_subst_v subst_ft_v.simps subst_v_c_def forget_subst_sv subst_v_τ_def by fastforce
  qed

  fix p::perm and x1::x and v::v and t1::fun_typ
  show "p ∙ subst_v t1 x1 v = subst_v (p ∙ t1) (p ∙ x1) (p ∙ v)" 
  proof(nominal_induct t1 avoiding: x1 v rule:fun_typ.strong_induct)
    case (AF_fun_typ x1a x2a x3a x4a x5a)
    then show ?case unfolding subst_ft_v.simps subst_v_fun_typ_def fun_typ.fresh  using forget_subst_v subst_ft_v.simps subst_v_c_def forget_subst_sv subst_v_τ_def by fastforce
  qed

  fix x::x and c::fun_typ and z::x
  show "atom x ♯ c ==> ((x ↔ z) ∙ c) = c[z::=[x]^v]_v"
    apply(nominal_induct c avoiding: x z rule:fun_typ.strong_induct)
    by (auto simp add: subst_v_c_def subst_v_s_def subst_v_τ_def subst_v_fun_typ_def)

  fix x::x and c::fun_typ and z::x
  show  "atom x ♯ c ==> c[z::=[x]^v]_v[x::=v]_v = c[z::=v]_v"
    apply(nominal_induct c avoiding: z x v rule:fun_typ.strong_induct)
    apply auto
    by (auto simp add: subst_v_c_def subst_v_s_def subst_v_τ_def subst_v_fun_typ_def )
qed
end

instantiation fun_typ_q :: has_subst_v
begin

definition 
  "subst_v = subst_ftq_v"

instance proof
  fix j::atom and i::x and  x::v and t::fun_typ_q
  show  "(j ♯ subst_v t i x) = ((atom i ♯ t ∧ j ♯ t) ∨ (j ♯ x ∧ (j ♯ t ∨ j = atom i)))"
    apply(nominal_induct t avoiding: i x rule:fun_typ_q.strong_induct,auto)
                   apply(auto simp add: subst_v_fun_typ_def subst_v_s_def subst_v_τ_def subst_v_fun_typ_q_def fresh_subst_v_if )    
    by (metis (no_types) fresh_subst_v_if subst_v_fun_typ_def)+

  fix i::x and t::fun_typ_q and x::v
  show "atom i ♯ t ==> subst_v t i x = t"
    apply(nominal_induct t avoiding: i x rule:fun_typ_q.strong_induct,auto)
    by(auto simp add: subst_v_fun_typ_def subst_v_s_def subst_v_τ_def subst_v_fun_typ_q_def fresh_subst_v_if )    

  fix i::x and t::fun_typ_q
  show "subst_v t i (V_var i) = t" using subst_cv_id  subst_v_fun_typ_def  
    apply(nominal_induct t avoiding: i x rule:fun_typ_q.strong_induct,auto)
    by(auto simp add: subst_v_fun_typ_def subst_v_s_def subst_v_τ_def subst_v_fun_typ_q_def fresh_subst_v_if )  

  fix p::perm and x1::x and v::v and t1::fun_typ_q
  show "p ∙ subst_v t1 x1 v = subst_v (p ∙ t1) (p ∙ x1) (p ∙ v)" 
    apply(nominal_induct t1 avoiding: v x1 rule:fun_typ_q.strong_induct,auto)
    by(auto simp add: subst_v_fun_typ_def subst_v_s_def subst_v_τ_def subst_v_fun_typ_q_def fresh_subst_v_if )  

  fix x::x and c::fun_typ_q and z::x
  show "atom x ♯ c ==> ((x ↔ z) ∙ c) = c[z::=[x]^v]_v"
    apply(nominal_induct c avoiding: x z rule:fun_typ_q.strong_induct,auto)
    by(auto simp add: subst_v_fun_typ_def subst_v_s_def subst_v_τ_def subst_v_fun_typ_q_def fresh_subst_v_if )  

  fix x::x and c::fun_typ_q and z::x
  show  "atom x ♯ c ==> c[z::=[x]^v]_v[x::=v]_v = c[z::=v]_v"
    apply(nominal_induct c avoiding: z x v rule:fun_typ_q.strong_induct,auto)
     apply(auto simp add: subst_v_fun_typ_def subst_v_s_def subst_v_τ_def subst_v_fun_typ_q_def fresh_subst_v_if )  
    by (metis subst_v_fun_typ_def flip_bv_x_cancel subst_ft_v.eqvt subst_v_simple_commute v.perm_simps )+
qed

end

section ‹Variable Context›

lemma subst_dv_fst_eq:
  "fst ` setD (Δ[x::=v]<sub>\</sub><Delta><sub>v</sub>) = fst ` setD Δ" 
  by(induct Δ rule: Δ_induct,simp,force)

lemma subst_gv_member_iff:
  fixes x'::x and x::x and v::v and c'::c
  assumes "(x',b',c') ∈ toSet Γ" and "atom x ∉ atom_dom Γ" 
  shows "(x',b',c'[x::=v]_cv) ∈ toSet Γ[x::=v]_\<Gamma>_v"
proof -
  have "x' ≠ x" using assms fresh_dom_free2 by metis
  then show ?thesis  using assms proof(induct Γ rule: Γ_induct)
    case GNil
    then show ?case by auto
  next
    case (GCons x1 b1 c1 Γ')
    show ?case proof(cases "(x',b',c') = (x1,b1,c1)")
      case True
      hence "((x1, b1, c1) #_\<Gamma> Γ')[x::=v]_\<Gamma>_v = ((x1, b1, c1[x::=v]_cv) #_\<Gamma> (Γ'[x::=v]_\<Gamma>_v))"  using subst_gv.simps  ‹x'≠x› by auto
      then show ?thesis using True by auto
    next
      case False
      have "x1≠x" using fresh_def fresh_GCons fresh_Pair supp_at_base GCons fresh_dom_free2 by auto
      hence "(x', b', c') ∈ toSet Γ'" using GCons False toSet.simps by auto
      moreover have "atom x ∉ atom_dom Γ'" using fresh_GCons GCons dom.simps toSet.simps by simp
      ultimately have  "(x', b', c'[x::=v]_cv) ∈ toSet Γ'[x::=v]_\<Gamma>_v" using GCons by auto
      hence "(x', b', c'[x::=v]_cv) ∈ toSet ((x1, b1, c1[x::=v]_cv) #_\<Gamma> (Γ'[x::=v]_\<Gamma>_v))" by auto
      then show ?thesis using subst_gv.simps ‹x1≠x› by auto
    qed
  qed
qed

lemma fresh_subst_gv_if:
  fixes j::atom and i::x and  x::v and t::Γ
  assumes "j ♯ t ∧ j ♯ x" 
  shows  "(j ♯ subst_gv t i x)"
  using assms proof(induct t rule: Γ_induct)
  case GNil
  then show ?case using subst_gv.simps fresh_GNil by auto
next
  case (GCons x' b' c' Γ')
  then show ?case unfolding subst_gv.simps using fresh_GCons fresh_subst_cv_if by auto
qed

section ‹Lookup›

lemma set_GConsD: "y ∈ toSet (x #_\<Gamma> xs) ==> y=x ∨ y ∈ toSet xs"
  by auto

lemma  subst_g_assoc_cons:
  assumes "x ≠ x'"
  shows "(((x', b', c') #_\<Gamma> Γ')[x::=v]_\<Gamma>_v @ G) = ((x', b', c'[x::=v]_cv) #_\<Gamma> ((Γ'[x::=v]_\<Gamma>_v) @ G))"
  using subst_gv.simps append_g.simps assms by auto

end