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