57 |
57 |
58 text{*compatibility*} |
58 text{*compatibility*} |
59 lemmas o_def = comp_def |
59 lemmas o_def = comp_def |
60 |
60 |
61 constdefs |
61 constdefs |
62 inj_on :: "['a => 'b, 'a set] => bool" (*injective*) |
62 inj_on :: "['a => 'b, 'a set] => bool" -- "injective" |
63 "inj_on f A == ! x:A. ! y:A. f(x)=f(y) --> x=y" |
63 "inj_on f A == ! x:A. ! y:A. f(x)=f(y) --> x=y" |
|
64 |
|
65 definition |
|
66 bij_betw :: "('a => 'b) => 'a set => 'b set => bool" where -- "bijective" |
|
67 "bij_betw f A B \<longleftrightarrow> inj_on f A & f ` A = B" |
|
68 |
64 |
69 |
65 text{*A common special case: functions injective over the entire domain type.*} |
70 text{*A common special case: functions injective over the entire domain type.*} |
66 |
71 |
67 abbreviation |
72 abbreviation |
68 "inj f == inj_on f UNIV" |
73 "inj f == inj_on f UNIV" |
235 apply (drule_tac x = y in spec, clarify) |
240 apply (drule_tac x = y in spec, clarify) |
236 apply (drule_tac x = x in spec, blast) |
241 apply (drule_tac x = x in spec, blast) |
237 done |
242 done |
238 |
243 |
239 |
244 |
240 |
245 subsection{*The Predicate @{const bij}: Bijectivity*} |
241 subsection{*The Predicate @{term bij}: Bijectivity*} |
|
242 |
246 |
243 lemma bijI: "[| inj f; surj f |] ==> bij f" |
247 lemma bijI: "[| inj f; surj f |] ==> bij f" |
244 by (simp add: bij_def) |
248 by (simp add: bij_def) |
245 |
249 |
246 lemma bij_is_inj: "bij f ==> inj f" |
250 lemma bij_is_inj: "bij f ==> inj f" |
247 by (simp add: bij_def) |
251 by (simp add: bij_def) |
248 |
252 |
249 lemma bij_is_surj: "bij f ==> surj f" |
253 lemma bij_is_surj: "bij f ==> surj f" |
250 by (simp add: bij_def) |
254 by (simp add: bij_def) |
|
255 |
|
256 |
|
257 subsection{*The Predicate @{const bij_betw}: Bijectivity*} |
|
258 |
|
259 lemma bij_betw_imp_inj_on: "bij_betw f A B \<Longrightarrow> inj_on f A" |
|
260 by (simp add: bij_betw_def) |
|
261 |
|
262 lemma bij_betw_inv: assumes "bij_betw f A B" shows "EX g. bij_betw g B A" |
|
263 proof - |
|
264 have i: "inj_on f A" and s: "f ` A = B" |
|
265 using assms by(auto simp:bij_betw_def) |
|
266 let ?P = "%b a. a:A \<and> f a = b" let ?g = "%b. The (?P b)" |
|
267 { fix a b assume P: "?P b a" |
|
268 hence ex1: "\<exists>a. ?P b a" using s unfolding image_def by blast |
|
269 hence uex1: "\<exists>!a. ?P b a" by(blast dest:inj_onD[OF i]) |
|
270 hence " ?g b = a" using the1_equality[OF uex1, OF P] P by simp |
|
271 } note g = this |
|
272 have "inj_on ?g B" |
|
273 proof(rule inj_onI) |
|
274 fix x y assume "x:B" "y:B" "?g x = ?g y" |
|
275 from s `x:B` obtain a1 where a1: "?P x a1" unfolding image_def by blast |
|
276 from s `y:B` obtain a2 where a2: "?P y a2" unfolding image_def by blast |
|
277 from g[OF a1] a1 g[OF a2] a2 `?g x = ?g y` show "x=y" by simp |
|
278 qed |
|
279 moreover have "?g ` B = A" |
|
280 proof(auto simp:image_def) |
|
281 fix b assume "b:B" |
|
282 with s obtain a where P: "?P b a" unfolding image_def by blast |
|
283 thus "?g b \<in> A" using g[OF P] by auto |
|
284 next |
|
285 fix a assume "a:A" |
|
286 then obtain b where P: "?P b a" using s unfolding image_def by blast |
|
287 then have "b:B" using s unfolding image_def by blast |
|
288 with g[OF P] show "\<exists>b\<in>B. a = ?g b" by blast |
|
289 qed |
|
290 ultimately show ?thesis by(auto simp:bij_betw_def) |
|
291 qed |
251 |
292 |
252 |
293 |
253 subsection{*Facts About the Identity Function*} |
294 subsection{*Facts About the Identity Function*} |
254 |
295 |
255 text{*We seem to need both the @{term id} forms and the @{term "\<lambda>x. x"} |
296 text{*We seem to need both the @{term id} forms and the @{term "\<lambda>x. x"} |