src/HOL/Matrix/Matrix.thy
changeset 39302 d7728f65b353
parent 38526 a9ce311eb6b9
child 41413 64cd30d6b0b8
equal deleted inserted replaced
39301:e1bd8a54c40f 39302:d7728f65b353
    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)