171 finally show "(\<Union>i\<in>K. X(i)) \<lesssim> K" . |
171 finally show "(\<Union>i\<in>K. X(i)) \<lesssim> K" . |
172 qed |
172 qed |
173 |
173 |
174 text{*The same again, using @{term csucc}*} |
174 text{*The same again, using @{term csucc}*} |
175 lemma cardinal_UN_lt_csucc: |
175 lemma cardinal_UN_lt_csucc: |
176 "[| InfCard(K); \<forall>i\<in>K. |X(i)| < csucc(K) |] |
176 "[| InfCard(K); \<And>i. i\<in>K \<Longrightarrow> |X(i)| < csucc(K) |] |
177 ==> |\<Union>i\<in>K. X(i)| < csucc(K)" |
177 ==> |\<Union>i\<in>K. X(i)| < csucc(K)" |
178 by (simp add: Card_lt_csucc_iff cardinal_UN_le InfCard_is_Card Card_cardinal) |
178 by (simp add: Card_lt_csucc_iff cardinal_UN_le InfCard_is_Card Card_cardinal) |
179 |
179 |
180 text{*The same again, for a union of ordinals. In use, j(i) is a bit like rank(i), |
180 text{*The same again, for a union of ordinals. In use, j(i) is a bit like rank(i), |
181 the least ordinal j such that i:Vfrom(A,j). *} |
181 the least ordinal j such that i:Vfrom(A,j). *} |
182 lemma cardinal_UN_Ord_lt_csucc: |
182 lemma cardinal_UN_Ord_lt_csucc: |
183 "[| InfCard(K); \<forall>i\<in>K. j(i) < csucc(K) |] |
183 "[| InfCard(K); \<And>i. i\<in>K \<Longrightarrow> j(i) < csucc(K) |] |
184 ==> (\<Union>i\<in>K. j(i)) < csucc(K)" |
184 ==> (\<Union>i\<in>K. j(i)) < csucc(K)" |
185 apply (rule cardinal_UN_lt_csucc [THEN Card_lt_imp_lt], assumption) |
185 apply (rule cardinal_UN_lt_csucc [THEN Card_lt_imp_lt], assumption) |
186 apply (blast intro: Ord_cardinal_le [THEN lt_trans1] elim: ltE) |
186 apply (blast intro: Ord_cardinal_le [THEN lt_trans1] elim: ltE) |
187 apply (blast intro!: Ord_UN elim: ltE) |
187 apply (blast intro!: Ord_UN elim: ltE) |
188 apply (erule InfCard_is_Card [THEN Card_is_Ord, THEN Card_csucc]) |
188 apply (erule InfCard_is_Card [THEN Card_is_Ord, THEN Card_csucc]) |
189 done |
189 done |
190 |
190 |
191 |
191 |
192 (** Main result for infinite-branching datatypes. As above, but the index |
192 subsection{*The Main Result for Infinite-Branching Datatypes*} |
193 set need not be a cardinal. Surprisingly complicated proof! |
193 |
194 **) |
194 text{*As above, but the index set need not be a cardinal. Work |
195 |
195 backwards along the injection from @{term W} into @{term K}, given |
196 text{*Work backwards along the injection from @{term W} into @{term K}, given that @{term"W\<noteq>0"}.*} |
196 that @{term"W\<noteq>0"}.*} |
197 |
197 |
198 lemma inj_UN_subset: |
198 lemma inj_UN_subset: |
199 assumes f: "f \<in> inj(A,B)" and a: "a \<in> A" |
199 assumes f: "f \<in> inj(A,B)" and a: "a \<in> A" |
200 shows "(\<Union>x\<in>A. C(x)) \<subseteq> (\<Union>y\<in>B. C(if y \<in> range(f) then converse(f)`y else a))" |
200 shows "(\<Union>x\<in>A. C(x)) \<subseteq> (\<Union>y\<in>B. C(if y \<in> range(f) then converse(f)`y else a))" |
201 proof (rule UN_least) |
201 proof (rule UN_least) |
207 also have "... \<subseteq> (\<Union>y\<in>B. C(if y \<in> range(f) then converse(f) ` y else a))" |
207 also have "... \<subseteq> (\<Union>y\<in>B. C(if y \<in> range(f) then converse(f) ` y else a))" |
208 by (rule UN_upper [OF fx]) |
208 by (rule UN_upper [OF fx]) |
209 finally show "C(x) \<subseteq> (\<Union>y\<in>B. C(if y \<in> range(f) then converse(f)`y else a))" . |
209 finally show "C(x) \<subseteq> (\<Union>y\<in>B. C(if y \<in> range(f) then converse(f)`y else a))" . |
210 qed |
210 qed |
211 |
211 |
212 text{*Simpler to require |W|=K; we'd have a bijection; but the theorem would |
212 theorem le_UN_Ord_lt_csucc: |
213 be weaker.*} |
213 assumes IK: "InfCard(K)" and WK: "|W| \<le> K" and j: "\<And>w. w\<in>W \<Longrightarrow> j(w) < csucc(K)" |
214 lemma le_UN_Ord_lt_csucc: |
214 shows "(\<Union>w\<in>W. j(w)) < csucc(K)" |
215 "[| InfCard(K); |W| \<le> K; \<forall>w\<in>W. j(w) < csucc(K) |] |
215 proof - |
216 ==> (\<Union>w\<in>W. j(w)) < csucc(K)" |
216 have CK: "Card(K)" |
217 apply (case_tac "W=0") --{*solve the easy 0 case*} |
217 by (simp add: InfCard_is_Card IK) |
218 apply (simp add: InfCard_is_Card Card_is_Ord [THEN Card_csucc] |
218 then obtain f where f: "f \<in> inj(W, K)" using WK |
219 Card_is_Ord Ord_0_lt_csucc) |
219 by(auto simp add: le_Card_iff lepoll_def) |
220 apply (simp add: InfCard_is_Card le_Card_iff lepoll_def) |
220 have OU: "Ord(\<Union>w\<in>W. j(w))" using j |
221 apply (safe intro!: equalityI) |
221 by (blast elim: ltE) |
222 apply (erule swap) |
222 note lt_subset_trans [OF _ _ OU, trans] |
223 apply (rule lt_subset_trans [OF inj_UN_subset cardinal_UN_Ord_lt_csucc], assumption+) |
223 show ?thesis |
224 apply (simp add: inj_converse_fun [THEN apply_type]) |
224 proof (cases "W=0") |
225 apply (blast intro!: Ord_UN elim: ltE) |
225 case True --{*solve the easy 0 case*} |
226 done |
226 thus ?thesis by (simp add: CK Card_is_Ord Card_csucc Ord_0_lt_csucc) |
|
227 next |
|
228 case False |
|
229 then obtain x where x: "x \<in> W" by blast |
|
230 have "(\<Union>x\<in>W. j(x)) \<subseteq> (\<Union>k\<in>K. j(if k \<in> range(f) then converse(f) ` k else x))" |
|
231 by (rule inj_UN_subset [OF f x]) |
|
232 also have "... < csucc(K)" using IK |
|
233 proof (rule cardinal_UN_Ord_lt_csucc) |
|
234 fix k |
|
235 assume "k \<in> K" |
|
236 thus "j(if k \<in> range(f) then converse(f) ` k else x) < csucc(K)" using f x j |
|
237 by (simp add: inj_converse_fun [THEN apply_type]) |
|
238 qed |
|
239 finally show ?thesis . |
|
240 qed |
|
241 qed |
227 |
242 |
228 end |
243 end |