proposition: Lemma subst_apply_encs_to s n u k : k >= n -> subst (apply_encs_to s n) k u = apply_encs_to (subst s k u) n.
proof: Proof. induction n in s, k |- *; intros Hk; cbn -[many_vars]. + reflexivity. + unfold apply_encs_to. rewrite many_vars_S. cbn. unfold apply_encs_to in IHn. rewrite IHn. cbn. repeat (rewrite subst_closed; [| now Lproc]). destruct (Nat.eqb_spec n k). lia. match goal with |- context[subst (ext ?s) _ _] => assert (closed (ext s)) by Lproc end. repeat f_equal. eapply H. lia. Qed.
imports: Undecidability.Shared.Libs.PSL(Vectors) Coq(Vector List) Undecidability.L(L LTactics L_facts Functions.Eval) Undecidability.L.Util(NaryApp)