src/HOL/Transitive_Closure.thy
changeset 30240 5b25fee0362c
parent 29609 a010aab5bed0
child 30242 aea5d7fa7ef5
equal deleted inserted replaced
30239:179ff9cb160b 30240:5b25fee0362c
    62   reflcl  ("(_\<^sup>=)" [1000] 999)
    62   reflcl  ("(_\<^sup>=)" [1000] 999)
    63 
    63 
    64 
    64 
    65 subsection {* Reflexive closure *}
    65 subsection {* Reflexive closure *}
    66 
    66 
    67 lemma reflexive_reflcl[simp]: "reflexive(r^=)"
    67 lemma refl_reflcl[simp]: "refl(r^=)"
    68 by(simp add:refl_def)
    68 by(simp add:refl_on_def)
    69 
    69 
    70 lemma antisym_reflcl[simp]: "antisym(r^=) = antisym r"
    70 lemma antisym_reflcl[simp]: "antisym(r^=) = antisym r"
    71 by(simp add:antisym_def)
    71 by(simp add:antisym_def)
    72 
    72 
    73 lemma trans_reflclI[simp]: "trans r \<Longrightarrow> trans(r^=)"
    73 lemma trans_reflclI[simp]: "trans r \<Longrightarrow> trans(r^=)"
   116 
   116 
   117 lemmas rtrancl_induct2 =
   117 lemmas rtrancl_induct2 =
   118   rtrancl_induct[of "(ax,ay)" "(bx,by)", split_format (complete),
   118   rtrancl_induct[of "(ax,ay)" "(bx,by)", split_format (complete),
   119                  consumes 1, case_names refl step]
   119                  consumes 1, case_names refl step]
   120 
   120 
   121 lemma reflexive_rtrancl: "reflexive (r^*)"
   121 lemma refl_rtrancl: "refl (r^*)"
   122   by (unfold refl_def) fast
   122 by (unfold refl_on_def) fast
   123 
   123 
   124 text {* Transitivity of transitive closure. *}
   124 text {* Transitivity of transitive closure. *}
   125 lemma trans_rtrancl: "trans (r^*)"
   125 lemma trans_rtrancl: "trans (r^*)"
   126 proof (rule transI)
   126 proof (rule transI)
   127   fix x y z
   127   fix x y z
   644     val trancl_into_rtrancl = @{thm trancl_into_rtrancl};
   644     val trancl_into_rtrancl = @{thm trancl_into_rtrancl};
   645     val rtrancl_trancl_trancl = @{thm rtrancl_trancl_trancl};
   645     val rtrancl_trancl_trancl = @{thm rtrancl_trancl_trancl};
   646     val trancl_rtrancl_trancl = @{thm trancl_rtrancl_trancl};
   646     val trancl_rtrancl_trancl = @{thm trancl_rtrancl_trancl};
   647     val rtrancl_trans = @{thm rtrancl_trans};
   647     val rtrancl_trans = @{thm rtrancl_trans};
   648 
   648 
   649   fun decomp (Trueprop $ t) =
   649   fun decomp (@{const Trueprop} $ t) =
   650     let fun dec (Const ("op :", _) $ (Const ("Pair", _) $ a $ b) $ rel ) =
   650     let fun dec (Const ("op :", _) $ (Const ("Pair", _) $ a $ b) $ rel ) =
   651         let fun decr (Const ("Transitive_Closure.rtrancl", _ ) $ r) = (r,"r*")
   651         let fun decr (Const ("Transitive_Closure.rtrancl", _ ) $ r) = (r,"r*")
   652               | decr (Const ("Transitive_Closure.trancl", _ ) $ r)  = (r,"r+")
   652               | decr (Const ("Transitive_Closure.trancl", _ ) $ r)  = (r,"r+")
   653               | decr r = (r,"r");
   653               | decr r = (r,"r");
   654             val (rel,r) = decr (Envir.beta_eta_contract rel);
   654             val (rel,r) = decr (Envir.beta_eta_contract rel);
   655         in SOME (a,b,rel,r) end
   655         in SOME (a,b,rel,r) end
   656       | dec _ =  NONE
   656       | dec _ =  NONE
   657     in dec t end;
   657     in dec t end
       
   658     | decomp _ = NONE;
   658 
   659 
   659   end);
   660   end);
   660 
   661 
   661 structure Tranclp_Tac = Trancl_Tac_Fun (
   662 structure Tranclp_Tac = Trancl_Tac_Fun (
   662   struct
   663   struct
   667     val trancl_into_rtrancl = @{thm tranclp_into_rtranclp};
   668     val trancl_into_rtrancl = @{thm tranclp_into_rtranclp};
   668     val rtrancl_trancl_trancl = @{thm rtranclp_tranclp_tranclp};
   669     val rtrancl_trancl_trancl = @{thm rtranclp_tranclp_tranclp};
   669     val trancl_rtrancl_trancl = @{thm tranclp_rtranclp_tranclp};
   670     val trancl_rtrancl_trancl = @{thm tranclp_rtranclp_tranclp};
   670     val rtrancl_trans = @{thm rtranclp_trans};
   671     val rtrancl_trans = @{thm rtranclp_trans};
   671 
   672 
   672   fun decomp (Trueprop $ t) =
   673   fun decomp (@{const Trueprop} $ t) =
   673     let fun dec (rel $ a $ b) =
   674     let fun dec (rel $ a $ b) =
   674         let fun decr (Const ("Transitive_Closure.rtranclp", _ ) $ r) = (r,"r*")
   675         let fun decr (Const ("Transitive_Closure.rtranclp", _ ) $ r) = (r,"r*")
   675               | decr (Const ("Transitive_Closure.tranclp", _ ) $ r)  = (r,"r+")
   676               | decr (Const ("Transitive_Closure.tranclp", _ ) $ r)  = (r,"r+")
   676               | decr r = (r,"r");
   677               | decr r = (r,"r");
   677             val (rel,r) = decr rel;
   678             val (rel,r) = decr rel;
   678         in SOME (a, b, rel, r) end
   679         in SOME (a, b, rel, r) end
   679       | dec _ =  NONE
   680       | dec _ =  NONE
   680     in dec t end;
   681     in dec t end
       
   682     | decomp _ = NONE;
   681 
   683 
   682   end);
   684   end);
   683 *}
   685 *}
   684 
   686 
   685 declaration {* fn _ =>
   687 declaration {* fn _ =>