diff options
Diffstat (limited to 'theories/Logic/Decidable.v')
| -rw-r--r-- | theories/Logic/Decidable.v | 11 |
1 files changed, 10 insertions, 1 deletions
diff --git a/theories/Logic/Decidable.v b/theories/Logic/Decidable.v index 3724d8e2..545f92bd 100644 --- a/theories/Logic/Decidable.v +++ b/theories/Logic/Decidable.v @@ -1,6 +1,6 @@ (************************************************************************) (* v * The Coq Proof Assistant / The Coq Development Team *) -(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2014 *) +(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2015 *) (* \VV/ **************************************************************) (* // * This file is distributed under the terms of the *) (* * GNU Lesser General Public License Version 2.1 *) @@ -175,7 +175,16 @@ Proof. unfold decidable. tauto. Qed. +(* Functional relations on decidable co-domains are decidable *) +Theorem dec_functional_relation : + forall (X Y : Type) (A:X->Y->Prop), (forall y y' : Y, decidable (y=y')) -> + (forall x, exists! y, A x y) -> forall x y, decidable (A x y). +Proof. +intros X Y A Hdec H x y. +destruct (H x) as (y',(Hex,Huniq)). +destruct (Hdec y y') as [->|Hnot]; firstorder. +Qed. (** With the following hint database, we can leverage [auto] to check decidability of propositions. *) |