35 |
35 |
36 (** Equivalence classes **) |
36 (** Equivalence classes **) |
37 |
37 |
38 (*Lemma for the next result*) |
38 (*Lemma for the next result*) |
39 Goalw [equiv_def,trans_def,sym_def] |
39 Goalw [equiv_def,trans_def,sym_def] |
40 "[| equiv A r; (a,b): r |] ==> r```{a} <= r```{b}"; |
40 "[| equiv A r; (a,b): r |] ==> r``{a} <= r``{b}"; |
41 by (Blast_tac 1); |
41 by (Blast_tac 1); |
42 qed "equiv_class_subset"; |
42 qed "equiv_class_subset"; |
43 |
43 |
44 Goal "[| equiv A r; (a,b): r |] ==> r```{a} = r```{b}"; |
44 Goal "[| equiv A r; (a,b): r |] ==> r``{a} = r``{b}"; |
45 by (REPEAT (ares_tac [equalityI, equiv_class_subset] 1)); |
45 by (REPEAT (ares_tac [equalityI, equiv_class_subset] 1)); |
46 by (rewrite_goals_tac [equiv_def,sym_def]); |
46 by (rewrite_goals_tac [equiv_def,sym_def]); |
47 by (Blast_tac 1); |
47 by (Blast_tac 1); |
48 qed "equiv_class_eq"; |
48 qed "equiv_class_eq"; |
49 |
49 |
50 Goalw [equiv_def,refl_def] "[| equiv A r; a: A |] ==> a: r```{a}"; |
50 Goalw [equiv_def,refl_def] "[| equiv A r; a: A |] ==> a: r``{a}"; |
51 by (Blast_tac 1); |
51 by (Blast_tac 1); |
52 qed "equiv_class_self"; |
52 qed "equiv_class_self"; |
53 |
53 |
54 (*Lemma for the next result*) |
54 (*Lemma for the next result*) |
55 Goalw [equiv_def,refl_def] |
55 Goalw [equiv_def,refl_def] |
56 "[| equiv A r; r```{b} <= r```{a}; b: A |] ==> (a,b): r"; |
56 "[| equiv A r; r``{b} <= r``{a}; b: A |] ==> (a,b): r"; |
57 by (Blast_tac 1); |
57 by (Blast_tac 1); |
58 qed "subset_equiv_class"; |
58 qed "subset_equiv_class"; |
59 |
59 |
60 Goal "[| r```{a} = r```{b}; equiv A r; b: A |] ==> (a,b): r"; |
60 Goal "[| r``{a} = r``{b}; equiv A r; b: A |] ==> (a,b): r"; |
61 by (REPEAT (ares_tac [equalityD2, subset_equiv_class] 1)); |
61 by (REPEAT (ares_tac [equalityD2, subset_equiv_class] 1)); |
62 qed "eq_equiv_class"; |
62 qed "eq_equiv_class"; |
63 |
63 |
64 (*thus r```{a} = r```{b} as well*) |
64 (*thus r``{a} = r``{b} as well*) |
65 Goalw [equiv_def,trans_def,sym_def] |
65 Goalw [equiv_def,trans_def,sym_def] |
66 "[| equiv A r; x: (r```{a} Int r```{b}) |] ==> (a,b): r"; |
66 "[| equiv A r; x: (r``{a} Int r``{b}) |] ==> (a,b): r"; |
67 by (Blast_tac 1); |
67 by (Blast_tac 1); |
68 qed "equiv_class_nondisjoint"; |
68 qed "equiv_class_nondisjoint"; |
69 |
69 |
70 Goalw [equiv_def,refl_def] "equiv A r ==> r <= A <*> A"; |
70 Goalw [equiv_def,refl_def] "equiv A r ==> r <= A <*> A"; |
71 by (Blast_tac 1); |
71 by (Blast_tac 1); |
72 qed "equiv_type"; |
72 qed "equiv_type"; |
73 |
73 |
74 Goal "equiv A r ==> ((x,y): r) = (r```{x} = r```{y} & x:A & y:A)"; |
74 Goal "equiv A r ==> ((x,y): r) = (r``{x} = r``{y} & x:A & y:A)"; |
75 by (blast_tac (claset() addSIs [equiv_class_eq] |
75 by (blast_tac (claset() addSIs [equiv_class_eq] |
76 addDs [eq_equiv_class, equiv_type]) 1); |
76 addDs [eq_equiv_class, equiv_type]) 1); |
77 qed "equiv_class_eq_iff"; |
77 qed "equiv_class_eq_iff"; |
78 |
78 |
79 Goal "[| equiv A r; x: A; y: A |] ==> (r```{x} = r```{y}) = ((x,y): r)"; |
79 Goal "[| equiv A r; x: A; y: A |] ==> (r``{x} = r``{y}) = ((x,y): r)"; |
80 by (blast_tac (claset() addSIs [equiv_class_eq] |
80 by (blast_tac (claset() addSIs [equiv_class_eq] |
81 addDs [eq_equiv_class, equiv_type]) 1); |
81 addDs [eq_equiv_class, equiv_type]) 1); |
82 qed "eq_equiv_class_iff"; |
82 qed "eq_equiv_class_iff"; |
83 |
83 |
84 (*** Quotients ***) |
84 (*** Quotients ***) |
85 |
85 |
86 (** Introduction/elimination rules -- needed? **) |
86 (** Introduction/elimination rules -- needed? **) |
87 |
87 |
88 Goalw [quotient_def] "x:A ==> r```{x}: A//r"; |
88 Goalw [quotient_def] "x:A ==> r``{x}: A//r"; |
89 by (Blast_tac 1); |
89 by (Blast_tac 1); |
90 qed "quotientI"; |
90 qed "quotientI"; |
91 |
91 |
92 val [major,minor] = Goalw [quotient_def] |
92 val [major,minor] = Goalw [quotient_def] |
93 "[| X:(A//r); !!x. [| X = r```{x}; x:A |] ==> P |] \ |
93 "[| X:(A//r); !!x. [| X = r``{x}; x:A |] ==> P |] \ |
94 \ ==> P"; |
94 \ ==> P"; |
95 by (resolve_tac [major RS UN_E] 1); |
95 by (resolve_tac [major RS UN_E] 1); |
96 by (rtac minor 1); |
96 by (rtac minor 1); |
97 by (assume_tac 2); |
97 by (assume_tac 2); |
98 by (Fast_tac 1); (*Blast_tac FAILS to prove it*) |
98 by (Fast_tac 1); (*Blast_tac FAILS to prove it*) |
125 equiv A r; congruent r b |
125 equiv A r; congruent r b |
126 **) |
126 **) |
127 |
127 |
128 (*Conversion rule*) |
128 (*Conversion rule*) |
129 Goal "[| equiv A r; congruent r b; a: A |] \ |
129 Goal "[| equiv A r; congruent r b; a: A |] \ |
130 \ ==> (UN x:r```{a}. b(x)) = b(a)"; |
130 \ ==> (UN x:r``{a}. b(x)) = b(a)"; |
131 by (rtac (equiv_class_self RS UN_constant_eq) 1 THEN REPEAT (assume_tac 1)); |
131 by (rtac (equiv_class_self RS UN_constant_eq) 1 THEN REPEAT (assume_tac 1)); |
132 by (rewrite_goals_tac [equiv_def,congruent_def,sym_def]); |
132 by (rewrite_goals_tac [equiv_def,congruent_def,sym_def]); |
133 by (blast_tac (claset() delrules [equalityI]) 1); |
133 by (blast_tac (claset() delrules [equalityI]) 1); |
134 qed "UN_equiv_class"; |
134 qed "UN_equiv_class"; |
135 |
135 |
136 (*type checking of UN x:r``{a}. b(x) *) |
136 (*type checking of UN x:r`{a}. b(x) *) |
137 val prems = Goalw [quotient_def] |
137 val prems = Goalw [quotient_def] |
138 "[| equiv A r; congruent r b; X: A//r; \ |
138 "[| equiv A r; congruent r b; X: A//r; \ |
139 \ !!x. x : A ==> b(x) : B |] \ |
139 \ !!x. x : A ==> b(x) : B |] \ |
140 \ ==> (UN x:X. b(x)) : B"; |
140 \ ==> (UN x:X. b(x)) : B"; |
141 by (cut_facts_tac prems 1); |
141 by (cut_facts_tac prems 1); |
169 by (Blast_tac 1); |
169 by (Blast_tac 1); |
170 qed "congruent2_implies_congruent"; |
170 qed "congruent2_implies_congruent"; |
171 |
171 |
172 Goalw [congruent_def] |
172 Goalw [congruent_def] |
173 "[| equiv A r; congruent2 r b; a: A |] ==> \ |
173 "[| equiv A r; congruent2 r b; a: A |] ==> \ |
174 \ congruent r (%x1. UN x2:r```{a}. b x1 x2)"; |
174 \ congruent r (%x1. UN x2:r``{a}. b x1 x2)"; |
175 by (Clarify_tac 1); |
175 by (Clarify_tac 1); |
176 by (rtac (equiv_type RS subsetD RS SigmaE2) 1 THEN REPEAT (assume_tac 1)); |
176 by (rtac (equiv_type RS subsetD RS SigmaE2) 1 THEN REPEAT (assume_tac 1)); |
177 by (asm_simp_tac (simpset() addsimps [UN_equiv_class, |
177 by (asm_simp_tac (simpset() addsimps [UN_equiv_class, |
178 congruent2_implies_congruent]) 1); |
178 congruent2_implies_congruent]) 1); |
179 by (rewrite_goals_tac [congruent2_def,equiv_def,refl_def]); |
179 by (rewrite_goals_tac [congruent2_def,equiv_def,refl_def]); |
180 by (blast_tac (claset() delrules [equalityI]) 1); |
180 by (blast_tac (claset() delrules [equalityI]) 1); |
181 qed "congruent2_implies_congruent_UN"; |
181 qed "congruent2_implies_congruent_UN"; |
182 |
182 |
183 Goal "[| equiv A r; congruent2 r b; a1: A; a2: A |] \ |
183 Goal "[| equiv A r; congruent2 r b; a1: A; a2: A |] \ |
184 \ ==> (UN x1:r```{a1}. UN x2:r```{a2}. b x1 x2) = b a1 a2"; |
184 \ ==> (UN x1:r``{a1}. UN x2:r``{a2}. b x1 x2) = b a1 a2"; |
185 by (asm_simp_tac (simpset() addsimps [UN_equiv_class, |
185 by (asm_simp_tac (simpset() addsimps [UN_equiv_class, |
186 congruent2_implies_congruent, |
186 congruent2_implies_congruent, |
187 congruent2_implies_congruent_UN]) 1); |
187 congruent2_implies_congruent_UN]) 1); |
188 qed "UN_equiv_class2"; |
188 qed "UN_equiv_class2"; |
189 |
189 |