proposition: Fact fol_equiv_spec φ : fol_sem M φ fol_equivalence <-> equiv _ (fun x y => x ≈ y).
proof: Proof. unfold fol_equivalence. repeat (rewrite fol_sem_bin_fix). repeat fol equiv conj. + rewrite fol_sem_quant_fix; apply forall_equiv; intro. rewrite fol_sem_e; simpl; tauto. + do 3 (rewrite fol_sem_quant_fix; apply forall_equiv; intro). do 2 rewrite fol_sem_bin_fix. do 3 rewrite fol_sem_e; simpl; tauto. + do 2 (rewrite fol_sem_quant_fix; apply forall_equiv; intro). rewrite fol_sem_bin_fix. do 2 rewrite fol_sem_e; simpl; tauto. Qed.
imports: List Arith Lia Relations Undecidability.Shared.Libs.DLW.Utils(utils_tac utils_list utils_nat finite) Undecidability.Shared.Libs.DLW.Vec(pos vec) Undecidability.FOL.TRAKHTENBROT(notations utils fol_ops fo_sig fo_terms fo_logic) Undecidability.Shared.ListAutomation