proposition: Theorem Post_Markov : Posts_thm -> Markovs_princ.
proof: Proof. intros PT f Hf. destruct PT with (P := fun (_ : unit) => exists n, f n = true) (x := tt); auto. + exists (fun n _ => f n); tauto. + exists (fun n _ => false). intros _; split. * intros; exfalso; apply Hf; auto. * intros (_ & ?); discriminate. + destruct Hf; auto. Qed.
imports: List Arith Bool Lia Eqdep_dec Undecidability.Synthetic.Definitions Undecidability.Synthetic.ReducibilityFacts Undecidability.Synthetic.InformativeDefinitions Undecidability.Synthetic.InformativeReducibilityFacts 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 decidable)