equal
deleted
inserted
replaced
72 let ?A = "{pos. Rep_matrix x (snd pos) (fst pos) \<noteq> 0}" |
72 let ?A = "{pos. Rep_matrix x (snd pos) (fst pos) \<noteq> 0}" |
73 let ?swap = "% pos. (snd pos, fst pos)" |
73 let ?swap = "% pos. (snd pos, fst pos)" |
74 let ?B = "{pos. Rep_matrix x (fst pos) (snd pos) \<noteq> 0}" |
74 let ?B = "{pos. Rep_matrix x (fst pos) (snd pos) \<noteq> 0}" |
75 have swap_image: "?swap`?A = ?B" |
75 have swap_image: "?swap`?A = ?B" |
76 apply (simp add: image_def) |
76 apply (simp add: image_def) |
77 apply (rule set_ext) |
77 apply (rule set_eqI) |
78 apply (simp) |
78 apply (simp) |
79 proof |
79 proof |
80 fix y |
80 fix y |
81 assume hyp: "\<exists>a b. Rep_matrix x b a \<noteq> 0 \<and> y = (b, a)" |
81 assume hyp: "\<exists>a b. Rep_matrix x b a \<noteq> 0 \<and> y = (b, a)" |
82 thus "Rep_matrix x (fst y) (snd y) \<noteq> 0" |
82 thus "Rep_matrix x (fst y) (snd y) \<noteq> 0" |
206 lemma finite_natarray1: "finite {x. x < (n::nat)}" |
206 lemma finite_natarray1: "finite {x. x < (n::nat)}" |
207 apply (induct n) |
207 apply (induct n) |
208 apply (simp) |
208 apply (simp) |
209 proof - |
209 proof - |
210 fix n |
210 fix n |
211 have "{x. x < Suc n} = insert n {x. x < n}" by (rule set_ext, simp, arith) |
211 have "{x. x < Suc n} = insert n {x. x < n}" by (rule set_eqI, simp, arith) |
212 moreover assume "finite {x. x < n}" |
212 moreover assume "finite {x. x < n}" |
213 ultimately show "finite {x. x < Suc n}" by (simp) |
213 ultimately show "finite {x. x < Suc n}" by (simp) |
214 qed |
214 qed |
215 |
215 |
216 lemma finite_natarray2: "finite {pos. (fst pos) < (m::nat) & (snd pos) < (n::nat)}" |
216 lemma finite_natarray2: "finite {pos. (fst pos) < (m::nat) & (snd pos) < (n::nat)}" |
223 let ?sd = "{pos. fst pos = m & snd pos < n}" |
223 let ?sd = "{pos. fst pos = m & snd pos < n}" |
224 assume f0: "finite ?s0" |
224 assume f0: "finite ?s0" |
225 have f1: "finite ?sd" |
225 have f1: "finite ?sd" |
226 proof - |
226 proof - |
227 let ?f = "% x. (m, x)" |
227 let ?f = "% x. (m, x)" |
228 have "{pos. fst pos = m & snd pos < n} = ?f ` {x. x < n}" by (rule set_ext, simp add: image_def, auto) |
228 have "{pos. fst pos = m & snd pos < n} = ?f ` {x. x < n}" by (rule set_eqI, simp add: image_def, auto) |
229 moreover have "finite {x. x < n}" by (simp add: finite_natarray1) |
229 moreover have "finite {x. x < n}" by (simp add: finite_natarray1) |
230 ultimately show "finite {pos. fst pos = m & snd pos < n}" by (simp) |
230 ultimately show "finite {pos. fst pos = m & snd pos < n}" by (simp) |
231 qed |
231 qed |
232 have su: "?s0 \<union> ?sd = ?s1" by (rule set_ext, simp, arith) |
232 have su: "?s0 \<union> ?sd = ?s1" by (rule set_eqI, simp, arith) |
233 from f0 f1 have "finite (?s0 \<union> ?sd)" by (rule finite_UnI) |
233 from f0 f1 have "finite (?s0 \<union> ?sd)" by (rule finite_UnI) |
234 with su show "finite ?s1" by (simp) |
234 with su show "finite ?s1" by (simp) |
235 qed |
235 qed |
236 |
236 |
237 lemma RepAbs_matrix: |
237 lemma RepAbs_matrix: |
245 let ?u = "{pos. x (fst pos) (snd pos) \<noteq> 0}" |
245 let ?u = "{pos. x (fst pos) (snd pos) \<noteq> 0}" |
246 let ?v = "{pos. fst pos < m & snd pos < n}" |
246 let ?v = "{pos. fst pos < m & snd pos < n}" |
247 have c: "!! (m::nat) a. ~(m <= a) \<Longrightarrow> a < m" by (arith) |
247 have c: "!! (m::nat) a. ~(m <= a) \<Longrightarrow> a < m" by (arith) |
248 from a b have "(?u \<inter> (-?v)) = {}" |
248 from a b have "(?u \<inter> (-?v)) = {}" |
249 apply (simp) |
249 apply (simp) |
250 apply (rule set_ext) |
250 apply (rule set_eqI) |
251 apply (simp) |
251 apply (simp) |
252 apply auto |
252 apply auto |
253 by (rule c, auto)+ |
253 by (rule c, auto)+ |
254 then have d: "?u \<subseteq> ?v" by blast |
254 then have d: "?u \<subseteq> ?v" by blast |
255 moreover have "finite ?v" by (simp add: finite_natarray2) |
255 moreover have "finite ?v" by (simp add: finite_natarray2) |