author | wenzelm |
Tue, 10 Nov 2020 12:48:56 +0100 | |
changeset 72571 | ab4a0b19648a |
parent 70365 | 4df0628e8545 |
child 75878 | fcd118d9242f |
permissions | -rw-r--r-- |
41959 | 1 |
(* Title: HOL/Archimedean_Field.thy |
2 |
Author: Brian Huffman |
|
30096 | 3 |
*) |
4 |
||
60758 | 5 |
section \<open>Archimedean Fields, Floor and Ceiling Functions\<close> |
30096 | 6 |
|
7 |
theory Archimedean_Field |
|
8 |
imports Main |
|
9 |
begin |
|
10 |
||
63331 | 11 |
lemma cInf_abs_ge: |
63489 | 12 |
fixes S :: "'a::{linordered_idom,conditionally_complete_linorder} set" |
13 |
assumes "S \<noteq> {}" |
|
14 |
and bdd: "\<And>x. x\<in>S \<Longrightarrow> \<bar>x\<bar> \<le> a" |
|
63331 | 15 |
shows "\<bar>Inf S\<bar> \<le> a" |
16 |
proof - |
|
17 |
have "Sup (uminus ` S) = - (Inf S)" |
|
18 |
proof (rule antisym) |
|
63489 | 19 |
show "- (Inf S) \<le> Sup (uminus ` S)" |
63331 | 20 |
apply (subst minus_le_iff) |
21 |
apply (rule cInf_greatest [OF \<open>S \<noteq> {}\<close>]) |
|
22 |
apply (subst minus_le_iff) |
|
63489 | 23 |
apply (rule cSup_upper) |
24 |
apply force |
|
25 |
using bdd |
|
26 |
apply (force simp: abs_le_iff bdd_above_def) |
|
63331 | 27 |
done |
28 |
next |
|
70365
4df0628e8545
a few new lemmas and a bit of tidying
paulson <lp15@cam.ac.uk>
parents:
68721
diff
changeset
|
29 |
have *: "\<And>x. x \<in> S \<Longrightarrow> Inf S \<le> x" |
4df0628e8545
a few new lemmas and a bit of tidying
paulson <lp15@cam.ac.uk>
parents:
68721
diff
changeset
|
30 |
by (meson abs_le_iff bdd bdd_below_def cInf_lower minus_le_iff) |
63331 | 31 |
show "Sup (uminus ` S) \<le> - Inf S" |
70365
4df0628e8545
a few new lemmas and a bit of tidying
paulson <lp15@cam.ac.uk>
parents:
68721
diff
changeset
|
32 |
using \<open>S \<noteq> {}\<close> by (force intro: * cSup_least) |
63331 | 33 |
qed |
63489 | 34 |
with cSup_abs_le [of "uminus ` S"] assms show ?thesis |
35 |
by fastforce |
|
63331 | 36 |
qed |
37 |
||
38 |
lemma cSup_asclose: |
|
63489 | 39 |
fixes S :: "'a::{linordered_idom,conditionally_complete_linorder} set" |
63331 | 40 |
assumes S: "S \<noteq> {}" |
41 |
and b: "\<forall>x\<in>S. \<bar>x - l\<bar> \<le> e" |
|
42 |
shows "\<bar>Sup S - l\<bar> \<le> e" |
|
43 |
proof - |
|
63489 | 44 |
have *: "\<bar>x - l\<bar> \<le> e \<longleftrightarrow> l - e \<le> x \<and> x \<le> l + e" for x l e :: 'a |
63331 | 45 |
by arith |
46 |
have "bdd_above S" |
|
47 |
using b by (auto intro!: bdd_aboveI[of _ "l + e"]) |
|
48 |
with S b show ?thesis |
|
63489 | 49 |
unfolding * by (auto intro!: cSup_upper2 cSup_least) |
63331 | 50 |
qed |
51 |
||
52 |
lemma cInf_asclose: |
|
63489 | 53 |
fixes S :: "'a::{linordered_idom,conditionally_complete_linorder} set" |
63331 | 54 |
assumes S: "S \<noteq> {}" |
55 |
and b: "\<forall>x\<in>S. \<bar>x - l\<bar> \<le> e" |
|
56 |
shows "\<bar>Inf S - l\<bar> \<le> e" |
|
57 |
proof - |
|
63489 | 58 |
have *: "\<bar>x - l\<bar> \<le> e \<longleftrightarrow> l - e \<le> x \<and> x \<le> l + e" for x l e :: 'a |
63331 | 59 |
by arith |
60 |
have "bdd_below S" |
|
61 |
using b by (auto intro!: bdd_belowI[of _ "l - e"]) |
|
62 |
with S b show ?thesis |
|
63489 | 63 |
unfolding * by (auto intro!: cInf_lower2 cInf_greatest) |
63331 | 64 |
qed |
65 |
||
63489 | 66 |
|
60758 | 67 |
subsection \<open>Class of Archimedean fields\<close> |
30096 | 68 |
|
60758 | 69 |
text \<open>Archimedean fields have no infinite elements.\<close> |
30096 | 70 |
|
47108
2a1953f0d20d
merged fork with new numeral representation (see NEWS)
huffman
parents:
43733
diff
changeset
|
71 |
class archimedean_field = linordered_field + |
30096 | 72 |
assumes ex_le_of_int: "\<exists>z. x \<le> of_int z" |
73 |
||
63489 | 74 |
lemma ex_less_of_int: "\<exists>z. x < of_int z" |
75 |
for x :: "'a::archimedean_field" |
|
30096 | 76 |
proof - |
77 |
from ex_le_of_int obtain z where "x \<le> of_int z" .. |
|
78 |
then have "x < of_int (z + 1)" by simp |
|
79 |
then show ?thesis .. |
|
80 |
qed |
|
81 |
||
63489 | 82 |
lemma ex_of_int_less: "\<exists>z. of_int z < x" |
83 |
for x :: "'a::archimedean_field" |
|
30096 | 84 |
proof - |
85 |
from ex_less_of_int obtain z where "- x < of_int z" .. |
|
86 |
then have "of_int (- z) < x" by simp |
|
87 |
then show ?thesis .. |
|
88 |
qed |
|
89 |
||
63489 | 90 |
lemma reals_Archimedean2: "\<exists>n. x < of_nat n" |
91 |
for x :: "'a::archimedean_field" |
|
30096 | 92 |
proof - |
63489 | 93 |
obtain z where "x < of_int z" |
94 |
using ex_less_of_int .. |
|
95 |
also have "\<dots> \<le> of_int (int (nat z))" |
|
96 |
by simp |
|
97 |
also have "\<dots> = of_nat (nat z)" |
|
98 |
by (simp only: of_int_of_nat_eq) |
|
30096 | 99 |
finally show ?thesis .. |
100 |
qed |
|
101 |
||
63489 | 102 |
lemma real_arch_simple: "\<exists>n. x \<le> of_nat n" |
103 |
for x :: "'a::archimedean_field" |
|
30096 | 104 |
proof - |
63489 | 105 |
obtain n where "x < of_nat n" |
106 |
using reals_Archimedean2 .. |
|
107 |
then have "x \<le> of_nat n" |
|
108 |
by simp |
|
30096 | 109 |
then show ?thesis .. |
110 |
qed |
|
111 |
||
60758 | 112 |
text \<open>Archimedean fields have no infinitesimal elements.\<close> |
30096 | 113 |
|
62623
dbc62f86a1a9
rationalisation of theorem names esp about "real Archimedian" etc.
paulson <lp15@cam.ac.uk>
parents:
62348
diff
changeset
|
114 |
lemma reals_Archimedean: |
30096 | 115 |
fixes x :: "'a::archimedean_field" |
63489 | 116 |
assumes "0 < x" |
117 |
shows "\<exists>n. inverse (of_nat (Suc n)) < x" |
|
30096 | 118 |
proof - |
60758 | 119 |
from \<open>0 < x\<close> have "0 < inverse x" |
30096 | 120 |
by (rule positive_imp_inverse_positive) |
121 |
obtain n where "inverse x < of_nat n" |
|
62623
dbc62f86a1a9
rationalisation of theorem names esp about "real Archimedian" etc.
paulson <lp15@cam.ac.uk>
parents:
62348
diff
changeset
|
122 |
using reals_Archimedean2 .. |
30096 | 123 |
then obtain m where "inverse x < of_nat (Suc m)" |
60758 | 124 |
using \<open>0 < inverse x\<close> by (cases n) (simp_all del: of_nat_Suc) |
30096 | 125 |
then have "inverse (of_nat (Suc m)) < inverse (inverse x)" |
60758 | 126 |
using \<open>0 < inverse x\<close> by (rule less_imp_inverse_less) |
30096 | 127 |
then have "inverse (of_nat (Suc m)) < x" |
60758 | 128 |
using \<open>0 < x\<close> by (simp add: nonzero_inverse_inverse_eq) |
30096 | 129 |
then show ?thesis .. |
130 |
qed |
|
131 |
||
132 |
lemma ex_inverse_of_nat_less: |
|
133 |
fixes x :: "'a::archimedean_field" |
|
63489 | 134 |
assumes "0 < x" |
135 |
shows "\<exists>n>0. inverse (of_nat n) < x" |
|
62623
dbc62f86a1a9
rationalisation of theorem names esp about "real Archimedian" etc.
paulson <lp15@cam.ac.uk>
parents:
62348
diff
changeset
|
136 |
using reals_Archimedean [OF \<open>0 < x\<close>] by auto |
30096 | 137 |
|
138 |
lemma ex_less_of_nat_mult: |
|
139 |
fixes x :: "'a::archimedean_field" |
|
63489 | 140 |
assumes "0 < x" |
141 |
shows "\<exists>n. y < of_nat n * x" |
|
30096 | 142 |
proof - |
63489 | 143 |
obtain n where "y / x < of_nat n" |
144 |
using reals_Archimedean2 .. |
|
145 |
with \<open>0 < x\<close> have "y < of_nat n * x" |
|
146 |
by (simp add: pos_divide_less_eq) |
|
30096 | 147 |
then show ?thesis .. |
148 |
qed |
|
149 |
||
150 |
||
60758 | 151 |
subsection \<open>Existence and uniqueness of floor function\<close> |
30096 | 152 |
|
153 |
lemma exists_least_lemma: |
|
154 |
assumes "\<not> P 0" and "\<exists>n. P n" |
|
155 |
shows "\<exists>n. \<not> P n \<and> P (Suc n)" |
|
156 |
proof - |
|
63489 | 157 |
from \<open>\<exists>n. P n\<close> have "P (Least P)" |
158 |
by (rule LeastI_ex) |
|
60758 | 159 |
with \<open>\<not> P 0\<close> obtain n where "Least P = Suc n" |
30096 | 160 |
by (cases "Least P") auto |
63489 | 161 |
then have "n < Least P" |
162 |
by simp |
|
163 |
then have "\<not> P n" |
|
164 |
by (rule not_less_Least) |
|
30096 | 165 |
then have "\<not> P n \<and> P (Suc n)" |
60758 | 166 |
using \<open>P (Least P)\<close> \<open>Least P = Suc n\<close> by simp |
30096 | 167 |
then show ?thesis .. |
168 |
qed |
|
169 |
||
170 |
lemma floor_exists: |
|
171 |
fixes x :: "'a::archimedean_field" |
|
172 |
shows "\<exists>z. of_int z \<le> x \<and> x < of_int (z + 1)" |
|
63489 | 173 |
proof (cases "0 \<le> x") |
174 |
case True |
|
175 |
then have "\<not> x < of_nat 0" |
|
176 |
by simp |
|
30096 | 177 |
then have "\<exists>n. \<not> x < of_nat n \<and> x < of_nat (Suc n)" |
62623
dbc62f86a1a9
rationalisation of theorem names esp about "real Archimedian" etc.
paulson <lp15@cam.ac.uk>
parents:
62348
diff
changeset
|
178 |
using reals_Archimedean2 by (rule exists_least_lemma) |
30096 | 179 |
then obtain n where "\<not> x < of_nat n \<and> x < of_nat (Suc n)" .. |
63489 | 180 |
then have "of_int (int n) \<le> x \<and> x < of_int (int n + 1)" |
181 |
by simp |
|
30096 | 182 |
then show ?thesis .. |
183 |
next |
|
63489 | 184 |
case False |
185 |
then have "\<not> - x \<le> of_nat 0" |
|
186 |
by simp |
|
30096 | 187 |
then have "\<exists>n. \<not> - x \<le> of_nat n \<and> - x \<le> of_nat (Suc n)" |
62623
dbc62f86a1a9
rationalisation of theorem names esp about "real Archimedian" etc.
paulson <lp15@cam.ac.uk>
parents:
62348
diff
changeset
|
188 |
using real_arch_simple by (rule exists_least_lemma) |
30096 | 189 |
then obtain n where "\<not> - x \<le> of_nat n \<and> - x \<le> of_nat (Suc n)" .. |
63489 | 190 |
then have "of_int (- int n - 1) \<le> x \<and> x < of_int (- int n - 1 + 1)" |
191 |
by simp |
|
30096 | 192 |
then show ?thesis .. |
193 |
qed |
|
194 |
||
63489 | 195 |
lemma floor_exists1: "\<exists>!z. of_int z \<le> x \<and> x < of_int (z + 1)" |
196 |
for x :: "'a::archimedean_field" |
|
30096 | 197 |
proof (rule ex_ex1I) |
198 |
show "\<exists>z. of_int z \<le> x \<and> x < of_int (z + 1)" |
|
199 |
by (rule floor_exists) |
|
200 |
next |
|
63489 | 201 |
fix y z |
202 |
assume "of_int y \<le> x \<and> x < of_int (y + 1)" |
|
203 |
and "of_int z \<le> x \<and> x < of_int (z + 1)" |
|
54281 | 204 |
with le_less_trans [of "of_int y" "x" "of_int (z + 1)"] |
63489 | 205 |
le_less_trans [of "of_int z" "x" "of_int (y + 1)"] show "y = z" |
206 |
by (simp del: of_int_add) |
|
30096 | 207 |
qed |
208 |
||
209 |
||
60758 | 210 |
subsection \<open>Floor function\<close> |
30096 | 211 |
|
43732
6b2bdc57155b
adding a floor_ceiling type class for different instantiations of floor (changeset from Brian Huffman)
bulwahn
parents:
43704
diff
changeset
|
212 |
class floor_ceiling = archimedean_field + |
61942 | 213 |
fixes floor :: "'a \<Rightarrow> int" ("\<lfloor>_\<rfloor>") |
214 |
assumes floor_correct: "of_int \<lfloor>x\<rfloor> \<le> x \<and> x < of_int (\<lfloor>x\<rfloor> + 1)" |
|
30096 | 215 |
|
63489 | 216 |
lemma floor_unique: "of_int z \<le> x \<Longrightarrow> x < of_int z + 1 \<Longrightarrow> \<lfloor>x\<rfloor> = z" |
30096 | 217 |
using floor_correct [of x] floor_exists1 [of x] by auto |
218 |
||
66515 | 219 |
lemma floor_eq_iff: "\<lfloor>x\<rfloor> = a \<longleftrightarrow> of_int a \<le> x \<and> x < of_int a + 1" |
220 |
using floor_correct floor_unique by auto |
|
59613
7103019278f0
The function frac. Various lemmas about limits, series, the exp function, etc.
paulson <lp15@cam.ac.uk>
parents:
58889
diff
changeset
|
221 |
|
61942 | 222 |
lemma of_int_floor_le [simp]: "of_int \<lfloor>x\<rfloor> \<le> x" |
30096 | 223 |
using floor_correct .. |
224 |
||
61942 | 225 |
lemma le_floor_iff: "z \<le> \<lfloor>x\<rfloor> \<longleftrightarrow> of_int z \<le> x" |
30096 | 226 |
proof |
61942 | 227 |
assume "z \<le> \<lfloor>x\<rfloor>" |
228 |
then have "(of_int z :: 'a) \<le> of_int \<lfloor>x\<rfloor>" by simp |
|
229 |
also have "of_int \<lfloor>x\<rfloor> \<le> x" by (rule of_int_floor_le) |
|
30096 | 230 |
finally show "of_int z \<le> x" . |
231 |
next |
|
232 |
assume "of_int z \<le> x" |
|
61942 | 233 |
also have "x < of_int (\<lfloor>x\<rfloor> + 1)" using floor_correct .. |
234 |
finally show "z \<le> \<lfloor>x\<rfloor>" by (simp del: of_int_add) |
|
30096 | 235 |
qed |
236 |
||
61942 | 237 |
lemma floor_less_iff: "\<lfloor>x\<rfloor> < z \<longleftrightarrow> x < of_int z" |
30096 | 238 |
by (simp add: not_le [symmetric] le_floor_iff) |