proposition: Lemma func_subst_comp {ff:falsity_flag} s rho phi : func_subst_respects s -> phi[s/func][rho>>var] = phi[rho>>var][s/func].
proof: Proof. intros Hresp. induction phi in s,rho,Hresp|-*. - easy. - cbn. rewrite ! map_map. f_equal. apply map_ext. intros a. now apply func_subst_term_comp. - cbn. rewrite IHphi1. 1: now rewrite IHphi2. easy. - cbn. f_equal. rewrite ! (subst_ext _ (up_var_comp _) ). rewrite IHphi. 1:easy. easy. Qed.
imports: Undecidability.Synthetic(Definitions DecidabilityFacts EnumerabilityFacts ListEnumerabilityFacts ReducibilityFacts) Undecidability(Shared.ListAutomation Shared.Dec) Coq(Eqdep_dec) Coq.Vectors.Vector Undecidability.Shared.Libs.PSL.Vectors(Vectors) EqdepFacts