equal
deleted
inserted
replaced
21 |
21 |
22 (*** inj(f): f is a one-to-one function ***) |
22 (*** inj(f): f is a one-to-one function ***) |
23 |
23 |
24 val prems = goalw Fun.thy [inj_def] |
24 val prems = goalw Fun.thy [inj_def] |
25 "[| !! x y. f(x) = f(y) ==> x=y |] ==> inj(f)"; |
25 "[| !! x y. f(x) = f(y) ==> x=y |] ==> inj(f)"; |
26 by (blast_tac (!claset addIs prems) 1); |
26 by (blast_tac (claset() addIs prems) 1); |
27 qed "injI"; |
27 qed "injI"; |
28 |
28 |
29 val [major] = goal Fun.thy "(!!x. g(f(x)) = x) ==> inj(f)"; |
29 val [major] = goal Fun.thy "(!!x. g(f(x)) = x) ==> inj(f)"; |
30 by (rtac injI 1); |
30 by (rtac injI 1); |
31 by (etac (arg_cong RS box_equals) 1); |
31 by (etac (arg_cong RS box_equals) 1); |
67 |
67 |
68 (*** inj_onto f A: f is one-to-one over A ***) |
68 (*** inj_onto f A: f is one-to-one over A ***) |
69 |
69 |
70 val prems = goalw Fun.thy [inj_onto_def] |
70 val prems = goalw Fun.thy [inj_onto_def] |
71 "(!! x y. [| f(x) = f(y); x:A; y:A |] ==> x=y) ==> inj_onto f A"; |
71 "(!! x y. [| f(x) = f(y); x:A; y:A |] ==> x=y) ==> inj_onto f A"; |
72 by (blast_tac (!claset addIs prems) 1); |
72 by (blast_tac (claset() addIs prems) 1); |
73 qed "inj_ontoI"; |
73 qed "inj_ontoI"; |
74 |
74 |
75 val [major] = goal Fun.thy |
75 val [major] = goal Fun.thy |
76 "(!!x. x:A ==> g(f(x)) = x) ==> inj_onto f A"; |
76 "(!!x. x:A ==> g(f(x)) = x) ==> inj_onto f A"; |
77 by (rtac inj_ontoI 1); |
77 by (rtac inj_ontoI 1); |
84 by (rtac (major RS bspec RS bspec RS mp) 1); |
84 by (rtac (major RS bspec RS bspec RS mp) 1); |
85 by (REPEAT (resolve_tac prems 1)); |
85 by (REPEAT (resolve_tac prems 1)); |
86 qed "inj_ontoD"; |
86 qed "inj_ontoD"; |
87 |
87 |
88 goal Fun.thy "!!x y.[| inj_onto f A; x:A; y:A |] ==> (f(x)=f(y)) = (x=y)"; |
88 goal Fun.thy "!!x y.[| inj_onto f A; x:A; y:A |] ==> (f(x)=f(y)) = (x=y)"; |
89 by (blast_tac (!claset addSDs [inj_ontoD]) 1); |
89 by (blast_tac (claset() addSDs [inj_ontoD]) 1); |
90 qed "inj_onto_iff"; |
90 qed "inj_onto_iff"; |
91 |
91 |
92 val major::prems = goal Fun.thy |
92 val major::prems = goal Fun.thy |
93 "[| inj_onto f A; ~x=y; x:A; y:A |] ==> ~ f(x)=f(y)"; |
93 "[| inj_onto f A; ~x=y; x:A; y:A |] ==> ~ f(x)=f(y)"; |
94 by (rtac contrapos 1); |
94 by (rtac contrapos 1); |
104 |
104 |
105 (*** Lemmas about inj ***) |
105 (*** Lemmas about inj ***) |
106 |
106 |
107 goalw Fun.thy [o_def] |
107 goalw Fun.thy [o_def] |
108 "!!f g. [| inj(f); inj_onto g (range f) |] ==> inj(g o f)"; |
108 "!!f g. [| inj(f); inj_onto g (range f) |] ==> inj(g o f)"; |
109 by (fast_tac (!claset addIs [injI] addEs [injD, inj_ontoD]) 1); |
109 by (fast_tac (claset() addIs [injI] addEs [injD, inj_ontoD]) 1); |
110 qed "comp_inj"; |
110 qed "comp_inj"; |
111 |
111 |
112 val [prem] = goal Fun.thy "inj(f) ==> inj_onto f A"; |
112 val [prem] = goal Fun.thy "inj(f) ==> inj_onto f A"; |
113 by (blast_tac (!claset addIs [prem RS injD, inj_ontoI]) 1); |
113 by (blast_tac (claset() addIs [prem RS injD, inj_ontoI]) 1); |
114 qed "inj_imp"; |
114 qed "inj_imp"; |
115 |
115 |
116 val [prem] = goalw Fun.thy [inv_def] "y : range(f) ==> f(inv f y) = y"; |
116 val [prem] = goalw Fun.thy [inv_def] "y : range(f) ==> f(inv f y) = y"; |
117 by (EVERY1 [rtac (prem RS rangeE), rtac selectI, etac sym]); |
117 by (EVERY1 [rtac (prem RS rangeE), rtac selectI, etac sym]); |
118 qed "f_inv_f"; |
118 qed "f_inv_f"; |
122 by (rtac (arg_cong RS box_equals) 1); |
122 by (rtac (arg_cong RS box_equals) 1); |
123 by (REPEAT (resolve_tac (prems @ [f_inv_f]) 1)); |
123 by (REPEAT (resolve_tac (prems @ [f_inv_f]) 1)); |
124 qed "inv_injective"; |
124 qed "inv_injective"; |
125 |
125 |
126 goal Fun.thy "!!f. [| inj(f); A<=range(f) |] ==> inj_onto (inv f) A"; |
126 goal Fun.thy "!!f. [| inj(f); A<=range(f) |] ==> inj_onto (inv f) A"; |
127 by (fast_tac (!claset addIs [inj_ontoI] |
127 by (fast_tac (claset() addIs [inj_ontoI] |
128 addEs [inv_injective,injD]) 1); |
128 addEs [inv_injective,injD]) 1); |
129 qed "inj_onto_inv"; |
129 qed "inj_onto_inv"; |
130 |
130 |
131 goalw thy [inj_onto_def] |
131 goalw thy [inj_onto_def] |
132 "!!f. [| inj_onto f C; A<=C; B<=C |] ==> f``(A Int B) = f``A Int f``B"; |
132 "!!f. [| inj_onto f C; A<=C; B<=C |] ==> f``(A Int B) = f``A Int f``B"; |
145 goalw thy [inj_def] "!!f. inj f ==> f``(A-B) = f``A - f``B"; |
145 goalw thy [inj_def] "!!f. inj f ==> f``(A-B) = f``A - f``B"; |
146 by (Blast_tac 1); |
146 by (Blast_tac 1); |
147 qed "image_set_diff"; |
147 qed "image_set_diff"; |
148 |
148 |
149 |
149 |
150 val set_cs = !claset delrules [equalityI]; |
150 val set_cs = claset() delrules [equalityI]; |