X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;f=helm%2Fsoftware%2Fmatita%2Flibrary%2Fnat%2Fexp.ma;h=25c81c0697bdd167b48883261e1fa5af5c62c0aa;hb=10f29fdd78ee089a9a94446207b543d33d6c851c;hp=11d84f74ca7deb3b676007693f72b585c0547435;hpb=55b82bd235d82ff7f0a40d980effe1efde1f5073;p=helm.git

diff --git a/helm/software/matita/library/nat/exp.ma b/helm/software/matita/library/nat/exp.ma
index 11d84f74c..25c81c069 100644
--- a/helm/software/matita/library/nat/exp.ma
+++ b/helm/software/matita/library/nat/exp.ma
@@ -15,6 +15,7 @@
 set "baseuri" "cic:/matita/nat/exp".
 
 include "nat/div_and_mod.ma".
+include "nat/lt_arith.ma".
 
 let rec exp n m on m\def 
  match m with 
@@ -39,6 +40,19 @@ theorem exp_n_SO : \forall n:nat. n = n \sup (S O).
 intro.simplify.rewrite < times_n_SO.reflexivity.
 qed.
 
+theorem exp_SO_n : \forall n:nat. S O = (S O) \sup n.
+intro.elim n
+  [reflexivity
+  |simplify.rewrite < plus_n_O.assumption
+  ]
+qed.
+
+theorem exp_SSO: \forall n. exp n (S(S O)) = n*n.
+intro.simplify.
+rewrite < times_n_SO.
+reflexivity.
+qed.
+
 theorem exp_exp_times : \forall n,p,q:nat. 
 (n \sup p) \sup q = n \sup (p * q).
 intros.
@@ -54,7 +68,7 @@ apply le_times.assumption.assumption.
 qed.
 
 theorem lt_m_exp_nm: \forall n,m:nat. (S O) < n \to m < n \sup m.
-intros.elim m.simplify.unfold lt.reflexivity.
+intros.elim m.simplify.unfold lt.apply le_n.
 simplify.unfold lt.
 apply (trans_le ? ((S(S O))*(S n1))).
 simplify.
@@ -95,3 +109,129 @@ qed.
 variant inj_exp_r: \forall p:nat. (S O) < p \to \forall n,m:nat.
 p \sup n = p \sup m \to n = m \def
 injective_exp_r.
+
+theorem le_exp: \forall n,m,p:nat. O < p \to n \le m \to exp p n \le exp p m.
+apply nat_elim2
+  [intros.
+   apply lt_O_exp.assumption
+  |intros.
+   apply False_ind.
+   apply (le_to_not_lt ? ? ? H1).
+   apply le_O_n
+  |intros.
+   simplify.
+   apply le_times
+    [apply le_n
+    |apply H[assumption|apply le_S_S_to_le.assumption]
+    ]
+  ]
+qed.
+
+theorem lt_exp: \forall n,m,p:nat. S O < p \to n < m \to exp p n < exp p m.
+apply nat_elim2
+  [intros.
+   apply (lt_O_n_elim ? H1).intro.
+   simplify.unfold lt.
+   rewrite > times_n_SO.
+   apply le_times
+    [assumption
+    |apply lt_O_exp.
+     apply (trans_lt ? (S O))[apply le_n|assumption]
+    ]
+  |intros.
+   apply False_ind.
+   apply (le_to_not_lt ? ? ? H1).
+   apply le_O_n
+  |intros.simplify.
+   apply lt_times_r1
+    [apply (trans_lt ? (S O))[apply le_n|assumption]
+    |apply H
+      [apply H1
+      |apply le_S_S_to_le.assumption
+      ]
+    ]
+  ]
+qed.
+
+theorem lt_exp1: \forall n,m,p:nat. O < p \to n < m \to exp n p < exp m p.
+intros.
+elim H
+  [rewrite < exp_n_SO.rewrite < exp_n_SO.assumption
+  |simplify.
+   apply lt_times;assumption
+  ]
+qed.
+
+theorem le_exp_to_le: 
+\forall a,n,m. S O < a \to exp a n \le exp a m \to n \le m.
+intro.
+apply nat_elim2;intros
+  [apply le_O_n
+  |apply False_ind.
+   apply (le_to_not_lt ? ? H1).
+   simplify.
+   rewrite > times_n_SO.
+   apply lt_to_le_to_lt_times
+    [assumption
+    |apply lt_O_exp.apply lt_to_le.assumption
+    |apply lt_O_exp.apply lt_to_le.assumption
+    ]
+  |simplify in H2.
+   apply le_S_S.
+   apply H
+    [assumption
+    |apply (le_times_to_le a)
+      [apply lt_to_le.assumption|assumption]
+    ]
+  ]
+qed.
+
+theorem le_exp_to_le1 : \forall n,m,p.O < p \to exp n p \leq exp m p \to n \leq m.
+intros;apply not_lt_to_le;intro;apply (lt_to_not_le ? ? ? H1);
+apply lt_exp1;assumption.
+qed.
+     
+theorem lt_exp_to_lt: 
+\forall a,n,m. S O < a \to exp a n < exp a m \to n < m.
+intros.
+elim (le_to_or_lt_eq n m)
+  [assumption
+  |apply False_ind.
+   apply (lt_to_not_eq ? ? H1).
+   rewrite < H2.
+   reflexivity
+  |apply (le_exp_to_le a)
+    [assumption
+    |apply lt_to_le.
+     assumption
+    ]
+  ]
+qed.
+     
+theorem times_exp: 
+\forall n,m,p. exp n p * exp m p = exp (n*m) p.
+intros.elim p
+  [simplify.reflexivity
+  |simplify.
+   rewrite > assoc_times.
+   rewrite < assoc_times in ⊢ (? ? (? ? %) ?).
+   rewrite < sym_times in ⊢ (? ? (? ? (? % ?)) ?).
+   rewrite > assoc_times in ⊢ (? ? (? ? %) ?).
+   rewrite < assoc_times.
+   rewrite < H.
+   reflexivity
+  ]
+qed.
+
+theorem monotonic_exp1: \forall n.
+monotonic nat le (\lambda x.(exp x n)).
+unfold monotonic. intros.
+simplify.elim n
+  [apply le_n
+  |simplify.
+   apply le_times;assumption
+  ]
+qed.
+  
+   
+   
\ No newline at end of file