56 text{*This is theorem @{text increasingD2} of ZF/Zorn.thy*} |
56 text{*This is theorem @{text increasingD2} of ZF/Zorn.thy*} |
57 |
57 |
58 lemma Abrial_axiom1: "x \<subseteq> succ S x" |
58 lemma Abrial_axiom1: "x \<subseteq> succ S x" |
59 apply (auto simp add: succ_def super_def maxchain_def) |
59 apply (auto simp add: succ_def super_def maxchain_def) |
60 apply (rule contrapos_np, assumption) |
60 apply (rule contrapos_np, assumption) |
61 apply (rule_tac Q="\<lambda>S. xa \<in> S" in someI2, blast+) |
61 apply (rule someI2) |
|
62 apply blast+ |
62 done |
63 done |
63 |
64 |
64 lemmas TFin_UnionI = TFin.Pow_UnionI [OF PowI] |
65 lemmas TFin_UnionI = TFin.Pow_UnionI [OF PowI] |
65 |
66 |
66 lemma TFin_induct: |
67 lemma TFin_induct: |
67 assumes H: "n \<in> TFin S" |
68 assumes H: "n \<in> TFin S" and |
68 and I: "!!x. x \<in> TFin S ==> P x ==> P (succ S x)" |
69 I: "!!x. x \<in> TFin S ==> P x ==> P (succ S x)" |
69 "!!Y. Y \<subseteq> TFin S ==> Ball Y P ==> P(Union Y)" |
70 "!!Y. Y \<subseteq> TFin S ==> Ball Y P ==> P (Union Y)" |
70 shows "P n" using H |
71 shows "P n" |
71 apply (induct rule: TFin.induct [where P=P]) |
72 using H by induct (blast intro: I)+ |
72 apply (blast intro: I)+ |
|
73 done |
|
74 |
73 |
75 lemma succ_trans: "x \<subseteq> y ==> x \<subseteq> succ S y" |
74 lemma succ_trans: "x \<subseteq> y ==> x \<subseteq> succ S y" |
76 apply (erule subset_trans) |
75 apply (erule subset_trans) |
77 apply (rule Abrial_axiom1) |
76 apply (rule Abrial_axiom1) |
78 done |
77 done |
158 by (unfold super_def maxchain_def) auto |
157 by (unfold super_def maxchain_def) auto |
159 |
158 |
160 lemma select_super: |
159 lemma select_super: |
161 "c \<in> chain S - maxchain S ==> (\<some>c'. c': super S c): super S c" |
160 "c \<in> chain S - maxchain S ==> (\<some>c'. c': super S c): super S c" |
162 apply (erule mem_super_Ex [THEN exE]) |
161 apply (erule mem_super_Ex [THEN exE]) |
163 apply (rule someI2 [where Q="%X. X : super S c"], auto) |
162 apply (rule someI2) |
|
163 apply auto |
164 done |
164 done |
165 |
165 |
166 lemma select_not_equals: |
166 lemma select_not_equals: |
167 "c \<in> chain S - maxchain S ==> (\<some>c'. c': super S c) \<noteq> c" |
167 "c \<in> chain S - maxchain S ==> (\<some>c'. c': super S c) \<noteq> c" |
168 apply (rule notI) |
168 apply (rule notI) |
183 apply (erule TFin_induct) |
183 apply (erule TFin_induct) |
184 apply (simp add: succ_def select_super [THEN super_subset_chain[THEN subsetD]]) |
184 apply (simp add: succ_def select_super [THEN super_subset_chain[THEN subsetD]]) |
185 apply (unfold chain_def chain_subset_def) |
185 apply (unfold chain_def chain_subset_def) |
186 apply (rule CollectI, safe) |
186 apply (rule CollectI, safe) |
187 apply (drule bspec, assumption) |
187 apply (drule bspec, assumption) |
188 apply (rule_tac [2] m1 = Xa and n1 = X in TFin_subset_linear [THEN disjE], |
188 apply (rule_tac [2] m1 = Xa and n1 = X in TFin_subset_linear [THEN disjE]) |
189 best+) |
189 apply blast+ |
190 done |
190 done |
191 |
191 |
192 theorem Hausdorff: "\<exists>c. (c :: 'a set set): maxchain S" |
192 theorem Hausdorff: "\<exists>c. (c :: 'a set set): maxchain S" |
193 apply (rule_tac x = "Union (TFin S)" in exI) |
193 apply (rule_tac x = "Union (TFin S)" in exI) |
194 apply (rule classical) |
194 apply (rule classical) |