Imported Upstream version 8.2~beta3+dfsgupstream/8.2.beta3+dfsg

1 files changed, 39 insertions, 0 deletions

diff --git a/theories/Logic/IndefiniteDescription.v b/theories/Logic/IndefiniteDescription.v
new file mode 100644
index 00000000..740b889a
--- /dev/null
+++ b/theories/Logic/IndefiniteDescription.v
@@ -0,0 +1,39 @@
+(************************************************************************)
+(*  v      *   The Coq Proof Assistant  /  The Coq Development Team     *)
+(* <O___,, * CNRS-Ecole Polytechnique-INRIA Futurs-Universite Paris Sud *)
+(*   \VV/  **************************************************************)
+(*    //   *      This file is distributed under the terms of the       *)
+(*         *       GNU Lesser General Public License Version 2.1        *)
+(************************************************************************)
+
+(*i $Id: IndefiniteDescription.v 10170 2007-10-03 14:41:25Z herbelin $ i*)
+
+(** This file provides a constructive form of indefinite description that
+    allows to build choice functions; this is weaker than Hilbert's
+    epsilon operator (which implies weakly classical properties) but
+    stronger than the axiom of choice (which cannot be used outside
+    the context of a theorem proof). *)
+
+Require Import ChoiceFacts.
+
+Set Implicit Arguments.
+
+Axiom constructive_indefinite_description :
+  forall (A : Type) (P : A->Prop), 
+    (exists x, P x) -> { x : A | P x }.
+
+Lemma constructive_definite_description :
+  forall (A : Type) (P : A->Prop), 
+    (exists! x, P x) -> { x : A | P x }.
+Proof.
+  intros; apply constructive_indefinite_description; firstorder.
+Qed.
+
+Lemma functional_choice :
+  forall (A B : Type) (R:A->B->Prop),
+    (forall x : A, exists y : B, R x y) ->
+    (exists f : A->B, forall x : A, R x (f x)).
+Proof.
+  apply constructive_indefinite_descr_fun_choice.
+  exact constructive_indefinite_description.
+Qed.