proposition: Theorem fol_sem_dec A φ : { ⟪A⟫ φ } + { ~ ⟪A⟫ φ }.
proof: Proof. Proof using rels_dec M_fin. revert φ. induction A as [ | p v | b A IHA B IHB | q A IHA ]; intros phi. + simpl; tauto. + simpl; apply rels_dec. + simpl fol_sem; apply fol_bin_sem_dec; auto. + simpl fol_sem; apply fol_quant_sem_dec; auto. Qed.
imports: List Arith Lia 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) Undecidability.Shared.ListAutomation