--- a/src/HOL/Algebra/Divisibility.thy Sun Sep 11 23:32:45 2016 +0200
+++ b/src/HOL/Algebra/Divisibility.thy Mon Sep 12 00:11:30 2016 +0200
@@ -187,8 +187,7 @@
and elim: "\<And>c. \<lbrakk>b = a \<otimes> c; c \<in> carrier G\<rbrakk> \<Longrightarrow> P"
shows "P"
proof -
- from dividesD[OF d]
- obtain c where "c \<in> carrier G" and "b = a \<otimes> c" by auto
+ from dividesD[OF d] obtain c where "c \<in> carrier G" and "b = a \<otimes> c" by auto
then show P by (elim elim)
qed
@@ -319,14 +318,12 @@
unfolding associated_def
proof clarify
assume "b divides a"
- then have "\<exists>u\<in>carrier G. a = b \<otimes> u" by (rule dividesD)
then obtain u where ucarr: "u \<in> carrier G" and a: "a = b \<otimes> u"
- by auto
+ by (rule dividesE)
assume "a divides b"
- then have "\<exists>u'\<in>carrier G. b = a \<otimes> u'" by (rule dividesD)
then obtain u' where u'carr: "u' \<in> carrier G" and b: "b = a \<otimes> u'"
- by auto
+ by (rule dividesE)
note carr = carr ucarr u'carr
from carr have "a \<otimes> \<one> = a" by simp
@@ -559,8 +556,7 @@
assumes advdb: "a divides b"
and neq: "\<not>(a \<sim> b)"
shows "properfactor G a b"
- apply (rule properfactorI, rule advdb)
-proof (rule ccontr, simp)
+proof (rule properfactorI, rule advdb, rule notI)
assume "b divides a"
with advdb have "a \<sim> b" by (rule associatedI)
with neq show "False" by fast
@@ -758,7 +754,7 @@
apply (elim irreducibleE, intro irreducibleI, clarify)
apply (subgoal_tac "a \<in> Units G", simp)
apply (intro prod_unit_r[of a b] carr bunit, assumption)
- apply (metis assms associatedI2 m_closed properfactor_cong_r)
+ apply (metis assms(2,3) associatedI2 m_closed properfactor_cong_r)
done
lemma (in comm_monoid) irreducible_prod_lI:
@@ -784,8 +780,7 @@
proof (cases "a \<in> Units G")
case aunit: True
have "irreducible G b"
- apply (rule irreducibleI)
- proof (rule ccontr, simp)
+ proof (rule irreducibleI, rule notI)
assume "b \<in> Units G"
with aunit have "(a \<otimes> b) \<in> Units G" by fast
with abnunit show "False" ..
@@ -804,8 +799,7 @@
then have bunit: "b \<in> Units G" by (intro isunit, simp)
have "irreducible G a"
- apply (rule irreducibleI)
- proof (rule ccontr, simp)
+ proof (rule irreducibleI, rule notI)
assume "a \<in> Units G"
with bunit have "(a \<otimes> b) \<in> Units G" by fast
with abnunit show "False" ..
@@ -1010,10 +1004,8 @@
proof (elim essentially_equalE)
fix fs
assume "as <~~> fs" "fs [\<sim>] bs"
- then have "\<exists>fs'. as [\<sim>] fs' \<and> fs' <~~> bs"
- by (rule perm_assoc_switch_r)
- then obtain fs' where a: "as [\<sim>] fs'" and p: "fs' <~~> bs"
- by auto
+ from perm_assoc_switch_r [OF this] obtain fs' where a: "as [\<sim>] fs'" and p: "fs' <~~> bs"
+ by blast
from p have "bs <~~> fs'" by (rule perm_sym)
with a[symmetric] carr show ?thesis
by (iprover intro: essentially_equalI perm_closed)
@@ -1028,11 +1020,9 @@
using ab bc
proof (elim essentially_equalE)
fix abs bcs
- assume "abs [\<sim>] bs" and pb: "bs <~~> bcs"
- then have "\<exists>bs'. abs <~~> bs' \<and> bs' [\<sim>] bcs"
- by (rule perm_assoc_switch)
- then obtain bs' where p: "abs <~~> bs'" and a: "bs' [\<sim>] bcs"
- by auto
+ assume "abs [\<sim>] bs" and pb: "bs <~~> bcs"
+ from perm_assoc_switch [OF this] obtain bs' where p: "abs <~~> bs'" and a: "bs' [\<sim>] bcs"
+ by blast
assume "as <~~> abs"
with p have pp: "as <~~> bs'" by fast
@@ -1184,10 +1174,11 @@
and wf: "wfactors G fs a"
and carr[simp]: "set fs \<subseteq> carrier G"
shows "fs = []"
-proof (rule ccontr, cases fs, simp)
- fix f fs'
- assume fs: "fs = f # fs'"
-
+proof (cases fs)
+ case Nil
+ then show ?thesis .
+next
+ case fs: (Cons f fs')
from carr have fcarr[simp]: "f \<in> carrier G" and carr'[simp]: "set fs' \<subseteq> carrier G"
by (simp_all add: fs)
@@ -1203,7 +1194,7 @@
by (simp add: Units_closed[OF aunit] a[symmetric])
finally have "f \<otimes> foldr (op \<otimes>) fs' \<one> \<in> Units G" by simp
then have "f \<in> Units G" by (intro unit_factor[of f], simp+)
- with fnunit show "False" by simp
+ with fnunit show ?thesis by contradiction
qed
@@ -1366,10 +1357,8 @@
note carr[simp] = factors_closed[OF afs ascarr] ascarr[THEN subsetD]
factors_closed[OF bfs bscarr] bscarr[THEN subsetD]
- from ab carr have "\<exists>u\<in>Units G. a = b \<otimes> u"
- by (fast elim: associatedE2)
- then obtain u where uunit: "u \<in> Units G" and a: "a = b \<otimes> u"
- by auto
+ from ab carr obtain u where uunit: "u \<in> Units G" and a: "a = b \<otimes> u"
+ by (elim associatedE2)
from uunit bscarr have ee: "essentially_equal G (bs[0 := (bs!0 \<otimes> u)]) bs"
(is "essentially_equal G ?bs' bs")
@@ -1420,10 +1409,8 @@
with anunit show False ..
qed
- have "\<exists>a'. factors G as a' \<and> a' \<sim> a"
- by (rule wfactors_factors[OF asf ascarr])
- then obtain a' where fa': "factors G as a'" and a': "a' \<sim> a"
- by auto
+ from wfactors_factors[OF asf ascarr] obtain a' where fa': "factors G as a'" and a': "a' \<sim> a"
+ by blast
from fa' ascarr have a'carr[simp]: "a' \<in> carrier G"
by fast
@@ -1436,10 +1423,8 @@
show "False" ..
qed
- have "\<exists>b'. factors G bs b' \<and> b' \<sim> b"
- by (rule wfactors_factors[OF bsf bscarr])
- then obtain b' where fb': "factors G bs b'" and b': "b' \<sim> b"
- by auto
+ from wfactors_factors[OF bsf bscarr] obtain b' where fb': "factors G bs b'" and b': "b' \<sim> b"
+ by blast
from fb' bscarr have b'carr[simp]: "b' \<in> carrier G"
by fast
@@ -1476,10 +1461,8 @@
then show ?thesis by (intro exI) force
next
case False
- then have "\<exists>fs. set fs \<subseteq> carrier G \<and> factors G fs a"
- by (intro factors_exist acarr)
- then obtain fs where fscarr: "set fs \<subseteq> carrier G" and f: "factors G fs a"
- by auto
+ with factors_exist [OF acarr] obtain fs where fscarr: "set fs \<subseteq> carrier G" and f: "factors G fs a"
+ by blast
from f have "wfactors G fs a" by (rule factors_wfactors) fact
with fscarr show ?thesis by fast
qed
@@ -1593,11 +1576,9 @@
from wfactors_exists[OF acarr]
obtain as where ascarr: "set as \<subseteq> carrier G" and afs: "wfactors G as a"
- by auto
- from afs ascarr have "\<exists>a'. factors G as a' \<and> a' \<sim> a"
- by (rule wfactors_factors)
- then obtain a' where afs': "factors G as a'" and a'a: "a' \<sim> a"
- by auto
+ by blast
+ from wfactors_factors [OF afs ascarr] obtain a' where afs': "factors G as a'" and a'a: "a' \<sim> a"
+ by blast
from afs' ascarr have a'carr: "a' \<in> carrier G"
by fast
have a'nunit: "a' \<notin> Units G"
@@ -1608,10 +1589,8 @@
with anunit show False ..
qed
- from a'carr acarr a'a have "\<exists>u. u \<in> Units G \<and> a' = a \<otimes> u"
+ from a'carr acarr a'a obtain u where uunit: "u \<in> Units G" and a': "a' = a \<otimes> u"
by (blast elim: associatedE2)
- then obtain u where uunit: "u \<in> Units G" and a': "a' = a \<otimes> u"
- by auto
note [simp] = acarr Units_closed[OF uunit] Units_inv_closed[OF uunit]
@@ -1764,16 +1743,19 @@
have "set (map (assocs G) as) = {assocs G x | x. x \<in> set as}" by auto
with setys have "set ys \<subseteq> { assocs G x | x. x \<in> set as}" by simp
then have "\<exists>yy. ys = map (assocs G) yy"
- apply (induct ys)
- apply simp
- apply clarsimp
- proof -
- fix yy x
- show "\<exists>yya. (assocs G x) # map (assocs G) yy = map (assocs G) yya"
- by (rule exI[of _ "x#yy"]) simp
+ proof (induct ys)
+ case Nil
+ then show ?case by simp
+ next
+ case Cons
+ then show ?case
+ proof clarsimp
+ fix yy x
+ show "\<exists>yya. assocs G x # map (assocs G) yy = map (assocs G) yya"
+ by (rule exI[of _ "x#yy"]) simp
+ qed
qed
- then obtain yy where ys: "ys = map (assocs G) yy"
- by auto
+ then obtain yy where ys: "ys = map (assocs G) yy" ..
from p1 ys have "\<exists>as'. as <~~> as' \<and> map (assocs G) as' = map (assocs G) yy"
by (intro r1) simp
@@ -1785,14 +1767,16 @@
then obtain as'' where yyas'': "yy <~~> as''" and as''bs: "map (assocs G) as'' = map (assocs G) bs"
by auto
- from as'yy and yyas'' have "\<exists>cs. as' <~~> cs \<and> map (assocs G) cs = map (assocs G) as''"
- by (rule perm_map_switch)
- then obtain cs where as'cs: "as' <~~> cs" and csas'': "map (assocs G) cs = map (assocs G) as''"
- by auto
-
- from asas' and as'cs have ascs: "as <~~> cs" by fast
- from csas'' and as''bs have "map (assocs G) cs = map (assocs G) bs" by simp
- with ascs show "\<exists>as'. as <~~> as' \<and> map (assocs G) as' = map (assocs G) bs" by fast
+ from perm_map_switch [OF as'yy yyas'']
+ obtain cs where as'cs: "as' <~~> cs" and csas'': "map (assocs G) cs = map (assocs G) as''"
+ by blast
+
+ from asas' and as'cs have ascs: "as <~~> cs"
+ by fast
+ from csas'' and as''bs have "map (assocs G) cs = map (assocs G) bs"
+ by simp
+ with ascs show "\<exists>as'. as <~~> as' \<and> map (assocs G) as' = map (assocs G) bs"
+ by fast
qed
lemma (in comm_monoid_cancel) fmset_ee:
@@ -1803,17 +1787,14 @@
from mset have mpp: "map (assocs G) as <~~> map (assocs G) bs"
by (simp add: fmset_def mset_eq_perm del: mset_map)
- have "\<exists>cas. cas = map (assocs G) as" by simp
- then obtain cas where cas: "cas = map (assocs G) as" by simp
-
- have "\<exists>cbs. cbs = map (assocs G) bs" by simp
- then obtain cbs where cbs: "cbs = map (assocs G) bs" by simp
-
- from cas cbs mpp have [rule_format]:
+ define cas where "cas = map (assocs G) as"
+ define cbs where "cbs = map (assocs G) bs"
+
+ from cas_def cbs_def mpp have [rule_format]:
"\<forall>as bs. (cas <~~> cbs \<and> cas = map (assocs G) as \<and> cbs = map (assocs G) bs)
\<longrightarrow> (\<exists>as'. as <~~> as' \<and> map (assocs G) as' = cbs)"
by (intro fmset_ee__hlp_induct, simp+)
- with mpp cas cbs have "\<exists>as'. as <~~> as' \<and> map (assocs G) as' = map (assocs G) bs"
+ with mpp cas_def cbs_def have "\<exists>as'. as <~~> as' \<and> map (assocs G) as' = map (assocs G) bs"
by simp
then obtain as' where tp: "as <~~> as'" and tm: "map (assocs G) as' = map (assocs G) bs"
@@ -1825,8 +1806,7 @@
with ascarr have as'carr: "set as' \<subseteq> carrier G"
by simp
- from tm as'carr[THEN subsetD] bscarr[THEN subsetD]
- have "as' [\<sim>] bs"
+ from tm as'carr[THEN subsetD] bscarr[THEN subsetD] have "as' [\<sim>] bs"
by (induct as' arbitrary: bs) (simp, fastforce dest: assocs_eqD[THEN associated_sym])
with tp show "essentially_equal G as bs"
by (fast intro: essentially_equalI)
@@ -1844,11 +1824,8 @@
assumes elems: "\<And>X. X \<in> set_mset Cs \<Longrightarrow> \<exists>x. P x \<and> X = assocs G x"
shows "\<exists>cs. (\<forall>c \<in> set cs. P c) \<and> fmset G cs = Cs"
proof -
- have "\<exists>Cs'. Cs = mset Cs'"
- by (rule surjE[OF surj_mset], fast)
- then obtain Cs' where Cs: "Cs = mset Cs'"
- by auto
-
+ from surjE[OF surj_mset] obtain Cs' where Cs: "Cs = mset Cs'"
+ by blast
have "\<exists>cs. (\<forall>c \<in> set cs. P c) \<and> mset (map (assocs G) cs) = Cs"
using elems
unfolding Cs
@@ -1858,11 +1835,14 @@
assume ih: "\<And>X. X = a \<or> X \<in> set Cs' \<Longrightarrow> \<exists>x. P x \<and> X = assocs G x"
and csP: "\<forall>x\<in>set cs. P x"
and mset: "mset (map (assocs G) cs) = mset Cs'"
- from ih have "\<exists>x. P x \<and> a = assocs G x" by fast
- then obtain c where cP: "P c" and a: "a = assocs G c" by auto
- from cP csP have tP: "\<forall>x\<in>set (c#cs). P x" by simp
- from mset a have "mset (map (assocs G) (c#cs)) = add_mset a (mset Cs')" by simp
- with tP show "\<exists>cs. (\<forall>x\<in>set cs. P x) \<and> mset (map (assocs G) cs) = add_mset a (mset Cs')" by fast
+ from ih obtain c where cP: "P c" and a: "a = assocs G c"
+ by auto
+ from cP csP have tP: "\<forall>x\<in>set (c#cs). P x"
+ by simp
+ from mset a have "mset (map (assocs G) (c#cs)) = add_mset a (mset Cs')"
+ by simp
+ with tP show "\<exists>cs. (\<forall>x\<in>set cs. P x) \<and> mset (map (assocs G) cs) = add_mset a (mset Cs')"
+ by fast
qed
then show ?thesis by (simp add: fmset_def)
qed
@@ -1875,7 +1855,6 @@
by (intro mset_fmsetEx, rule elems)
then obtain cs where p[rule_format]: "\<forall>c\<in>set cs. c \<in> carrier G \<and> irreducible G c"
and Cs[symmetric]: "fmset G cs = Cs" by auto
-
from p have cscarr: "set cs \<subseteq> carrier G" by fast
from p have "\<exists>c. c \<in> carrier G \<and> wfactors G cs c"
by (intro wfactors_prod_exists) auto
@@ -1944,10 +1923,9 @@
proof (elim dividesE)
fix c
assume ccarr: "c \<in> carrier G"
- then have "\<exists>cs. set cs \<subseteq> carrier G \<and> wfactors G cs c"
- by (rule wfactors_exist)
- then obtain cs where cscarr: "set cs \<subseteq> carrier G" and cfs: "wfactors G cs c"
- by auto
+ from wfactors_exist [OF this]
+ obtain cs where cscarr: "set cs \<subseteq> carrier G" and cfs: "wfactors G cs c"
+ by blast
note carr = carr ccarr cscarr
assume "b = a \<otimes> c"
@@ -2070,24 +2048,19 @@
and pnunit: "p \<notin> Units G"
assume irreduc[rule_format]:
"\<forall>b. b \<in> carrier G \<and> properfactor G b p \<longrightarrow> b \<in> Units G"
- from pdvdab
- have "\<exists>c\<in>carrier G. a \<otimes> b = p \<otimes> c" by (rule dividesD)
- then obtain c where ccarr: "c \<in> carrier G" and abpc: "a \<otimes> b = p \<otimes> c"
- by auto
-
- from acarr have "\<exists>fs. set fs \<subseteq> carrier G \<and> wfactors G fs a"
- by (rule wfactors_exist)
- then obtain as where ascarr: "set as \<subseteq> carrier G" and afs: "wfactors G as a"
+ from pdvdab obtain c where ccarr: "c \<in> carrier G" and abpc: "a \<otimes> b = p \<otimes> c"
+ by (rule dividesE)
+
+ from wfactors_exist [OF acarr]
+ obtain as where ascarr: "set as \<subseteq> carrier G" and afs: "wfactors G as a"
+ by blast
+
+ from wfactors_exist [OF bcarr]
+ obtain bs where bscarr: "set bs \<subseteq> carrier G" and bfs: "wfactors G bs b"
by auto
- from bcarr have "\<exists>fs. set fs \<subseteq> carrier G \<and> wfactors G fs b"
- by (rule wfactors_exist)
- then obtain bs where bscarr: "set bs \<subseteq> carrier G" and bfs: "wfactors G bs b"
- by auto
-
- from ccarr have "\<exists>fs. set fs \<subseteq> carrier G \<and> wfactors G fs c"
- by (rule wfactors_exist)
- then obtain cs where cscarr: "set cs \<subseteq> carrier G" and cfs: "wfactors G cs c"
+ from wfactors_exist [OF ccarr]
+ obtain cs where cscarr: "set cs \<subseteq> carrier G" and cfs: "wfactors G cs c"
by auto
note carr[simp] = pcarr acarr bcarr ccarr ascarr bscarr cscarr
@@ -2103,16 +2076,12 @@
from abfs' abfs have "essentially_equal G (p # cs) (as @ bs)"
by (rule wfactors_unique) simp+
- then have "\<exists>ds. p # cs <~~> ds \<and> ds [\<sim>] (as @ bs)"
+ then obtain ds where "p # cs <~~> ds" and dsassoc: "ds [\<sim>] (as @ bs)"
by (fast elim: essentially_equalE)
- then obtain ds where "p # cs <~~> ds" and dsassoc: "ds [\<sim>] (as @ bs)"
- by auto
then have "p \<in> set ds"
by (simp add: perm_set_eq[symmetric])
- with dsassoc have "\<exists>p'. p' \<in> set (as@bs) \<and> p \<sim> p'"
+ with dsassoc obtain p' where "p' \<in> set (as@bs)" and pp': "p \<sim> p'"
unfolding list_all2_conv_all_nth set_conv_nth by force
- then obtain p' where "p' \<in> set (as@bs)" and pp': "p \<sim> p'"
- by auto
then consider "p' \<in> set as" | "p' \<in> set bs" by auto
then show "p divides a \<or> p divides b"
proof cases
@@ -2151,10 +2120,8 @@
and bcarr: "b \<in> carrier G"
and pdvdab: "p divides (a \<otimes> b)"
assume irreduc[rule_format]: "\<forall>b. b \<in> carrier G \<and> properfactor G b p \<longrightarrow> b \<in> Units G"
- from pdvdab have "\<exists>c\<in>carrier G. a \<otimes> b = p \<otimes> c"
- by (rule dividesD)
- then obtain c where ccarr: "c \<in> carrier G" and abpc: "a \<otimes> b = p \<otimes> c"
- by auto
+ from pdvdab obtain c where ccarr: "c \<in> carrier G" and abpc: "a \<otimes> b = p \<otimes> c"
+ by (rule dividesE)
note [simp] = pcarr acarr bcarr ccarr
show "p divides a \<or> p divides b"
@@ -2181,7 +2148,7 @@
next
case bnunit: False
have cnunit: "c \<notin> Units G"
- proof (rule ccontr, simp)
+ proof
assume cunit: "c \<in> Units G"
from bnunit have "properfactor G a (a \<otimes> b)"
by (intro properfactorI3[of _ _ b], simp+)
@@ -2200,19 +2167,16 @@
with anunit show False ..
qed
- from acarr anunit have "\<exists>fs. set fs \<subseteq> carrier G \<and> factors G fs a"
- by (rule factors_exist)
- then obtain as where ascarr: "set as \<subseteq> carrier G" and afac: "factors G as a"
- by auto
-
- from bcarr bnunit have "\<exists>fs. set fs \<subseteq> carrier G \<and> factors G fs b"
- by (rule factors_exist)
- then obtain bs where bscarr: "set bs \<subseteq> carrier G" and bfac: "factors G bs b"
- by auto
-
- from ccarr cnunit have "\<exists>fs. set fs \<subseteq> carrier G \<and> factors G fs c"
- by (rule factors_exist)
- then obtain cs where cscarr: "set cs \<subseteq> carrier G" and cfac: "factors G cs c"
+ from factors_exist [OF acarr anunit]
+ obtain as where ascarr: "set as \<subseteq> carrier G" and afac: "factors G as a"
+ by blast
+
+ from factors_exist [OF bcarr bnunit]
+ obtain bs where bscarr: "set bs \<subseteq> carrier G" and bfac: "factors G bs b"
+ by blast
+
+ from factors_exist [OF ccarr cnunit]
+ obtain cs where cscarr: "set cs \<subseteq> carrier G" and cfac: "factors G cs c"
by auto
note [simp] = ascarr bscarr cscarr
@@ -2227,16 +2191,12 @@
from abfac' abfac have "essentially_equal G (p # cs) (as @ bs)"
by (rule factors_unique) (fact | simp)+
- then have "\<exists>ds. p # cs <~~> ds \<and> ds [\<sim>] (as @ bs)"
+ then obtain ds where "p # cs <~~> ds" and dsassoc: "ds [\<sim>] (as @ bs)"
by (fast elim: essentially_equalE)
- then obtain ds where "p # cs <~~> ds" and dsassoc: "ds [\<sim>] (as @ bs)"
- by auto
then have "p \<in> set ds"
by (simp add: perm_set_eq[symmetric])
- with dsassoc have "\<exists>p'. p' \<in> set (as@bs) \<and> p \<sim> p'"
+ with dsassoc obtain p' where "p' \<in> set (as@bs)" and pp': "p \<sim> p'"
unfolding list_all2_conv_all_nth set_conv_nth by force
- then obtain p' where "p' \<in> set (as@bs)" and pp': "p \<sim> p'"
- by auto
then consider "p' \<in> set as" | "p' \<in> set bs" by auto
then show "p divides a \<or> p divides b"
proof cases
@@ -2333,16 +2293,15 @@
and bcarr: "b \<in> carrier G"
shows "\<exists>c. c \<in> carrier G \<and> c gcdof a b"
proof -
- from acarr have "\<exists>as. set as \<subseteq> carrier G \<and> wfactors G as a" by (rule wfactors_exist)
- then obtain as where ascarr: "set as \<subseteq> carrier G" and afs: "wfactors G as a"
- by auto
+ from wfactors_exist [OF acarr]
+ obtain as where ascarr: "set as \<subseteq> carrier G" and afs: "wfactors G as a"
+ by blast
from afs have airr: "\<forall>a \<in> set as. irreducible G a"
by (fast elim: wfactorsE)
- from bcarr have "\<exists>bs. set bs \<subseteq> carrier G \<and> wfactors G bs b"
- by (rule wfactors_exist)
- then obtain bs where bscarr: "set bs \<subseteq> carrier G" and bfs: "wfactors G bs b"
- by auto
+ from wfactors_exist [OF bcarr]
+ obtain bs where bscarr: "set bs \<subseteq> carrier G" and bfs: "wfactors G bs b"
+ by blast
from bfs have birr: "\<forall>b \<in> set bs. irreducible G b"
by (fast elim: wfactorsE)
@@ -2357,13 +2316,13 @@
then have "\<exists>x. X = assocs G x \<and> x \<in> set as"
by (induct as) auto
then obtain x where X: "X = assocs G x" and xas: "x \<in> set as"
- by auto
+ by blast
with ascarr have xcarr: "x \<in> carrier G"
- by fast
+ by blast
from xas airr have xirr: "irreducible G x"
by simp
from xcarr and xirr and X show "\<exists>x. (x \<in> carrier G \<and> irreducible G x) \<and> X = assocs G x"
- by fast
+ by blast
qed
then obtain c cs
where ccarr: "c \<in> carrier G"
@@ -2385,11 +2344,10 @@
by (rule fmsubset_divides) fact+
next
fix y
- assume ycarr: "y \<in> carrier G"
- then have "\<exists>ys. set ys \<subseteq> carrier G \<and> wfactors G ys y"
- by (rule wfactors_exist)
- then obtain ys where yscarr: "set ys \<subseteq> carrier G" and yfs: "wfactors G ys y"
- by auto
+ assume "y \<in> carrier G"
+ from wfactors_exist [OF this]
+ obtain ys where yscarr: "set ys \<subseteq> carrier G" and yfs: "wfactors G ys y"
+ by blast
assume "y divides a"
then have ya: "fmset G ys \<le># fmset G as"
@@ -2413,17 +2371,15 @@
and bcarr: "b \<in> carrier G"
shows "\<exists>c. c \<in> carrier G \<and> c lcmof a b"
proof -
- from acarr have "\<exists>as. set as \<subseteq> carrier G \<and> wfactors G as a"
- by (rule wfactors_exist)
- then obtain as where ascarr: "set as \<subseteq> carrier G" and afs: "wfactors G as a"
- by auto
+ from wfactors_exist [OF acarr]
+ obtain as where ascarr: "set as \<subseteq> carrier G" and afs: "wfactors G as a"
+ by blast
from afs have airr: "\<forall>a \<in> set as. irreducible G a"
by (fast elim: wfactorsE)
- from bcarr have "\<exists>bs. set bs \<subseteq> carrier G \<and> wfactors G bs b"
- by (rule wfactors_exist)
- then obtain bs where bscarr: "set bs \<subseteq> carrier G" and bfs: "wfactors G bs b"
- by auto
+ from wfactors_exist [OF bcarr]
+ obtain bs where bscarr: "set bs \<subseteq> carrier G" and bfs: "wfactors G bs b"
+ by blast
from bfs have birr: "\<forall>b \<in> set bs. irreducible G b"
by (fast elim: wfactorsE)
@@ -2475,11 +2431,10 @@
by (rule fmsubset_divides) fact+
next
fix y
- assume ycarr: "y \<in> carrier G"
- then have "\<exists>ys. set ys \<subseteq> carrier G \<and> wfactors G ys y"
- by (rule wfactors_exist)
- then obtain ys where yscarr: "set ys \<subseteq> carrier G" and yfs: "wfactors G ys y"
- by auto
+ assume "y \<in> carrier G"
+ from wfactors_exist [OF this]
+ obtain ys where yscarr: "set ys \<subseteq> carrier G" and yfs: "wfactors G ys y"
+ by blast
assume "a divides y"
then have ya: "fmset G as \<le># fmset G ys"
@@ -2516,9 +2471,8 @@
proof -
fix x y
assume carr: "x \<in> carrier G" "y \<in> carrier G"
- then have "\<exists>z. z \<in> carrier G \<and> z gcdof x y" by (rule gcdof_exists)
- then obtain z where zcarr: "z \<in> carrier G" and isgcd: "z gcdof x y"
- by auto
+ from gcdof_exists [OF this] obtain z where zcarr: "z \<in> carrier G" and isgcd: "z gcdof x y"
+ by blast
with carr have "greatest (division_rel G) z (Lower (division_rel G) {x, y})"
by (subst gcdof_greatestLower[symmetric], simp+)
then show "\<exists>z. greatest (division_rel G) z (Lower (division_rel G) {x, y})"
@@ -2719,18 +2673,14 @@
from cd'ca cd'cb have cd'e: "c \<otimes> ?d divides ?e"
by (rule gcd_divides) simp_all
- then have "\<exists>u. u \<in> carrier G \<and> ?e = c \<otimes> ?d \<otimes> u"
- by (elim dividesE) fast
then obtain u where ucarr[simp]: "u \<in> carrier G" and e_cdu: "?e = c \<otimes> ?d \<otimes> u"
- by auto
+ by blast
note carr = carr ucarr
have "?e divides c \<otimes> a" by (rule gcd_divides_l) simp_all
- then have "\<exists>x. x \<in> carrier G \<and> c \<otimes> a = ?e \<otimes> x"
- by (elim dividesE) fast
then obtain x where xcarr: "x \<in> carrier G" and ca_ex: "c \<otimes> a = ?e \<otimes> x"
- by auto
+ by blast
with e_cdu have ca_cdux: "c \<otimes> a = c \<otimes> ?d \<otimes> u \<otimes> x"
by simp
@@ -2742,10 +2692,8 @@
by (rule dividesI[OF xcarr])
have "?e divides c \<otimes> b" by (intro gcd_divides_r) simp_all
- then have "\<exists>x. x \<in> carrier G \<and> c \<otimes> b = ?e \<otimes> x"
- by (elim dividesE) fast
then obtain x where xcarr: "x \<in> carrier G" and cb_ex: "c \<otimes> b = ?e \<otimes> x"
- by auto
+ by blast
with e_cdu have cb_cdux: "c \<otimes> b = c \<otimes> ?d \<otimes> u \<otimes> x"
by simp
@@ -2840,7 +2788,7 @@
apply (clarsimp simp add: Unit_eq_dividesone[symmetric])
apply (rule r, rule, assumption)
apply (rule properfactorI, assumption)
- proof (rule ccontr, simp)
+ proof
fix y
assume ycarr: "y \<in> carrier G"
assume "p divides y"
@@ -2860,7 +2808,7 @@
apply (clarsimp simp add: Unit_eq_dividesone[symmetric])
apply (rule r, rule, assumption)
apply (rule properfactorI, assumption)
- proof (rule ccontr, simp)
+ proof
fix y
assume ycarr: "y \<in> carrier G"
assume "p divides y"
@@ -2921,23 +2869,20 @@
done
then obtain y where ycarr: "y \<in> carrier G" and ynunit: "y \<notin> Units G"
and pfyx: "properfactor G y x"
- by auto
+ by blast
have ih': "\<And>y. \<lbrakk>y \<in> carrier G; properfactor G y x\<rbrakk>
\<Longrightarrow> \<exists>as. set as \<subseteq> carrier G \<and> wfactors G as y"
by (rule ih[rule_format, simplified]) (simp add: xcarr)+
- from ycarr pfyx have "\<exists>as. set as \<subseteq> carrier G \<and> wfactors G as y"
- by (rule ih')
- then obtain ys where yscarr: "set ys \<subseteq> carrier G" and yfs: "wfactors G ys y"
- by auto
+ from ih' [OF ycarr pfyx]
+ obtain ys where yscarr: "set ys \<subseteq> carrier G" and yfs: "wfactors G ys y"
+ by blast
from pfyx have "y divides x" and nyx: "\<not> y \<sim> x"
by (fast elim: properfactorE2)+
- then have "\<exists>z. z \<in> carrier G \<and> x = y \<otimes> z"
- by fast
then obtain z where zcarr: "z \<in> carrier G" and x: "x = y \<otimes> z"
- by auto
+ by blast
from zcarr ycarr have "properfactor G z x"
apply (subst x)
@@ -2945,11 +2890,9 @@
apply (simp add: m_comm)
apply (simp add: ynunit)+
done
- with zcarr have "\<exists>as. set as \<subseteq> carrier G \<and> wfactors G as z"
- by (rule ih')
- then obtain zs where zscarr: "set zs \<subseteq> carrier G" and zfs: "wfactors G zs z"
- by auto
-
+ from ih' [OF zcarr this]
+ obtain zs where zscarr: "set zs \<subseteq> carrier G" and zfs: "wfactors G zs z"
+ by blast
from yscarr zscarr have xscarr: "set (ys@zs) \<subseteq> carrier G"
by simp
from yfs zfs ycarr zcarr yscarr zscarr have "wfactors G (ys@zs) (y\<otimes>z)"
@@ -2998,8 +2941,7 @@
with p1 show ?thesis by fast
next
assume "a divides foldr op \<otimes> as \<one>"
- then have "\<exists>i. i < length as \<and> a divides as ! i" by (rule ih)
- then obtain i where "a divides as ! i" and len: "i < length as" by auto
+ from ih [OF this] obtain i where "a divides as ! i" and len: "i < length as" by auto
then have p1: "a divides (aa#as) ! (Suc i)" by simp
from len have "Suc i < Suc (length as)" by simp
with p1 show ?thesis by force
@@ -3039,13 +2981,13 @@
and afs: "wfactors G (ah # as) a"
and afs': "wfactors G as' a"
then have ahdvda: "ah divides a"
- by (intro wfactors_dividesI[of "ah#as" "a"], simp+)
- then have "\<exists>a'\<in> carrier G. a = ah \<otimes> a'" by fast
+ by (intro wfactors_dividesI[of "ah#as" "a"]) simp_all
then obtain a' where a'carr: "a' \<in> carrier G" and a: "a = ah \<otimes> a'"
- by auto
+ by blast
have a'fs: "wfactors G as a'"
apply (rule wfactorsE[OF afs], rule wfactorsI, simp)
- apply (simp add: a, insert ascarr a'carr)
+ apply (simp add: a)
+ apply (insert ascarr a'carr)
apply (intro assoc_l_cancel[of ah _ a'] multlist_closed ahcarr, assumption+)
done
from afs have ahirr: "irreducible G ah"
@@ -3061,19 +3003,17 @@
finally have "ah divides (foldr (op \<otimes>) as' \<one>)"
by simp
with ahprime have "\<exists>i<length as'. ah divides as'!i"
- by (intro multlist_prime_pos, simp+)
+ by (intro multlist_prime_pos) simp_all
then obtain i where len: "i<length as'" and ahdvd: "ah divides as'!i"
- by auto
+ by blast
from afs' carr have irrasi: "irreducible G (as'!i)"
by (fast intro: nth_mem[OF len] elim: wfactorsE)
from len carr have asicarr[simp]: "as'!i \<in> carrier G"
unfolding set_conv_nth by force
note carr = carr asicarr
- from ahdvd have "\<exists>x \<in> carrier G. as'!i = ah \<otimes> x"
- by fast
- then obtain x where "x \<in> carrier G" and asi: "as'!i = ah \<otimes> x"
- by auto
+ from ahdvd obtain x where "x \<in> carrier G" and asi: "as'!i = ah \<otimes> x"
+ by blast
with carr irrasi[simplified asi] have asiah: "as'!i \<sim> ah"
apply -
apply (elim irreducible_prodE[of "ah" "x"], assumption+)
@@ -3241,17 +3181,17 @@
proof (rule dividesE[OF dvd])
fix c
from assms have "\<exists>as. set as \<subseteq> carrier G \<and> wfactors G as a"
- by fast
+ by blast
then obtain as where ascarr: "set as \<subseteq> carrier G" and afs: "wfactors G as a"
- by auto
+ by blast
with acarr have fca: "factorcount G a = length as"
by (intro factorcount_unique)
assume ccarr: "c \<in> carrier G"
then have "\<exists>cs. set cs \<subseteq> carrier G \<and> wfactors G cs c"
- by fast
+ by blast
then obtain cs where cscarr: "set cs \<subseteq> carrier G" and cfs: "wfactors G cs c"
- by auto
+ by blast
note [simp] = acarr bcarr ccarr ascarr cscarr
@@ -3286,17 +3226,17 @@
proof (rule properfactorE[OF pf], elim dividesE)
fix c
from assms have "\<exists>as. set as \<subseteq> carrier G \<and> wfactors G as a"
- by fast
+ by blast
then obtain as where ascarr: "set as \<subseteq> carrier G" and afs: "wfactors G as a"
- by auto
+ by blast
with acarr have fca: "factorcount G a = length as"
by (intro factorcount_unique)
assume ccarr: "c \<in> carrier G"
then have "\<exists>cs. set cs \<subseteq> carrier G \<and> wfactors G cs c"
- by fast
+ by blast
then obtain cs where cscarr: "set cs \<subseteq> carrier G" and cfs: "wfactors G cs c"
- by auto
+ by blast
assume b: "b = a \<otimes> c"
@@ -3311,7 +3251,7 @@
assume nbdvda: "\<not> b divides a"
have "c \<notin> Units G"
- proof (rule ccontr, simp)
+ proof
assume cunit:"c \<in> Units G"
have "b \<otimes> inv c = a \<otimes> c \<otimes> inv c"
by (simp add: b)
@@ -3361,14 +3301,12 @@
proof (unfold_locales, simp_all)
fix x y
assume carr: "x \<in> carrier G" "y \<in> carrier G"
- then have "\<exists>z. z \<in> carrier G \<and> z lcmof x y"
- by (rule lcmof_exists)
- then obtain z where zcarr: "z \<in> carrier G" and isgcd: "z lcmof x y"
- by auto
+ from lcmof_exists [OF this] obtain z where zcarr: "z \<in> carrier G" and isgcd: "z lcmof x y"
+ by blast
with carr have "least (division_rel G) z (Upper (division_rel G) {x, y})"
by (simp add: lcmof_leastUpper[symmetric])
then show "\<exists>z. least (division_rel G) z (Upper (division_rel G) {x, y})"
- by fast
+ by blast
qed
qed
@@ -3376,9 +3314,8 @@
subsection \<open>Factoriality Theorems\<close>
theorem factorial_condition_one: (* Jacobson theorem 2.21 *)
- "(divisor_chain_condition_monoid G \<and> primeness_condition_monoid G) = factorial_monoid G"
- apply rule
-proof clarify
+ "divisor_chain_condition_monoid G \<and> primeness_condition_monoid G \<longleftrightarrow> factorial_monoid G"
+proof (rule iffI, clarify)
assume dcc: "divisor_chain_condition_monoid G"
and pc: "primeness_condition_monoid G"
interpret divisor_chain_condition_monoid "G" by (rule dcc)
@@ -3386,16 +3323,15 @@
show "factorial_monoid G"
by (fast intro: factorial_monoidI wfactors_exist wfactors_unique)
next
- assume fm: "factorial_monoid G"
- interpret factorial_monoid "G" by (rule fm)
+ assume "factorial_monoid G"
+ then interpret factorial_monoid "G" .
show "divisor_chain_condition_monoid G \<and> primeness_condition_monoid G"
by rule unfold_locales
qed
theorem factorial_condition_two: (* Jacobson theorem 2.22 *)
- shows "(divisor_chain_condition_monoid G \<and> gcd_condition_monoid G) = factorial_monoid G"
- apply rule
-proof clarify
+ "divisor_chain_condition_monoid G \<and> gcd_condition_monoid G \<longleftrightarrow> factorial_monoid G"
+proof (rule iffI, clarify)
assume dcc: "divisor_chain_condition_monoid G"
and gc: "gcd_condition_monoid G"
interpret divisor_chain_condition_monoid "G" by (rule dcc)
@@ -3403,8 +3339,8 @@
show "factorial_monoid G"
by (simp add: factorial_condition_one[symmetric], rule, unfold_locales)
next
- assume fm: "factorial_monoid G"
- interpret factorial_monoid "G" by (rule fm)
+ assume "factorial_monoid G"
+ then interpret factorial_monoid "G" .
show "divisor_chain_condition_monoid G \<and> gcd_condition_monoid G"
by rule unfold_locales
qed