546 by (blast_tac (claset() addIs [funcset_compose]) 1); |
546 by (blast_tac (claset() addIs [funcset_compose]) 1); |
547 by (rewrite_goals_tac [Pi_def, compose_def, restrict_def]); |
547 by (rewrite_goals_tac [Pi_def, compose_def, restrict_def]); |
548 by Auto_tac; |
548 by Auto_tac; |
549 qed "compose_assoc"; |
549 qed "compose_assoc"; |
550 |
550 |
551 Goal "[| f: A funcset B; g: B funcset C; x: A |]==> compose A g f x = g(f(x))"; |
551 Goal "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_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 = B; g ` B = C |] ==> compose A g f ` A = C"; |
556 \ ==> compose A g f ` A = C"; |
556 by (auto_tac (claset(), simpset() addsimps [image_def, compose_eq])); |
557 by (auto_tac (claset(), |
|
558 simpset() addsimps [image_def, compose_eq])); |
|
559 qed "surj_compose"; |
557 qed "surj_compose"; |
560 |
558 |
561 Goal "[| f : A funcset B; g: B funcset C; f ` A = B; inj_on f A; inj_on g B |]\ |
559 Goal "[| f ` A = B; inj_on f A; inj_on g B |] ==> inj_on (compose A g f) A"; |
562 \ ==> inj_on (compose A g f) A"; |
560 by (auto_tac (claset(), simpset() addsimps [inj_on_def, compose_eq])); |
563 by (auto_tac (claset(), |
|
564 simpset() addsimps [inj_on_def, compose_eq])); |
|
565 qed "inj_on_compose"; |
561 qed "inj_on_compose"; |
566 |
562 |
567 |
563 |
568 (*** restrict / lam ***) |
564 (*** restrict / lam ***) |
569 |
565 |
594 qed "inj_on_restrict_eq"; |
590 qed "inj_on_restrict_eq"; |
595 |
591 |
596 |
592 |
597 (*** Inverse ***) |
593 (*** Inverse ***) |
598 |
594 |
599 Goal "[|f ` A = B; x: B |] ==> ? y: A. f y = x"; |
595 Goalw [Inv_def] "f ` A = B ==> (lam x: B. (Inv A f) x) : B funcset A"; |
600 by (Blast_tac 1); |
|
601 qed "surj_image"; |
|
602 |
|
603 Goalw [Inv_def] "[| f ` A = B; f : A funcset B |] \ |
|
604 \ ==> (lam x: B. (Inv A f) x) : B funcset A"; |
|
605 by (fast_tac (claset() addIs [restrict_in_funcset, someI2]) 1); |
596 by (fast_tac (claset() addIs [restrict_in_funcset, someI2]) 1); |
606 qed "Inv_funcset"; |
597 qed "Inv_funcset"; |
607 |
598 |
608 Goal "[| inj_on f A; f: A funcset (f`A); x : A |] \ |
599 Goal "[| inj_on f A; x : A |] ==> Inv A f (f x) = x"; |
609 \ ==> Inv A f (f x) = x"; |
|
610 by (asm_full_simp_tac (simpset() addsimps [Inv_def, inj_on_def]) 1); |
600 by (asm_full_simp_tac (simpset() addsimps [Inv_def, inj_on_def]) 1); |
611 by (rtac someI2 1); |
601 by (blast_tac (claset() addIs [someI2]) 1); |
612 by Auto_tac; |
|
613 qed "Inv_f_f"; |
602 qed "Inv_f_f"; |
614 |
603 |
615 (*a strange theorem, but so is f_inv_f*) |
604 Goal "y : f`A ==> f (Inv A f y) = y"; |
616 Goal "[| f: A funcset B; f ` A = B; x: B |] \ |
|
617 \ ==> f ((lam y: B. (Inv A f y)) x) = x"; |
|
618 by (asm_simp_tac (simpset() addsimps [Inv_def]) 1); |
605 by (asm_simp_tac (simpset() addsimps [Inv_def]) 1); |
619 by (fast_tac (claset() addIs [someI2]) 1); |
606 by (fast_tac (claset() addIs [someI2]) 1); |
620 qed "f_Inv_f"; |
607 qed "f_Inv_f"; |
621 |
608 |
622 Goal "[| f: A funcset B; inj_on f A; f ` A = B |]\ |
609 Goal "[| Inv A f x = Inv A f y; x : f`A; y : f`A |] ==> x=y"; |
|
610 by (rtac (arg_cong RS box_equals) 1); |
|
611 by (REPEAT (ares_tac [f_Inv_f] 1)); |
|
612 qed "Inv_injective"; |
|
613 |
|
614 Goal "B <= f`A ==> inj_on (Inv A f) B"; |
|
615 by (rtac inj_onI 1); |
|
616 by (blast_tac (claset() addIs [inj_onI] addDs [Inv_injective, injD]) 1); |
|
617 qed "inj_on_Inv"; |
|
618 |
|
619 Goal "f : A funcset B ==> compose A (lam y:B. y) f = f"; |
|
620 by (rtac ext 1); |
|
621 by (auto_tac (claset(), simpset() addsimps [compose_def, Pi_def])); |
|
622 qed "Id_compose"; |
|
623 |
|
624 Goal "g : A funcset B ==> compose A g (lam x:A. x) = g"; |
|
625 by (rtac ext 1); |
|
626 by (auto_tac (claset(), simpset() addsimps [compose_def, Pi_def])); |
|
627 qed "compose_Id"; |
|
628 |
|
629 Goal "[| inj_on f A; f ` A = B |] \ |
623 \ ==> compose A (lam y:B. (Inv A f) y) f = (lam x: A. x)"; |
630 \ ==> compose A (lam y:B. (Inv A f) y) f = (lam x: A. x)"; |
624 by (rtac Pi_extensionality 1); |
631 by (asm_simp_tac (simpset() addsimps [compose_def]) 1); |
625 by (blast_tac (claset() addIs [funcset_compose, Inv_funcset]) 1); |
632 by (rtac restrict_ext 1); |
626 by (blast_tac (claset() addIs [restrict_in_funcset]) 1); |
633 by Auto_tac; |
627 by (asm_simp_tac |
634 by (etac subst 1); |
628 (simpset() addsimps [compose_def, Inv_f_f]) 1); |
635 by (asm_full_simp_tac (simpset() addsimps [Inv_f_f]) 1); |
629 by Auto_tac; |
|
630 qed "compose_Inv_id"; |
636 qed "compose_Inv_id"; |
631 |
637 |
632 |
638 |
633 (*** Pi ***) |
639 (*** Pi ***) |
634 |
640 |