229 val con_rews = maps (gts "con_rews" ) dnames; |
229 val con_rews = maps (gts "con_rews" ) dnames; |
230 end; |
230 end; |
231 |
231 |
232 val {take_0_thms, take_Suc_thms, chain_take_thms, ...} = take_info; |
232 val {take_0_thms, take_Suc_thms, chain_take_thms, ...} = take_info; |
233 val {lub_take_thms, finite_defs, reach_thms, ...} = take_info; |
233 val {lub_take_thms, finite_defs, reach_thms, ...} = take_info; |
|
234 val {take_induct_thms, ...} = take_info; |
234 |
235 |
235 fun one_con p (con, args) = |
236 fun one_con p (con, args) = |
236 let |
237 let |
237 val P_names = map P_name (1 upto (length dnames)); |
238 val P_names = map P_name (1 upto (length dnames)); |
238 val vns = Name.variant_list P_names (map vname args); |
239 val vns = Name.variant_list P_names (map vname args); |
280 fun lazy_rec_to ns = rec_to exists I lazy_rec_to ns; |
281 fun lazy_rec_to ns = rec_to exists I lazy_rec_to ns; |
281 |
282 |
282 in |
283 in |
283 val n__eqs = mapn (fn n => fn (_,cons) => (n,cons)) 0 eqs; |
284 val n__eqs = mapn (fn n => fn (_,cons) => (n,cons)) 0 eqs; |
284 val is_emptys = map warn n__eqs; |
285 val is_emptys = map warn n__eqs; |
285 val is_finite = forall (not o lazy_rec_to [] false) n__eqs; |
286 val is_finite = #is_finite take_info; |
286 val _ = if is_finite |
287 val _ = if is_finite |
287 then message ("Proving finiteness rule for domain "^comp_dnam^" ...") |
288 then message ("Proving finiteness rule for domain "^comp_dnam^" ...") |
288 else (); |
289 else (); |
289 end; |
290 end; |
290 val _ = trace " Proving finite_ind..."; |
291 val _ = trace " Proving finite_ind..."; |
324 |
325 |
325 (* ----- theorems concerning finiteness and induction ----------------------- *) |
326 (* ----- theorems concerning finiteness and induction ----------------------- *) |
326 |
327 |
327 val global_ctxt = ProofContext.init thy; |
328 val global_ctxt = ProofContext.init thy; |
328 |
329 |
329 val _ = trace " Proving finites, ind..."; |
330 val _ = trace " Proving ind..."; |
330 val (finites, ind) = |
331 val ind = |
331 ( |
332 ( |
332 if is_finite |
333 if is_finite |
333 then (* finite case *) |
334 then (* finite case *) |
334 let |
335 let |
335 val decisive_lemma = |
336 fun concf n dn = %:(P_name n) $ %:(x_name n); |
|
337 fun tacf {prems, context} = |
336 let |
338 let |
337 val iso_locale_thms = |
339 fun finite_tacs (take_induct, fin_ind) = [ |
338 map2 (fn x => fn y => @{thm iso.intro} OF [x, y]) |
340 rtac take_induct 1, |
339 axs_abs_iso axs_rep_iso; |
341 rtac fin_ind 1, |
340 val decisive_abs_rep_thms = |
342 ind_prems_tac prems]; |
341 map (fn x => @{thm decisive_abs_rep} OF [x]) |
343 in |
342 iso_locale_thms; |
344 TRY (safe_tac HOL_cs) :: |
343 val n = Free ("n", @{typ nat}); |
345 maps finite_tacs (take_induct_thms ~~ atomize global_ctxt finite_ind) |
344 fun mk_decisive t = %%: @{const_name decisive} $ t; |
346 end; |
345 fun f dn = mk_decisive (dc_take dn $ n); |
347 in pg'' thy [] (ind_term concf) tacf end |
346 val goal = mk_trp (foldr1 mk_conj (map f dnames)); |
|
347 val rules0 = @{thm decisive_bottom} :: take_0_thms; |
|
348 val rules1 = |
|
349 take_Suc_thms @ decisive_abs_rep_thms |
|
350 @ @{thms decisive_ID decisive_ssum_map decisive_sprod_map}; |
|
351 val tacs = [ |
|
352 rtac @{thm nat.induct} 1, |
|
353 simp_tac (HOL_ss addsimps rules0) 1, |
|
354 asm_simp_tac (HOL_ss addsimps rules1) 1]; |
|
355 in pg [] goal (K tacs) end; |
|
356 fun take_enough dn = mk_ex ("n",dc_take dn $ Bound 0 ` %:"x" === %:"x"); |
|
357 fun one_finite (dn, decisive_thm) = |
|
358 let |
|
359 val goal = mk_trp (%%:(dn^"_finite") $ %:"x"); |
|
360 val tacs = [ |
|
361 rtac @{thm lub_ID_finite} 1, |
|
362 resolve_tac chain_take_thms 1, |
|
363 resolve_tac lub_take_thms 1, |
|
364 rtac decisive_thm 1]; |
|
365 in pg finite_defs goal (K tacs) end; |
|
366 |
|
367 val _ = trace " Proving finites"; |
|
368 val finites = map one_finite (dnames ~~ atomize global_ctxt decisive_lemma); |
|
369 val _ = trace " Proving ind"; |
|
370 val ind = |
|
371 let |
|
372 fun concf n dn = %:(P_name n) $ %:(x_name n); |
|
373 fun tacf {prems, context} = |
|
374 let |
|
375 fun finite_tacs (finite, fin_ind) = [ |
|
376 rtac(rewrite_rule finite_defs finite RS exE)1, |
|
377 etac subst 1, |
|
378 rtac fin_ind 1, |
|
379 ind_prems_tac prems]; |
|
380 in |
|
381 TRY (safe_tac HOL_cs) :: |
|
382 maps finite_tacs (finites ~~ atomize global_ctxt finite_ind) |
|
383 end; |
|
384 in pg'' thy [] (ind_term concf) tacf end; |
|
385 in (finites, ind) end (* let *) |
|
386 |
348 |
387 else (* infinite case *) |
349 else (* infinite case *) |
388 let |
350 let |
389 fun one_finite n dn = |
|
390 read_instantiate global_ctxt [(("P", 0), dn ^ "_finite " ^ x_name n)] excluded_middle; |
|
391 val finites = mapn one_finite 1 dnames; |
|
392 |
|
393 val goal = |
351 val goal = |
394 let |
352 let |
395 fun one_adm n _ = mk_trp (mk_adm (%:(P_name n))); |
353 fun one_adm n _ = mk_trp (mk_adm (%:(P_name n))); |
396 fun concf n dn = %:(P_name n) $ %:(x_name n); |
354 fun concf n dn = %:(P_name n) $ %:(x_name n); |
397 in Logic.list_implies (mapn one_adm 1 dnames, ind_term concf) end; |
355 in Logic.list_implies (mapn one_adm 1 dnames, ind_term concf) end; |
443 |
401 |
444 val induct_failed = (Thm.prop_of ind = Thm.prop_of TrueI); |
402 val induct_failed = (Thm.prop_of ind = Thm.prop_of TrueI); |
445 |
403 |
446 in thy |> Sign.add_path comp_dnam |
404 in thy |> Sign.add_path comp_dnam |
447 |> snd o PureThy.add_thmss [ |
405 |> snd o PureThy.add_thmss [ |
448 ((Binding.name "finites" , finites ), []), |
|
449 ((Binding.name "finite_ind" , [finite_ind]), []), |
406 ((Binding.name "finite_ind" , [finite_ind]), []), |
450 ((Binding.name "ind" , [ind] ), [])] |
407 ((Binding.name "ind" , [ind] ), [])] |
451 |> (if induct_failed then I |
408 |> (if induct_failed then I |
452 else snd o PureThy.add_thmss (map ind_rule (dnames ~~ inducts))) |
409 else snd o PureThy.add_thmss (map ind_rule (dnames ~~ inducts))) |
453 |> Sign.parent_path |
410 |> Sign.parent_path |