proposition: Fact opt_enum_t_prod X Y (P : X -> Prop) (Q : Y -> Prop) : opt_enum_t P -> opt_enum_t Q -> opt_enum_t (fun c => P (fst c) /\ Q (snd c)).
proof: Proof. intros (f & Hf) (g & Hg). exists (fun n => let (a,b) := surj n in match f a, g b with | Some x, Some y => Some (x,y) | _ , _ => None end). intros (x,y); simpl; rewrite Hf, Hg; split. + intros ((a & Ha) & (b & Hb)). destruct (Hsurj a b) as (n & Hn). exists n; rewrite Hn, <- Ha, <- Hb; auto. + intros (n & Hn). destruct (surj n) as (a,b). revert Hn. case_eq (f a); try discriminate; intros u Hu. case_eq (g b); try discriminate; intros v Hv. inversion 1; split; [ exists a | exists b ]; 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)