helm/software/matita/library/demo/natural_deduction.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 definition cast ≝ λA:CProp.λa:A.a.
  16
  17 notation < "\infrule (t\atop ⋮) a ?" with precedence 19 for @{ 'cast $a $t }.
  18 interpretation "cast" 'cast a t = (cast a t).
  19
  20 definition assumpt ≝ λA:CProp.λa:A.a.
  21
  22 notation < "[ a ] \sup H" with precedence 19 for @{ 'ass $a $H }.
  23 interpretation "assumption" 'ass a H = (cast _ (assumpt a H)).
  24
  25 inductive Imply (A,B:CProp) : CProp ≝
  26  Imply_intro: (A → B) → Imply A B.
  27
  28 notation "hbox(a break ⇒ b)" right associative with precedence 20 for @{ 'Imply $a $b }.
  29 interpretation "Imply" 'Imply a b = (Imply a b).
  30
  31 notation < "\infrule hbox(\emsp b \emsp) ab (⇒\sub\i \emsp ident H) " with precedence 19 for @{ 'Imply_intro $ab (λ${ident H}:$p.$b) }.
  32 interpretation "Imply_intro" 'Imply_intro ab \eta.b = (cast ab (Imply_intro _ _ b)).
  33
  34 definition Imply_elim ≝ λA,B.λf:Imply A B.λa:A.match f with [ Imply_intro g ⇒ g a].
  35
  36 notation < "\infrule hbox(\emsp ab \emsp\emsp\emsp a\emsp) b (⇒\sub\e) " with precedence 19 for @{ 'Imply_elim $ab $a $b }.
  37 interpretation "Imply_elim" 'Imply_elim ab a b = (cast b (Imply_elim _ _ ab a)).
  38
  39 inductive And (A,B:CProp) : CProp ≝
  40  And_intro: A → B → And A B.
  41
  42 interpretation "constructive and" 'and x y = (And x y).
  43
  44 notation < "\infrule hbox(\emsp a \emsp\emsp\emsp b \emsp) ab (∧\sub\i)" with precedence 19 for @{ 'And_intro $a $b $ab }.
  45 interpretation "And_intro" 'And_intro a b ab = (cast ab (And_intro _ _ a b)).
  46
  47 definition And_elim_l ≝
  48  λA,B.λc:A∧B.match c with [ And_intro a b ⇒ a ].
  49
  50 notation < "\infrule hbox(\emsp ab \emsp) a (∧\sub\e\sup\l)" with precedence 19 for @{ 'And_elim_l $ab $a }.
  51 interpretation "And_elim_l" 'And_elim_l ab a = (cast a (And_elim_l _ _ ab)).
  52
  53 definition And_elim_r ≝
  54  λA,B.λc:A∧B.match c with [ And_intro a b ⇒ b ].
  55
  56 notation < "\infrule hbox(\emsp ab \emsp) b (∧\sub\e\sup\r)" with precedence 19 for @{ 'And_elim_r $ab $b }.
  57 interpretation "And_elim_r" 'And_elim_r ab b = (cast b (And_elim_r _ _ ab)).
  58
  59 inductive Or (A,B:CProp) : CProp ≝
  60  | Or_intro_l: A → Or A B
  61  | Or_intro_r: B → Or A B.
  62
  63 interpretation "constructive or" 'or x y = (Or x y).
  64
  65 notation < "\infrule hbox(\emsp a \emsp) ab (∨\sub\i\sup\l)" with precedence 19 for @{ 'Or_intro_l $a $ab }.
  66 interpretation "Or_intro_l" 'Or_intro_l a ab = (cast ab (Or_intro_l _ _ a)).
  67
  68 notation < "\infrule hbox(\emsp b \emsp) ab (∨\sub\i\sup\l)" with precedence 19 for @{ 'Or_intro_r $b $ab }.
  69 interpretation "Or_intro_l" 'Or_intro_r b ab = (cast ab (Or_intro_r _ _ b)).
  70
  71 definition Or_elim ≝
  72  λA,B,C:CProp.λc:A∨B.λfa: A → C.λfb: B → C.
  73   match c with [ Or_intro_l a ⇒ fa a | Or_intro_r b ⇒ fb b].
  74
  75 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
  76 for @{ 'Or_elim $ab (λ${ident Ha}:$ta.$ac) (λ${ident Hb}:$tb.$bc) $c }.
  77 interpretation "Or_elim" 'Or_elim ab \eta.ac \eta.bc c = (cast c (Or_elim _ _ _ ab ac bc)).
  78
  79 inductive Exists (A:Type) (P:A→CProp) : CProp ≝
  80   Exists_intro: ∀w:A. P w → Exists A P.
  81
  82 interpretation "constructive ex" 'exists \eta.x = (Exists _ x).
  83
  84 notation < "\infrule hbox(\emsp Pn \emsp) Px (∃\sub\i)" with precedence 19
  85 for @{ 'Exists_intro $Pn $Px }.
  86 interpretation "Exists_intro" 'Exists_intro Pn Px = (cast Px (Exists_intro _ _ _ Pn)).
  87
  88 definition Exists_elim ≝
  89   λA:Type.λP:A→CProp.λC:CProp.λc:∃x:A.P x.λH:(∀x.P x → C).
  90    match c with [ Exists_intro w p ⇒ H w p ].
  91
  92 notation < "\infrule hbox(\emsp ExPx \emsp\emsp\emsp Pc \emsp) c (∃\sub\e \emsp ident n \emsp ident HPn)" with precedence 19
  93 for @{ 'Exists_elim $ExPx (λ${ident n}:$tn.λ${ident HPn}:$Pn.$Pc) $c }.
  94 interpretation "Exists_elim" 'Exists_elim ExPx Pc c = (cast c (Exists_elim _ _ _ ExPx Pc)).
  95
  96 inductive Forall (A:Type) (P:A→CProp) : CProp ≝
  97  Forall_intro: (∀n:A. P n) → Forall A P.
  98
  99 notation "\forall ident x:A.break term 19 Px" with precedence 20
 100 for @{ 'Forall (λ${ident x}:$A.$Px) }.
 101 interpretation "Forall" 'Forall \eta.Px = (Forall _ Px).
 102
 103 notation < "\infrule hbox(\emsp Px \emsp) Pn (∀\sub\i \emsp ident x)" with precedence 19
 104 for @{ 'Forall_intro (λ${ident x}:$tx.$Px) $Pn }.
 105 interpretation "Forall_intro" 'Forall_intro Px Pn = (cast Pn (Forall_intro _ _ Px)).
 106
 107 definition Forall_elim ≝
 108  λA:Type.λP:A→CProp.λn:A.λf:∀x:A.P x.match f with [ Forall_intro g ⇒ g n ].
 109
 110 notation < "\infrule hbox(\emsp Px \emsp) Pn (∀\sub\i)" with precedence 19 for @{ 'Forall_elim $Px $Pn }.
 111 interpretation "Forall_elim" 'Forall_elim Px Pn = (cast Pn (Forall_elim _ _ _ Px)).
 112
 113 axiom A: CProp.
 114 axiom B: CProp.
 115 axiom C: CProp.
 116 axiom D: CProp.
 117 axiom E: CProp.
 118
 119
 120 notation > "[H]" with precedence 90
 121 for @{ assumpt ? $H}.
 122 notation > "⇒\sub\i [ident H] term 90 b" with precedence 19
 123 for @{ Imply_intro ?? (λ${ident H}.cast $b ?) }.
 124 notation > "⇒\sub\e term 90 ab term 90 a" with precedence 19
 125 for @{ Imply_elim ?? (cast $ab ?) (cast $a ?) }.
 126 notation > "∧\sub\i term 90 a term 90 b" with precedence 19
 127 for @{ And_intro ?? (cast $a ?) (cast $b ?) }.
 128 notation > "∧\sub\e\sup\l term 90 ab" with precedence 19
 129 for @{ And_elim_l ?? (cast $ab ?) }.
 130 notation > "∧\sub\e\sup\r term 90 ab" with precedence 19
 131 for @{ And_elim_r ?? (cast $ab ?) }.
 132 notation > "∨\sub\i\sup\l term 90 a" with precedence 19
 133 for @{ Or_intro_l ?? (cast $a ?) }.
 134 notation > "∨\sub\i\sup\r term 90 a" with precedence 19
 135 for @{ Or_intro_r ?? (cast $a ?) }.
 136 notation > "∨\sub\e term 90 ab [ident Ha] term 90 c1 [ident Hb] term 90 c2" with precedence 19
 137 for @{ Or_elim ??? (cast $ab ?) (λ${ident Ha}.cast $c1 ?) (λ${ident Hb}.cast $c2 ?) }.
 138 notation > "∀\sub\i [ident z] term 90 a" with precedence 19
 139 for @{ Forall_intro ?? (λ${ident z}.cast $a ?) }.
 140 notation > "∀\sub\e term 90 ab" with precedence 19
 141 for @{ Forall_elim ?? ? (cast $ab ?) }.
 142 notation > "∃\sub\e term 90 enpn [ident z] [ident pz] term 90 c" with precedence 19
 143 for @{ Exists_elim ??? (cast $enpn ?) (λ${ident z}.λ${ident pz}.cast $c ?) }.
 144 notation > "∃\sub\i term 90 n term 90 pn" with precedence 19
 145 for @{ Exists_intro ? (λ_.?) $n (cast $pn ?) }.
 146
 147 lemma ex1 : (A ⇒ E) ∨ B ⇒ A ∧ C ⇒ (E ∧ C) ∨ B.
 148  apply cast;
 149  apply (⇒\sub\i [H] (A∧C⇒E∧C∨B));
 150  apply (⇒\sub\i [K] (E∧C∨B));
 151  apply (∨\sub\e ((A⇒E)∨B) [C1] (E∧C∨B) [C2] (E∧C∨B));
 152 [ apply [H];
 153 | apply (∨\sub\i\sup\l (E∧C));
 154   apply (∧\sub\i E C);
 155   [ apply (⇒\sub\e (A⇒E) A);
 156     [ apply [C1];
 157     | apply (∧\sub\e\sup\l (A∧C));
 158       apply [K];
 159     ]
 160   | apply (∧\sub\e\sup\r (A∧C));
 161     apply [K];
 162   ]
 163 | apply (∨\sub\i\sup\r B);
 164   apply [C2];
 165 ]
 166 qed.
 167
 168 axiom N: Type.
 169 axiom R: N → N → CProp.
 170
 171 lemma ex2: (∀a:N.∀b:N.R a b ⇒ R b a) ⇒ ∀z:N.(∃x.R x z) ⇒ ∃y. R z y.
 172  apply cast;
 173  apply (⇒\sub\i [H] (∀z:N.(∃x:N.R x z)⇒∃y:N.R z y));
 174  apply (∀\sub\i [z] ((∃x:N.R x z)⇒∃y:N.R z y));
 175  apply (⇒\sub\i [H2] (∃y:N.R z y));
 176  apply (∃\sub\e (∃x:N.R x z) [n] [H3] (∃y:N.R z y));
 177   [ apply [H2]
 178   | apply (∃\sub\i n (R z n));
 179     apply (⇒\sub\e (R n z ⇒ R z n) (R n z));
 180      [ apply (∀\sub\e (∀b:N.R n b ⇒ R b n));
 181        apply (∀\sub\e (∀a:N.∀b:N.R a b ⇒ R b a));
 182        apply [H]
 183      | apply [H3]
 184      ]
 185   ]
 186 qed.