286 |
286 |
287 |
287 |
288 (** We seem to need both the id-forms and the (%x. x) forms; the latter can |
288 (** We seem to need both the id-forms and the (%x. x) forms; the latter can |
289 arise by rewriting, while id may be used explicitly. **) |
289 arise by rewriting, while id may be used explicitly. **) |
290 |
290 |
291 Goal "(%x. x) `` Y = Y"; |
291 Goal "(%x. x) ` Y = Y"; |
292 by (Blast_tac 1); |
292 by (Blast_tac 1); |
293 qed "image_ident"; |
293 qed "image_ident"; |
294 |
294 |
295 Goalw [id_def] "id `` Y = Y"; |
295 Goalw [id_def] "id ` Y = Y"; |
296 by (Blast_tac 1); |
296 by (Blast_tac 1); |
297 qed "image_id"; |
297 qed "image_id"; |
298 Addsimps [image_ident, image_id]; |
298 Addsimps [image_ident, image_id]; |
299 |
299 |
300 Goal "(%x. x) -`` Y = Y"; |
300 Goal "(%x. x) -` Y = Y"; |
301 by (Blast_tac 1); |
301 by (Blast_tac 1); |
302 qed "vimage_ident"; |
302 qed "vimage_ident"; |
303 |
303 |
304 Goalw [id_def] "id -`` A = A"; |
304 Goalw [id_def] "id -` A = A"; |
305 by Auto_tac; |
305 by Auto_tac; |
306 qed "vimage_id"; |
306 qed "vimage_id"; |
307 Addsimps [vimage_ident, vimage_id]; |
307 Addsimps [vimage_ident, vimage_id]; |
308 |
308 |
309 Goal "f -`` (f `` A) = {y. EX x:A. f x = f y}"; |
309 Goal "f -` (f ` A) = {y. EX x:A. f x = f y}"; |
310 by (blast_tac (claset() addIs [sym]) 1); |
310 by (blast_tac (claset() addIs [sym]) 1); |
311 qed "vimage_image_eq"; |
311 qed "vimage_image_eq"; |
312 |
312 |
313 Goal "f `` (f -`` A) <= A"; |
313 Goal "f ` (f -` A) <= A"; |
314 by (Blast_tac 1); |
314 by (Blast_tac 1); |
315 qed "image_vimage_subset"; |
315 qed "image_vimage_subset"; |
316 |
316 |
317 Goal "f `` (f -`` A) = A Int range f"; |
317 Goal "f ` (f -` A) = A Int range f"; |
318 by (Blast_tac 1); |
318 by (Blast_tac 1); |
319 qed "image_vimage_eq"; |
319 qed "image_vimage_eq"; |
320 Addsimps [image_vimage_eq]; |
320 Addsimps [image_vimage_eq]; |
321 |
321 |
322 Goal "surj f ==> f `` (f -`` A) = A"; |
322 Goal "surj f ==> f ` (f -` A) = A"; |
323 by (asm_simp_tac (simpset() addsimps [surj_range]) 1); |
323 by (asm_simp_tac (simpset() addsimps [surj_range]) 1); |
324 qed "surj_image_vimage_eq"; |
324 qed "surj_image_vimage_eq"; |
325 |
325 |
326 Goal "surj f ==> f `` (inv f `` A) = A"; |
326 Goal "surj f ==> f ` (inv f ` A) = A"; |
327 by (asm_simp_tac (simpset() addsimps [image_eq_UN, surj_f_inv_f]) 1); |
327 by (asm_simp_tac (simpset() addsimps [image_eq_UN, surj_f_inv_f]) 1); |
328 qed "image_surj_f_inv_f"; |
328 qed "image_surj_f_inv_f"; |
329 |
329 |
330 Goalw [inj_on_def] "inj f ==> f -`` (f `` A) = A"; |
330 Goalw [inj_on_def] "inj f ==> f -` (f ` A) = A"; |
331 by (Blast_tac 1); |
331 by (Blast_tac 1); |
332 qed "inj_vimage_image_eq"; |
332 qed "inj_vimage_image_eq"; |
333 |
333 |
334 Goal "inj f ==> (inv f) `` (f `` A) = A"; |
334 Goal "inj f ==> (inv f) ` (f ` A) = A"; |
335 by (asm_simp_tac (simpset() addsimps [image_eq_UN]) 1); |
335 by (asm_simp_tac (simpset() addsimps [image_eq_UN]) 1); |
336 qed "image_inv_f_f"; |
336 qed "image_inv_f_f"; |
337 |
337 |
338 Goalw [surj_def] "surj f ==> f -`` B <= A ==> B <= f `` A"; |
338 Goalw [surj_def] "surj f ==> f -` B <= A ==> B <= f ` A"; |
339 by (blast_tac (claset() addIs [sym]) 1); |
339 by (blast_tac (claset() addIs [sym]) 1); |
340 qed "vimage_subsetD"; |
340 qed "vimage_subsetD"; |
341 |
341 |
342 Goalw [inj_on_def] "inj f ==> B <= f `` A ==> f -`` B <= A"; |
342 Goalw [inj_on_def] "inj f ==> B <= f ` A ==> f -` B <= A"; |
343 by (Blast_tac 1); |
343 by (Blast_tac 1); |
344 qed "vimage_subsetI"; |
344 qed "vimage_subsetI"; |
345 |
345 |
346 Goalw [bij_def] "bij f ==> (f -`` B <= A) = (B <= f `` A)"; |
346 Goalw [bij_def] "bij f ==> (f -` B <= A) = (B <= f ` A)"; |
347 by (blast_tac (claset() delrules [subsetI] |
347 by (blast_tac (claset() delrules [subsetI] |
348 addIs [vimage_subsetI, vimage_subsetD]) 1); |
348 addIs [vimage_subsetI, vimage_subsetD]) 1); |
349 qed "vimage_subset_eq"; |
349 qed "vimage_subset_eq"; |
350 |
350 |
351 Goal "f``(A Int B) <= f``A Int f``B"; |
351 Goal "f`(A Int B) <= f`A Int f`B"; |
352 by (Blast_tac 1); |
352 by (Blast_tac 1); |
353 qed "image_Int_subset"; |
353 qed "image_Int_subset"; |
354 |
354 |
355 Goal "f``A - f``B <= f``(A - B)"; |
355 Goal "f`A - f`B <= f`(A - B)"; |
356 by (Blast_tac 1); |
356 by (Blast_tac 1); |
357 qed "image_diff_subset"; |
357 qed "image_diff_subset"; |
358 |
358 |
359 Goalw [inj_on_def] |
359 Goalw [inj_on_def] |
360 "[| inj_on f C; A<=C; B<=C |] ==> f``(A Int B) = f``A Int f``B"; |
360 "[| inj_on f C; A<=C; B<=C |] ==> f`(A Int B) = f`A Int f`B"; |
361 by (Blast_tac 1); |
361 by (Blast_tac 1); |
362 qed "inj_on_image_Int"; |
362 qed "inj_on_image_Int"; |
363 |
363 |
364 Goalw [inj_on_def] |
364 Goalw [inj_on_def] |
365 "[| inj_on f C; A<=C; B<=C |] ==> f``(A-B) = f``A - f``B"; |
365 "[| inj_on f C; A<=C; B<=C |] ==> f`(A-B) = f`A - f`B"; |
366 by (Blast_tac 1); |
366 by (Blast_tac 1); |
367 qed "inj_on_image_set_diff"; |
367 qed "inj_on_image_set_diff"; |
368 |
368 |
369 Goalw [inj_on_def] "inj f ==> f``(A Int B) = f``A Int f``B"; |
369 Goalw [inj_on_def] "inj f ==> f`(A Int B) = f`A Int f`B"; |
370 by (Blast_tac 1); |
370 by (Blast_tac 1); |
371 qed "image_Int"; |
371 qed "image_Int"; |
372 |
372 |
373 Goalw [inj_on_def] "inj f ==> f``(A-B) = f``A - f``B"; |
373 Goalw [inj_on_def] "inj f ==> f`(A-B) = f`A - f`B"; |
374 by (Blast_tac 1); |
374 by (Blast_tac 1); |
375 qed "image_set_diff"; |
375 qed "image_set_diff"; |
376 |
376 |
377 Goalw [image_def] "inj(f) ==> inv(f)``(f``X) = X"; |
377 Goalw [image_def] "inj(f) ==> inv(f)`(f`X) = X"; |
378 by Auto_tac; |
378 by Auto_tac; |
379 qed "inv_image_comp"; |
379 qed "inv_image_comp"; |
380 |
380 |
381 Goal "inj f ==> (f a : f``A) = (a : A)"; |
381 Goal "inj f ==> (f a : f`A) = (a : A)"; |
382 by (blast_tac (claset() addDs [injD]) 1); |
382 by (blast_tac (claset() addDs [injD]) 1); |
383 qed "inj_image_mem_iff"; |
383 qed "inj_image_mem_iff"; |
384 |
384 |
385 Goalw [inj_on_def] "inj f ==> (f``A <= f``B) = (A<=B)"; |
385 Goalw [inj_on_def] "inj f ==> (f`A <= f`B) = (A<=B)"; |
386 by (Blast_tac 1); |
386 by (Blast_tac 1); |
387 qed "inj_image_subset_iff"; |
387 qed "inj_image_subset_iff"; |
388 |
388 |
389 Goal "inj f ==> (f``A = f``B) = (A = B)"; |
389 Goal "inj f ==> (f`A = f`B) = (A = B)"; |
390 by (blast_tac (claset() addSEs [equalityE] addDs [injD]) 1); |
390 by (blast_tac (claset() addSEs [equalityE] addDs [injD]) 1); |
391 qed "inj_image_eq_iff"; |
391 qed "inj_image_eq_iff"; |
392 |
392 |
393 Goal "(f `` (UNION A B)) = (UN x:A.(f `` (B x)))"; |
393 Goal "(f ` (UNION A B)) = (UN x:A.(f ` (B x)))"; |
394 by (Blast_tac 1); |
394 by (Blast_tac 1); |
395 qed "image_UN"; |
395 qed "image_UN"; |
396 |
396 |
397 (*injectivity's required. Left-to-right inclusion holds even if A is empty*) |
397 (*injectivity's required. Left-to-right inclusion holds even if A is empty*) |
398 Goalw [inj_on_def] |
398 Goalw [inj_on_def] |
399 "[| inj_on f C; ALL x:A. B x <= C; j:A |] \ |
399 "[| inj_on f C; ALL x:A. B x <= C; j:A |] \ |
400 \ ==> f `` (INTER A B) = (INT x:A. f `` B x)"; |
400 \ ==> f ` (INTER A B) = (INT x:A. f ` B x)"; |
401 by (Blast_tac 1); |
401 by (Blast_tac 1); |
402 qed "image_INT"; |
402 qed "image_INT"; |
403 |
403 |
404 (*Compare with image_INT: no use of inj_on, and if f is surjective then |
404 (*Compare with image_INT: no use of inj_on, and if f is surjective then |
405 it doesn't matter whether A is empty*) |
405 it doesn't matter whether A is empty*) |
406 Goalw [bij_def] "bij f ==> f `` (INTER A B) = (INT x:A. f `` B x)"; |
406 Goalw [bij_def] "bij f ==> f ` (INTER A B) = (INT x:A. f ` B x)"; |
407 by (force_tac (claset() addSIs [surj_f_inv_f RS sym RS image_eqI], |
407 by (force_tac (claset() addSIs [surj_f_inv_f RS sym RS image_eqI], |
408 simpset()) 1); |
408 simpset()) 1); |
409 qed "bij_image_INT"; |
409 qed "bij_image_INT"; |
410 |
410 |
411 Goal "bij f ==> f `` Collect P = {y. P (inv f y)}"; |
411 Goal "bij f ==> f ` Collect P = {y. P (inv f y)}"; |
412 by Auto_tac; |
412 by Auto_tac; |
413 by (force_tac (claset(), simpset() addsimps [bij_is_inj]) 1); |
413 by (force_tac (claset(), simpset() addsimps [bij_is_inj]) 1); |
414 by (blast_tac (claset() addIs [bij_is_surj RS surj_f_inv_f RS sym]) 1); |
414 by (blast_tac (claset() addIs [bij_is_surj RS surj_f_inv_f RS sym]) 1); |
415 qed "bij_image_Collect_eq"; |
415 qed "bij_image_Collect_eq"; |
416 |
416 |
417 Goal "bij f ==> f -`` A = inv f `` A"; |
417 Goal "bij f ==> f -` A = inv f ` A"; |
418 by Safe_tac; |
418 by Safe_tac; |
419 by (asm_simp_tac (simpset() addsimps [bij_is_surj RS surj_f_inv_f]) 2); |
419 by (asm_simp_tac (simpset() addsimps [bij_is_surj RS surj_f_inv_f]) 2); |
420 by (blast_tac (claset() addIs [bij_is_inj RS inv_f_f RS sym]) 1); |
420 by (blast_tac (claset() addIs [bij_is_inj RS inv_f_f RS sym]) 1); |
421 qed "bij_vimage_eq_inv_image"; |
421 qed "bij_vimage_eq_inv_image"; |
422 |
422 |
423 Goal "surj f ==> -(f``A) <= f``(-A)"; |
423 Goal "surj f ==> -(f`A) <= f`(-A)"; |
424 by (auto_tac (claset(), simpset() addsimps [surj_def])); |
424 by (auto_tac (claset(), simpset() addsimps [surj_def])); |
425 qed "surj_Compl_image_subset"; |
425 qed "surj_Compl_image_subset"; |
426 |
426 |
427 Goal "inj f ==> f``(-A) <= -(f``A)"; |
427 Goal "inj f ==> f`(-A) <= -(f`A)"; |
428 by (auto_tac (claset(), simpset() addsimps [inj_on_def])); |
428 by (auto_tac (claset(), simpset() addsimps [inj_on_def])); |
429 qed "inj_image_Compl_subset"; |
429 qed "inj_image_Compl_subset"; |
430 |
430 |
431 Goalw [bij_def] "bij f ==> f``(-A) = -(f``A)"; |
431 Goalw [bij_def] "bij f ==> f`(-A) = -(f`A)"; |
432 by (rtac equalityI 1); |
432 by (rtac equalityI 1); |
433 by (ALLGOALS (asm_simp_tac (simpset() addsimps [inj_image_Compl_subset, |
433 by (ALLGOALS (asm_simp_tac (simpset() addsimps [inj_image_Compl_subset, |
434 surj_Compl_image_subset]))); |
434 surj_Compl_image_subset]))); |
435 qed "bij_image_Compl_eq"; |
435 qed "bij_image_Compl_eq"; |
436 |
436 |
550 |
550 |
551 Goal "[| f: A funcset B; g: B funcset C; x: A |]==> compose A g f x = g(f(x))"; |
551 Goal "[| f: A funcset B; g: B funcset C; x: A |]==> compose A g f x = g(f(x))"; |
552 by (asm_full_simp_tac (simpset() addsimps [compose_def, restrict_def]) 1); |
552 by (asm_full_simp_tac (simpset() addsimps [compose_def, restrict_def]) 1); |
553 qed "compose_eq"; |
553 qed "compose_eq"; |
554 |
554 |
555 Goal "[| f : A funcset B; f `` A = B; g: B funcset C; g `` B = C |]\ |
555 Goal "[| f : A funcset B; f ` A = B; g: B funcset C; g ` B = C |]\ |
556 \ ==> compose A g f `` A = C"; |
556 \ ==> compose A g f ` A = C"; |
557 by (auto_tac (claset(), |
557 by (auto_tac (claset(), |
558 simpset() addsimps [image_def, compose_eq])); |
558 simpset() addsimps [image_def, compose_eq])); |
559 qed "surj_compose"; |
559 qed "surj_compose"; |
560 |
560 |
561 Goal "[| f : A funcset B; g: B funcset C; f `` A = B; inj_on f A; inj_on g B |]\ |
561 Goal "[| f : A funcset B; g: B funcset C; f ` A = B; inj_on f A; inj_on g B |]\ |
562 \ ==> inj_on (compose A g f) A"; |
562 \ ==> inj_on (compose A g f) A"; |
563 by (auto_tac (claset(), |
563 by (auto_tac (claset(), |
564 simpset() addsimps [inj_on_def, compose_eq])); |
564 simpset() addsimps [inj_on_def, compose_eq])); |
565 qed "inj_on_compose"; |
565 qed "inj_on_compose"; |
566 |
566 |
567 |
567 |
568 (*** restrict / lam ***) |
568 (*** restrict / lam ***) |
569 |
569 |
570 Goal "f``A <= B ==> (lam x: A. f x) : A funcset B"; |
570 Goal "f`A <= B ==> (lam x: A. f x) : A funcset B"; |
571 by (auto_tac (claset(), |
571 by (auto_tac (claset(), |
572 simpset() addsimps [restrict_def, Pi_def])); |
572 simpset() addsimps [restrict_def, Pi_def])); |
573 qed "restrict_in_funcset"; |
573 qed "restrict_in_funcset"; |
574 |
574 |
575 val prems = Goalw [restrict_def, Pi_def] |
575 val prems = Goalw [restrict_def, Pi_def] |
601 qed "inj_on_restrict_eq"; |
601 qed "inj_on_restrict_eq"; |
602 |
602 |
603 |
603 |
604 (*** Inverse ***) |
604 (*** Inverse ***) |
605 |
605 |
606 Goal "[|f `` A = B; x: B |] ==> ? y: A. f y = x"; |
606 Goal "[|f ` A = B; x: B |] ==> ? y: A. f y = x"; |
607 by (Blast_tac 1); |
607 by (Blast_tac 1); |
608 qed "surj_image"; |
608 qed "surj_image"; |
609 |
609 |
610 Goalw [Inv_def] "[| f `` A = B; f : A funcset B |] \ |
610 Goalw [Inv_def] "[| f ` A = B; f : A funcset B |] \ |
611 \ ==> (lam x: B. (Inv A f) x) : B funcset A"; |
611 \ ==> (lam x: B. (Inv A f) x) : B funcset A"; |
612 by (fast_tac (claset() addIs [restrict_in_funcset, someI2]) 1); |
612 by (fast_tac (claset() addIs [restrict_in_funcset, someI2]) 1); |
613 qed "Inv_funcset"; |
613 qed "Inv_funcset"; |
614 |
614 |
615 |
615 |
616 Goal "[| f: A funcset B; inj_on f A; f `` A = B; x: A |] \ |
616 Goal "[| f: A funcset B; inj_on f A; f ` A = B; x: A |] \ |
617 \ ==> (lam y: B. (Inv A f) y) (f x) = x"; |
617 \ ==> (lam y: B. (Inv A f) y) (f x) = x"; |
618 by (asm_simp_tac (simpset() addsimps [restrict_apply1, funcset_mem]) 1); |
618 by (asm_simp_tac (simpset() addsimps [restrict_apply1, funcset_mem]) 1); |
619 by (asm_full_simp_tac (simpset() addsimps [Inv_def, inj_on_def]) 1); |
619 by (asm_full_simp_tac (simpset() addsimps [Inv_def, inj_on_def]) 1); |
620 by (rtac someI2 1); |
620 by (rtac someI2 1); |
621 by Auto_tac; |
621 by Auto_tac; |
622 qed "Inv_f_f"; |
622 qed "Inv_f_f"; |
623 |
623 |
624 Goal "[| f: A funcset B; f `` A = B; x: B |] \ |
624 Goal "[| f: A funcset B; f ` A = B; x: B |] \ |
625 \ ==> f ((lam y: B. (Inv A f y)) x) = x"; |
625 \ ==> f ((lam y: B. (Inv A f y)) x) = x"; |
626 by (asm_simp_tac (simpset() addsimps [Inv_def, restrict_apply1]) 1); |
626 by (asm_simp_tac (simpset() addsimps [Inv_def, restrict_apply1]) 1); |
627 by (fast_tac (claset() addIs [someI2]) 1); |
627 by (fast_tac (claset() addIs [someI2]) 1); |
628 qed "f_Inv_f"; |
628 qed "f_Inv_f"; |
629 |
629 |
630 Goal "[| f: A funcset B; inj_on f A; f `` A = B |]\ |
630 Goal "[| f: A funcset B; inj_on f A; f ` A = B |]\ |
631 \ ==> compose A (lam y:B. (Inv A f) y) f = (lam x: A. x)"; |
631 \ ==> compose A (lam y:B. (Inv A f) y) f = (lam x: A. x)"; |
632 by (rtac Pi_extensionality 1); |
632 by (rtac Pi_extensionality 1); |
633 by (blast_tac (claset() addIs [funcset_compose, Inv_funcset]) 1); |
633 by (blast_tac (claset() addIs [funcset_compose, Inv_funcset]) 1); |
634 by (blast_tac (claset() addIs [restrict_in_funcset]) 1); |
634 by (blast_tac (claset() addIs [restrict_in_funcset]) 1); |
635 by (asm_simp_tac |
635 by (asm_simp_tac |