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 < "[ a ] \sup H" with precedence 19 for @{ 'ass $a $H }.
  18 interpretation "assumption" 'ass a H = (cast a H).
  19
  20 inductive Imply (A,B:CProp) : CProp ≝
  21  Imply_intro: (A → B) → Imply A B.
  22
  23 notation "hbox(a break ⇒ b)" right associative with precedence 20 for @{ 'Imply $a $b }.
  24 interpretation "Imply" 'Imply a b = (Imply a b).
  25
  26 notation < "\infrule hbox(\emsp b \emsp) ab (⇒\sub\i) " with precedence 19 for @{ 'Imply_intro $ab (λ${ident H}:$p.$b) }.
  27 interpretation "Imply_intro" 'Imply_intro ab \eta.b = (cast ab (Imply_intro _ _ b)).
  28
  29 definition Imply_elim ≝ λA,B.λf:Imply A B.λa:A.match f with [ Imply_intro g ⇒ g a].
  30
  31 notation < "\infrule hbox(\emsp ab \emsp\emsp\emsp a\emsp) b (⇒\sub\e) " with precedence 19 for @{ 'Imply_elim $ab $a $b }.
  32 interpretation "Imply_elim" 'Imply_elim ab a b = (cast b (Imply_elim _ _ ab a)).
  33
  34 inductive And (A,B:CProp) : CProp ≝
  35  And_intro: A → B → And A B.
  36
  37 interpretation "constructive and" 'and x y = (And x y).
  38
  39 notation < "\infrule hbox(\emsp a \emsp\emsp\emsp b \emsp) ab (∧\sub\i)" with precedence 19 for @{ 'And_intro $a $b $ab }.
  40 interpretation "And_intro" 'And_intro a b ab = (cast ab (And_intro _ _ a b)).
  41
  42 definition And_elim_l ≝
  43  λA,B.λc:A∧B.match c with [ And_intro a b ⇒ a ].
  44
  45 notation < "\infrule hbox(\emsp ab \emsp) a (∧\sub\e\sup\l)" with precedence 19 for @{ 'And_elim_l $ab $a }.
  46 interpretation "And_elim_l" 'And_elim_l ab a = (cast a (And_elim_l _ _ ab)).
  47
  48 definition And_elim_r ≝
  49  λA,B.λc:A∧B.match c with [ And_intro a b ⇒ b ].
  50
  51 notation < "\infrule hbox(\emsp ab \emsp) b (∧\sub\e\sup\r)" with precedence 19 for @{ 'And_elim_r $ab $b }.
  52 interpretation "And_elim_r" 'And_elim_r ab b = (cast b (And_elim_r _ _ ab)).
  53
  54 inductive Or (A,B:CProp) : CProp ≝
  55  | Or_intro_l: A → Or A B
  56  | Or_intro_r: B → Or A B.
  57
  58 interpretation "constructive or" 'or x y = (Or x y).
  59
  60 notation < "\infrule hbox(\emsp a \emsp) ab (∨\sub\i\sup\l)" with precedence 19 for @{ 'Or_intro_l $a $ab }.
  61 interpretation "Or_intro_l" 'Or_intro_l a ab = (cast ab (Or_intro_l _ _ a)).
  62
  63 notation < "\infrule hbox(\emsp b \emsp) ab (∨\sub\i\sup\l)" with precedence 19 for @{ 'Or_intro_r $b $ab }.
  64 interpretation "Or_intro_l" 'Or_intro_r b ab = (cast ab (Or_intro_r _ _ b)).
  65
  66 definition Or_elim ≝
  67  λA,B,C:CProp.λc:A∨B.λfa: A → C.λfb: B → C.
  68   match c with [ Or_intro_l a ⇒ fa a | Or_intro_r b ⇒ fb b].
  69
  70 notation < "\infrule hbox(\emsp ab \emsp\emsp\emsp ac \emsp\emsp\emsp bc \emsp) c (∨\sub\e)" with precedence 19 for @{ 'Or_elim $ab (λ${ident Ha}:$ta.$ac) (λ${ident Hb}:$tb.$bc) $c }.
  71 interpretation "Or_elim" 'Or_elim ab ac bc c = (cast c (Or_elim _ _ _ ab ac bc)).
  72
  73 inductive Exists (A:Type) (P:A→CProp) : CProp ≝
  74   Exists_intro: ∀w:A. P w → Exists A P.
  75
  76 interpretation "constructive ex" 'exists \eta.x = (Exists _ x).
  77
  78 notation < "\infrule hbox(\emsp Pn \emsp) Px (∃\sub\i)" with precedence 19 for @{ 'Exists_intro $Pn $Px }.
  79 interpretation "Exists_intro" 'Exists_intro Pn Px = (cast Px (Exists_intro _ _ _ Pn)).
  80
  81 definition Exists_elim ≝
  82   λA:Type.λP:A→CProp.λC:CProp.λc:∃x:A.P x.λH:(∀x.P x → C).
  83    match c with [ Exists_intro w p ⇒ H w p ].
  84
  85 notation < "\infrule hbox(\emsp ExPx \emsp\emsp\emsp Pc \emsp) c (∃\sub\e)" with precedence 19 for @{ 'Exists_elim $ExPx (λ${ident n}:$tn.λ${ident HPn}:$Pn.$Pc) $c }.
  86 interpretation "Exists_elim" 'Exists_elim ExPx Pc c = (cast c (Exists_elim _ _ _ ExPx Pc)).
  87
  88 inductive Forall (A:Type) (P:A→CProp) : CProp ≝
  89  Forall_intro: (∀n:A. P n) → Forall A P.
  90
  91 notation "\forall ident x:A.break term 19 Px" with precedence 20 for @{ 'Forall (λ${ident x}:$A.$Px) }.
  92 interpretation "Forall" 'Forall \eta.Px = (Forall _ Px).
  93
  94 notation < "\infrule hbox(\emsp Px \emsp) Pn (∀\sub\i)" with precedence 19 for @{ 'Forall_intro (λ${ident x}:$tx.$Px) $Pn }.
  95 interpretation "Forall_intro" 'Forall_intro Px Pn = (cast Pn (Forall_intro _ _ Px)).
  96
  97 definition Forall_elim ≝
  98  λA:Type.λP:A→CProp.λn:A.λf:∀x:A.P x.match f with [ Forall_intro g ⇒ g n ].
  99
 100 notation < "\infrule hbox(\emsp Px \emsp) Pn (∀\sub\i)" with precedence 19 for @{ 'Forall_elim $Px $Pn }.
 101 interpretation "Forall_elim" 'Forall_elim Px Pn = (cast Pn (Forall_elim _ _ _ Px)).
 102
 103 axiom A: CProp.
 104 axiom B: CProp.
 105 axiom C: CProp.
 106 axiom D: CProp.
 107 axiom E: CProp.
 108
 109 lemma ex1 : (A ⇒ E) ∨ B ⇒ A ∧ C ⇒ (E ∧ C) ∨ B.
 110 repeat (apply cast; constructor 1; intro);
 111 apply cast; apply (Or_elim (A ⇒ E) B (E∧C∨B)); try intro;
 112 [ apply cast; assumption
 113 | apply cast; apply Or_intro_l;
 114   apply cast; constructor 1;
 115   [ apply cast; apply (Imply_elim A E);
 116     [ apply cast; assumption
 117     | apply cast; apply (And_elim_l A C);
 118       apply cast; assumption
 119     ]
 120   | apply cast; apply (And_elim_r A C);
 121     apply cast; assumption
 122   ]
 123 | apply cast; apply Or_intro_r;
 124   apply cast; assumption
 125 ]
 126 qed.
 127
 128 axiom N: Type.
 129 axiom R: N → N → CProp.
 130
 131 lemma ex2: (∀a:N.∀b:N.R a b ⇒ R b a) ⇒ ∀z:N.(∃x.R x z) ⇒ ∃y. R z y.
 132  apply cast; apply Imply_intro; intro;
 133  apply cast; apply Forall_intro; intro z;
 134  apply cast; apply Imply_intro; intro;
 135  apply cast; apply (Exists_elim N (λy.R y z)); try intros (n);
 136   [ apply cast; assumption
 137   | apply cast; apply (Exists_intro ? ? n);
 138     apply cast; apply (Imply_elim (R n z) (R z n));
 139      [ apply cast; apply (Forall_elim N (λb:N.R n b ⇒ R b n) z);
 140        apply cast; apply (Forall_elim N (λa:N.∀b:N.R a b ⇒ R b a) n);
 141        apply cast; assumption
 142      | apply cast; assumption
 143      ]
 144   ]
 145 qed.