proposition: Lemma min_embed (rho : nat -> V) (phi : form') : sat I rho (embed phi) <-> sat min_model rho phi.
proof: Proof. induction phi as [| |b [] phi1 IH1 phi2 IH2|b [] phi IH] in rho |- *; cbn. 3-5: specialize (IH1 rho); specialize (IH2 rho); tauto. - easy. - destruct P. erewrite Vector.map_map, Vector.map_ext. + reflexivity. + apply min_embed_eval. - now split; intros; apply IH. - split; intros [? ?]; eexists; apply IH; eassumption. Qed.
imports: Undecidability.FOL.Syntax.Facts Undecidability.FOL.Syntax.Asimpl Undecidability.FOL.Semantics.Tarski.FullFacts Undecidability.FOL.Deduction.FullNDFacts Undecidability.FOL.Sets(binZF ZF) Undecidability.FOL.Reductions.PCPb_to_ZF Undecidability(Shared.ListAutomation) Morphisms Undecidability.FOL(Reductions.PCPb_to_ZFeq)