src/HOL/List.thy
changeset 25162 ad4d5365d9d8
parent 25157 8b80535cd017
child 25215 f53dc3c413f5
equal deleted inserted replaced
25161:aa8474398030 25162:ad4d5365d9d8
   948   have fin: "finite ?S" by(fast intro: bounded_nat_set_is_finite)
   948   have fin: "finite ?S" by(fast intro: bounded_nat_set_is_finite)
   949   show ?case (is "?l = card ?S'")
   949   show ?case (is "?l = card ?S'")
   950   proof (cases)
   950   proof (cases)
   951     assume "p x"
   951     assume "p x"
   952     hence eq: "?S' = insert 0 (Suc ` ?S)"
   952     hence eq: "?S' = insert 0 (Suc ` ?S)"
   953       by(auto simp: nth_Cons image_def split:nat.split dest:not0_implies_Suc)
   953       by(auto simp: image_def split:nat.split dest:gr0_implies_Suc)
   954     have "length (filter p (x # xs)) = Suc(card ?S)"
   954     have "length (filter p (x # xs)) = Suc(card ?S)"
   955       using Cons `p x` by simp
   955       using Cons `p x` by simp
   956     also have "\<dots> = Suc(card(Suc ` ?S))" using fin
   956     also have "\<dots> = Suc(card(Suc ` ?S))" using fin
   957       by (simp add: card_image inj_Suc)
   957       by (simp add: card_image inj_Suc)
   958     also have "\<dots> = card ?S'" using eq fin
   958     also have "\<dots> = card ?S'" using eq fin
   959       by (simp add:card_insert_if) (simp add:image_def)
   959       by (simp add:card_insert_if) (simp add:image_def)
   960     finally show ?thesis .
   960     finally show ?thesis .
   961   next
   961   next
   962     assume "\<not> p x"
   962     assume "\<not> p x"
   963     hence eq: "?S' = Suc ` ?S"
   963     hence eq: "?S' = Suc ` ?S"
   964       by(auto simp add: image_def neq0_conv split:nat.split elim:lessE)
   964       by(auto simp add: image_def split:nat.split elim:lessE)
   965     have "length (filter p (x # xs)) = card ?S"
   965     have "length (filter p (x # xs)) = card ?S"
   966       using Cons `\<not> p x` by simp
   966       using Cons `\<not> p x` by simp
   967     also have "\<dots> = card(Suc ` ?S)" using fin
   967     also have "\<dots> = card(Suc ` ?S)" using fin
   968       by (simp add: card_image inj_Suc)
   968       by (simp add: card_image inj_Suc)
   969     also have "\<dots> = card ?S'" using eq fin
   969     also have "\<dots> = card ?S'" using eq fin
  2454 apply (simp del: append_Cons add: append_Cons[symmetric] sublist_append)
  2454 apply (simp del: append_Cons add: append_Cons[symmetric] sublist_append)
  2455 done
  2455 done
  2456 
  2456 
  2457 lemma set_sublist: "set(sublist xs I) = {xs!i|i. i<size xs \<and> i \<in> I}"
  2457 lemma set_sublist: "set(sublist xs I) = {xs!i|i. i<size xs \<and> i \<in> I}"
  2458 apply(induct xs arbitrary: I)
  2458 apply(induct xs arbitrary: I)
  2459 apply(auto simp: sublist_Cons nth_Cons split:nat.split dest!: not0_implies_Suc)
  2459 apply(auto simp: sublist_Cons nth_Cons split:nat.split dest!: gr0_implies_Suc)
  2460 done
  2460 done
  2461 
  2461 
  2462 lemma set_sublist_subset: "set(sublist xs I) \<subseteq> set xs"
  2462 lemma set_sublist_subset: "set(sublist xs I) \<subseteq> set xs"
  2463 by(auto simp add:set_sublist)
  2463 by(auto simp add:set_sublist)
  2464 
  2464