matita/matita/lib/arithmetics/exp.ma

   1 (*
   2     ||M||  This file is part of HELM, an Hypertextual, Electronic
   3     ||A||  Library of Mathematics, developed at the Computer Science
   4     ||T||  Department of the University of Bologna, Italy.
   5     ||I||
   6     ||T||
   7     ||A||  This file is distributed under the terms of the
   8     \   /  GNU General Public License Version 2
   9      \ /
  10       V_______________________________________________________________ *)
  11
  12 include "arithmetics/div_and_mod.ma".
  13
  14 let rec exp n m on m ≝
  15  match m with
  16  [ O ⇒ 1
  17  | S p ⇒ (exp n p) * n].
  18
  19 interpretation "natural exponent" 'exp a b = (exp a b).
  20
  21 theorem exp_plus_times : ∀n,p,q:nat.
  22   n^(p + q) = n^p * n^q.
  23 #n #p #q elim p normalize //
  24 qed.
  25
  26 theorem exp_n_O : ∀n:nat. 1 = n^O.
  27 //
  28 qed.
  29
  30 theorem exp_n_1 : ∀n:nat. n = n^1.
  31 #n normalize //
  32 qed.
  33
  34 theorem exp_1_n : ∀n:nat. 1 = 1^n.
  35 #n (elim n) normalize //
  36 qed.
  37
  38 theorem exp_2: ∀n. n^2 = n*n.
  39 #n normalize //
  40 qed.
  41
  42 theorem exp_exp_times : ∀n,p,q:nat.
  43   (n^p)^q = n^(p * q).
  44 #n #p #q (elim q) normalize
  45 (* [applyS exp_n_O funziona ma non lo trova *)
  46 // <times_n_O //
  47 qed.
  48
  49 theorem lt_O_exp: ∀n,m:nat. O < n → O < n^m.
  50 #n #m (elim m) normalize // #a #Hind #posn
  51 @(le_times 1 ? 1) /2/
  52 qed.
  53
  54 theorem lt_m_exp_nm: ∀n,m:nat. 1 < n → m < n^m.
  55 #n #m #lt1n (elim m) normalize //
  56 #n #Hind @(transitive_le ? ((S n)*2)) // @le_times //
  57 qed.
  58
  59 theorem exp_to_eq_O: ∀n,m:nat. 1 < n →
  60   n^m = 1 → m = O.
  61 #n #m #ltin #eq1 @le_to_le_to_eq //
  62 @le_S_S_to_le <eq1 @lt_m_exp_nm //
  63 qed.
  64
  65 theorem injective_exp_r: ∀b:nat. 1 < b →
  66   injective nat nat (λi:nat. b^i).
  67 #b #lt1b @nat_elim2 normalize
  68   [#n #H @sym_eq @(exp_to_eq_O b n lt1b) //
  69   |#n #H @False_ind @(absurd (1 < 1) ? (not_le_Sn_n 1))
  70    <H in ⊢ (??%) @(lt_to_le_to_lt ? (1*b)) //
  71    @le_times // @lt_O_exp /2/
  72   |#n #m #Hind #H @eq_f @Hind @(injective_times_l … H) /2/
  73   ]
  74 qed.
  75
  76 theorem le_exp: ∀n,m,p:nat. O < p →
  77   n ≤m → p^n ≤ p^m.
  78 @nat_elim2
  79   [#n #m #ltm #len @lt_O_exp //
  80   |#n #m #_ #len @False_ind /2/
  81   |#n #m #Hind #p #posp #lenm normalize @le_times //
  82    @Hind /2/
  83   ]
  84 qed.
  85
  86 theorem le_exp1: ∀n,m,a:nat. O < a →
  87   n ≤m → n^a ≤ m^a.
  88 #n #m #a #posa #lenm (elim posa) //
  89 #a #posa #Hind @le_times //
  90 qed.
  91
  92 theorem lt_exp: ∀n,m,p:nat. 1 < p →
  93   n < m → p^n < p^m.
  94 #n #m #p #lt1p #ltnm
  95 cut (p \sup n ≤ p \sup m) [@le_exp /2/] #H
  96 cases(le_to_or_lt_eq … H) // #eqexp
  97 @False_ind @(absurd (n=m)) /2/
  98 qed.
  99
 100 theorem lt_exp1: ∀n,m,p:nat. 0 < p →
 101   n < m → n^p < m^p.
 102 #n #m #p #posp #ltnm (elim posp) //
 103 #p #posp #Hind @lt_times //
 104 qed.
 105
 106 theorem le_exp_to_le:
 107 ∀b,n,m. 1 < b → b^n ≤ b^m → n ≤ m.
 108 #b #n #m #lt1b #leexp cases(decidable_le n m) //
 109 #notle @False_ind @(absurd … leexp) @lt_to_not_le
 110 @lt_exp /2/
 111 qed.
 112
 113 theorem le_exp_to_le1 : ∀n,m,p.O < p →
 114   n^p ≤ m^p → n ≤ m.
 115 #n #m #p #posp #leexp @not_lt_to_le
 116 @(not_to_not … (lt_exp1 ??? posp)) @le_to_not_lt //
 117 qed.
 118
 119 theorem lt_exp_to_lt:
 120 ∀a,n,m. 0 < a → a^n < a^m → n < m.
 121 #a #n #m #lt1a #ltexp cases(decidable_le (S n) m) //
 122 #H @False_ind @(absurd … ltexp) @le_to_not_lt
 123 @le_exp // @not_lt_to_le @H
 124 qed.
 125
 126 theorem lt_exp_to_lt1:
 127 ∀a,n,m. O < a → n^a < m^a → n < m.
 128 #a #n #m #posa #ltexp cases(decidable_le (S n) m) //
 129 #H @False_ind @(absurd … ltexp) @le_to_not_lt
 130 @le_exp1 // @not_lt_to_le @H
 131 qed.
 132
 133 theorem times_exp: ∀n,m,p.
 134   n^p * m^p = (n*m)^p.
 135 #n #m #p (elim p) // #p #Hind normalize //
 136 qed.
 137
 138
 139
 140