src/HOL/Univ.ML
changeset 1264 3eb91524b938
parent 976 14b55f7fbf15
child 1465 5d7a7e439cec
equal deleted inserted replaced
1263:290c4dfc34ba 1264:3eb91524b938
   240 val Numb_neq_Scons = sym RS Scons_neq_Numb;
   240 val Numb_neq_Scons = sym RS Scons_neq_Numb;
   241 
   241 
   242 (** Leaf vs Numb **)
   242 (** Leaf vs Numb **)
   243 
   243 
   244 goalw Univ.thy [Leaf_def,Numb_def] "Leaf(a) ~= Numb(k)";
   244 goalw Univ.thy [Leaf_def,Numb_def] "Leaf(a) ~= Numb(k)";
   245 by (simp_tac (HOL_ss addsimps [Atom_Atom_eq,Inl_not_Inr]) 1);
   245 by (simp_tac (!simpset addsimps [Atom_Atom_eq,Inl_not_Inr]) 1);
   246 qed "Leaf_not_Numb";
   246 qed "Leaf_not_Numb";
   247 bind_thm ("Numb_not_Leaf", (Leaf_not_Numb RS not_sym));
   247 bind_thm ("Numb_not_Leaf", (Leaf_not_Numb RS not_sym));
   248 
   248 
   249 bind_thm ("Leaf_neq_Numb", (Leaf_not_Numb RS notE));
   249 bind_thm ("Leaf_neq_Numb", (Leaf_not_Numb RS notE));
   250 val Numb_neq_Leaf = sym RS Leaf_neq_Numb;
   250 val Numb_neq_Leaf = sym RS Leaf_neq_Numb;
   251 
   251 
   252 
   252 
   253 (*** ndepth -- the depth of a node ***)
   253 (*** ndepth -- the depth of a node ***)
   254 
   254 
   255 val univ_simps = [apfst_conv,Scons_not_Atom,Atom_not_Scons,Scons_Scons_eq];
   255 Addsimps [apfst_conv,Scons_not_Atom,Atom_not_Scons,Scons_Scons_eq];
   256 val univ_ss = nat_ss addsimps univ_simps;
       
   257 
   256 
   258 
   257 
   259 goalw Univ.thy [ndepth_def] "ndepth (Abs_Node((%k.0, x))) = 0";
   258 goalw Univ.thy [ndepth_def] "ndepth (Abs_Node((%k.0, x))) = 0";
   260 by (sstac [Node_K0_I RS Abs_Node_inverse, split] 1);
   259 by (sstac [Node_K0_I RS Abs_Node_inverse, split] 1);
   261 by (rtac Least_equality 1);
   260 by (rtac Least_equality 1);
   263 by (etac less_zeroE 1);
   262 by (etac less_zeroE 1);
   264 qed "ndepth_K0";
   263 qed "ndepth_K0";
   265 
   264 
   266 goal Univ.thy "k < Suc(LEAST x. f(x)=0) --> nat_case (Suc i) f k ~= 0";
   265 goal Univ.thy "k < Suc(LEAST x. f(x)=0) --> nat_case (Suc i) f k ~= 0";
   267 by (nat_ind_tac "k" 1);
   266 by (nat_ind_tac "k" 1);
   268 by (ALLGOALS (simp_tac nat_ss));
   267 by (ALLGOALS Simp_tac);
   269 by (rtac impI 1);
   268 by (rtac impI 1);
   270 by (etac not_less_Least 1);
   269 by (etac not_less_Least 1);
   271 qed "ndepth_Push_lemma";
   270 qed "ndepth_Push_lemma";
   272 
   271 
   273 goalw Univ.thy [ndepth_def,Push_Node_def]
   272 goalw Univ.thy [ndepth_def,Push_Node_def]
   274     "ndepth (Push_Node i n) = Suc(ndepth(n))";
   273     "ndepth (Push_Node i n) = Suc(ndepth(n))";
   275 by (stac (Rep_Node RS Node_Push_I RS Abs_Node_inverse) 1);
   274 by (stac (Rep_Node RS Node_Push_I RS Abs_Node_inverse) 1);
   276 by (cut_facts_tac [rewrite_rule [Node_def] Rep_Node] 1);
   275 by (cut_facts_tac [rewrite_rule [Node_def] Rep_Node] 1);
   277 by (safe_tac set_cs);
   276 by (safe_tac set_cs);
   278 be ssubst 1;  (*instantiates type variables!*)
   277 be ssubst 1;  (*instantiates type variables!*)
   279 by (simp_tac univ_ss 1);
   278 by (Simp_tac 1);
   280 by (rtac Least_equality 1);
   279 by (rtac Least_equality 1);
   281 by (rewtac Push_def);
   280 by (rewtac Push_def);
   282 by (rtac (nat_case_Suc RS trans) 1);
   281 by (rtac (nat_case_Suc RS trans) 1);
   283 by (etac LeastI 1);
   282 by (etac LeastI 1);
   284 by (etac (ndepth_Push_lemma RS mp) 1);
   283 by (etac (ndepth_Push_lemma RS mp) 1);
   315 qed "ntrunc_Scons";
   314 qed "ntrunc_Scons";
   316 
   315 
   317 (** Injection nodes **)
   316 (** Injection nodes **)
   318 
   317 
   319 goalw Univ.thy [In0_def] "ntrunc (Suc 0) (In0 M) = {}";
   318 goalw Univ.thy [In0_def] "ntrunc (Suc 0) (In0 M) = {}";
   320 by (simp_tac (univ_ss addsimps [ntrunc_Scons,ntrunc_0]) 1);
   319 by (simp_tac (!simpset addsimps [ntrunc_Scons,ntrunc_0]) 1);
   321 by (rewtac Scons_def);
   320 by (rewtac Scons_def);
   322 by (safe_tac (set_cs addSIs [equalityI]));
   321 by (safe_tac (set_cs addSIs [equalityI]));
   323 qed "ntrunc_one_In0";
   322 qed "ntrunc_one_In0";
   324 
   323 
   325 goalw Univ.thy [In0_def]
   324 goalw Univ.thy [In0_def]
   326     "ntrunc (Suc (Suc k)) (In0 M) = In0 (ntrunc (Suc k) M)";
   325     "ntrunc (Suc (Suc k)) (In0 M) = In0 (ntrunc (Suc k) M)";
   327 by (simp_tac (univ_ss addsimps [ntrunc_Scons,ntrunc_Numb]) 1);
   326 by (simp_tac (!simpset addsimps [ntrunc_Scons,ntrunc_Numb]) 1);
   328 qed "ntrunc_In0";
   327 qed "ntrunc_In0";
   329 
   328 
   330 goalw Univ.thy [In1_def] "ntrunc (Suc 0) (In1 M) = {}";
   329 goalw Univ.thy [In1_def] "ntrunc (Suc 0) (In1 M) = {}";
   331 by (simp_tac (univ_ss addsimps [ntrunc_Scons,ntrunc_0]) 1);
   330 by (simp_tac (!simpset addsimps [ntrunc_Scons,ntrunc_0]) 1);
   332 by (rewtac Scons_def);
   331 by (rewtac Scons_def);
   333 by (safe_tac (set_cs addSIs [equalityI]));
   332 by (safe_tac (set_cs addSIs [equalityI]));
   334 qed "ntrunc_one_In1";
   333 qed "ntrunc_one_In1";
   335 
   334 
   336 goalw Univ.thy [In1_def]
   335 goalw Univ.thy [In1_def]
   337     "ntrunc (Suc (Suc k)) (In1 M) = In1 (ntrunc (Suc k) M)";
   336     "ntrunc (Suc (Suc k)) (In1 M) = In1 (ntrunc (Suc k) M)";
   338 by (simp_tac (univ_ss addsimps [ntrunc_Scons,ntrunc_Numb]) 1);
   337 by (simp_tac (!simpset addsimps [ntrunc_Scons,ntrunc_Numb]) 1);
   339 qed "ntrunc_In1";
   338 qed "ntrunc_In1";
   340 
   339 
   341 
   340 
   342 (*** Cartesian Product ***)
   341 (*** Cartesian Product ***)
   343 
   342 
   609 by (fast_tac (prod_cs addIs [equalityI, usum_In0I, usum_In1I, 
   608 by (fast_tac (prod_cs addIs [equalityI, usum_In0I, usum_In1I, 
   610 			     dsum_In0I, dsum_In1I]
   609 			     dsum_In0I, dsum_In1I]
   611                      addSEs [usumE, dsumE]) 1);
   610                      addSEs [usumE, dsumE]) 1);
   612 qed "fst_image_dsum";
   611 qed "fst_image_dsum";
   613 
   612 
   614 val fst_image_simps = [fst_image_diag, fst_image_dprod, fst_image_dsum];
   613 Addsimps [fst_image_diag, fst_image_dprod, fst_image_dsum];
   615 val fst_image_ss = univ_ss addsimps fst_image_simps;