Debian Codegraph @

Formal_ineqs/lib/ipow.hl

raw
1 (* ========================================================================== *)
2 (* Formal verification of FPTaylor certificates *)
3 (* *)
4 (* Copyright (c) 2015 Alexey Solovyev, University of Utah *)
5 (* *)
6 (* This file is distributed under the terms of the MIT licence *)
7 (* ========================================================================== *)
8
9 (* -------------------------------------------------------------------------- *)
10 (* Integer powers of real numbers *)
11 (* -------------------------------------------------------------------------- *)
12
13
14 module Ipow = struct
15
16 prioritize_real();;
17
18 unparse_as_infix("ipow");;
19
20 let ipow = new_definition
21 `ipow (x:real) (e:int) =
22 (if (&0 <= e)
23 then (x pow (num_of_int e))
24 else (inv (x pow (num_of_int (--e)))))`;;
25
26 parse_as_infix("ipow",(24,"left"));;
27
28 let IPOW_LT_0 = prove
29 (`!(r:real) (i:int). &0 < r ==> &0 < r ipow i`,
30 REPEAT STRIP_TAC THEN REWRITE_TAC[ipow] THEN
31 COND_CASES_TAC THEN ASM_SIMP_TAC[REAL_POW_LT; REAL_LT_INV]);;
32
33 let IPOW_LE_0 = prove
34 (`!(r:real) (i:int). &0 <= r ==> &0 <= r ipow i`,
35 REPEAT STRIP_TAC THEN REWRITE_TAC[ipow] THEN
36 COND_CASES_TAC THEN ASM_SIMP_TAC[REAL_POW_LE; REAL_LE_INV]);;
37
38 let IPOW_NUM = prove
39 (`!x n. x ipow (&n) = x pow n`,
40 REWRITE_TAC[ipow; INT_POS; NUM_OF_INT_OF_NUM]);;
41
42 let IPOW_0 = prove
43 (`!x. x ipow &0 = &1`,
44 REWRITE_TAC[IPOW_NUM; real_pow]);;
45
46 let IPOW_1 = prove
47 (`!x. x ipow &1 = x`,
48 REWRITE_TAC[IPOW_NUM; REAL_POW_1]);;
49
50 let IPOW_2 = prove
51 (`!x. x ipow &2 = x * x`,
52 REWRITE_TAC[IPOW_NUM; REAL_POW_2]);;
53
54 let IPOW_INV = prove
55 (`!x i. (inv x) ipow i = inv (x ipow i)`,
56 REPEAT STRIP_TAC THEN ASM_CASES_TAC `i:int = &0` THENL [
57 ASM_REWRITE_TAC[IPOW_0; INT_NEG_0; REAL_INV_1];
58 ALL_TAC
59 ] THEN
60 REWRITE_TAC[ipow] THEN REPEAT COND_CASES_TAC THEN
61 REWRITE_TAC[REAL_INV_POW; REAL_INV_INV] THEN ASM_ARITH_TAC);;
62
63 let INV_IPOW = prove
64 (`!x i. inv (x ipow i) = (inv x) ipow i`,
65 REWRITE_TAC[IPOW_INV]);;
66
67 let IPOW_NEG = prove
68 (`!x i. x ipow (--i) = inv (x ipow i)`,
69 REPEAT STRIP_TAC THEN
70 ASM_CASES_TAC `i:int = &0` THENL [
71 ASM_REWRITE_TAC[IPOW_0; INT_NEG_0; REAL_INV_1];
72 ALL_TAC
73 ] THEN
74 REWRITE_TAC[ipow] THEN REPEAT COND_CASES_TAC THEN
75 ASM_REWRITE_TAC[INT_NEG_NEG; REAL_INV_INV] THEN ASM_ARITH_TAC);;
76
77 let IPOW_NEG_NUM = prove
78 (`!x n. x ipow (-- &n) = inv x pow n`,
79 REWRITE_TAC[IPOW_NEG; INV_IPOW; IPOW_NUM]);;
80
81 let IPOW_NEG_1 = prove
82 (`!x. x ipow (-- &1) = inv x`,
83 REWRITE_TAC[IPOW_NEG_NUM; REAL_POW_1]);;
84
85 let NUM_OF_INT_ADD = prove
86 (`!n m. num_of_int (&n + &m) = n + m`,
87 REWRITE_TAC[INT_OF_NUM_ADD; NUM_OF_INT_OF_NUM]);;
88
89 let NUM_OF_INT_MUL = prove
90 (`!n m. num_of_int (&n * &m) = n * m`,
91 REWRITE_TAC[INT_OF_NUM_MUL; NUM_OF_INT_OF_NUM]);;
92
93 let NUM_OF_INT_SUB = prove
94 (`!n m. m <= n ==> num_of_int (&n - &m) = n - m`,
95 SIMP_TAC[INT_OF_NUM_SUB; NUM_OF_INT_OF_NUM]);;
96
97 let IPOW_SUB_NUM = prove
98 (`!x n m. ~(x = &0) ==> x ipow (&n - &m) = x pow n * inv x pow m`,
99 REPEAT STRIP_TAC THEN
100 SUBGOAL_THEN `!n m. m <= n ==> x ipow (&n - &m) = x pow n * inv x pow m` ASSUME_TAC THENL [
101 REPEAT STRIP_TAC THEN ASM_SIMP_TAC[INT_OF_NUM_SUB; IPOW_NUM] THEN
102 ASM_SIMP_TAC[REAL_POW_SUB; real_div; REAL_INV_POW];
103 ALL_TAC
104 ] THEN
105 DISJ_CASES_TAC (ARITH_RULE `m <= n \/ n <= m:num`) THEN ASM_SIMP_TAC[] THEN
106 ONCE_REWRITE_TAC[INT_ARITH `&n - &m = --(&m - &n):int`] THEN
107 ASM_SIMP_TAC[IPOW_NEG; REAL_INV_MUL; REAL_INV_POW; REAL_INV_INV; REAL_MUL_AC]);;
108
109 let INT_EQ_NUM_SUB = prove
110 (`!i:int. ?n m. i = &n - &m`,
111 GEN_TAC THEN ASM_CASES_TAC `&0 <= i:int` THENL [
112 MAP_EVERY EXISTS_TAC [`num_of_int i`; `0`] THEN
113 POP_ASSUM MP_TAC THEN REWRITE_TAC[NUM_OF_INT] THEN INT_ARITH_TAC;
114 MAP_EVERY EXISTS_TAC [`0`; `num_of_int (-- i)`] THEN
115 SUBGOAL_THEN `&0 <= --i:int` MP_TAC THENL [ ASM_INT_ARITH_TAC; ALL_TAC ] THEN
116 REWRITE_TAC[NUM_OF_INT] THEN INT_ARITH_TAC
117 ]);;
118
119 let IPOW_ADD = prove
120 (`!x u v. ~(x = &0) ==> x ipow (u + v) = x ipow u * x ipow v`,
121 REPEAT STRIP_TAC THEN
122 MAP_EVERY (fun tm -> STRIP_ASSUME_TAC (SPEC tm INT_EQ_NUM_SUB)) [`u:int`; `v:int`] THEN
123 ASM_REWRITE_TAC[INT_ARITH `a - b + c - d:int = (a + c) - (b + d)`; INT_OF_NUM_ADD] THEN
124 ASM_SIMP_TAC[IPOW_SUB_NUM; REAL_POW_ADD] THEN
125 REAL_ARITH_TAC);;
126
127 let IPOW_MUL = prove
128 (`!x y u. (x * y) ipow u = x ipow u * y ipow u`,
129 REPEAT GEN_TAC THEN REWRITE_TAC[ipow] THEN
130 COND_CASES_TAC THEN REWRITE_TAC[REAL_POW_MUL; REAL_INV_MUL]);;
131
132 let IPOW_ZERO = prove
133 (`!u. &0 ipow u = (if u = &0 then &1 else &0)`,
134 GEN_TAC THEN STRIP_ASSUME_TAC (SPEC `u:int` INT_EQ_NUM_SUB) THEN REWRITE_TAC[ipow] THEN
135 ASM_REWRITE_TAC[REAL_POW_ZERO; INT_SUB_LE; INT_OF_NUM_LE; INT_SUB_0; INT_OF_NUM_EQ] THEN
136 COND_CASES_TAC THENL [
137 ASM_SIMP_TAC[NUM_OF_INT_SUB; ARITH_RULE `m <= n ==> (n - m = 0 <=> n = m:num)`];
138 ASM_SIMP_TAC[ARITH_RULE `~(m <= n) ==> ~(n = m:num)`; INT_ARITH `--(a - b) = b - a:int`] THEN
139 SUBGOAL_THEN `num_of_int (&m - &n) = m - n` ASSUME_TAC THENL [
140 MATCH_MP_TAC NUM_OF_INT_SUB THEN ASM_ARITH_TAC;
141 ALL_TAC
142 ] THEN
143 ASM_SIMP_TAC[ARITH_RULE `~(m <= n) ==> ~(m - n = 0)`; REAL_INV_0]
144 ]);;
145
146 let IPOW_ONE = prove
147 (`!u. &1 ipow u = &1`,
148 REWRITE_TAC[ipow; REAL_POW_ONE; REAL_INV_1; COND_ID]);;
149
150 let IPOW_IPOW = prove
151 (`!x u v. (x ipow u) ipow v = x ipow (u * v)`,
152 REPEAT STRIP_TAC THEN ASM_CASES_TAC `x = &0` THENL [
153 ASM_REWRITE_TAC[IPOW_ZERO] THEN
154 COND_CASES_TAC THEN ASM_REWRITE_TAC[INT_MUL_LZERO; IPOW_ONE] THEN
155 REWRITE_TAC[IPOW_ZERO] THEN
156 COND_CASES_TAC THEN ASM_REWRITE_TAC[INT_ENTIRE; INT_MUL_RZERO];
157 ALL_TAC
158 ] THEN
159 MAP_EVERY (fun tm -> STRIP_ASSUME_TAC (SPEC tm INT_EQ_NUM_SUB)) [`u:int`; `v:int`] THEN
160 ASM_REWRITE_TAC[INT_ARITH `(a - b) * (c - d) = (a * c + b * d) - (b * c + a * d:int)`] THEN
161 REWRITE_TAC[INT_OF_NUM_ADD; INT_OF_NUM_MUL] THEN
162 SUBGOAL_THEN `~(x pow n * inv x pow m = &0)` ASSUME_TAC THENL [
163 REWRITE_TAC[REAL_ENTIRE; DE_MORGAN_THM] THEN
164 ASM_SIMP_TAC[REAL_POW_NZ; REAL_INV_EQ_0];
165 ALL_TAC
166 ] THEN
167 ASM_SIMP_TAC[IPOW_SUB_NUM] THEN
168 REWRITE_TAC[REAL_POW_MUL; REAL_POW_POW; REAL_INV_MUL; REAL_INV_POW; REAL_INV_INV] THEN
169 REWRITE_TAC[REAL_POW_ADD] THEN REAL_ARITH_TAC);;
170
171 let IPOW_ADD_1 = prove
172 (`!x i. ~(x = &0) ==> x ipow (i + &1) = x * x ipow i`,
173 SIMP_TAC[IPOW_ADD; IPOW_1; REAL_MUL_AC]);;
174
175 let IPOW_MONO = prove
176 (`!x u v. &1 <= x /\ u <= v ==> x ipow u <= x ipow v`,
177 REPEAT STRIP_TAC THEN
178 SUBGOAL_THEN `~(x = &0) /\ &0 < x` ASSUME_TAC THENL [
179 ASM_ARITH_TAC;
180 ALL_TAC
181 ] THEN
182 MAP_EVERY (fun tm -> STRIP_ASSUME_TAC (SPEC tm INT_EQ_NUM_SUB)) [`u:int`; `v:int`] THEN
183 ASM_SIMP_TAC[IPOW_SUB_NUM] THEN ONCE_REWRITE_TAC[REAL_MUL_AC] THEN
184 MATCH_MP_TAC (SPEC `x pow m'` REAL_LE_LCANCEL_IMP) THEN
185 ASM_SIMP_TAC[REAL_POW_LT; REAL_POW_INV; REAL_POW_NZ; REAL_MUL_ASSOC; REAL_MUL_RINV] THEN
186 ONCE_REWRITE_TAC[REAL_ARITH `(a * b) * c = b * (a * c):real`] THEN
187 MATCH_MP_TAC (SPEC `x pow m` REAL_LE_LCANCEL_IMP) THEN
188 ASM_SIMP_TAC[REAL_POW_LT; REAL_POW_INV; REAL_POW_NZ; REAL_MUL_ASSOC; REAL_MUL_RINV] THEN
189 REWRITE_TAC[REAL_MUL_LID; REAL_MUL_RID; GSYM REAL_POW_ADD] THEN
190 MATCH_MP_TAC REAL_POW_MONO THEN ASM_REWRITE_TAC[] THEN
191 REWRITE_TAC[GSYM INT_OF_NUM_LE; GSYM INT_OF_NUM_ADD] THEN ASM_INT_ARITH_TAC);;
192
193 let IPOW_MONO_LT = prove
194 (`!x u v. &1 < x /\ u < v ==> x ipow u < x ipow v`,
195 REPEAT STRIP_TAC THEN
196 SUBGOAL_THEN `~(x = &0) /\ &0 < x` ASSUME_TAC THENL [
197 ASM_ARITH_TAC;
198 ALL_TAC
199 ] THEN
200 MAP_EVERY (fun tm -> STRIP_ASSUME_TAC (SPEC tm INT_EQ_NUM_SUB)) [`u:int`; `v:int`] THEN
201 ASM_SIMP_TAC[IPOW_SUB_NUM] THEN ONCE_REWRITE_TAC[REAL_MUL_AC] THEN
202 MATCH_MP_TAC (SPEC `x pow m'` REAL_LT_LCANCEL_IMP) THEN
203 ASM_SIMP_TAC[REAL_POW_LT; REAL_POW_INV; REAL_POW_NZ; REAL_MUL_ASSOC; REAL_MUL_RINV] THEN
204 ONCE_REWRITE_TAC[REAL_ARITH `(a * b) * c = b * (a * c):real`] THEN
205 MATCH_MP_TAC (SPEC `x pow m` REAL_LT_LCANCEL_IMP) THEN
206 ASM_SIMP_TAC[REAL_POW_LT; REAL_POW_INV; REAL_POW_NZ; REAL_MUL_ASSOC; REAL_MUL_RINV] THEN
207 REWRITE_TAC[REAL_MUL_LID; REAL_MUL_RID; GSYM REAL_POW_ADD] THEN
208 MATCH_MP_TAC REAL_POW_MONO_LT THEN ASM_REWRITE_TAC[] THEN
209 REWRITE_TAC[GSYM INT_OF_NUM_LT; GSYM INT_OF_NUM_ADD] THEN ASM_INT_ARITH_TAC);;
210
211 let IPOW_MONO_INV = prove
212 (`!x u v. &0 < x /\ x <= &1 /\ u <= v ==> x ipow v <= x ipow u`,
213 REPEAT STRIP_TAC THEN
214 MP_TAC (SPECL[`inv x`; `--v:int`; `--u:int`] IPOW_MONO) THEN
215 REWRITE_TAC[IPOW_NEG; IPOW_INV; REAL_INV_INV] THEN
216 DISCH_THEN MATCH_MP_TAC THEN
217 ASM_SIMP_TAC[REAL_INV_1_LE] THEN ASM_ARITH_TAC);;
218
219 let IPOW_MONO_INV_LT = prove
220 (`!x u v. &0 < x /\ x < &1 /\ u < v ==> x ipow v < x ipow u`,
221 REPEAT STRIP_TAC THEN
222 MP_TAC (SPECL[`inv x`; `--v:int`; `--u:int`] IPOW_MONO_LT) THEN
223 REWRITE_TAC[IPOW_NEG; IPOW_INV; REAL_INV_INV] THEN
224 DISCH_THEN MATCH_MP_TAC THEN
225 ASM_SIMP_TAC[REAL_INV_1_LT] THEN ASM_ARITH_TAC);;
226
227 let ABS_IPOW = prove
228 (`!x u. abs (x ipow u) = abs x ipow u`,
229 REPEAT GEN_TAC THEN REWRITE_TAC[ipow] THEN COND_CASES_TAC THEN
230 REWRITE_TAC[REAL_ABS_INV; REAL_ABS_POW]);;
231
232 let IPOW_DIV = prove
233 (`!x y u. (x / y) ipow u = (x ipow u) * (y ipow --u)`,
234 REWRITE_TAC[real_div; IPOW_MUL; IPOW_NEG; INV_IPOW]);;
235
236 let IPOW_NZ = prove
237 (`!x u. ~(x = &0) ==> ~(x ipow u = &0)`,
238 REPEAT GEN_TAC THEN DISCH_TAC THEN REWRITE_TAC[ipow] THEN COND_CASES_TAC THEN
239 ASM_SIMP_TAC[REAL_INV_EQ_0; REAL_POW_NZ]);;
240
241 let IPOW_SUB = prove
242 (`!x u v. ~(x = &0) ==> x ipow (u - v) = x ipow u * x ipow (--v)`,
243 SIMP_TAC[INT_SUB; IPOW_ADD]);;
244
245 let IPOW_EQ_0 = prove
246 (`!x u. (x ipow u = &0) <=> (x = &0) /\ ~(u = &0)`,
247 REPEAT GEN_TAC THEN EQ_TAC THEN REPEAT STRIP_TAC THENL [
248 POP_ASSUM MP_TAC THEN ONCE_REWRITE_TAC[GSYM CONTRAPOS_THM] THEN
249 MATCH_ACCEPT_TAC IPOW_NZ;
250 UNDISCH_TAC `x ipow u = &0` THEN ASM_REWRITE_TAC[IPOW_0] THEN REAL_ARITH_TAC;
251 ASM_REWRITE_TAC[IPOW_ZERO]
252 ]);;
253
254 let IPOW_POS_NUM_OF_INT = prove
255 (`!u x. &0 <= u ==> x ipow u = x pow (num_of_int u)`,
256 SIMP_TAC[ipow]);;
257
258 let IPOW_NEG_NUM_OF_INT = prove
259 (`!u x. u <= &0 ==> x ipow u = inv x pow (num_of_int (--u))`,
260 REPEAT STRIP_TAC THEN
261 ONCE_REWRITE_TAC[GSYM (SPEC `u:int` INT_NEG_NEG)] THEN
262 ONCE_REWRITE_TAC[IPOW_NEG] THEN
263 ASM_SIMP_TAC[IPOW_POS_NUM_OF_INT; INT_ARITH `u <= &0 ==> &0 <= --u:int`] THEN
264 REWRITE_TAC[INT_NEG_NEG; REAL_INV_POW]);;
265
266 let IPOW_LE_1 = prove
267 (`!u x. &1 <= x /\ &0 <= u ==> &1 <= x ipow u`,
268 REPEAT STRIP_TAC THEN ASM_SIMP_TAC[IPOW_POS_NUM_OF_INT; REAL_POW_LE_1]);;
269
270 let IPOW_LE_1_NEG = prove
271 (`!u x. &1 <= x /\ u <= &0 ==> x ipow u <= &1`,
272 REPEAT STRIP_TAC THEN ASM_SIMP_TAC[IPOW_NEG_NUM_OF_INT] THEN
273 MATCH_MP_TAC REAL_POW_1_LE THEN
274 ASM_SIMP_TAC[REAL_LE_INV; REAL_INV_LE_1; REAL_ARITH `&1 <= x ==> &0 <= x`]);;
275
276 let IPOW_1_LE = prove
277 (`!u x. &0 <= x /\ x <= &1 /\ &0 <= u ==> x ipow u <= &1`,
278 REPEAT STRIP_TAC THEN ASM_SIMP_TAC[IPOW_POS_NUM_OF_INT; REAL_POW_1_LE]);;
279
280 let IPOW_1_LE_NEG = prove
281 (`!u x. &0 < x /\ x <= &1 /\ u <= &0 ==> &1 <= x ipow u`,
282 REPEAT STRIP_TAC THEN ASM_SIMP_TAC[IPOW_NEG_NUM_OF_INT] THEN
283 MATCH_MP_TAC REAL_POW_LE_1 THEN ASM_SIMP_TAC[REAL_INV_1_LE]);;
284
285 let IPOW_LT_1 = prove
286 (`!u x. &1 < x /\ &0 < u ==> &1 < x ipow u`,
287 REPEAT STRIP_TAC THEN ASM_SIMP_TAC[IPOW_POS_NUM_OF_INT; INT_LT_IMP_LE] THEN
288 MATCH_MP_TAC REAL_POW_LT_1 THEN
289 ASM_SIMP_TAC[GSYM INT_OF_NUM_EQ; INT_OF_NUM_OF_INT; INT_LT_IMP_LE] THEN
290 POP_ASSUM MP_TAC THEN INT_ARITH_TAC);;
291
292 let IPOW_LT_1_NEG = prove
293 (`!u x. &1 < x /\ u < &0 ==> x ipow u < &1`,
294 REPEAT STRIP_TAC THEN ASM_SIMP_TAC[IPOW_NEG_NUM_OF_INT; INT_LT_IMP_LE] THEN
295 MATCH_MP_TAC REAL_POW_1_LT THEN
296 ASM_SIMP_TAC[REAL_LE_INV; REAL_INV_LT_1; REAL_ARITH `&1 < x ==> &0 <= x`] THEN
297 ASM_SIMP_TAC[GSYM INT_OF_NUM_EQ; INT_OF_NUM_OF_INT; INT_ARITH `u < &0 ==> &0 <= --u:int`] THEN
298 POP_ASSUM MP_TAC THEN INT_ARITH_TAC);;
299
300 let IPOW_1_LT = prove
301 (`!u x. &0 <= x /\ x < &1 /\ &0 < u ==> x ipow u < &1`,
302 REPEAT STRIP_TAC THEN ASM_SIMP_TAC[IPOW_POS_NUM_OF_INT; INT_LT_IMP_LE] THEN
303 MATCH_MP_TAC REAL_POW_1_LT THEN
304 ASM_SIMP_TAC[GSYM INT_OF_NUM_EQ; INT_OF_NUM_OF_INT; INT_LT_IMP_LE] THEN
305 POP_ASSUM MP_TAC THEN INT_ARITH_TAC);;
306
307 let IPOW_1_LT_NEG = prove
308 (`!u x. &0 < x /\ x < &1 /\ u < &0 ==> &1 < x ipow u`,
309 REPEAT STRIP_TAC THEN ASM_SIMP_TAC[IPOW_NEG_NUM_OF_INT; INT_LT_IMP_LE] THEN
310 MATCH_MP_TAC REAL_POW_LT_1 THEN ASM_SIMP_TAC[REAL_INV_1_LT] THEN
311 ASM_SIMP_TAC[GSYM INT_OF_NUM_EQ; INT_OF_NUM_OF_INT; INT_ARITH `u < &0 ==> &0 <= --u:int`] THEN
312 POP_ASSUM MP_TAC THEN INT_ARITH_TAC);;
313
314 let DIV_IPOW2 = prove
315 (`!x u v. ~(x = &0) ==> x ipow u / x ipow v = x ipow (u - v)`,
316 SIMP_TAC[real_div; IPOW_SUB; IPOW_NEG]);;
317
318 let IPOW_EQ = prove
319 (`!u x y. ~(u = &0) /\ &0 <= x /\ &0 <= y /\ x ipow u = y ipow u ==> x = y`,
320 REPEAT GEN_TAC THEN REWRITE_TAC[ipow] THEN COND_CASES_TAC THEN STRIP_TAC THENL [
321 MATCH_MP_TAC REAL_POW_EQ THEN EXISTS_TAC `num_of_int u` THEN
322 ASM_SIMP_TAC[GSYM INT_OF_NUM_EQ; INT_OF_NUM_OF_INT];
323 ONCE_REWRITE_TAC[GSYM REAL_EQ_INV2] THEN REWRITE_TAC[GSYM REAL_ABS_INV] THEN
324 MATCH_MP_TAC REAL_POW_EQ THEN EXISTS_TAC `num_of_int (--u)` THEN
325 ASM_SIMP_TAC[REAL_POW_INV; GSYM INT_OF_NUM_EQ; REAL_LE_INV] THEN
326 ASM_SIMP_TAC[INT_OF_NUM_OF_INT; INT_ARITH `~(&0 <= u) ==> &0 <= --u:int /\ ~(--u = &0)`]
327 ]);;
328
329 let IPOW_EQ_ABS = prove
330 (`!u x y. ~(u = &0) /\ x ipow u = y ipow u ==> abs x = abs y`,
331 REPEAT GEN_TAC THEN REWRITE_TAC[ipow] THEN COND_CASES_TAC THEN STRIP_TAC THENL [
332 MATCH_MP_TAC REAL_POW_EQ_ABS THEN EXISTS_TAC `num_of_int u` THEN
333 ASM_SIMP_TAC[GSYM INT_OF_NUM_EQ; INT_OF_NUM_OF_INT];
334 ONCE_REWRITE_TAC[GSYM REAL_EQ_INV2] THEN REWRITE_TAC[GSYM REAL_ABS_INV] THEN
335 MATCH_MP_TAC REAL_POW_EQ_ABS THEN EXISTS_TAC `num_of_int (--u)` THEN
336 ASM_SIMP_TAC[REAL_POW_INV; GSYM INT_OF_NUM_EQ] THEN
337 ASM_SIMP_TAC[INT_OF_NUM_OF_INT; INT_ARITH `~(&0 <= u) ==> &0 <= --u:int /\ ~(--u = &0)`]
338 ]);;
339
340 let IPOW_EQ_1_IMP = prove
341 (`!x u. ~(u = &0) /\ x ipow u = &1 ==> abs x = &1`,
342 REPEAT GEN_TAC THEN REWRITE_TAC[ipow] THEN COND_CASES_TAC THEN STRIP_TAC THENL [
343 MATCH_MP_TAC REAL_POW_EQ_1_IMP THEN EXISTS_TAC `num_of_int u` THEN
344 ASM_SIMP_TAC[GSYM INT_OF_NUM_EQ; INT_OF_NUM_OF_INT];
345 ONCE_REWRITE_TAC[GSYM REAL_EQ_INV2] THEN REWRITE_TAC[GSYM REAL_ABS_INV; REAL_INV_1] THEN
346 MATCH_MP_TAC REAL_POW_EQ_1_IMP THEN EXISTS_TAC `num_of_int (--u)` THEN
347 ASM_SIMP_TAC[REAL_POW_INV; GSYM INT_OF_NUM_EQ] THEN
348 ASM_SIMP_TAC[INT_OF_NUM_OF_INT; INT_ARITH `~(&0 <= u) ==> &0 <= --u:int /\ ~(--u = &0)`]
349 ]);;
350
351 let IPOW_OF_NUM = prove
352 (`!x i. &x ipow i =
353 if &0 <= i then &(x EXP (num_of_int i)) else inv (&(x EXP (num_of_int (--i))))`,
354 REPEAT STRIP_TAC THEN REWRITE_TAC[ipow] THEN
355 COND_CASES_TAC THEN REWRITE_TAC[REAL_OF_NUM_POW]);;
356
357 let IPOW_EQ_EXP = prove
358 (`!(r:num) (i:int). &0 <= i ==> ?m. m = num_of_int i /\ &r ipow i = &(r EXP m)`,
359 REPEAT STRIP_TAC THEN EXISTS_TAC `num_of_int i` THEN ASM_REWRITE_TAC[IPOW_OF_NUM]);;
360
361 let IPOW_EQ_EXP_P = prove
362 (`!(r:num) (p:num). 0 < p ==> &r ipow (&p - &1) = &(r EXP (p - 1))`,
363 REPEAT STRIP_TAC THEN REWRITE_TAC[IPOW_OF_NUM] THEN
364 ASM_SIMP_TAC[INT_OF_NUM_SUB; ARITH_RULE `0 < p ==> 1 <= p`; INT_POS] THEN
365 REWRITE_TAC[NUM_OF_INT_OF_NUM]);;
366
367 let IPOW_BETWEEN = prove
368 (`!(x:real) (y:num) (z:num) (e:int).
369 &0 < x /\ &y * x ipow e <= &z * x ipow e /\
370 &z * x ipow e <= (&y + &1) * x ipow e ==>
371 z = y \/ z = y + 1`,
372 REPEAT STRIP_TAC THEN
373 MP_TAC (SPECL[`&y:real`; `&z:real`; `x ipow e`] REAL_LE_RCANCEL_IMP) THEN
374 MP_TAC (SPECL[`&z:real`; `&y + &1:real`; `x ipow e`] REAL_LE_RCANCEL_IMP) THEN
375 ASM_SIMP_TAC[IPOW_LT_0; REAL_OF_NUM_ADD; REAL_OF_NUM_LE] THEN
376 ARITH_TAC);;
377
378 let EXP_LE_NUM = prove
379 (`!r n. 2 <= r ==> n <= r EXP n`,
380 GEN_TAC THEN INDUCT_TAC THEN REWRITE_TAC[EXP; LE_0] THEN
381 ASM_CASES_TAC `n = 0` THENL [ ASM_REWRITE_TAC[] THEN ARITH_TAC; ALL_TAC ] THEN
382 DISCH_TAC THEN MATCH_MP_TAC LE_TRANS THEN EXISTS_TAC `r * n:num` THEN
383 ASM_SIMP_TAC[LE_MULT_LCANCEL; ARITH_RULE `2 <= r ==> ~(r = 0)`] THEN
384 MATCH_MP_TAC LE_TRANS THEN EXISTS_TAC `2 * n` THEN
385 ASM_REWRITE_TAC[LE_MULT_RCANCEL] THEN ASM_ARITH_TAC);;
386
387 let IPOW_LE_NUM = prove
388 (`!(r:num) (n:num). 2 <= r ==> ?e. &n <= &r ipow e`,
389 REPEAT STRIP_TAC THEN EXISTS_TAC `&n:int` THEN
390 REWRITE_TAC[IPOW_OF_NUM; INT_POS; NUM_OF_INT_OF_NUM; REAL_OF_NUM_LE] THEN
391 ASM_SIMP_TAC[EXP_LE_NUM]);;
392
393 let IPOW_LE_REAL = prove
394 (`!(r:num) (z:real). 2 <= r ==> ?e. z <= &r ipow e`,
395 REPEAT STRIP_TAC THEN
396 MP_TAC (SPEC `z:real` REAL_ARCH_SIMPLE) THEN STRIP_TAC THEN
397 MP_TAC (SPECL[`r:num`; `n:num`] IPOW_LE_NUM) THEN ASM_REWRITE_TAC[] THEN STRIP_TAC THEN
398 EXISTS_TAC `e:int` THEN ASM_ARITH_TAC);;
399
400 let IPOW_LE_REAL_2 = prove
401 (`!(r:num) (z:real). &0 < z /\ 2 <= r ==> ?e. &r ipow e <= z`,
402 REPEAT STRIP_TAC THEN
403 MP_TAC (SPECL[`r:num`; `inv z`] IPOW_LE_REAL) THEN ASM_REWRITE_TAC[] THEN STRIP_TAC THEN
404 EXISTS_TAC `--e:int` THEN REWRITE_TAC[IPOW_NEG] THEN
405 SUBGOAL_THEN `z = inv (inv z)` (fun th -> ONCE_REWRITE_TAC[th]) THENL [
406 REWRITE_TAC[REAL_INV_INV];
407 ALL_TAC
408 ] THEN
409 MATCH_MP_TAC REAL_LE_INV2 THEN
410 ASM_SIMP_TAC[REAL_LT_INV]);;
411
412 let IPOW_EXP_MONO = prove
413 (`!x e1 e2. &1 < x /\ x ipow e1 <= x ipow e2 ==> e1 <= e2`,
414 REPEAT STRIP_TAC THEN
415 ASM_CASES_TAC `e1 <= e2:int` THEN ASM_REWRITE_TAC[] THEN
416 UNDISCH_TAC `x ipow e1 <= x ipow e2` THEN REWRITE_TAC[REAL_NOT_LE] THEN
417 MATCH_MP_TAC IPOW_MONO_LT THEN ASM_ARITH_TAC);;
418
419 let IPOW_EXP_MONO_INV = prove
420 (`!x e1 e2. &0 < x /\ x < &1 /\ x ipow e2 <= x ipow e1 ==> e1 <= e2`,
421 REPEAT STRIP_TAC THEN
422 ASM_CASES_TAC `e1 <= e2:int` THEN ASM_REWRITE_TAC[] THEN
423 UNDISCH_TAC `x ipow e2 <= x ipow e1` THEN REWRITE_TAC[REAL_NOT_LE] THEN
424 MATCH_MP_TAC IPOW_MONO_INV_LT THEN ASM_ARITH_TAC);;
425
426 let IPOW_EXP_MONO_LT = prove
427 (`!x e1 e2. &1 <= x /\ x ipow e1 < x ipow e2 ==> e1 < e2`,
428 REPEAT STRIP_TAC THEN
429 ASM_CASES_TAC `e1 < e2:int` THEN ASM_REWRITE_TAC[] THEN
430 UNDISCH_TAC `x ipow e1 < x ipow e2` THEN REWRITE_TAC[REAL_NOT_LT] THEN
431 MATCH_MP_TAC IPOW_MONO THEN ASM_ARITH_TAC);;
432
433 let IPOW_EXP_MONO_INV_LT = prove
434 (`!x e1 e2. &0 < x /\ x <= &1 /\ x ipow e2 < x ipow e1 ==> e1 < e2`,
435 REPEAT STRIP_TAC THEN
436 ASM_CASES_TAC `e1 < e2:int` THEN ASM_REWRITE_TAC[] THEN
437 UNDISCH_TAC `x ipow e2 < x ipow e1` THEN REWRITE_TAC[REAL_NOT_LT] THEN
438 MATCH_MP_TAC IPOW_MONO_INV THEN ASM_ARITH_TAC);;
439
440 let IPOW_MONOTONE = prove
441 (`!(x:num) (e1:int) (e2:int).
442 2 <= x /\ &x ipow e1 <= &x ipow e2 ==> e1 <= e2`,
443 REPEAT STRIP_TAC THEN MATCH_MP_TAC IPOW_EXP_MONO THEN
444 EXISTS_TAC `&x:real` THEN ASM_REWRITE_TAC[REAL_OF_NUM_LT] THEN
445 ASM_ARITH_TAC);;
446
447 end;;