proposition: Fact opt_enum_t_dep_sum X (f : X -> Type) (P : forall x, f x -> Prop) : discrete X -> type_enum_t X -> (forall x, opt_enum_t (P x)) -> opt_enum_t (fun p : sigT f => P _ (projT2 p)).
proof: Proof. intros D (g & Hg) H. apply constructive_choice in H; destruct H as (h & Hh). exists (fun n : nat => match surj n with (a,b) => match g a with | Some x => match h x b with | Some y => Some (existT _ x y) | None => None end | None => None end end). intros (x & y); simpl; rewrite Hh; split. + intros (b & Hb). destruct (Hg x) as (a & Ha). destruct (Hsurj a b) as (n & Hn). exists n; rewrite Hn, <- Ha, <- Hb; auto. + intros (n & Hn); revert Hn. destruct (surj n) as (a,b). case_eq (g a); try discriminate; intros x' Hx'. case_eq (h x' b); try discriminate; intros y' Hy'. inversion 1; subst x'; exists b; rewrite Hy'. apply inj_pair2_eq_dec in H1; subst; 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)