src/HOL/BNF_FP_Base.thy
author wenzelm
Fri Mar 07 22:30:58 2014 +0100 (2014-03-07)
changeset 55990 41c6b99c5fb7
parent 55966 972f0aa7091b
child 56640 0a35354137a5
permissions -rw-r--r--
more antiquotations;
     1 (*  Title:      HOL/BNF_FP_Base.thy
     2     Author:     Lorenz Panny, TU Muenchen
     3     Author:     Dmitriy Traytel, TU Muenchen
     4     Author:     Jasmin Blanchette, TU Muenchen
     5     Copyright   2012, 2013
     6 
     7 Shared fixed point operations on bounded natural functors.
     8 *)
     9 
    10 header {* Shared Fixed Point Operations on Bounded Natural Functors *}
    11 
    12 theory BNF_FP_Base
    13 imports BNF_Comp Basic_BNFs
    14 begin
    15 
    16 lemma mp_conj: "(P \<longrightarrow> Q) \<and> R \<Longrightarrow> P \<Longrightarrow> R \<and> Q"
    17 by auto
    18 
    19 lemma eq_sym_Unity_conv: "(x = (() = ())) = x"
    20 by blast
    21 
    22 lemma case_unit_Unity: "(case u of () \<Rightarrow> f) = f"
    23 by (cases u) (hypsubst, rule unit.case)
    24 
    25 lemma case_prod_Pair_iden: "(case p of (x, y) \<Rightarrow> (x, y)) = p"
    26 by simp
    27 
    28 lemma unit_all_impI: "(P () \<Longrightarrow> Q ()) \<Longrightarrow> \<forall>x. P x \<longrightarrow> Q x"
    29 by simp
    30 
    31 lemma pointfree_idE: "f \<circ> g = id \<Longrightarrow> f (g x) = x"
    32 unfolding comp_def fun_eq_iff by simp
    33 
    34 lemma o_bij:
    35   assumes gf: "g \<circ> f = id" and fg: "f \<circ> g = id"
    36   shows "bij f"
    37 unfolding bij_def inj_on_def surj_def proof safe
    38   fix a1 a2 assume "f a1 = f a2"
    39   hence "g ( f a1) = g (f a2)" by simp
    40   thus "a1 = a2" using gf unfolding fun_eq_iff by simp
    41 next
    42   fix b
    43   have "b = f (g b)"
    44   using fg unfolding fun_eq_iff by simp
    45   thus "EX a. b = f a" by blast
    46 qed
    47 
    48 lemma ssubst_mem: "\<lbrakk>t = s; s \<in> X\<rbrakk> \<Longrightarrow> t \<in> X" by simp
    49 
    50 lemma case_sum_step:
    51 "case_sum (case_sum f' g') g (Inl p) = case_sum f' g' p"
    52 "case_sum f (case_sum f' g') (Inr p) = case_sum f' g' p"
    53 by auto
    54 
    55 lemma obj_one_pointE: "\<forall>x. s = x \<longrightarrow> P \<Longrightarrow> P"
    56 by blast
    57 
    58 lemma type_copy_obj_one_point_absE:
    59   assumes "type_definition Rep Abs UNIV" "\<forall>x. s = Abs x \<longrightarrow> P" shows P
    60   using type_definition.Rep_inverse[OF assms(1)]
    61   by (intro mp[OF spec[OF assms(2), of "Rep s"]]) simp
    62 
    63 lemma obj_sumE_f:
    64   assumes "\<forall>x. s = f (Inl x) \<longrightarrow> P" "\<forall>x. s = f (Inr x) \<longrightarrow> P"
    65   shows "\<forall>x. s = f x \<longrightarrow> P"
    66 proof
    67   fix x from assms show "s = f x \<longrightarrow> P" by (cases x) auto
    68 qed
    69 
    70 lemma case_sum_if:
    71 "case_sum f g (if p then Inl x else Inr y) = (if p then f x else g y)"
    72 by simp
    73 
    74 lemma Inl_Inr_False: "(Inl x = Inr y) = False"
    75 by simp
    76 
    77 lemma prod_set_simps:
    78 "fsts (x, y) = {x}"
    79 "snds (x, y) = {y}"
    80 unfolding fsts_def snds_def by simp+
    81 
    82 lemma sum_set_simps:
    83 "setl (Inl x) = {x}"
    84 "setl (Inr x) = {}"
    85 "setr (Inl x) = {}"
    86 "setr (Inr x) = {x}"
    87 unfolding sum_set_defs by simp+
    88 
    89 lemma spec2: "\<forall>x y. P x y \<Longrightarrow> P x y"
    90 by blast
    91 
    92 lemma rewriteR_comp_comp: "\<lbrakk>g o h = r\<rbrakk> \<Longrightarrow> f o g o h = f o r"
    93   unfolding comp_def fun_eq_iff by auto
    94 
    95 lemma rewriteR_comp_comp2: "\<lbrakk>g o h = r1 o r2; f o r1 = l\<rbrakk> \<Longrightarrow> f o g o h = l o r2"
    96   unfolding comp_def fun_eq_iff by auto
    97 
    98 lemma rewriteL_comp_comp: "\<lbrakk>f o g = l\<rbrakk> \<Longrightarrow> f o (g o h) = l o h"
    99   unfolding comp_def fun_eq_iff by auto
   100 
   101 lemma rewriteL_comp_comp2: "\<lbrakk>f o g = l1 o l2; l2 o h = r\<rbrakk> \<Longrightarrow> f o (g o h) = l1 o r"
   102   unfolding comp_def fun_eq_iff by auto
   103 
   104 lemma convol_o: "<f, g> o h = <f o h, g o h>"
   105   unfolding convol_def by auto
   106 
   107 lemma map_prod_o_convol: "map_prod h1 h2 o <f, g> = <h1 o f, h2 o g>"
   108   unfolding convol_def by auto
   109 
   110 lemma map_prod_o_convol_id: "(map_prod f id \<circ> <id , g>) x = <id \<circ> f , g> x"
   111   unfolding map_prod_o_convol id_comp comp_id ..
   112 
   113 lemma o_case_sum: "h o case_sum f g = case_sum (h o f) (h o g)"
   114   unfolding comp_def by (auto split: sum.splits)
   115 
   116 lemma case_sum_o_map_sum: "case_sum f g o map_sum h1 h2 = case_sum (f o h1) (g o h2)"
   117   unfolding comp_def by (auto split: sum.splits)
   118 
   119 lemma case_sum_o_map_sum_id: "(case_sum id g o map_sum f id) x = case_sum (f o id) g x"
   120   unfolding case_sum_o_map_sum id_comp comp_id ..
   121 
   122 lemma rel_fun_def_butlast:
   123   "rel_fun R (rel_fun S T) f g = (\<forall>x y. R x y \<longrightarrow> (rel_fun S T) (f x) (g y))"
   124   unfolding rel_fun_def ..
   125 
   126 lemma subst_eq_imp: "(\<forall>a b. a = b \<longrightarrow> P a b) \<equiv> (\<forall>a. P a a)"
   127   by auto
   128 
   129 lemma eq_subset: "op = \<le> (\<lambda>a b. P a b \<or> a = b)"
   130   by auto
   131 
   132 lemma eq_le_Grp_id_iff: "(op = \<le> Grp (Collect R) id) = (All R)"
   133   unfolding Grp_def id_apply by blast
   134 
   135 lemma Grp_id_mono_subst: "(\<And>x y. Grp P id x y \<Longrightarrow> Grp Q id (f x) (f y)) \<equiv>
   136    (\<And>x. x \<in> P \<Longrightarrow> f x \<in> Q)"
   137   unfolding Grp_def by rule auto
   138 
   139 lemma vimage2p_mono: "vimage2p f g R x y \<Longrightarrow> R \<le> S \<Longrightarrow> vimage2p f g S x y"
   140   unfolding vimage2p_def by blast
   141 
   142 lemma vimage2p_refl: "(\<And>x. R x x) \<Longrightarrow> vimage2p f f R x x"
   143   unfolding vimage2p_def by auto
   144 
   145 lemma
   146   assumes "type_definition Rep Abs UNIV"
   147   shows type_copy_Rep_o_Abs: "Rep \<circ> Abs = id" and type_copy_Abs_o_Rep: "Abs o Rep = id"
   148   unfolding fun_eq_iff comp_apply id_apply
   149     type_definition.Abs_inverse[OF assms UNIV_I] type_definition.Rep_inverse[OF assms] by simp_all
   150 
   151 lemma type_copy_map_comp0_undo:
   152   assumes "type_definition Rep Abs UNIV"
   153           "type_definition Rep' Abs' UNIV"
   154           "type_definition Rep'' Abs'' UNIV"
   155   shows "Abs' o M o Rep'' = (Abs' o M1 o Rep) o (Abs o M2 o Rep'') \<Longrightarrow> M1 o M2 = M"
   156   by (rule sym) (auto simp: fun_eq_iff type_definition.Abs_inject[OF assms(2) UNIV_I UNIV_I]
   157     type_definition.Abs_inverse[OF assms(1) UNIV_I]
   158     type_definition.Abs_inverse[OF assms(3) UNIV_I] dest: spec[of _ "Abs'' x" for x])
   159 
   160 lemma vimage2p_id: "vimage2p id id R = R"
   161   unfolding vimage2p_def by auto
   162 
   163 lemma vimage2p_comp: "vimage2p (f1 o f2) (g1 o g2) = vimage2p f2 g2 o vimage2p f1 g1"
   164   unfolding fun_eq_iff vimage2p_def o_apply by simp
   165 
   166 ML_file "Tools/BNF/bnf_fp_util.ML"
   167 ML_file "Tools/BNF/bnf_fp_def_sugar_tactics.ML"
   168 ML_file "Tools/BNF/bnf_fp_def_sugar.ML"
   169 ML_file "Tools/BNF/bnf_fp_n2m_tactics.ML"
   170 ML_file "Tools/BNF/bnf_fp_n2m.ML"
   171 ML_file "Tools/BNF/bnf_fp_n2m_sugar.ML"
   172 
   173 end