helm/software/matita/library/demo/power_derivative.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 include "nat/plus.ma".
  16 include "nat/orders.ma".
  17 include "nat/compare.ma".
  18
  19 axiom R: Type.
  20 axiom R0: R.
  21 axiom R1: R.
  22 axiom Rplus: R→R→R.
  23 axiom Rmult: R→R→R.
  24
  25 notation "0" with precedence 89
  26 for @{ 'zero }.
  27 interpretation "Rzero" 'zero = (R0).
  28 interpretation "Nzero" 'zero = (O).
  29
  30 notation "1" with precedence 89
  31 for @{ 'one }.
  32 interpretation "Rone" 'one = (R1).
  33 interpretation "None" 'one = (S O).
  34
  35 interpretation "Rplus" 'plus x y = (Rplus x y).
  36
  37 interpretation "Rmult" 'middot x y = (Rmult x y).
  38
  39 definition Fplus ≝
  40  λf,g:R→R.λx:R.f x + g x.
  41
  42 definition Fmult ≝
  43  λf,g:R→R.λx:R.f x · g x.
  44
  45 interpretation "Fplus" 'plus x y = (Fplus x y).
  46 interpretation "Fmult" 'middot x y = (Fmult x y).
  47
  48 notation "2" with precedence 89
  49 for @{ 'two }.
  50 interpretation "Rtwo" 'two = (Rplus R1 R1).
  51 interpretation "Ntwo" 'two = (S (S O)).
  52
  53 let rec Rpower (x:R) (n:nat) on n ≝
  54  match n with
  55   [ O ⇒ 1
  56   | S n ⇒ x · (Rpower x n)
  57   ].
  58
  59 interpretation "Rpower" 'exp x n = (Rpower x n).
  60
  61 let rec inj (n:nat) on n : R ≝
  62  match n with
  63   [ O ⇒ 0
  64   | S n ⇒
  65      match n with
  66       [ O ⇒ 1
  67       | S m ⇒ 1 + inj n
  68       ]
  69   ].
  70
  71 coercion inj.
  72
  73 axiom Rplus_Rzero_x: ∀x:R.0+x=x.
  74 axiom Rplus_comm: symmetric ? Rplus.
  75 axiom Rplus_assoc: associative ? Rplus.
  76 axiom Rmult_Rone_x: ∀x:R.1 · x=x.
  77 axiom Rmult_Rzero_x: ∀x:R.0 · x=0.
  78 axiom Rmult_assoc: associative ? Rmult.
  79 axiom Rmult_comm: symmetric ? Rmult.
  80 axiom Rmult_Rplus_distr: distributive ? Rmult Rplus.
  81
  82 alias symbol "middot" = "Rmult".
  83 alias symbol "plus" = "natural plus".
  84
  85 definition monomio ≝
  86  λn.λx:R.x\sup n.
  87
  88 definition costante : nat → R → R ≝
  89  λa:nat.λx:R.inj a.
  90
  91 coercion costante with 1.
  92
  93 axiom f_eq_extensional:
  94  ∀f,g:R→R.(∀x:R.f x = g x) → f=g.
  95
  96 lemma Fmult_one_f: ∀f:R→R.1·f=f.
  97  intro;
  98  unfold Fmult;
  99  simplify;
 100  apply f_eq_extensional;
 101  intro;
 102  autobatch.
 103 qed.
 104
 105 lemma Fmult_zero_f: ∀f:R→R.0·f=0.
 106  intro;
 107  unfold Fmult;
 108  simplify;
 109  apply f_eq_extensional;
 110  intro;
 111  autobatch.
 112 qed.
 113
 114 lemma Fmult_commutative: symmetric ? Fmult.
 115  unfold;
 116  intros;
 117  unfold Fmult;
 118  apply f_eq_extensional;
 119  intros;
 120  autobatch.
 121 qed.
 122
 123 lemma Fmult_associative: associative ? Fmult.
 124  unfold;
 125  intros;
 126  unfold Fmult;
 127  unfold Fmult;
 128  apply f_eq_extensional;
 129  intros;
 130  autobatch.
 131 qed.
 132
 133 lemma Fmult_Fplus_distr: distributive ? Fmult Fplus.
 134  unfold;
 135  intros;
 136  unfold Fmult;
 137  unfold Fplus;
 138  apply f_eq_extensional;
 139  intros;
 140  simplify;
 141  autobatch.
 142 qed.
 143
 144 lemma monomio_product:
 145  ∀n,m.monomio (n+m) = monomio n · monomio m.
 146  intros;
 147  unfold monomio;
 148  unfold Fmult;
 149  simplify;
 150  elim n;
 151   [ simplify;
 152     apply f_eq_extensional;
 153     intro;
 154     autobatch
 155   | simplify;
 156     apply f_eq_extensional;
 157     intro;
 158     cut (x\sup (n1+m) = x \sup n1 · x \sup m);
 159      [ rewrite > Hcut;
 160        autobatch
 161      | change in ⊢ (? ? % ?) with ((λx:R.x\sup(n1+m)) x);
 162        rewrite > H;
 163        reflexivity
 164      ]
 165   ].
 166 qed.
 167
 168 lemma costante_sum:
 169  ∀n,m.costante n + costante m = costante (n+m).
 170  intros;
 171  unfold Fplus;
 172  unfold costante;
 173  apply f_eq_extensional;
 174  intros;
 175  elim n;
 176   [ simplify;
 177     autobatch
 178   | simplify;
 179     clear x;
 180     clear H;
 181     clear n;
 182     elim n1;
 183      [ simplify;
 184        elim m;
 185         [ simplify;
 186           autobatch
 187         | simplify;
 188           rewrite < H;
 189           autobatch
 190         ]
 191      | simplify;
 192        rewrite < H;
 193        clear H;
 194        elim n;
 195         [ simplify;
 196           autobatch
 197         | simplify;
 198           autobatch
 199         ]
 200      ]
 201    ].
 202 qed.
 203
 204 axiom derivative: (R→R) → R → R.
 205
 206 notation "hvbox('D'[f])"
 207   non associative with precedence 90
 208 for @{ 'derivative $f }.
 209
 210 interpretation "Rderivative" 'derivative f = (derivative f).
 211
 212 (*  FG: we definitely do not want 'x' as a keyward!
 213  *  Any file that includes this one can not use 'x' as an identifier
 214  *)
 215 notation "hvbox('X' \sup n)"
 216   non associative with precedence 60
 217 for @{ 'monomio $n }.
 218
 219 notation "hvbox('X')"
 220   non associative with precedence 60
 221 for @{ 'monomio 1 }.
 222
 223 interpretation "Rmonomio" 'monomio n = (monomio n).
 224
 225 axiom derivative_x0: D[X \sup 0] = 0.
 226 axiom derivative_x1: D[X] = 1.
 227
 228 axiom derivative_mult: ∀f,g:R→R. D[f·g] = D[f]·g + f·D[g].
 229
 230 alias symbol "middot" = "Fmult".
 231
 232 theorem derivative_power: ∀n:nat. D[X \sup n] = n·X \sup (pred n).
 233  assume n:nat.
 234  (*we proceed by induction on n to prove
 235  (D[X \sup n] = n · X \sup (pred n)).*)
 236  elim n 0.
 237  case O.
 238    the thesis becomes (D[X \sup 0] = 0·X \sup (pred 0)).
 239   done.
 240  case S (m:nat).
 241   by induction hypothesis we know
 242    (D[X \sup m] = m·X \sup (pred m)) (H).
 243   the thesis becomes
 244    (D[X \sup (1+m)] = (1+m) · X \sup m).
 245   we need to prove
 246    (m · (X \sup (1+ pred m)) = m · X \sup m) (Ppred).
 247    lapply depth=0 le_n;
 248    we proved (0 < m ∨ 0=m) (cases).
 249    we proceed by induction on cases
 250    to prove (m · (X \sup (1+ pred m)) = m · X \sup m).
 251     case left.
 252       suppose (0 < m) (m_pos).
 253       using (S_pred ? m_pos) we proved (m = 1 + pred m) (H1).
 254       by H1 done.
 255     case right.
 256       suppose (0=m) (m_zero).
 257     by m_zero, Fmult_zero_f done.
 258   conclude
 259      (D[X \sup (1+m)])
 260    = (D[X · X \sup m]).
 261    = (D[X] · X \sup m + X · D[X \sup m]).
 262    = (X \sup m + X · (m · X \sup (pred m))).
 263    lapply depth=0 Fmult_associative;
 264    lapply depth=0 Fmult_commutative;
 265    = (X \sup m + m · (X · X \sup (pred m))) by Fmult_associative, Fmult_commutative.
 266    = (X \sup m + m · (X \sup (1 + pred m))).
 267    = (X \sup m + m · X \sup m).
 268    = ((1+m) · X \sup m) by Fmult_one_f, Fmult_commutative, Fmult_Fplus_distr, costante_sum
 269   done.
 270 qed.
 271
 272 (*
 273 notation "hvbox(\frac 'd' ('d' ident i) break p)"
 274   right associative with precedence 90
 275 for @{ 'derivative ${default
 276   @{\lambda ${ident i} : $ty. $p)}
 277   @{\lambda ${ident i} . $p}}}.
 278
 279 interpretation "Rderivative" 'derivative \eta.f = (derivative f).
 280 *)
 281
 282 notation "hvbox(\frac 'd' ('d' 'X') break p)" with precedence 90
 283 for @{ 'derivative $p}.
 284
 285 interpretation "Rderivative" 'derivative f = (derivative f).
 286
 287 theorem derivative_power': ∀n:nat. D[X \sup (1+n)] = (1+n) · X \sup n.
 288  assume n:nat.
 289  (*we proceed by induction on n to prove
 290  (D[X \sup (1+n)] = (1+n) · X \sup n).*) elim n 0.
 291  case O.
 292    the thesis becomes (D[X \sup 1] = 1 · X \sup 0).
 293   done.
 294  case S (m:nat).
 295   by induction hypothesis we know
 296    (D[X \sup (1+m)] = (1+m) · X \sup m) (H).
 297   the thesis becomes
 298    (D[X \sup (2+m)] = (2+m) · X \sup (1+m)).
 299   conclude
 300      (D[X \sup (2+m)])
 301    = (D[X · X \sup (1+m)]).
 302    = (D[X] · X \sup (1+m) + X · D[X \sup (1+m)]).
 303    = (X \sup (1+m) + X · (costante (1+m) · X \sup m)).
 304    = (X \sup (1+m) + costante (1+m) · X \sup (1+m)).
 305    = ((2+m) · X \sup (1+m)) timeout=30 by Fmult_one_f, Fmult_commutative,
 306        Fmult_Fplus_distr, assoc_plus, plus_n_SO, costante_sum
 307   done.
 308 qed.