aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorGravatar Hugo Herbelin <Hugo.Herbelin@inria.fr>2016-10-06 07:02:24 +0200
committerGravatar Hugo Herbelin <Hugo.Herbelin@inria.fr>2017-03-03 14:40:31 +0100
commit7497d4129775d15cdce862a0ac681c6400aabe54 (patch)
tree534649a6dca0cea29028e657c4cbe55838f9fac6
parenta0bd33bdb81271025494d3f7ac7ae20bd6671579 (diff)
Logic library: Adding a characterization of excluded-middle in term of
choice of a representative in a partition of bool. Also move a result about propositional extensionality from ClassicalFacts.v to PropExtensionalityFacts.v, generalizing it by symmetry. Also spotting typos (thanks to Théo).
-rw-r--r--doc/stdlib/index-list.html.template1
-rw-r--r--theories/Logic/ClassicalFacts.v66
-rw-r--r--theories/Logic/PropExtensionalityFacts.v109
3 files changed, 173 insertions, 3 deletions
diff --git a/doc/stdlib/index-list.html.template b/doc/stdlib/index-list.html.template
index 9216c81fc..4a685a3b8 100644
--- a/doc/stdlib/index-list.html.template
+++ b/doc/stdlib/index-list.html.template
@@ -55,6 +55,7 @@ through the <tt>Require Import</tt> command.</p>
theories/Logic/Description.v
theories/Logic/Epsilon.v
theories/Logic/IndefiniteDescription.v
+ theories/Logic/PropExtensionalityFacts.v
theories/Logic/FunctionalExtensionality.v
theories/Logic/ExtensionalityFacts.v
theories/Logic/WeakFan.v
diff --git a/theories/Logic/ClassicalFacts.v b/theories/Logic/ClassicalFacts.v
index afd64efdf..021408a37 100644
--- a/theories/Logic/ClassicalFacts.v
+++ b/theories/Logic/ClassicalFacts.v
@@ -34,8 +34,11 @@ Table of contents:
3 3. Independence of general premises and drinker's paradox
-4. Classical logic and principle of unrestricted minimization
+4. Principles equivalent to classical logic
+4.1 Classical logic = principle of unrestricted minimization
+
+4.2 Classical logic = choice of representatives in a partition of bool
*)
(************************************************************************)
@@ -94,12 +97,14 @@ Qed.
(** A weakest form of propositional extensionality: extensionality for
provable propositions only *)
+Require Import PropExtensionalityFacts.
+
Definition provable_prop_extensionality := forall A:Prop, A -> A = True.
Lemma provable_prop_ext :
prop_extensionality -> provable_prop_extensionality.
Proof.
- intros Ext A Ha; apply Ext; split; trivial.
+ exact PropExt_imp_ProvPropExt.
Qed.
(************************************************************************)
@@ -516,7 +521,7 @@ End Weak_proof_irrelevance_CCI.
(** ** Weak excluded-middle *)
(** The weak classical logic based on [~~A \/ ~A] is referred to with
- name KC in {[ChagrovZakharyaschev97]]
+ name KC in [[ChagrovZakharyaschev97]]
[[ChagrovZakharyaschev97]] Alexander Chagrov and Michael
Zakharyaschev, "Modal Logic", Clarendon Press, 1997.
@@ -661,6 +666,8 @@ Proof.
exists x0; exact Hnot.
Qed.
+(** * Axioms equivalent to classical logic *)
+
(** ** Principle of unrestricted minimization *)
Require Import Coq.Arith.PeanoNat.
@@ -736,3 +743,56 @@ Section Example_of_undecidable_predicate_with_the_minimization_property.
Qed.
End Example_of_undecidable_predicate_with_the_minimization_property.
+
+(** ** Choice of representatives in a partition of bool *)
+
+(** This is similar to Bell's "weak extensional selection principle" in [[Bell]]
+
+ [[Bell]] John L. Bell, Choice principles in intuitionistic set theory, unpublished.
+*)
+
+Require Import RelationClasses.
+
+Local Notation representative_boolean_partition :=
+ (forall R:bool->bool->Prop,
+ Equivalence R -> exists f, forall x, R x (f x) /\ forall y, R x y -> f x = f y).
+
+Theorem representative_boolean_partition_imp_excluded_middle :
+ representative_boolean_partition -> excluded_middle.
+Proof.
+ intros ReprFunChoice P.
+ pose (R (b1 b2 : bool) := b1 = b2 \/ P).
+ assert (Equivalence R).
+ { split.
+ - now left.
+ - destruct 1. now left. now right.
+ - destruct 1, 1; try now right. left; now transitivity y. }
+ destruct (ReprFunChoice R H) as (f,Hf). clear H.
+ destruct (Bool.bool_dec (f true) (f false)) as [Heq|Hneq].
+ + left.
+ destruct (Hf false) as ([Hfalse|HP],_); try easy.
+ destruct (Hf true) as ([Htrue|HP],_); try easy.
+ congruence.
+ + right. intro HP.
+ destruct (Hf true) as (_,H). apply Hneq, H. now right.
+Qed.
+
+Theorem excluded_middle_imp_representative_boolean_partition :
+ excluded_middle -> representative_boolean_partition.
+Proof.
+ intros EM R H.
+ destruct (EM (R true false)).
+ - exists (fun _ => true).
+ intros []; firstorder.
+ - exists (fun b => b).
+ intro b. split.
+ + reflexivity.
+ + destruct b, y; intros HR; easy || now symmetry in HR.
+Qed.
+
+Theorem excluded_middle_iff_representative_boolean_partition :
+ excluded_middle <-> representative_boolean_partition.
+Proof.
+ split; auto using excluded_middle_imp_representative_boolean_partition,
+ representative_boolean_partition_imp_excluded_middle.
+Qed.
diff --git a/theories/Logic/PropExtensionalityFacts.v b/theories/Logic/PropExtensionalityFacts.v
new file mode 100644
index 000000000..7e455dfa1
--- /dev/null
+++ b/theories/Logic/PropExtensionalityFacts.v
@@ -0,0 +1,109 @@
+(************************************************************************)
+(* v * The Coq Proof Assistant / The Coq Development Team *)
+(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2016 *)
+(* \VV/ **************************************************************)
+(* // * This file is distributed under the terms of the *)
+(* * GNU Lesser General Public License Version 2.1 *)
+(************************************************************************)
+
+(** Some facts and definitions about propositional and predicate extensionality
+
+We investigate the relations between the following extensionality principles
+
+- Proposition extensionality
+- Predicate extensionality
+- Propositional functional extensionality
+- Provable-proposition extensionality
+- Refutable-proposition extensionality
+- Extensional proposition representatives
+- Extensional predicate representatives
+- Extensional propositional function representatives
+
+Table of contents
+
+1. Definitions
+
+2.1 Predicate extensionality <-> Proposition extensionality + Propositional functional extensionality
+
+2.2 Propositional extensionality -> Provable propositional extensionality
+
+2.3 Propositional extensionality -> Refutable propositional extensionality
+
+*)
+
+Set Implicit Arguments.
+
+(**********************************************************************)
+(** * Definitions *)
+
+(** Propositional extensionality *)
+
+Local Notation PropositionalExtensionality :=
+ (forall A B : Prop, (A <-> B) -> A = B).
+
+(** Provable-proposition extensionality *)
+
+Local Notation ProvablePropositionExtensionality :=
+ (forall A:Prop, A -> A = True).
+
+(** Refutable-proposition extensionality *)
+
+Local Notation RefutablePropositionExtensionality :=
+ (forall A:Prop, ~A -> A = False).
+
+(** Predicate extensionality *)
+
+Local Notation PredicateExtensionality :=
+ (forall (A:Type) (P Q : A -> Prop), (forall x, P x <-> Q x) -> P = Q).
+
+(** Propositional functional extensionality *)
+
+Local Notation PropositionalFunctionalExtensionality :=
+ (forall (A:Type) (P Q : A -> Prop), (forall x, P x = Q x) -> P = Q).
+
+(**********************************************************************)
+(** * Propositional and predicate extensionality *)
+
+(**********************************************************************)
+(** ** Predicate extensionality <-> Propositional extensionality + Propositional functional extensionality *)
+
+Lemma PredExt_imp_PropExt : PredicateExtensionality -> PropositionalExtensionality.
+Proof.
+ intros Ext A B Equiv.
+ change A with ((fun _ => A) I).
+ now rewrite Ext with (P := fun _ : True =>A) (Q := fun _ => B).
+Qed.
+
+Lemma PredExt_imp_PropFunExt : PredicateExtensionality -> PropositionalFunctionalExtensionality.
+Proof.
+ intros Ext A P Q Eq. apply Ext. intros x. now rewrite (Eq x).
+Qed.
+
+Lemma PropExt_and_PropFunExt_imp_PredExt :
+ PropositionalExtensionality -> PropositionalFunctionalExtensionality -> PredicateExtensionality.
+Proof.
+ intros Ext FunExt A P Q Equiv.
+ apply FunExt. intros x. now apply Ext.
+Qed.
+
+Theorem PropExt_and_PropFunExt_iff_PredExt :
+ PropositionalExtensionality /\ PropositionalFunctionalExtensionality <-> PredicateExtensionality.
+Proof.
+ firstorder using PredExt_imp_PropExt, PredExt_imp_PropFunExt, PropExt_and_PropFunExt_imp_PredExt.
+Qed.
+
+(**********************************************************************)
+(** ** Propositional extensionality and provable proposition extensionality *)
+
+Lemma PropExt_imp_ProvPropExt : PropositionalExtensionality -> ProvablePropositionExtensionality.
+Proof.
+ intros Ext A Ha; apply Ext; split; trivial.
+Qed.
+
+(**********************************************************************)
+(** ** Propositional extensionality and refutable proposition extensionality *)
+
+Lemma PropExt_imp_RefutPropExt : PropositionalExtensionality -> RefutablePropositionExtensionality.
+Proof.
+ intros Ext A Ha; apply Ext; split; easy.
+Qed.