author | paulson |
Tue, 10 Feb 2004 12:02:11 +0100 | |
changeset 14378 | 69c4d5997669 |
parent 14371 | c78c7da09519 |
permissions | -rw-r--r-- |
13957 | 1 |
(* Title : NSPrimes.ML |
2 |
Author : Jacques D. Fleuriot |
|
3 |
Copyright : 2002 University of Edinburgh |
|
4 |
Description : The nonstandard primes as an extension of |
|
5 |
the prime numbers |
|
6 |
*) |
|
7 |
||
8 |
(*--------------------------------------------------------------*) |
|
9 |
(* A "choice" theorem for ultrafilters cf. almost everywhere *) |
|
10 |
(* quantification *) |
|
11 |
(*--------------------------------------------------------------*) |
|
12 |
||
13 |
Goal "{n. EX m. Q n m} : FreeUltrafilterNat \ |
|
14 |
\ ==> EX f. {n. Q n (f n)} : FreeUltrafilterNat"; |
|
15 |
by (res_inst_tac [("x","%n. (@x. Q n x)")] exI 1); |
|
16 |
by (Ultra_tac 1 THEN rtac someI 1 THEN Auto_tac); |
|
17 |
qed "UF_choice"; |
|
18 |
||
19 |
Goal "({n. P n} : FreeUltrafilterNat --> {n. Q n} : FreeUltrafilterNat) = \ |
|
20 |
\ ({n. P n --> Q n} : FreeUltrafilterNat)"; |
|
21 |
by Auto_tac; |
|
22 |
by (ALLGOALS(Ultra_tac)); |
|
23 |
qed "UF_if"; |
|
24 |
||
25 |
Goal "({n. P n} : FreeUltrafilterNat & {n. Q n} : FreeUltrafilterNat) = \ |
|
26 |
\ ({n. P n & Q n} : FreeUltrafilterNat)"; |
|
27 |
by Auto_tac; |
|
28 |
by (ALLGOALS(Ultra_tac)); |
|
29 |
qed "UF_conj"; |
|
30 |
||
31 |
Goal "(ALL f. {n. Q n (f n)} : FreeUltrafilterNat) = \ |
|
32 |
\ ({n. ALL m. Q n m} : FreeUltrafilterNat)"; |
|
33 |
by Auto_tac; |
|
34 |
by (Ultra_tac 2); |
|
35 |
by (rtac ccontr 1); |
|
36 |
by (rtac swap 1 THEN assume_tac 2); |
|
37 |
by (simp_tac (simpset() addsimps [FreeUltrafilterNat_Compl_iff1, |
|
38 |
CLAIM "-{n. Q n} = {n. ~ Q n}"]) 1); |
|
39 |
by (rtac UF_choice 1); |
|
40 |
by (Ultra_tac 1 THEN Auto_tac); |
|
41 |
qed "UF_choice_ccontr"; |
|
42 |
||
43 |
Goal "ALL M. EX N. 0 < N & (ALL m. 0 < m & (m::nat) <= M --> m dvd N)"; |
|
44 |
by (rtac allI 1); |
|
45 |
by (induct_tac "M" 1); |
|
46 |
by Auto_tac; |
|
47 |
by (res_inst_tac [("x","N * (Suc n)")] exI 1); |
|
48 |
by (Step_tac 1 THEN Force_tac 1); |
|
49 |
by (dtac le_imp_less_or_eq 1 THEN etac disjE 1); |
|
50 |
by (force_tac (claset() addSIs [dvd_mult2],simpset()) 1); |
|
51 |
by (force_tac (claset() addSIs [dvd_mult],simpset()) 1); |
|
52 |
qed "dvd_by_all"; |
|
53 |
||
54 |
bind_thm ("dvd_by_all2",dvd_by_all RS spec); |
|
55 |
||
56 |
Goal "(EX (x::hypnat). P x) = (EX f. P (Abs_hypnat(hypnatrel `` {f})))"; |
|
57 |
by Auto_tac; |
|
58 |
by (res_inst_tac [("z","x")] eq_Abs_hypnat 1); |
|
59 |
by Auto_tac; |
|
60 |
qed "lemma_hypnat_P_EX"; |
|
61 |
||
62 |
Goal "(ALL (x::hypnat). P x) = (ALL f. P (Abs_hypnat(hypnatrel `` {f})))"; |
|
63 |
by Auto_tac; |
|
64 |
by (res_inst_tac [("z","x")] eq_Abs_hypnat 1); |
|
65 |
by Auto_tac; |
|
66 |
qed "lemma_hypnat_P_ALL"; |
|
67 |
||
68 |
Goalw [hdvd_def] |
|
69 |
"(Abs_hypnat(hypnatrel``{%n. X n}) hdvd \ |
|
70 |
\ Abs_hypnat(hypnatrel``{%n. Y n})) = \ |
|
71 |
\ ({n. X n dvd Y n} : FreeUltrafilterNat)"; |
|
72 |
by (Auto_tac THEN Ultra_tac 1); |
|
73 |
qed "hdvd"; |
|
74 |
||
75 |
Goal "(hypnat_of_nat n <= 0) = (n = 0)"; |
|
76 |
by (stac (hypnat_of_nat_zero RS sym) 1); |
|
14371
c78c7da09519
Conversion of HyperNat to Isar format and its declaration as a semiring
paulson
parents:
13957
diff
changeset
|
77 |
by Auto_tac; |
13957 | 78 |
qed "hypnat_of_nat_le_zero_iff"; |
79 |
Addsimps [hypnat_of_nat_le_zero_iff]; |
|
80 |
||
81 |
||
82 |
(* Goldblatt: Exercise 5.11(2) - p. 57 *) |
|
83 |
Goal "ALL M. EX N. 0 < N & (ALL m. 0 < m & (m::hypnat) <= M --> m hdvd N)"; |
|
84 |
by (Step_tac 1); |
|
85 |
by (res_inst_tac [("z","M")] eq_Abs_hypnat 1); |
|
86 |
by (auto_tac (claset(),simpset() addsimps [lemma_hypnat_P_EX, |
|
87 |
lemma_hypnat_P_ALL,hypnat_zero_def,hypnat_le,hypnat_less,hdvd])); |
|
88 |
by (cut_facts_tac [dvd_by_all] 1); |
|
89 |
by (dtac (CLAIM "(ALL (M::nat). EX N. 0 < N & (ALL m. 0 < m & m <= M \ |
|
90 |
\ --> m dvd N)) \ |
|
91 |
\ ==> ALL (n::nat). EX N. 0 < N & (ALL m. 0 < (m::nat) & m <= (x n) \ |
|
92 |
\ --> m dvd N)") 1); |
|
93 |
by (dtac choice 1); |
|
94 |
by (Step_tac 1); |
|
95 |
by (res_inst_tac [("x","f")] exI 1); |
|
96 |
by Auto_tac; |
|
97 |
by (ALLGOALS(Ultra_tac)); |
|
98 |
by Auto_tac; |
|
99 |
qed "hdvd_by_all"; |
|
100 |
||
101 |
bind_thm ("hdvd_by_all2",hdvd_by_all RS spec); |
|
102 |
||
103 |
(* Goldblatt: Exercise 5.11(2) - p. 57 *) |
|
104 |
Goal "EX (N::hypnat). 0 < N & (ALL n : - {0::nat}. hypnat_of_nat(n) hdvd N)"; |
|
105 |
by (cut_facts_tac [hdvd_by_all] 1); |
|
106 |
by (dres_inst_tac [("x","whn")] spec 1); |
|
107 |
by Auto_tac; |
|
108 |
by (rtac exI 1 THEN Auto_tac); |
|
109 |
by (dres_inst_tac [("x","hypnat_of_nat n")] spec 1); |
|
14371
c78c7da09519
Conversion of HyperNat to Isar format and its declaration as a semiring
paulson
parents:
13957
diff
changeset
|
110 |
by (auto_tac (claset(), |
c78c7da09519
Conversion of HyperNat to Isar format and its declaration as a semiring
paulson
parents:
13957
diff
changeset
|
111 |
simpset() addsimps [linorder_not_less, hypnat_of_nat_zero_iff])); |
13957 | 112 |
qed "hypnat_dvd_all_hypnat_of_nat"; |
113 |
||
114 |
||
115 |
(*--------------------------------------------------------------*) |
|
116 |
(* the nonstandard extension of the set prime numbers consists *) |
|
117 |
(* of precisely those hypernaturals > 1 that have no nontrivial *) |
|
118 |
(* factors *) |
|
119 |
(*--------------------------------------------------------------*) |
|
120 |
||
121 |
(* Goldblatt: Exercise 5.11(3a) - p 57 *) |
|
122 |
Goalw [starprime_def,thm "prime_def"] |
|
123 |
"starprime = {p. 1 < p & (ALL m. m hdvd p --> m = 1 | m = p)}"; |
|
124 |
by (auto_tac (claset(),simpset() addsimps |
|
125 |
[CLAIM "{p. Q(p) & R(p)} = {p. Q(p)} Int {p. R(p)}",NatStar_Int])); |
|
126 |
by (ALLGOALS(res_inst_tac [("z","x")] eq_Abs_hypnat)); |
|
127 |
by (res_inst_tac [("z","m")] eq_Abs_hypnat 2); |
|
128 |
by (auto_tac (claset(),simpset() addsimps [hdvd,hypnat_one_def,hypnat_less, |
|
129 |
lemma_hypnat_P_ALL,starsetNat_def])); |
|
130 |
by (dtac bspec 1 THEN dtac bspec 2 THEN Auto_tac); |
|
131 |
by (Ultra_tac 1 THEN Ultra_tac 1); |
|
132 |
by (rtac ccontr 1); |
|
133 |
by (dtac FreeUltrafilterNat_Compl_mem 1); |
|
134 |
by (auto_tac (claset(),simpset() addsimps [CLAIM "- {p. Q p} = {p. ~ Q p}"])); |
|
135 |
by (dtac UF_choice 1 THEN Auto_tac); |
|
136 |
by (dres_inst_tac [("x","f")] spec 1 THEN Auto_tac); |
|
137 |
by (ALLGOALS(Ultra_tac)); |
|
138 |
qed "starprime"; |
|
139 |
||
140 |
Goalw [thm "prime_def"] "2 : prime"; |
|
141 |
by Auto_tac; |
|
142 |
by (ftac dvd_imp_le 1); |
|
143 |
by (auto_tac (claset() addDs [dvd_0_left],simpset() addsimps |
|
144 |
[ARITH_PROVE "(m <= (2::nat)) = (m = 0 | m = 1 | m = 2)"])); |
|
145 |
qed "prime_two"; |
|
146 |
Addsimps [prime_two]; |
|
147 |
||
148 |
(* proof uses course-of-value induction *) |
|
149 |
Goal "Suc 0 < n --> (EX k : prime. k dvd n)"; |
|
150 |
by (res_inst_tac [("n","n")] nat_less_induct 1); |
|
151 |
by Auto_tac; |
|
152 |
by (case_tac "n : prime" 1); |
|
153 |
by (res_inst_tac [("x","n")] bexI 1 THEN Auto_tac); |
|
154 |
by (dtac (conjI RS (thm "not_prime_ex_mk")) 1 THEN Auto_tac); |
|
155 |
by (dres_inst_tac [("x","m")] spec 1 THEN Auto_tac); |
|
156 |
by (res_inst_tac [("x","ka")] bexI 1); |
|
157 |
by (auto_tac (claset() addIs [dvd_mult2],simpset())); |
|
158 |
qed_spec_mp "prime_factor_exists"; |
|
159 |
||
160 |
(* Goldblatt Exercise 5.11(3b) - p 57 *) |
|
161 |
Goal "1 < n ==> (EX k : starprime. k hdvd n)"; |
|
162 |
by (res_inst_tac [("z","n")] eq_Abs_hypnat 1); |
|
163 |
by (auto_tac (claset(),simpset() addsimps [hypnat_one_def, |
|
164 |
hypnat_less,starprime_def,lemma_hypnat_P_EX,lemma_hypnat_P_ALL, |
|
165 |
hdvd,starsetNat_def,CLAIM "(ALL X: S. P X) = (ALL X. X : S --> P X)", |
|
166 |
UF_if])); |
|
167 |
by (res_inst_tac [("x","%n. @y. y : prime & y dvd x n")] exI 1); |
|
168 |
by Auto_tac; |
|
169 |
by (ALLGOALS (Ultra_tac)); |
|
170 |
by (dtac sym 1 THEN Asm_simp_tac 1); |
|
171 |
by (ALLGOALS(rtac someI2_ex)); |
|
172 |
by (auto_tac (claset() addSDs [prime_factor_exists],simpset())); |
|
173 |
qed_spec_mp "hyperprime_factor_exists"; |
|
174 |
||
175 |
(* behaves as expected! *) |
|
176 |
Goal "( *sNat* insert x A) = insert (hypnat_of_nat x) ( *sNat* A)"; |
|
177 |
by (auto_tac (claset(),simpset() addsimps [starsetNat_def, |
|
14378
69c4d5997669
generic of_nat and of_int functions, and generalization of iszero
paulson
parents:
14371
diff
changeset
|
178 |
hypnat_of_nat_eq])); |
13957 | 179 |
by (ALLGOALS(res_inst_tac [("z","xa")] eq_Abs_hypnat)); |
180 |
by Auto_tac; |
|
181 |
by (TRYALL(dtac bspec)); |
|
182 |
by Auto_tac; |
|
183 |
by (ALLGOALS(Ultra_tac)); |
|
184 |
qed "NatStar_insert"; |
|
185 |
||
186 |
(* Goldblatt Exercise 3.10(1) - p. 29 *) |
|
187 |
Goal "finite A ==> *sNat* A = hypnat_of_nat ` A"; |
|
188 |
by (res_inst_tac [("P","%x. *sNat* x = hypnat_of_nat ` x")] finite_induct 1); |
|
189 |
by (auto_tac (claset(),simpset() addsimps [NatStar_insert])); |
|
190 |
qed "NatStar_hypnat_of_nat"; |
|
191 |
||
192 |
(* proved elsewhere? *) |
|
193 |
Goal "{x} ~: FreeUltrafilterNat"; |
|
194 |
by (auto_tac (claset() addSIs [FreeUltrafilterNat_finite],simpset())); |
|
195 |
qed "FreeUltrafilterNat_singleton_not_mem"; |
|
196 |
Addsimps [FreeUltrafilterNat_singleton_not_mem]; |
|
197 |
||
198 |
(*-------------------------------------------------------------------------------*) |
|
199 |
(* Another characterization of infinite set of natural numbers *) |
|
200 |
(*-------------------------------------------------------------------------------*) |
|
201 |
||
202 |
Goal "finite N ==> EX n. (ALL i:N. i<(n::nat))"; |
|
203 |
by (eres_inst_tac [("F","N")] finite_induct 1); |
|
204 |
by Auto_tac; |
|
205 |
by (res_inst_tac [("x","Suc n + x")] exI 1); |
|
206 |
by Auto_tac; |
|
207 |
qed "finite_nat_set_bounded"; |
|
208 |
||
209 |
Goal "finite N = (EX n. (ALL i:N. i<(n::nat)))"; |
|
210 |
by (blast_tac (claset() addIs [finite_nat_set_bounded, |
|
211 |
bounded_nat_set_is_finite]) 1); |
|
212 |
qed "finite_nat_set_bounded_iff"; |
|
213 |
||
214 |
Goal "(~ finite N) = (ALL n. EX i:N. n <= (i::nat))"; |
|
215 |
by (auto_tac (claset(),simpset() addsimps [finite_nat_set_bounded_iff, |
|
216 |
le_def])); |
|
217 |
qed "not_finite_nat_set_iff"; |
|
218 |
||
219 |
Goal "(ALL i:N. i<=(n::nat)) ==> finite N"; |
|
220 |
by (rtac finite_subset 1); |
|
221 |
by (rtac finite_atMost 2); |
|
222 |
by Auto_tac; |
|
223 |
qed "bounded_nat_set_is_finite2"; |
|
224 |
||
225 |
Goal "finite N ==> EX n. (ALL i:N. i<=(n::nat))"; |
|
226 |
by (eres_inst_tac [("F","N")] finite_induct 1); |
|
227 |
by Auto_tac; |
|
228 |
by (res_inst_tac [("x","n + x")] exI 1); |
|
229 |
by Auto_tac; |
|
230 |
qed "finite_nat_set_bounded2"; |
|
231 |
||
232 |
Goal "finite N = (EX n. (ALL i:N. i<=(n::nat)))"; |
|
233 |
by (blast_tac (claset() addIs [finite_nat_set_bounded2, |
|
234 |
bounded_nat_set_is_finite2]) 1); |
|
235 |
qed "finite_nat_set_bounded_iff2"; |
|
236 |
||
237 |
Goal "(~ finite N) = (ALL n. EX i:N. n < (i::nat))"; |
|
238 |
by (auto_tac (claset(),simpset() addsimps [finite_nat_set_bounded_iff2, |
|
239 |
le_def])); |
|
240 |
qed "not_finite_nat_set_iff2"; |
|
241 |
||
242 |
(*-------------------------------------------------------------------------------*) |
|
243 |
(* An injective function cannot define an embedded natural number *) |
|
244 |
(*-------------------------------------------------------------------------------*) |
|
245 |
||
246 |
Goal "ALL m n. m ~= n --> f n ~= f m \ |
|
247 |
\ ==> {n. f n = N} = {} | (EX m. {n. f n = N} = {m})"; |
|
248 |
by Auto_tac; |
|
249 |
by (dres_inst_tac [("x","x")] spec 1 THEN Auto_tac); |
|
250 |
by (subgoal_tac "ALL n. (f n = f x) = (x = n)" 1); |
|
251 |
by Auto_tac; |
|
252 |
qed "lemma_infinite_set_singleton"; |
|
253 |
||
14378
69c4d5997669
generic of_nat and of_int functions, and generalization of iszero
paulson
parents:
14371
diff
changeset
|
254 |
Goal "inj f ==> Abs_hypnat(hypnatrel `` {f}) ~: Nats"; |
69c4d5997669
generic of_nat and of_int functions, and generalization of iszero
paulson
parents:
14371
diff
changeset
|
255 |
by (auto_tac (claset(), simpset() addsimps [SHNat_eq,hypnat_of_nat_eq])); |
13957 | 256 |
by (subgoal_tac "ALL m n. m ~= n --> f n ~= f m" 1); |
257 |
by Auto_tac; |
|
258 |
by (dtac injD 2); |
|
259 |
by (assume_tac 2 THEN Force_tac 2); |
|
260 |
by (dres_inst_tac[("N","N")] lemma_infinite_set_singleton 1); |
|
261 |
by Auto_tac; |
|
262 |
qed "inj_fun_not_hypnat_in_SHNat"; |
|
263 |
||
264 |
Goalw [starsetNat_def] |
|
265 |
"range f <= A ==> Abs_hypnat(hypnatrel `` {f}) : *sNat* A"; |
|
266 |
by Auto_tac; |
|
267 |
by (Ultra_tac 1); |
|
268 |
by (dres_inst_tac [("c","f x")] subsetD 1); |
|
269 |
by (rtac rangeI 1); |
|
270 |
by Auto_tac; |
|
271 |
qed "range_subset_mem_starsetNat"; |
|
272 |
||
273 |
(*--------------------------------------------------------------------------------*) |
|
274 |
(* Gleason Proposition 11-5.5. pg 149, pg 155 (ex. 3) and pg. 360 *) |
|
275 |
(* Let E be a nonvoid ordered set with no maximal elements (note: effectively an *) |
|
276 |
(* infinite set if we take E = N (Nats)). Then there exists an order-preserving *) |
|
277 |
(* injection from N to E. Of course, (as some doofus will undoubtedly point out! *) |
|
278 |
(* :-)) can use notion of least element in proof (i.e. no need for choice) if *) |
|
279 |
(* dealing with nats as we have well-ordering property *) |
|
280 |
(*--------------------------------------------------------------------------------*) |
|
281 |
||
282 |
Goal "E ~= {} ==> EX x. EX X : (Pow E - {{}}). x: X"; |
|
283 |
by Auto_tac; |
|
284 |
val lemmaPow3 = result(); |
|
285 |
||
286 |
Goalw [choicefun_def] "E ~= {} ==> choicefun E : E"; |
|
287 |
by (rtac (lemmaPow3 RS someI2_ex) 1); |
|
288 |
by Auto_tac; |
|
289 |
qed "choicefun_mem_set"; |
|
290 |
Addsimps [choicefun_mem_set]; |
|
291 |
||
292 |
Goal "[| E ~={}; ALL x. EX y: E. x < y |] ==> injf_max n E : E"; |
|
293 |
by (induct_tac "n" 1); |
|
294 |
by (Force_tac 1); |
|
295 |
by (simp_tac (simpset() addsimps [choicefun_def]) 1); |
|
296 |
by (rtac (lemmaPow3 RS someI2_ex) 1); |
|
297 |
by Auto_tac; |
|
298 |
qed "injf_max_mem_set"; |
|
299 |
||
300 |
Goal "ALL x. EX y: E. x < y ==> injf_max n E < injf_max (Suc n) E"; |
|
301 |
by (simp_tac (simpset() addsimps [choicefun_def]) 1); |
|
302 |
by (rtac (lemmaPow3 RS someI2_ex) 1); |
|
303 |
by Auto_tac; |
|
304 |
qed "injf_max_order_preserving"; |
|
305 |
||
306 |
Goal "ALL x. EX y: E. x < y \ |
|
307 |
\ ==> ALL n m. m < n --> injf_max m E < injf_max n E"; |
|
308 |
by (rtac allI 1); |
|
309 |
by (induct_tac "n" 1); |
|
310 |
by Auto_tac; |
|
311 |
by (simp_tac (simpset() addsimps [choicefun_def]) 1); |
|
312 |
by (rtac (lemmaPow3 RS someI2_ex) 1); |
|
313 |
by Auto_tac; |
|
314 |
by (dtac (CLAIM "m < Suc n ==> m = n | m < n") 1); |
|
315 |
by Auto_tac; |
|
316 |
by (dres_inst_tac [("x","m")] spec 1); |
|
317 |
by Auto_tac; |
|
318 |
by (dtac subsetD 1 THEN Auto_tac); |
|
319 |
by (dres_inst_tac [("x","injf_max m E")] order_less_trans 1); |
|
320 |
by Auto_tac; |
|
321 |
qed "injf_max_order_preserving2"; |
|
322 |
||
323 |
Goal "ALL x. EX y: E. x < y ==> inj (%n. injf_max n E)"; |
|
324 |
by (rtac injI 1); |
|
325 |
by (rtac ccontr 1); |
|
326 |
by Auto_tac; |
|
327 |
by (dtac injf_max_order_preserving2 1); |
|
328 |
by (cut_inst_tac [("m","x"),("n","y")] less_linear 1); |
|
329 |
by Auto_tac; |
|
330 |
by (auto_tac (claset() addSDs [spec],simpset())); |
|
331 |
qed "inj_injf_max"; |
|
332 |
||
333 |
Goal "[| (E::('a::{order} set)) ~= {}; ALL x. EX y: E. x < y |] \ |
|
334 |
\ ==> EX f. range f <= E & inj (f::nat => 'a) & (ALL m. f m < f(Suc m))"; |
|
335 |
by (res_inst_tac [("x","%n. injf_max n E")] exI 1); |
|
336 |
by (Step_tac 1); |
|
337 |
by (rtac injf_max_mem_set 1); |
|
338 |
by (rtac inj_injf_max 3); |
|
339 |
by (rtac injf_max_order_preserving 4); |
|
340 |
by Auto_tac; |
|
341 |
qed "infinite_set_has_order_preserving_inj"; |
|
342 |
||
343 |
(*-------------------------------------------------------------------------------*) |
|
344 |
(* Only need fact that we can have an injective function from N to A for proof *) |
|
345 |
(*-------------------------------------------------------------------------------*) |
|
346 |
||
347 |
Goal "~ finite A ==> hypnat_of_nat ` A < ( *sNat* A)"; |
|
348 |
by Auto_tac; |
|
349 |
by (rtac subsetD 1); |
|
350 |
by (rtac NatStar_hypreal_of_real_image_subset 1); |
|
351 |
by Auto_tac; |
|
352 |
by (subgoal_tac "A ~= {}" 1); |
|
353 |
by (Force_tac 2); |
|
354 |
by (dtac infinite_set_has_order_preserving_inj 1); |
|
355 |
by (etac (not_finite_nat_set_iff2 RS iffD1) 1); |
|
356 |
by Auto_tac; |
|
357 |
by (dtac inj_fun_not_hypnat_in_SHNat 1); |
|
358 |
by (dtac range_subset_mem_starsetNat 1); |
|
14378
69c4d5997669
generic of_nat and of_int functions, and generalization of iszero
paulson
parents:
14371
diff
changeset
|
359 |
by (auto_tac (claset(),simpset() addsimps [SHNat_eq])); |
13957 | 360 |
qed "hypnat_infinite_has_nonstandard"; |
361 |
||
362 |
Goal "*sNat* A = hypnat_of_nat ` A ==> finite A"; |
|
363 |
by (rtac ccontr 1); |
|
364 |
by (auto_tac (claset() addDs [hypnat_infinite_has_nonstandard], |
|
365 |
simpset())); |
|
366 |
qed "starsetNat_eq_hypnat_of_nat_image_finite"; |
|
367 |
||
368 |
Goal "( *sNat* A = hypnat_of_nat ` A) = (finite A)"; |
|
369 |
by (blast_tac (claset() addSIs [starsetNat_eq_hypnat_of_nat_image_finite, |
|
370 |
NatStar_hypnat_of_nat]) 1); |
|
371 |
qed "finite_starsetNat_iff"; |
|
372 |
||
373 |
Goal "(~ finite A) = (hypnat_of_nat ` A < *sNat* A)"; |
|
374 |
by (rtac iffI 1); |
|
375 |
by (blast_tac (claset() addSIs [hypnat_infinite_has_nonstandard]) 1); |
|
376 |
by (auto_tac (claset(),simpset() addsimps [finite_starsetNat_iff RS sym])); |
|
377 |
qed "hypnat_infinite_has_nonstandard_iff"; |
|
378 |
||
379 |
||
380 |
(*-------------------------------------------------------------------------------*) |
|
381 |
(* Existence of infinitely many primes: a nonstandard proof *) |
|
382 |
(*-------------------------------------------------------------------------------*) |
|
383 |
||
384 |
Goal "~ (ALL n:- {0}. hypnat_of_nat n hdvd 1)"; |
|
385 |
by Auto_tac; |
|
386 |
by (res_inst_tac [("x","2")] bexI 1); |
|
14378
69c4d5997669
generic of_nat and of_int functions, and generalization of iszero
paulson
parents:
14371
diff
changeset
|
387 |
by (auto_tac (claset(),simpset() addsimps [hypnat_of_nat_eq, |
13957 | 388 |
hypnat_one_def,hdvd,dvd_def])); |
389 |
val lemma_not_dvd_hypnat_one = result(); |
|
390 |
Addsimps [lemma_not_dvd_hypnat_one]; |
|
391 |
||
392 |
Goal "EX n:- {0}. ~ hypnat_of_nat n hdvd 1"; |
|
393 |
by (cut_facts_tac [lemma_not_dvd_hypnat_one] 1); |
|
394 |
by (auto_tac (claset(),simpset() delsimps [lemma_not_dvd_hypnat_one])); |
|
395 |
val lemma_not_dvd_hypnat_one2 = result(); |
|
396 |
Addsimps [lemma_not_dvd_hypnat_one2]; |
|
397 |
||
398 |
(* not needed here *) |
|
399 |
Goalw [hypnat_zero_def,hypnat_one_def] |
|
400 |
"[| 0 < (N::hypnat); N ~= 1 |] ==> 1 < N"; |
|
401 |
by (res_inst_tac [("z","N")] eq_Abs_hypnat 1); |
|
402 |
by (auto_tac (claset(),simpset() addsimps [hypnat_less])); |
|
403 |
by (Ultra_tac 1); |
|
404 |
qed "hypnat_gt_zero_gt_one"; |
|
405 |
||
406 |
Goalw [hypnat_zero_def,hypnat_one_def] |
|
407 |
"0 < N ==> 1 < (N::hypnat) + 1"; |
|
408 |
by (res_inst_tac [("z","N")] eq_Abs_hypnat 1); |
|
409 |
by (auto_tac (claset(),simpset() addsimps [hypnat_less,hypnat_add])); |
|
410 |
qed "hypnat_add_one_gt_one"; |
|
411 |
||
412 |
Goal "0 ~: prime"; |
|
413 |
by (Step_tac 1); |
|
414 |
by (dtac (thm "prime_g_zero") 1); |
|
415 |
by Auto_tac; |
|
416 |
qed "zero_not_prime"; |
|
417 |
Addsimps [zero_not_prime]; |
|
418 |
||
14378
69c4d5997669
generic of_nat and of_int functions, and generalization of iszero
paulson
parents:
14371
diff
changeset
|
419 |
Goal "hypnat_of_nat 0 ~: starprime"; |
69c4d5997669
generic of_nat and of_int functions, and generalization of iszero
paulson
parents:
14371
diff
changeset
|
420 |
by (auto_tac (claset() addSIs [bexI], |
69c4d5997669
generic of_nat and of_int functions, and generalization of iszero
paulson
parents:
14371
diff
changeset
|
421 |
simpset() addsimps [starprime_def,starsetNat_def,hypnat_of_nat_eq])); |
13957 | 422 |
qed "hypnat_of_nat_zero_not_prime"; |
423 |
Addsimps [hypnat_of_nat_zero_not_prime]; |
|
424 |
||
425 |
Goalw [starprime_def,starsetNat_def,hypnat_zero_def] |
|
426 |
"0 ~: starprime"; |
|
427 |
by (auto_tac (claset() addSIs [bexI],simpset())); |
|
428 |
qed "hypnat_zero_not_prime"; |
|
429 |
Addsimps [hypnat_zero_not_prime]; |
|
430 |
||
431 |
Goal "1 ~: prime"; |
|
432 |
by (Step_tac 1); |
|
433 |
by (dtac (thm "prime_g_one") 1); |
|
434 |
by Auto_tac; |
|
435 |
qed "one_not_prime"; |
|
436 |
Addsimps [one_not_prime]; |
|
437 |
||
438 |
Goal "Suc 0 ~: prime"; |
|
439 |
by (Step_tac 1); |
|
440 |
by (dtac (thm "prime_g_one") 1); |
|
441 |
by Auto_tac; |
|
442 |
qed "one_not_prime2"; |
|
443 |
Addsimps [one_not_prime2]; |
|
444 |
||
14378
69c4d5997669
generic of_nat and of_int functions, and generalization of iszero
paulson
parents:
14371
diff
changeset
|
445 |
Goal "hypnat_of_nat 1 ~: starprime"; |
69c4d5997669
generic of_nat and of_int functions, and generalization of iszero
paulson
parents:
14371
diff
changeset
|
446 |
by (auto_tac (claset() addSIs [bexI], |
69c4d5997669
generic of_nat and of_int functions, and generalization of iszero
paulson
parents:
14371
diff
changeset
|
447 |
simpset() addsimps [starprime_def,starsetNat_def,hypnat_of_nat_eq])); |
13957 | 448 |
qed "hypnat_of_nat_one_not_prime"; |
449 |
Addsimps [hypnat_of_nat_one_not_prime]; |
|
450 |
||
451 |
Goalw [starprime_def,starsetNat_def,hypnat_one_def] |
|
452 |
"1 ~: starprime"; |
|
453 |
by (auto_tac (claset() addSIs [bexI],simpset())); |
|
454 |
qed "hypnat_one_not_prime"; |
|
455 |
Addsimps [hypnat_one_not_prime]; |
|
456 |
||
457 |
Goal "[| k hdvd m; k hdvd n |] ==> k hdvd (m - n)"; |
|
458 |
by (res_inst_tac [("z","k")] eq_Abs_hypnat 1); |
|
459 |
by (res_inst_tac [("z","m")] eq_Abs_hypnat 1); |
|
460 |
by (res_inst_tac [("z","n")] eq_Abs_hypnat 1); |
|
461 |
by (auto_tac (claset(),simpset() addsimps [hdvd,hypnat_minus])); |
|
462 |
by (Ultra_tac 1); |
|
463 |
by (blast_tac (claset() addIs [dvd_diff]) 1); |
|
464 |
qed "hdvd_diff"; |
|
465 |
||
466 |
Goalw [dvd_def] "x dvd (1::nat) ==> x = 1"; |
|
467 |
by Auto_tac; |
|
468 |
qed "dvd_one_eq_one"; |
|
469 |
||
470 |
Goalw [hypnat_one_def] "x hdvd 1 ==> x = 1"; |
|
471 |
by (res_inst_tac [("z","x")] eq_Abs_hypnat 1); |
|
472 |
by (auto_tac (claset(),simpset() addsimps [hdvd])); |
|
473 |
qed "hdvd_one_eq_one"; |
|
474 |
||
475 |
Goal "~ finite prime"; |
|
476 |
by (rtac (hypnat_infinite_has_nonstandard_iff RS iffD2) 1); |
|
477 |
by (cut_facts_tac [hypnat_dvd_all_hypnat_of_nat] 1); |
|
478 |
by (etac exE 1); |
|
479 |
by (etac conjE 1); |
|
480 |
by (subgoal_tac "1 < N + 1" 1); |
|
481 |
by (blast_tac (claset() addIs [hypnat_add_one_gt_one]) 2); |
|
482 |
by (dtac hyperprime_factor_exists 1); |
|
483 |
by (auto_tac (claset() addIs [NatStar_mem],simpset())); |
|
484 |
by (subgoal_tac "k ~: hypnat_of_nat ` prime" 1); |
|
485 |
by (force_tac (claset(),simpset() addsimps [starprime_def]) 1); |
|
486 |
by (Step_tac 1); |
|
487 |
by (dres_inst_tac [("x","x")] bspec 1); |
|
488 |
by (rtac ccontr 1 THEN Asm_full_simp_tac 1); |
|
489 |
by (dtac hdvd_diff 1 THEN assume_tac 1); |
|
490 |
by (auto_tac (claset() addDs [hdvd_one_eq_one],simpset())); |
|
491 |
qed "not_finite_prime"; |