equal
deleted
inserted
replaced
47 Goalw [equiv_def,trans_def,sym_def] |
47 Goalw [equiv_def,trans_def,sym_def] |
48 "!!A r. [| equiv A r; (a,b): r |] ==> r^^{a} <= r^^{b}"; |
48 "!!A r. [| equiv A r; (a,b): r |] ==> r^^{a} <= r^^{b}"; |
49 by (Blast_tac 1); |
49 by (Blast_tac 1); |
50 qed "equiv_class_subset"; |
50 qed "equiv_class_subset"; |
51 |
51 |
52 Goal "!!A r. [| equiv A r; (a,b): r |] ==> r^^{a} = r^^{b}"; |
52 Goal "[| equiv A r; (a,b): r |] ==> r^^{a} = r^^{b}"; |
53 by (REPEAT (ares_tac [equalityI, equiv_class_subset] 1)); |
53 by (REPEAT (ares_tac [equalityI, equiv_class_subset] 1)); |
54 by (rewrite_goals_tac [equiv_def,sym_def]); |
54 by (rewrite_goals_tac [equiv_def,sym_def]); |
55 by (Blast_tac 1); |
55 by (Blast_tac 1); |
56 qed "equiv_class_eq"; |
56 qed "equiv_class_eq"; |
57 |
57 |
96 |
96 |
97 (*** Quotients ***) |
97 (*** Quotients ***) |
98 |
98 |
99 (** Introduction/elimination rules -- needed? **) |
99 (** Introduction/elimination rules -- needed? **) |
100 |
100 |
101 Goalw [quotient_def] "!!A. x:A ==> r^^{x}: A/r"; |
101 Goalw [quotient_def] "x:A ==> r^^{x}: A/r"; |
102 by (Blast_tac 1); |
102 by (Blast_tac 1); |
103 qed "quotientI"; |
103 qed "quotientI"; |
104 |
104 |
105 val [major,minor] = goalw Equiv.thy [quotient_def] |
105 val [major,minor] = goalw Equiv.thy [quotient_def] |
106 "[| X:(A/r); !!x. [| X = r^^{x}; x:A |] ==> P |] \ |
106 "[| X:(A/r); !!x. [| X = r^^{x}; x:A |] ==> P |] \ |
137 (** These proofs really require the local premises |
137 (** These proofs really require the local premises |
138 equiv A r; congruent r b |
138 equiv A r; congruent r b |
139 **) |
139 **) |
140 |
140 |
141 (*Conversion rule*) |
141 (*Conversion rule*) |
142 Goal "!!A r. [| equiv A r; congruent r b; a: A |] \ |
142 Goal "[| equiv A r; congruent r b; a: A |] \ |
143 \ ==> (UN x:r^^{a}. b(x)) = b(a)"; |
143 \ ==> (UN x:r^^{a}. b(x)) = b(a)"; |
144 by (rtac (equiv_class_self RS UN_singleton) 1 THEN REPEAT (assume_tac 1)); |
144 by (rtac (equiv_class_self RS UN_singleton) 1 THEN REPEAT (assume_tac 1)); |
145 by (rewrite_goals_tac [equiv_def,congruent_def,sym_def]); |
145 by (rewrite_goals_tac [equiv_def,congruent_def,sym_def]); |
146 by (Blast_tac 1); |
146 by (Blast_tac 1); |
147 qed "UN_equiv_class"; |
147 qed "UN_equiv_class"; |
242 |
242 |
243 |
243 |
244 (*** Cardinality results suggested by Florian Kammueller ***) |
244 (*** Cardinality results suggested by Florian Kammueller ***) |
245 |
245 |
246 (*Recall that equiv A r implies r <= A Times A (equiv_type) *) |
246 (*Recall that equiv A r implies r <= A Times A (equiv_type) *) |
247 Goal "!!A. [| finite A; r <= A Times A |] ==> finite (A/r)"; |
247 Goal "[| finite A; r <= A Times A |] ==> finite (A/r)"; |
248 by (rtac finite_subset 1); |
248 by (rtac finite_subset 1); |
249 by (etac (finite_Pow_iff RS iffD2) 2); |
249 by (etac (finite_Pow_iff RS iffD2) 2); |
250 by (rewtac quotient_def); |
250 by (rewtac quotient_def); |
251 by (Blast_tac 1); |
251 by (Blast_tac 1); |
252 qed "finite_quotient"; |
252 qed "finite_quotient"; |
256 by (rtac finite_subset 1); |
256 by (rtac finite_subset 1); |
257 by (assume_tac 2); |
257 by (assume_tac 2); |
258 by (Blast_tac 1); |
258 by (Blast_tac 1); |
259 qed "finite_equiv_class"; |
259 qed "finite_equiv_class"; |
260 |
260 |
261 Goal "!!A. [| finite A; equiv A r; ! X : A/r. k dvd card(X) |] \ |
261 Goal "[| finite A; equiv A r; ! X : A/r. k dvd card(X) |] \ |
262 \ ==> k dvd card(A)"; |
262 \ ==> k dvd card(A)"; |
263 by (rtac (Union_quotient RS subst) 1); |
263 by (rtac (Union_quotient RS subst) 1); |
264 by (assume_tac 1); |
264 by (assume_tac 1); |
265 by (rtac dvd_partition 1); |
265 by (rtac dvd_partition 1); |
266 by (blast_tac (claset() delrules [equalityI] addEs [quotient_disj RS disjE]) 4); |
266 by (blast_tac (claset() delrules [equalityI] addEs [quotient_disj RS disjE]) 4); |