src/HOL/Library/Cardinality.thy
changeset 49948 744934b818c7
parent 49689 b8a710806de9
child 51116 0dac0158b8d4
equal deleted inserted replaced
49947:29cd291bfea6 49948:744934b818c7
    90       where as: "set as = (UNIV :: 'a set)" and dista: "distinct as" by blast
    90       where as: "set as = (UNIV :: 'a set)" and dista: "distinct as" by blast
    91     have cb: "CARD('b) = length bs"
    91     have cb: "CARD('b) = length bs"
    92       unfolding bs[symmetric] distinct_card[OF distb] ..
    92       unfolding bs[symmetric] distinct_card[OF distb] ..
    93     have ca: "CARD('a) = length as"
    93     have ca: "CARD('a) = length as"
    94       unfolding as[symmetric] distinct_card[OF dista] ..
    94       unfolding as[symmetric] distinct_card[OF dista] ..
    95     let ?xs = "map (\<lambda>ys. the o map_of (zip as ys)) (Enum.n_lists (length as) bs)"
    95     let ?xs = "map (\<lambda>ys. the o map_of (zip as ys)) (List.n_lists (length as) bs)"
    96     have "UNIV = set ?xs"
    96     have "UNIV = set ?xs"
    97     proof(rule UNIV_eq_I)
    97     proof(rule UNIV_eq_I)
    98       fix f :: "'a \<Rightarrow> 'b"
    98       fix f :: "'a \<Rightarrow> 'b"
    99       from as have "f = the \<circ> map_of (zip as (map f as))"
    99       from as have "f = the \<circ> map_of (zip as (map f as))"
   100         by(auto simp add: map_of_zip_map)
   100         by(auto simp add: map_of_zip_map)
   101       thus "f \<in> set ?xs" using bs by(auto simp add: set_n_lists)
   101       thus "f \<in> set ?xs" using bs by(auto simp add: set_n_lists)
   102     qed
   102     qed
   103     moreover have "distinct ?xs" unfolding distinct_map
   103     moreover have "distinct ?xs" unfolding distinct_map
   104     proof(intro conjI distinct_n_lists distb inj_onI)
   104     proof(intro conjI distinct_n_lists distb inj_onI)
   105       fix xs ys :: "'b list"
   105       fix xs ys :: "'b list"
   106       assume xs: "xs \<in> set (Enum.n_lists (length as) bs)"
   106       assume xs: "xs \<in> set (List.n_lists (length as) bs)"
   107         and ys: "ys \<in> set (Enum.n_lists (length as) bs)"
   107         and ys: "ys \<in> set (List.n_lists (length as) bs)"
   108         and eq: "the \<circ> map_of (zip as xs) = the \<circ> map_of (zip as ys)"
   108         and eq: "the \<circ> map_of (zip as xs) = the \<circ> map_of (zip as ys)"
   109       from xs ys have [simp]: "length xs = length as" "length ys = length as"
   109       from xs ys have [simp]: "length xs = length as" "length ys = length as"
   110         by(simp_all add: length_n_lists_elem)
   110         by(simp_all add: length_n_lists_elem)
   111       have "map_of (zip as xs) = map_of (zip as ys)"
   111       have "map_of (zip as xs) = map_of (zip as ys)"
   112       proof
   112       proof
   470 end
   470 end
   471 
   471 
   472 hide_const (open) card' finite' subset' eq_set
   472 hide_const (open) card' finite' subset' eq_set
   473 
   473 
   474 end
   474 end
       
   475