helm/software/matita/library/demo/natural_deduction_support.ma

   1 (**************************************************************************)
   2 (*       ___                                                              *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||         The HELM team.                                      *)
   8 (*      ||A||         http://helm.cs.unibo.it                             *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU General Public License Version 2                  *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 axiom cast: ∀A,B:CProp.B → A.
  16
  17 notation > "'prove' p" non associative with precedence 19 for @{ cast ? $p}.
  18
  19 notation < "\infrule (t\atop ⋮) mstyle color #ff0000 (b) (? \ERROR)" with precedence 19
  20 for @{ 'caste $a $b $t }.
  21
  22 interpretation "cast ERR" 'caste a b t = (cast a b t).
  23
  24 notation < "\infrule (t\atop ⋮) a ?" with precedence 19 for @{ 'cast $a $t }.
  25
  26 interpretation "cast OK" 'cast a t = (cast a a t).
  27
  28 definition assumpt ≝ λA:CProp.λa:A.a.
  29
  30 notation < "[ a ] \sup mstyle color #ff0000 (H)" with precedence 19 for @{ 'asse $a $H }.
  31 interpretation "assumption" 'asse a H = (cast _ _ (assumpt a (cast _ _ H))).
  32
  33 notation < "[ a ] \sup H" with precedence 19 for @{ 'ass $a $H }.
  34 interpretation "assumption" 'ass a H = (cast a a  (assumpt a (cast a a H))).
  35
  36 inductive Imply (A,B:CProp) : CProp ≝
  37  Imply_intro: (A → B) → Imply A B.
  38
  39 notation "hbox(a break ⇒ b)" right associative with precedence 20 for @{ 'Imply $a $b }.
  40 interpretation "Imply" 'Imply a b = (Imply a b).
  41
  42 notation < "\infrule hbox(\emsp b \emsp) mstyle color #ff0000(ab) (⇒\sub\i \emsp ident H \ERROR) " with precedence 19
  43 for @{ 'Imply_introe $xxx $ab (λ${ident H}:$p.$b) }.
  44 interpretation "Imply_intro" 'Imply_introe xxx ab \eta.b = (cast xxx ab (Imply_intro _ _ b)).
  45
  46 notation < "\infrule hbox(\emsp b \emsp) ab (⇒\sub\i \emsp ident H) " with precedence 19
  47 for @{ 'Imply_intro $ab (λ${ident H}:$p.$b) }.
  48 interpretation "Imply_intro" 'Imply_intro ab \eta.b = (cast ab ab (Imply_intro _ _ b)).
  49
  50 definition Imply_elim ≝ λA,B.λf:Imply A B.λa:A.match f with [ Imply_intro g ⇒ g a].
  51
  52 notation < "\infrule hbox(\emsp ab \emsp\emsp\emsp a\emsp) b (⇒\sub\e) " with precedence 19 for @{ 'Imply_elim $ab $a $b }.
  53 interpretation "Imply_elim" 'Imply_elim ab a b = (cast _ b (Imply_elim _ _ ab a)).
  54
  55 inductive And (A,B:CProp) : CProp ≝
  56  And_intro: A → B → And A B.
  57
  58 interpretation "constructive and" 'and x y = (And x y).
  59
  60 notation < "\infrule hbox(\emsp a \emsp\emsp\emsp b \emsp) ab (∧\sub\i)" with precedence 19 for @{ 'And_intro $a $b $ab }.
  61 interpretation "And_intro" 'And_intro a b ab = (cast _ ab (And_intro _ _ a b)).
  62
  63 definition And_elim_l ≝
  64  λA,B.λc:A∧B.match c with [ And_intro a b ⇒ a ].
  65
  66 notation < "\infrule hbox(\emsp ab \emsp) a (∧\sub(\e_\l))" with precedence 19 for @{ 'And_elim_l $ab $a }.
  67 interpretation "And_elim_l" 'And_elim_l ab a = (cast _ a (And_elim_l _ _ ab)).
  68
  69 definition And_elim_r ≝
  70  λA,B.λc:A∧B.match c with [ And_intro a b ⇒ b ].
  71
  72 notation < "\infrule hbox(\emsp ab \emsp) b (∧\sub(\e_\r))" with precedence 19 for @{ 'And_elim_r $ab $b }.
  73 interpretation "And_elim_r" 'And_elim_r ab b = (cast _ b (And_elim_r _ _ ab)).
  74
  75 inductive Or (A,B:CProp) : CProp ≝
  76  | Or_intro_l: A → Or A B
  77  | Or_intro_r: B → Or A B.
  78
  79 interpretation "constructive or" 'or x y = (Or x y).
  80
  81 notation < "\infrule hbox(\emsp a \emsp) ab (∨\sub(\i_\l))" with precedence 19 for @{ 'Or_intro_l $a $ab }.
  82 interpretation "Or_intro_l" 'Or_intro_l a ab = (cast _ ab (Or_intro_l _ _ a)).
  83
  84 notation < "\infrule hbox(\emsp b \emsp) ab (∨\sub(\i_\r))" with precedence 19 for @{ 'Or_intro_r $b $ab }.
  85 interpretation "Or_intro_r" 'Or_intro_r b ab = (cast _ ab (Or_intro_r _ _ b)).
  86
  87 definition Or_elim ≝
  88  λA,B,C:CProp.λc:A∨B.λfa: A → C.λfb: B → C.
  89   match c with [ Or_intro_l a ⇒ fa a | Or_intro_r b ⇒ fb b].
  90
  91 notation < "\infrule hbox(\emsp ab \emsp\emsp\emsp ac \emsp\emsp\emsp bc \emsp) c (∨\sub\e \emsp ident Ha \emsp ident Hb)" with precedence 19
  92 for @{ 'Or_elim $ab (λ${ident Ha}:$ta.$ac) (λ${ident Hb}:$tb.$bc) $c }.
  93 interpretation "Or_elim" 'Or_elim ab \eta.ac \eta.bc c = (cast _ c (Or_elim _ _ _ ab ac bc)).
  94
  95 inductive Exists (A:Type) (P:A→CProp) : CProp ≝
  96   Exists_intro: ∀w:A. P w → Exists A P.
  97
  98 interpretation "constructive ex" 'exists \eta.x = (Exists _ x).
  99
 100 notation < "\infrule hbox(\emsp Pn \emsp) Px (∃\sub\i)" with precedence 19
 101 for @{ 'Exists_intro $Pn $Px }.
 102 interpretation "Exists_intro" 'Exists_intro Pn Px = (cast _ Px (Exists_intro _ _ _ Pn)).
 103
 104 definition Exists_elim ≝
 105   λA:Type.λP:A→CProp.λC:CProp.λc:∃x:A.P x.λH:(∀x.P x → C).
 106    match c with [ Exists_intro w p ⇒ H w p ].
 107
 108 notation < "\infrule hbox(\emsp ExPx \emsp\emsp\emsp Pc \emsp) c (∃\sub\e \emsp ident n \emsp ident HPn)" with precedence 19
 109 for @{ 'Exists_elim $ExPx (λ${ident n}:$tn.λ${ident HPn}:$Pn.$Pc) $c }.
 110 interpretation "Exists_elim" 'Exists_elim ExPx Pc c = (cast _ c (Exists_elim _ _ _ ExPx Pc)).
 111
 112 inductive Forall (A:Type) (P:A→CProp) : CProp ≝
 113  Forall_intro: (∀n:A. P n) → Forall A P.
 114
 115 notation "\forall ident x:A.break term 19 Px" with precedence 20
 116 for @{ 'Forall (λ${ident x}:$A.$Px) }.
 117 interpretation "Forall" 'Forall \eta.Px = (Forall _ Px).
 118
 119 notation < "\infrule hbox(\emsp Px \emsp) Pn (∀\sub\i \emsp ident x)" with precedence 19
 120 for @{ 'Forall_intro (λ${ident x}:$tx.$Px) $Pn }.
 121 interpretation "Forall_intro" 'Forall_intro Px Pn = (cast _ Pn (Forall_intro _ _ Px)).
 122
 123 definition Forall_elim ≝
 124  λA:Type.λP:A→CProp.λn:A.λf:∀x:A.P x.match f with [ Forall_intro g ⇒ g n ].
 125
 126 notation < "\infrule hbox(\emsp Px \emsp) Pn (∀\sub\i)" with precedence 19 for @{ 'Forall_elim $Px $Pn }.
 127 interpretation "Forall_elim" 'Forall_elim Px Pn = (cast _ Pn (Forall_elim _ _ _ Px)).
 128
 129 notation > "[H]" with precedence 90
 130 for @{ assumpt ? (cast ? ? $H)}.
 131 notation > "⇒_'i' [ident H] term 90 b" with precedence 19
 132 for @{ Imply_intro ?? (λ${ident H}.cast ? $b ?) }.
 133 notation > "⇒_'e' term 90 ab term 90 a" with precedence 19
 134 for @{ Imply_elim ?? (cast ? $ab ?) (cast $a $a ?) }.
 135 notation > "∧_'i' term 90 a term 90 b" with precedence 19
 136 for @{ And_intro ?? (cast ? $a ?) (cast ? $b ?) }.
 137 (*notation > "∧_'e_l' term 90 ab" with precedence 19
 138 for @{ And_elim_l ?? (cast (? ∧ False) $ab ?) }.
 139 notation > "∧_'e_l' term 90 a ∧ term 90 b" with precedence 19
 140 for @{ And_elim_l ?? (cast (? ∧ $b) ($a ∧ $b) ?) }. *)
 141 notation > "∧_'e_l' term 90 ab" with precedence 19
 142 for @{ And_elim_l ?? (cast $ab $ab ?) }. (* CSC: WRONG *)
 143 notation > "∧_'e_r' term 90 ab" with precedence 19
 144 for @{ And_elim_r ?? (cast $ab $ab ?) }. (* CSC: WRONG *)
 145 notation > "∨_'i_l' term 90 a" with precedence 19
 146 for @{ Or_intro_l ?? (cast ? $a ?) }.
 147 notation > "∨_'i_r' term 90 a" with precedence 19
 148 for @{ Or_intro_r ?? (cast ? $a ?) }.
 149 notation > "∨_'e' term 90 ab [ident Ha] term 90 c1 [ident Hb] term 90 c2" with precedence 19
 150 for @{ Or_elim ??? (cast $ab $ab ?) (λ${ident Ha}.cast ? $c1 ?) (λ${ident Hb}.cast ? $c2 ?) }.
 151 notation > "∀_'i' [ident z] term 90 a" with precedence 19
 152 for @{ Forall_intro ?? (λ${ident z}.cast ? $a ?) }.
 153 notation > "∀_'e' term 90 ab term 90 a" with precedence 19
 154 for @{ Forall_elim ?? $a (cast $ab $ab ?) }.
 155 notation > "∃_'e' term 90 enpn [ident z] [ident pz] term 90 c" with precedence 19
 156 for @{ Exists_elim ??? (cast $enpn $enpn ?) (λ${ident z}.λ${ident pz}.cast ? $c ?) }.
 157 notation > "∃_'i' term 90 n term 90 pn" with precedence 19
 158 for @{ Exists_intro ? (λ_.?) $n (cast ? $pn ?) }.