src/HOLCF/Dnat.ML
changeset 892 d0dc8d057929
parent 625 119391dd1d59
child 1168 74be52691d62
equal deleted inserted replaced
891:a5ad535a241a 892:d0dc8d057929
    42 
    42 
    43 (* ------------------------------------------------------------------------*)
    43 (* ------------------------------------------------------------------------*)
    44 (* Exhaustion and elimination for dnat                                     *)
    44 (* Exhaustion and elimination for dnat                                     *)
    45 (* ------------------------------------------------------------------------*)
    45 (* ------------------------------------------------------------------------*)
    46 
    46 
    47 val Exh_dnat = prove_goalw Dnat.thy [dsucc_def,dzero_def]
    47 qed_goalw "Exh_dnat" Dnat.thy [dsucc_def,dzero_def]
    48 	"n = UU | n = dzero | (? x . x~=UU & n = dsucc[x])"
    48 	"n = UU | n = dzero | (? x . x~=UU & n = dsucc[x])"
    49  (fn prems =>
    49  (fn prems =>
    50 	[
    50 	[
    51 	(simp_tac HOLCF_ss  1),
    51 	(simp_tac HOLCF_ss  1),
    52 	(rtac (dnat_rep_iso RS subst) 1),
    52 	(rtac (dnat_rep_iso RS subst) 1),
    61 	(rtac (disjI2 RS disjI2) 1),
    61 	(rtac (disjI2 RS disjI2) 1),
    62 	(asm_simp_tac (HOLCF_ss addsimps dnat_rews) 1),
    62 	(asm_simp_tac (HOLCF_ss addsimps dnat_rews) 1),
    63 	(fast_tac HOL_cs 1)
    63 	(fast_tac HOL_cs 1)
    64 	]);
    64 	]);
    65 
    65 
    66 val dnatE = prove_goal Dnat.thy 
    66 qed_goal "dnatE" Dnat.thy 
    67  "[| n=UU ==> Q; n=dzero ==> Q; !!x.[|n=dsucc[x];x~=UU|]==>Q|]==>Q"
    67  "[| n=UU ==> Q; n=dzero ==> Q; !!x.[|n=dsucc[x];x~=UU|]==>Q|]==>Q"
    68  (fn prems =>
    68  (fn prems =>
    69 	[
    69 	[
    70 	(rtac (Exh_dnat RS disjE) 1),
    70 	(rtac (Exh_dnat RS disjE) 1),
    71 	(eresolve_tac prems 1),
    71 	(eresolve_tac prems 1),
   357 
   357 
   358 (* ------------------------------------------------------------------------*)
   358 (* ------------------------------------------------------------------------*)
   359 (* Co -induction for dnats                                                 *)
   359 (* Co -induction for dnats                                                 *)
   360 (* ------------------------------------------------------------------------*)
   360 (* ------------------------------------------------------------------------*)
   361 
   361 
   362 val dnat_coind_lemma = prove_goalw Dnat.thy [dnat_bisim_def] 
   362 qed_goalw "dnat_coind_lemma" Dnat.thy [dnat_bisim_def] 
   363 "dnat_bisim(R) ==> ! p q.R(p,q) --> dnat_take(n)[p]=dnat_take(n)[q]"
   363 "dnat_bisim(R) ==> ! p q.R(p,q) --> dnat_take(n)[p]=dnat_take(n)[q]"
   364  (fn prems =>
   364  (fn prems =>
   365 	[
   365 	[
   366 	(cut_facts_tac prems 1),
   366 	(cut_facts_tac prems 1),
   367 	(nat_ind_tac "n" 1),
   367 	(nat_ind_tac "n" 1),
   378 	(REPEAT (etac conjE 1)),
   378 	(REPEAT (etac conjE 1)),
   379 	(rtac cfun_arg_cong 1),
   379 	(rtac cfun_arg_cong 1),
   380 	(fast_tac HOL_cs 1)
   380 	(fast_tac HOL_cs 1)
   381 	]);
   381 	]);
   382 
   382 
   383 val dnat_coind = prove_goal Dnat.thy "[|dnat_bisim(R);R(p,q)|] ==> p = q"
   383 qed_goal "dnat_coind" Dnat.thy "[|dnat_bisim(R);R(p,q)|] ==> p = q"
   384  (fn prems =>
   384  (fn prems =>
   385 	[
   385 	[
   386 	(rtac dnat_take_lemma 1),
   386 	(rtac dnat_take_lemma 1),
   387 	(rtac (dnat_coind_lemma RS spec RS spec RS mp) 1),
   387 	(rtac (dnat_coind_lemma RS spec RS spec RS mp) 1),
   388 	(resolve_tac prems 1),
   388 	(resolve_tac prems 1),
   393 (* ------------------------------------------------------------------------*)
   393 (* ------------------------------------------------------------------------*)
   394 (* structural induction for admissible predicates                          *)
   394 (* structural induction for admissible predicates                          *)
   395 (* ------------------------------------------------------------------------*)
   395 (* ------------------------------------------------------------------------*)
   396 
   396 
   397 (* not needed any longer
   397 (* not needed any longer
   398 val dnat_ind = prove_goal Dnat.thy
   398 qed_goal "dnat_ind" Dnat.thy
   399 "[| adm(P);\
   399 "[| adm(P);\
   400 \   P(UU);\
   400 \   P(UU);\
   401 \   P(dzero);\
   401 \   P(dzero);\
   402 \   !! s1.[|s1~=UU ; P(s1)|] ==> P(dsucc[s1])|] ==> P(s)"
   402 \   !! s1.[|s1~=UU ; P(s1)|] ==> P(dsucc[s1])|] ==> P(s)"
   403  (fn prems =>
   403  (fn prems =>
   424 	(eresolve_tac prems 1),
   424 	(eresolve_tac prems 1),
   425 	(etac spec 1)
   425 	(etac spec 1)
   426 	]);
   426 	]);
   427 *)
   427 *)
   428 
   428 
   429 val dnat_finite_ind = prove_goal Dnat.thy
   429 qed_goal "dnat_finite_ind" Dnat.thy
   430 "[|P(UU);P(dzero);\
   430 "[|P(UU);P(dzero);\
   431 \  !! s1.[|s1~=UU;P(s1)|] ==> P(dsucc[s1])\
   431 \  !! s1.[|s1~=UU;P(s1)|] ==> P(dsucc[s1])\
   432 \  |] ==> !s.P(dnat_take(n)[s])"
   432 \  |] ==> !s.P(dnat_take(n)[s])"
   433  (fn prems =>
   433  (fn prems =>
   434 	[
   434 	[
   448 	(resolve_tac prems 1),
   448 	(resolve_tac prems 1),
   449 	(atac 1),
   449 	(atac 1),
   450 	(etac spec 1)
   450 	(etac spec 1)
   451 	]);
   451 	]);
   452 
   452 
   453 val dnat_all_finite_lemma1 = prove_goal Dnat.thy
   453 qed_goal "dnat_all_finite_lemma1" Dnat.thy
   454 "!s.dnat_take(n)[s]=UU |dnat_take(n)[s]=s"
   454 "!s.dnat_take(n)[s]=UU |dnat_take(n)[s]=s"
   455  (fn prems =>
   455  (fn prems =>
   456 	[
   456 	[
   457 	(nat_ind_tac "n" 1),
   457 	(nat_ind_tac "n" 1),
   458 	(simp_tac (HOLCF_ss addsimps dnat_rews) 1),
   458 	(simp_tac (HOLCF_ss addsimps dnat_rews) 1),
   465 	(etac disjE 1),
   465 	(etac disjE 1),
   466 	(asm_simp_tac (HOLCF_ss addsimps dnat_rews) 1),
   466 	(asm_simp_tac (HOLCF_ss addsimps dnat_rews) 1),
   467 	(asm_simp_tac (HOLCF_ss addsimps dnat_rews) 1)
   467 	(asm_simp_tac (HOLCF_ss addsimps dnat_rews) 1)
   468 	]);
   468 	]);
   469 
   469 
   470 val dnat_all_finite_lemma2 = prove_goal Dnat.thy "? n.dnat_take(n)[s]=s"
   470 qed_goal "dnat_all_finite_lemma2" Dnat.thy "? n.dnat_take(n)[s]=s"
   471  (fn prems =>
   471  (fn prems =>
   472 	[
   472 	[
   473 	(res_inst_tac [("Q","s=UU")] classical2 1),
   473 	(res_inst_tac [("Q","s=UU")] classical2 1),
   474 	(asm_simp_tac (HOLCF_ss addsimps dnat_rews) 1),
   474 	(asm_simp_tac (HOLCF_ss addsimps dnat_rews) 1),
   475 	(subgoal_tac "(!n.dnat_take(n)[s]=UU) |(? n.dnat_take(n)[s]=s)" 1),
   475 	(subgoal_tac "(!n.dnat_take(n)[s]=UU) |(? n.dnat_take(n)[s]=s)" 1),
   483 	(rtac allI 1),
   483 	(rtac allI 1),
   484 	(rtac dnat_all_finite_lemma1 1)
   484 	(rtac dnat_all_finite_lemma1 1)
   485 	]);
   485 	]);
   486 
   486 
   487 
   487 
   488 val dnat_ind = prove_goal Dnat.thy
   488 qed_goal "dnat_ind" Dnat.thy
   489 "[|P(UU);P(dzero);\
   489 "[|P(UU);P(dzero);\
   490 \  !! s1.[|s1~=UU;P(s1)|] ==> P(dsucc[s1])\
   490 \  !! s1.[|s1~=UU;P(s1)|] ==> P(dsucc[s1])\
   491 \  |] ==> P(s)"
   491 \  |] ==> P(s)"
   492  (fn prems =>
   492  (fn prems =>
   493 	[
   493 	[
   497 	(REPEAT (resolve_tac prems 1)),
   497 	(REPEAT (resolve_tac prems 1)),
   498 	(REPEAT (atac 1))
   498 	(REPEAT (atac 1))
   499 	]);
   499 	]);
   500 
   500 
   501 
   501 
   502 val dnat_flat = prove_goalw Dnat.thy [flat_def] "flat(dzero)"
   502 qed_goalw "dnat_flat" Dnat.thy [flat_def] "flat(dzero)"
   503  (fn prems =>
   503  (fn prems =>
   504 	[
   504 	[
   505 	(rtac allI 1),
   505 	(rtac allI 1),
   506 	(res_inst_tac [("s","x")] dnat_ind 1),
   506 	(res_inst_tac [("s","x")] dnat_ind 1),
   507 	(fast_tac HOL_cs 1),
   507 	(fast_tac HOL_cs 1),