author | paulson |
Thu, 15 Nov 2001 16:12:49 +0100 | |
changeset 12196 | a3be6b3a9c0b |
parent 11704 | 3c50a2cd6f00 |
permissions | -rw-r--r-- |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
1 |
(* Title: HOL/GroupTheory/Exponent |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
2 |
ID: $Id$ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
3 |
Author: Florian Kammueller, with new proofs by L C Paulson |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
4 |
Copyright 2001 University of Cambridge |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
5 |
*) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
6 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
7 |
(*** prime theorems ***) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
8 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
9 |
val prime_def = thm "prime_def"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
10 |
|
11701
3d51fbf81c17
sane numerals (stage 1): added generic 1, removed 1' and 2 on nat,
wenzelm
parents:
11506
diff
changeset
|
11 |
Goalw [prime_def] "p\\<in>prime ==> Suc 0 < p"; |
11468 | 12 |
by (force_tac (claset(), simpset() addsimps []) 1); |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
13 |
qed "prime_imp_one_less"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
14 |
|
11701
3d51fbf81c17
sane numerals (stage 1): added generic 1, removed 1' and 2 on nat,
wenzelm
parents:
11506
diff
changeset
|
15 |
Goal "(p\\<in>prime) = (Suc 0 < p & (\\<forall>a b. p dvd a*b --> (p dvd a) | (p dvd b)))"; |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
16 |
by (auto_tac (claset(), simpset() addsimps [prime_imp_one_less])); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
17 |
by (blast_tac (claset() addSDs [thm "prime_dvd_mult"]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
18 |
by (auto_tac (claset(), simpset() addsimps [prime_def])); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
19 |
by (etac dvdE 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
20 |
by (case_tac "k=0" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
21 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
22 |
by (dres_inst_tac [("x","m")] spec 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
23 |
by (dres_inst_tac [("x","k")] spec 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
24 |
by (asm_full_simp_tac |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
25 |
(simpset() addsimps [dvd_mult_cancel1, dvd_mult_cancel2]) 1); |
11468 | 26 |
by Auto_tac; |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
27 |
qed "prime_iff"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
28 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
29 |
Goal "p\\<in>prime ==> 0 < p^a"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
30 |
by (force_tac (claset(), simpset() addsimps [prime_iff]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
31 |
qed "zero_less_prime_power"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
32 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
33 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
34 |
(*First some things about HOL and sets *) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
35 |
val [p1] = goal (the_context()) "(P x y) ==> ( (x, y)\\<in>{(a,b). P a b})"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
36 |
by (rtac CollectI 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
37 |
by (rewrite_goals_tac [split RS eq_reflection]); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
38 |
by (rtac p1 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
39 |
qed "CollectI_prod"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
40 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
41 |
val [p1] = goal (the_context()) "( (x, y)\\<in>{(a,b). P a b}) ==> (P x y)"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
42 |
by (res_inst_tac [("c1","P")] (split RS subst) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
43 |
by (res_inst_tac [("a","(x,y)")] CollectD 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
44 |
by (rtac p1 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
45 |
qed "CollectD_prod"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
46 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
47 |
val [p1] = goal (the_context()) "(P x y z v) ==> ( (x, y, z, v)\\<in>{(a,b,c,d). P a b c d})"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
48 |
by (rtac CollectI_prod 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
49 |
by (rewrite_goals_tac [split RS eq_reflection]); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
50 |
by (rtac p1 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
51 |
qed "CollectI_prod4"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
52 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
53 |
Goal "( (x, y, z, v)\\<in>{(a,b,c,d). P a b c d}) ==> (P x y z v)"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
54 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
55 |
qed "CollectD_prod4"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
56 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
57 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
58 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
59 |
val [p1] = goal (the_context()) "x\\<in>{y. P(y) & Q(y)} ==> P(x)"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
60 |
by (res_inst_tac [("Q","Q x"),("P", "P x")] conjE 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
61 |
by (assume_tac 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
62 |
by (res_inst_tac [("a", "x")] CollectD 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
63 |
by (rtac p1 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
64 |
qed "subset_lemma1"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
65 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
66 |
val [p1,p2] = goal (the_context()) "[|P == Q; P|] ==> Q"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
67 |
by (fold_goals_tac [p1]); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
68 |
by (rtac p2 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
69 |
qed "apply_def"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
70 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
71 |
Goal "S \\<noteq> {} ==> \\<exists>x. x\\<in>S"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
72 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
73 |
qed "NotEmpty_ExEl"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
74 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
75 |
Goal "\\<exists>x. x: S ==> S \\<noteq> {}"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
76 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
77 |
qed "ExEl_NotEmpty"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
78 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
79 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
80 |
(* The following lemmas are needed for existsM1inM *) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
81 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
82 |
Goal "[| {} \\<notin> A; M\\<in>A |] ==> M \\<noteq> {}"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
83 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
84 |
qed "MnotEqempty"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
85 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
86 |
val [p1] = goal (the_context()) "\\<exists>g \\<in> A. x = P(g) ==> \\<exists>g \\<in> A. P(g) = x"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
87 |
by (rtac bexE 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
88 |
by (rtac p1 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
89 |
by (rtac bexI 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
90 |
by (rtac sym 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
91 |
by (assume_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
92 |
by (assume_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
93 |
qed "bex_sym"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
94 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
95 |
Goalw [equiv_def,quotient_def,sym_def,trans_def] |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
96 |
"[| equiv A r; C\\<in>A // r |] ==> \\<forall>x \\<in> C. \\<forall>y \\<in> C. (x,y)\\<in>r"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
97 |
by (Blast_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
98 |
qed "ElemClassEquiv"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
99 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
100 |
Goalw [equiv_def,quotient_def,sym_def,trans_def] |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
101 |
"[|equiv A r; M\\<in>A // r; M1\\<in>M; (M1, M2)\\<in>r |] ==> M2\\<in>M"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
102 |
by (Blast_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
103 |
qed "EquivElemClass"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
104 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
105 |
Goal "[| 0 < c; a <= b |] ==> a <= b * (c::nat)"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
106 |
by (res_inst_tac [("P","%x. x <= b * c")] subst 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
107 |
by (rtac mult_1_right 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
108 |
by (rtac mult_le_mono 1); |
11468 | 109 |
by Auto_tac; |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
110 |
qed "le_extend_mult"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
111 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
112 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
113 |
Goal "0 < card(S) ==> S \\<noteq> {}"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
114 |
by (force_tac (claset(), simpset() addsimps [card_empty]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
115 |
qed "card_nonempty"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
116 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
117 |
Goal "[| x \\<notin> F; \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
118 |
\ \\<forall>c1\\<in>insert x F. \\<forall>c2 \\<in> insert x F. c1 \\<noteq> c2 --> c1 \\<inter> c2 = {}|]\ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
119 |
\ ==> x \\<inter> \\<Union> F = {}"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
120 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
121 |
qed "insert_partition"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
122 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
123 |
(* main cardinality theorem *) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
124 |
Goal "finite C ==> \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
125 |
\ finite (\\<Union> C) --> \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
126 |
\ (\\<forall>c\\<in>C. card c = k) --> \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
127 |
\ (\\<forall>c1 \\<in> C. \\<forall>c2 \\<in> C. c1 \\<noteq> c2 --> c1 \\<inter> c2 = {}) --> \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
128 |
\ k * card(C) = card (\\<Union> C)"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
129 |
by (etac finite_induct 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
130 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
131 |
by (asm_full_simp_tac |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
132 |
(simpset() addsimps [card_insert_disjoint, card_Un_disjoint, |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
133 |
insert_partition, inst "B" "\\<Union>(insert x F)" finite_subset]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
134 |
qed_spec_mp "card_partition"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
135 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
136 |
Goal "[| finite S; S \\<noteq> {} |] ==> 0 < card(S)"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
137 |
by (swap_res_tac [card_0_eq RS iffD1] 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
138 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
139 |
qed "zero_less_card_empty"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
140 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
141 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
142 |
Goal "[| p*k dvd m*n; p\\<in>prime |] \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
143 |
\ ==> (\\<exists>x. k dvd x*n & m = p*x) | (\\<exists>y. k dvd m*y & n = p*y)"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
144 |
by (asm_full_simp_tac (simpset() addsimps [prime_iff]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
145 |
by (ftac dvd_mult_left 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
146 |
by (subgoal_tac "p dvd m | p dvd n" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
147 |
by (Blast_tac 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
148 |
by (etac disjE 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
149 |
by (rtac disjI1 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
150 |
by (rtac disjI2 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
151 |
by (eres_inst_tac [("n","m")] dvdE 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
152 |
by (eres_inst_tac [("n","n")] dvdE 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
153 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
154 |
by (res_inst_tac [("k","p")] dvd_mult_cancel 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
155 |
by (res_inst_tac [("k","p")] dvd_mult_cancel 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
156 |
by (ALLGOALS (asm_full_simp_tac (simpset() addsimps mult_ac))); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
157 |
qed "prime_dvd_cases"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
158 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
159 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
160 |
Goal "p\\<in>prime \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
161 |
\ ==> \\<forall>m n. p^c dvd m*n --> \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
162 |
\ (\\<forall>a b. a+b = Suc c --> p^a dvd m | p^b dvd n)"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
163 |
by (induct_tac "c" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
164 |
by (Clarify_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
165 |
by (case_tac "a" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
166 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
167 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
168 |
(*inductive step*) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
169 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
170 |
by (Clarify_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
171 |
by (etac (prime_dvd_cases RS disjE) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
172 |
by (assume_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
173 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
174 |
(*case 1: p dvd m*) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
175 |
by (case_tac "a" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
176 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
177 |
by (Clarify_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
178 |
by (dtac spec 1 THEN dtac spec 1 THEN mp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
179 |
by (dres_inst_tac [("x","nat")] spec 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
180 |
by (dres_inst_tac [("x","b")] spec 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
181 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
182 |
by (blast_tac (claset() addIs [dvd_refl, mult_dvd_mono]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
183 |
(*case 2: p dvd n*) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
184 |
by (case_tac "b" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
185 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
186 |
by (Clarify_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
187 |
by (dtac spec 1 THEN dtac spec 1 THEN mp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
188 |
by (dres_inst_tac [("x","a")] spec 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
189 |
by (dres_inst_tac [("x","nat")] spec 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
190 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
191 |
by (blast_tac (claset() addIs [dvd_refl, mult_dvd_mono]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
192 |
qed_spec_mp "prime_power_dvd_cases"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
193 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
194 |
(*needed in this form in Sylow.ML*) |
11468 | 195 |
Goal "[| p \\<in> prime; ~ (p ^ (Suc r) dvd n); p^(a+r) dvd n*k |] \ |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
196 |
\ ==> p ^ a dvd k"; |
11468 | 197 |
by (dres_inst_tac [("a","Suc r"), ("b","a")] prime_power_dvd_cases 1); |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
198 |
by (assume_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
199 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
200 |
qed "div_combine"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
201 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
202 |
(*Lemma for power_dvd_bound*) |
11701
3d51fbf81c17
sane numerals (stage 1): added generic 1, removed 1' and 2 on nat,
wenzelm
parents:
11506
diff
changeset
|
203 |
Goal "Suc 0 < p ==> Suc n <= p^n"; |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
204 |
by (induct_tac "n" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
205 |
by (Asm_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
206 |
by (Asm_full_simp_tac 1); |
11704
3c50a2cd6f00
* sane numerals (stage 2): plain "num" syntax (removed "#");
wenzelm
parents:
11701
diff
changeset
|
207 |
by (subgoal_tac "2 * n + 2 <= p * p^n" 1); |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
208 |
by (Asm_full_simp_tac 1); |
11704
3c50a2cd6f00
* sane numerals (stage 2): plain "num" syntax (removed "#");
wenzelm
parents:
11701
diff
changeset
|
209 |
by (subgoal_tac "2 * p^n <= p * p^n" 1); |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
210 |
(*?arith_tac should handle all of this!*) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
211 |
by (rtac order_trans 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
212 |
by (assume_tac 2); |
11704
3c50a2cd6f00
* sane numerals (stage 2): plain "num" syntax (removed "#");
wenzelm
parents:
11701
diff
changeset
|
213 |
by (dres_inst_tac [("k","2")] mult_le_mono2 1); |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
214 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
215 |
by (rtac mult_le_mono1 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
216 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
217 |
qed "Suc_le_power"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
218 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
219 |
(*An upper bound for the n such that p^n dvd a: needed for GREATEST to exist*) |
11701
3d51fbf81c17
sane numerals (stage 1): added generic 1, removed 1' and 2 on nat,
wenzelm
parents:
11506
diff
changeset
|
220 |
Goal "[|p^n dvd a; Suc 0 < p; 0 < a|] ==> n < a"; |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
221 |
by (dtac dvd_imp_le 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
222 |
by (dres_inst_tac [("n","n")] Suc_le_power 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
223 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
224 |
qed "power_dvd_bound"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
225 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
226 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
227 |
(*** exponent theorems ***) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
228 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
229 |
Goal "[|p^k dvd n; p\\<in>prime; 0<n|] ==> k <= exponent p n"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
230 |
by (asm_full_simp_tac (simpset() addsimps [exponent_def]) 1); |
11506 | 231 |
by (etac (thm "Greatest_le") 1); |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
232 |
by (blast_tac (claset() addDs [prime_imp_one_less, power_dvd_bound]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
233 |
qed_spec_mp "exponent_ge"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
234 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
235 |
Goal "0<s ==> (p ^ exponent p s) dvd s"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
236 |
by (simp_tac (simpset() addsimps [exponent_def]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
237 |
by (Clarify_tac 1); |
11506 | 238 |
by (res_inst_tac [("k","0")] (thm "GreatestI") 1); |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
239 |
by (blast_tac (claset() addDs [prime_imp_one_less, power_dvd_bound]) 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
240 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
241 |
qed "power_exponent_dvd"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
242 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
243 |
Goal "[|(p * p ^ exponent p s) dvd s; p\\<in>prime |] ==> s=0"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
244 |
by (subgoal_tac "p ^ Suc(exponent p s) dvd s" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
245 |
by (Asm_full_simp_tac 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
246 |
by (rtac ccontr 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
247 |
by (dtac exponent_ge 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
248 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
249 |
qed "power_Suc_exponent_Not_dvd"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
250 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
251 |
Goal "p\\<in>prime ==> exponent p (p^a) = a"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
252 |
by (asm_simp_tac (simpset() addsimps [exponent_def]) 1); |
11506 | 253 |
by (rtac (thm "Greatest_equality") 1); |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
254 |
by (Asm_full_simp_tac 1); |
11468 | 255 |
by (asm_simp_tac (simpset() addsimps [prime_imp_one_less, power_dvd_imp_le]) 1); |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
256 |
qed "exponent_power_eq"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
257 |
Addsimps [exponent_power_eq]; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
258 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
259 |
Goal "!r::nat. (p^r dvd a) = (p^r dvd b) ==> exponent p a = exponent p b"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
260 |
by (asm_simp_tac (simpset() addsimps [exponent_def]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
261 |
qed "exponent_equalityI"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
262 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
263 |
Goal "p \\<notin> prime ==> exponent p s = 0"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
264 |
by (asm_simp_tac (simpset() addsimps [exponent_def]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
265 |
qed "exponent_eq_0"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
266 |
Addsimps [exponent_eq_0]; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
267 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
268 |
|
11701
3d51fbf81c17
sane numerals (stage 1): added generic 1, removed 1' and 2 on nat,
wenzelm
parents:
11506
diff
changeset
|
269 |
(* exponent_mult_add, easy inclusion. Could weaken p\\<in>prime to Suc 0 < p *) |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
270 |
Goal "[| 0 < a; 0 < b |] \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
271 |
\ ==> (exponent p a) + (exponent p b) <= exponent p (a * b)"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
272 |
by (case_tac "p \\<in> prime" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
273 |
by (rtac exponent_ge 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
274 |
by (auto_tac (claset(), simpset() addsimps [power_add])); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
275 |
by (blast_tac (claset() addIs [prime_imp_one_less, power_exponent_dvd, |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
276 |
mult_dvd_mono]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
277 |
qed "exponent_mult_add1"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
278 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
279 |
(* exponent_mult_add, opposite inclusion *) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
280 |
Goal "[| 0 < a; 0 < b |] \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
281 |
\ ==> exponent p (a * b) <= (exponent p a) + (exponent p b)"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
282 |
by (case_tac "p\\<in>prime" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
283 |
by (rtac leI 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
284 |
by (Clarify_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
285 |
by (cut_inst_tac [("p","p"),("s","a*b")] power_exponent_dvd 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
286 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
287 |
by (subgoal_tac "p ^ (Suc (exponent p a + exponent p b)) dvd a * b" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
288 |
by (rtac (le_imp_power_dvd RS dvd_trans) 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
289 |
by (assume_tac 3); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
290 |
by (Asm_full_simp_tac 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
291 |
by (forw_inst_tac [("a","Suc (exponent p a)"), ("b","Suc (exponent p b)")] |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
292 |
prime_power_dvd_cases 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
293 |
by (assume_tac 1 THEN Force_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
294 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
295 |
by (blast_tac (claset() addDs [power_Suc_exponent_Not_dvd]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
296 |
qed "exponent_mult_add2"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
297 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
298 |
Goal "[| 0 < a; 0 < b |] \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
299 |
\ ==> exponent p (a * b) = (exponent p a) + (exponent p b)"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
300 |
by (blast_tac (claset() addIs [exponent_mult_add1, exponent_mult_add2, |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
301 |
order_antisym]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
302 |
qed "exponent_mult_add"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
303 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
304 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
305 |
Goal "~ (p dvd n) ==> exponent p n = 0"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
306 |
by (case_tac "exponent p n" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
307 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
308 |
by (case_tac "n" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
309 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
310 |
by (cut_inst_tac [("s","n"),("p","p")] power_exponent_dvd 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
311 |
by (auto_tac (claset() addDs [dvd_mult_left], simpset())); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
312 |
qed "not_divides_exponent_0"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
313 |
|
11701
3d51fbf81c17
sane numerals (stage 1): added generic 1, removed 1' and 2 on nat,
wenzelm
parents:
11506
diff
changeset
|
314 |
Goal "exponent p (Suc 0) = 0"; |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
315 |
by (case_tac "p \\<in> prime" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
316 |
by (auto_tac (claset(), |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
317 |
simpset() addsimps [prime_iff, not_divides_exponent_0])); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
318 |
qed "exponent_1_eq_0"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
319 |
Addsimps [exponent_1_eq_0]; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
320 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
321 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
322 |
(*** Lemmas for the main combinatorial argument ***) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
323 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
324 |
Goal "[| 0 < (m::nat); 0<k; k < p^a; (p^r) dvd (p^a)* m - k |] ==> r <= a"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
325 |
by (rtac notnotD 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
326 |
by (rtac notI 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
327 |
by (dtac (leI RSN (2, contrapos_nn) RS notnotD) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
328 |
by (assume_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
329 |
by (dres_inst_tac [("m","a")] less_imp_le 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
330 |
by (dtac le_imp_power_dvd 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
331 |
by (dres_inst_tac [("n","p ^ r")] dvd_trans 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
332 |
by (assume_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
333 |
by (forw_inst_tac [("m","k")] less_imp_le 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
334 |
by (dres_inst_tac [("c","m")] le_extend_mult 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
335 |
by (assume_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
336 |
by (dres_inst_tac [("k","p ^ a"),("m","(p ^ a) * m")] dvd_diffD1 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
337 |
by (assume_tac 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
338 |
by (rtac (dvd_refl RS dvd_mult2) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
339 |
by (dres_inst_tac [("n","k")] dvd_imp_le 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
340 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
341 |
qed "p_fac_forw_lemma"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
342 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
343 |
Goal "[| 0 < (m::nat); 0<k; k < p^a; (p^r) dvd (p^a)* m - k |] \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
344 |
\ ==> (p^r) dvd (p^a) - k"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
345 |
by (forw_inst_tac [("k1","k"),("i","p")] |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
346 |
(p_fac_forw_lemma RS le_imp_power_dvd) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
347 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
348 |
by (subgoal_tac "p^r dvd p^a*m" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
349 |
by (blast_tac (claset() addIs [dvd_mult2]) 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
350 |
by (dtac dvd_diffD1 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
351 |
by (assume_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
352 |
by (blast_tac (claset() addIs [dvd_diff]) 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
353 |
by (dtac less_imp_Suc_add 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
354 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
355 |
qed "p_fac_forw"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
356 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
357 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
358 |
Goal "[| 0 < (k::nat); k < p^a; 0 < p; (p^r) dvd (p^a) - k |] ==> r <= a"; |
11701
3d51fbf81c17
sane numerals (stage 1): added generic 1, removed 1' and 2 on nat,
wenzelm
parents:
11506
diff
changeset
|
359 |
by (res_inst_tac [("m","Suc 0")] p_fac_forw_lemma 1); |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
360 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
361 |
qed "r_le_a_forw"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
362 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
363 |
Goal "[| 0<m; 0<k; 0 < (p::nat); k < p^a; (p^r) dvd p^a - k |] \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
364 |
\ ==> (p^r) dvd (p^a)*m - k"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
365 |
by (forw_inst_tac [("k1","k"),("i","p")] (r_le_a_forw RS le_imp_power_dvd) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
366 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
367 |
by (subgoal_tac "p^r dvd p^a*m" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
368 |
by (blast_tac (claset() addIs [dvd_mult2]) 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
369 |
by (dtac dvd_diffD1 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
370 |
by (assume_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
371 |
by (blast_tac (claset() addIs [dvd_diff]) 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
372 |
by (dtac less_imp_Suc_add 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
373 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
374 |
qed "p_fac_backw"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
375 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
376 |
Goal "[| 0<m; 0<k; 0 < (p::nat); k < p^a |] \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
377 |
\ ==> exponent p (p^a * m - k) = exponent p (p^a - k)"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
378 |
by (blast_tac (claset() addIs [exponent_equalityI, p_fac_forw, |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
379 |
p_fac_backw]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
380 |
qed "exponent_p_a_m_k_equation"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
381 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
382 |
(*Suc rules that we have to delete from the simpset*) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
383 |
val bad_Sucs = [binomial_Suc_Suc, mult_Suc, mult_Suc_right]; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
384 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
385 |
(*The bound K is needed; otherwise it's too weak to be used.*) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
386 |
Goal "[| \\<forall>i. Suc i < K --> exponent p (Suc i) = exponent p (Suc(j+i))|] \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
387 |
\ ==> k<K --> exponent p ((j+k) choose k) = 0"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
388 |
by (case_tac "p \\<in> prime" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
389 |
by (Asm_simp_tac 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
390 |
by (induct_tac "k" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
391 |
by (Simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
392 |
(*induction step*) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
393 |
by (subgoal_tac "0 < (Suc(j+n) choose Suc n)" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
394 |
by (simp_tac (simpset() addsimps [zero_less_binomial_iff]) 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
395 |
by (Clarify_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
396 |
by (subgoal_tac |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
397 |
"exponent p ((Suc(j+n) choose Suc n) * Suc n) = exponent p (Suc n)" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
398 |
(*First, use the assumed equation. We simplify the LHS to |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
399 |
exponent p (Suc (j + n) choose Suc n) + exponent p (Suc n); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
400 |
the common terms cancel, proving the conclusion.*) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
401 |
by (asm_full_simp_tac (simpset() delsimps bad_Sucs |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
402 |
addsimps [exponent_mult_add]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
403 |
(*Establishing the equation requires first applying Suc_times_binomial_eq...*) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
404 |
by (asm_full_simp_tac (simpset() delsimps bad_Sucs |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
405 |
addsimps [Suc_times_binomial_eq RS sym]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
406 |
(*...then exponent_mult_add and the quantified premise.*) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
407 |
by (asm_full_simp_tac (simpset() delsimps bad_Sucs |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
408 |
addsimps [zero_less_binomial_iff, exponent_mult_add]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
409 |
qed_spec_mp "p_not_div_choose_lemma"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
410 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
411 |
(*The lemma above, with two changes of variables*) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
412 |
Goal "[| k<K; k<=n; \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
413 |
\ \\<forall>j. 0<j & j<K --> exponent p (n - k + (K - j)) = exponent p (K - j)|] \ |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
414 |
\ ==> exponent p (n choose k) = 0"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
415 |
by (cut_inst_tac [("j","n-k"),("k","k"),("p","p")] p_not_div_choose_lemma 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
416 |
by (assume_tac 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
417 |
by (Asm_full_simp_tac 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
418 |
by (Clarify_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
419 |
by (dres_inst_tac [("x","K - Suc i")] spec 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
420 |
by (asm_full_simp_tac (simpset() addsimps [Suc_diff_le]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
421 |
qed "p_not_div_choose"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
422 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
423 |
|
11701
3d51fbf81c17
sane numerals (stage 1): added generic 1, removed 1' and 2 on nat,
wenzelm
parents:
11506
diff
changeset
|
424 |
Goal "0 < m ==> exponent p ((p^a * m - Suc 0) choose (p^a - Suc 0)) = 0"; |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
425 |
by (case_tac "p \\<in> prime" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
426 |
by (Asm_simp_tac 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
427 |
by (forw_inst_tac [("a","a")] zero_less_prime_power 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
428 |
by (res_inst_tac [("K","p^a")] p_not_div_choose 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
429 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
430 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
431 |
by (case_tac "m" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
432 |
by (case_tac "p^a" 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
433 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
434 |
(*now the hard case, simplified to |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
435 |
exponent p (Suc (p ^ a * m + i - p ^ a)) = exponent p (Suc i) *) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
436 |
by (subgoal_tac "0<p" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
437 |
by (force_tac (claset() addSDs [prime_imp_one_less], simpset()) 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
438 |
by (stac exponent_p_a_m_k_equation 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
439 |
by Auto_tac; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
440 |
qed "const_p_fac_right"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
441 |
|
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
442 |
Goal "0 < m ==> exponent p (((p^a) * m) choose p^a) = exponent p m"; |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
443 |
by (case_tac "p \\<in> prime" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
444 |
by (Asm_simp_tac 2); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
445 |
by (subgoal_tac "0 < p^a * m & p^a <= p^a * m" 1); |
12196 | 446 |
by (force_tac (claset(), simpset() addsimps [prime_iff]) 2); |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
447 |
(*A similar trick to the one used in p_not_div_choose_lemma: |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
448 |
insert an equation; use exponent_mult_add on the LHS; on the RHS, first |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
449 |
transform the binomial coefficient, then use exponent_mult_add.*) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
450 |
by (subgoal_tac |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
451 |
"exponent p ((((p^a) * m) choose p^a) * p^a) = a + exponent p m" 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
452 |
by (asm_full_simp_tac (simpset() delsimps bad_Sucs |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
453 |
addsimps [zero_less_binomial_iff, exponent_mult_add, prime_iff]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
454 |
(*one subgoal left!*) |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
455 |
by (stac times_binomial_minus1_eq 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
456 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
457 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
458 |
by (stac exponent_mult_add 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
459 |
by (Asm_full_simp_tac 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
460 |
by (asm_simp_tac (simpset() addsimps [zero_less_binomial_iff]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
461 |
by (arith_tac 1); |
12196 | 462 |
by (asm_full_simp_tac (simpset() delsimps bad_Sucs |
11370
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
463 |
addsimps [exponent_mult_add, const_p_fac_right]) 1); |
680946254afe
new GroupTheory example, e.g. the Sylow theorem (preliminary version)
paulson
parents:
diff
changeset
|
464 |
qed "const_p_fac"; |