proposition: Fact rec_enum_opt_enum_type_enum P : rec_enum P -> opt_enum P.
proof: Proof. Proof using Xenum. destruct Xenum as (s & Hs). intros (Q & HQ). set (f n := let (a,b) := surj n in match s a with | Some x => if Q b x then Some x else None | None => None end). exists f; intros x; rewrite HQ; split; unfold f. + intros (n & Hn). destruct (Hs x) as (a & Ha). destruct (Hsurj a n) as (m & Hm). exists m; rewrite Hm, <- Ha, Hn; auto. + intros (n & Hn). destruct (surj n) as (a,b). destruct (s a) as [ y | ]; try discriminate. revert Hn; case_eq (Q b y). * inversion 2; exists b; auto. * discriminate. 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)