proposition: Fact ireduction_decidable X Y (p : X -> Prop) (q : Y -> Prop) : p ⪯ᵢ q -> (forall y, decidable (q y)) -> forall x, decidable (p x).
proof: Proof. unfold decidable, decider, inf_reduces, reduction. intros (f & Hf) Hq x. destruct (Hq (f x)); [ left | right ]; rewrite Hf; auto. Qed.
imports: List Arith Bool 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)