Advertisement
elvecent

Excluded middle equivalents

Aug 30th, 2017
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.53 KB | None | 0 0
  1. Definition peirce := forall P Q: Prop,
  2. ((P->Q)->P)->P.
  3.  
  4. Definition double_negation_elimination := forall P:Prop,
  5. ~~P -> P.
  6.  
  7. Definition de_morgan_not_and_not := forall P Q:Prop,
  8. ~(~P /\ ~Q) -> P\/Q.
  9.  
  10. Definition implies_to_or := forall P Q:Prop,
  11. (P->Q) -> (~P\/Q).
  12.  
  13. Theorem em_peirce : excluded_middle → peirce.
  14. Proof.
  15. unfold peirce. intros.
  16. destruct (H P).
  17. - assumption.
  18. - apply H0. intros. exfalso. apply H1. assumption.
  19. Qed.
  20.  
  21. Theorem em_imp : excluded_middle -> implies_to_or.
  22. Proof.
  23. intros. unfold implies_to_or.
  24. intros. destruct (H P).
  25. - right. apply H0. assumption.
  26. - left. assumption.
  27. Qed.
  28.  
  29. Theorem dm_em : de_morgan_not_and_not -> excluded_middle.
  30. Proof.
  31. unfold de_morgan_not_and_not. unfold excluded_middle.
  32. intros. apply H. intros [Hnp Hnnp].
  33. apply Hnnp. assumption.
  34. Qed.
  35.  
  36. Theorem dm_peirce : de_morgan_not_and_not -> peirce.
  37. Proof.
  38. intros.
  39. apply em_peirce. apply dm_em.
  40. assumption.
  41. Qed.
  42.  
  43. Theorem dm_imp : de_morgan_not_and_not -> implies_to_or.
  44. Proof.
  45. intros.
  46. apply em_imp. apply dm_em.
  47. assumption.
  48. Qed.
  49.  
  50. Lemma and_p_p : ∀ P: Prop, P /\ P <-> P.
  51. Proof.
  52. intros. split; intros.
  53. - destruct H; assumption.
  54. - split; assumption.
  55. Qed.
  56.  
  57. Theorem dm_dne : de_morgan_not_and_not -> double_negation_elimination.
  58. Proof.
  59. unfold de_morgan_not_and_not. unfold double_negation_elimination.
  60. intros. assert (P \/ P).
  61. {
  62. apply H. rewrite and_p_p. assumption.
  63. }
  64. destruct H1; assumption.
  65. Qed.
  66.  
  67. Theorem em_dm : excluded_middle -> de_morgan_not_and_not.
  68. Proof.
  69. unfold excluded_middle. unfold de_morgan_not_and_not.
  70. intros. destruct (H P); destruct (H Q).
  71. - left. assumption.
  72. - left. assumption.
  73. - right. assumption.
  74. - assert (¬P /\ ¬Q).
  75. {
  76. split; assumption.
  77. }
  78. exfalso. apply H0. assumption.
  79. Qed.
  80.  
  81. Theorem dne_dm : double_negation_elimination -> de_morgan_not_and_not.
  82. Proof.
  83. unfold double_negation_elimination. unfold de_morgan_not_and_not.
  84. intros. apply (H (P \/ Q)). intros contra.
  85. apply H0. split.
  86. - intros contra'. apply contra.
  87. left. assumption.
  88. - intros contra'. apply contra.
  89. right. assumption.
  90. Qed.
  91.  
  92. Theorem imp_em : implies_to_or -> excluded_middle.
  93. Proof.
  94. unfold implies_to_or. unfold excluded_middle.
  95. intros. apply or_commut.
  96. apply H. intros. assumption.
  97. Qed.
  98.  
  99. Theorem peirce_em : peirce -> excluded_middle.
  100. Proof.
  101. unfold peirce. unfold excluded_middle.
  102. intros. apply (H (P \/ ¬P) (¬P)).
  103. intros. right. intros contra.
  104. apply H0. left. assumption. assumption.
  105. Qed.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement