src/HOLCF/Sprod.thy
author huffman
Thu Jun 23 22:07:30 2005 +0200 (2005-06-23)
changeset 16553 aa36d41e4263
parent 16317 868eddbcaf6e
child 16699 24b494ff8f0f
permissions -rw-r--r--
add csplit3, ssplit3, fup3 as simp rules
     1 (*  Title:      HOLCF/Sprod.thy
     2     ID:         $Id$
     3     Author:     Franz Regensburger and Brian Huffman
     4 
     5 Strict product with typedef.
     6 *)
     7 
     8 header {* The type of strict products *}
     9 
    10 theory Sprod
    11 imports Cprod TypedefPcpo
    12 begin
    13 
    14 defaultsort pcpo
    15 
    16 subsection {* Definition of strict product type *}
    17 
    18 typedef (Sprod)  ('a, 'b) "**" (infixr 20) =
    19         "{p::'a \<times> 'b. p = \<bottom> \<or> (cfst\<cdot>p \<noteq> \<bottom> \<and> csnd\<cdot>p \<noteq> \<bottom>)}"
    20 by (auto simp add: inst_cprod_pcpo)
    21 
    22 syntax (xsymbols)
    23   "**"		:: "[type, type] => type"	 ("(_ \<otimes>/ _)" [21,20] 20)
    24 syntax (HTML output)
    25   "**"		:: "[type, type] => type"	 ("(_ \<otimes>/ _)" [21,20] 20)
    26 
    27 subsection {* Class instances *}
    28 
    29 instance "**" :: (pcpo, pcpo) sq_ord ..
    30 defs (overloaded)
    31   less_sprod_def: "op \<sqsubseteq> \<equiv> \<lambda>x y. Rep_Sprod x \<sqsubseteq> Rep_Sprod y"
    32 
    33 lemma adm_Sprod: "adm (\<lambda>x. x \<in> Sprod)"
    34 by (simp add: Sprod_def)
    35 
    36 lemma UU_Sprod: "\<bottom> \<in> Sprod"
    37 by (simp add: Sprod_def)
    38 
    39 instance "**" :: (pcpo, pcpo) po
    40 by (rule typedef_po [OF type_definition_Sprod less_sprod_def])
    41 
    42 instance "**" :: (pcpo, pcpo) cpo
    43 by (rule typedef_cpo [OF type_definition_Sprod less_sprod_def adm_Sprod])
    44 
    45 instance "**" :: (pcpo, pcpo) pcpo
    46 by (rule typedef_pcpo_UU [OF type_definition_Sprod less_sprod_def UU_Sprod])
    47 
    48 lemmas cont_Rep_Sprod =
    49   typedef_cont_Rep [OF type_definition_Sprod less_sprod_def adm_Sprod]
    50 
    51 lemmas cont_Abs_Sprod = 
    52   typedef_cont_Abs [OF type_definition_Sprod less_sprod_def adm_Sprod]
    53 
    54 lemmas Rep_Sprod_strict =
    55   typedef_Rep_strict [OF type_definition_Sprod less_sprod_def UU_Sprod]
    56 
    57 lemmas Abs_Sprod_strict =
    58   typedef_Abs_strict [OF type_definition_Sprod less_sprod_def UU_Sprod]
    59 
    60 lemma UU_Abs_Sprod: "\<bottom> = Abs_Sprod <\<bottom>, \<bottom>>"
    61 by (simp add: Abs_Sprod_strict inst_cprod_pcpo2 [symmetric])
    62 
    63 lemma spair_lemma:
    64   "<strictify\<cdot>(\<Lambda> b. a)\<cdot>b, strictify\<cdot>(\<Lambda> a. b)\<cdot>a> \<in> Sprod"
    65 by (simp add: Sprod_def strictify_conv_if cpair_strict)
    66 
    67 subsection {* Definitions of constants *}
    68 
    69 consts
    70   sfst :: "('a ** 'b) \<rightarrow> 'a"
    71   ssnd :: "('a ** 'b) \<rightarrow> 'b"
    72   spair :: "'a \<rightarrow> 'b \<rightarrow> ('a ** 'b)"
    73   ssplit :: "('a \<rightarrow> 'b \<rightarrow> 'c) \<rightarrow> ('a ** 'b) \<rightarrow> 'c"
    74 
    75 defs
    76   sfst_def: "sfst \<equiv> \<Lambda> p. cfst\<cdot>(Rep_Sprod p)"
    77   ssnd_def: "ssnd \<equiv> \<Lambda> p. csnd\<cdot>(Rep_Sprod p)"
    78   spair_def: "spair \<equiv> \<Lambda> a b. Abs_Sprod
    79                 <strictify\<cdot>(\<Lambda> b. a)\<cdot>b, strictify\<cdot>(\<Lambda> a. b)\<cdot>a>"
    80   ssplit_def: "ssplit \<equiv> \<Lambda> f. strictify\<cdot>(\<Lambda> p. f\<cdot>(sfst\<cdot>p)\<cdot>(ssnd\<cdot>p))"
    81 
    82 syntax  
    83   "@stuple"	:: "['a, args] => 'a ** 'b"	("(1'(:_,/ _:'))")
    84 
    85 translations
    86         "(:x, y, z:)"   == "(:x, (:y, z:):)"
    87         "(:x, y:)"      == "spair$x$y"
    88 
    89 subsection {* Case analysis *}
    90 
    91 lemma spair_Abs_Sprod:
    92   "(:a, b:) = Abs_Sprod <strictify\<cdot>(\<Lambda> b. a)\<cdot>b, strictify\<cdot>(\<Lambda> a. b)\<cdot>a>"
    93 apply (unfold spair_def)
    94 apply (simp add: cont_Abs_Sprod spair_lemma)
    95 done
    96 
    97 lemma Exh_Sprod2:
    98   "z = \<bottom> \<or> (\<exists>a b. z = (:a, b:) \<and> a \<noteq> \<bottom> \<and> b \<noteq> \<bottom>)"
    99 apply (rule_tac x=z in Abs_Sprod_cases)
   100 apply (simp add: Sprod_def)
   101 apply (erule disjE)
   102 apply (simp add: Abs_Sprod_strict)
   103 apply (rule disjI2)
   104 apply (rule_tac x="cfst\<cdot>y" in exI)
   105 apply (rule_tac x="csnd\<cdot>y" in exI)
   106 apply (simp add: spair_Abs_Sprod Abs_Sprod_inject spair_lemma)
   107 apply (simp add: surjective_pairing_Cprod2)
   108 done
   109 
   110 lemma sprodE:
   111   "\<lbrakk>p = \<bottom> \<Longrightarrow> Q; \<And>x y. \<lbrakk>p = (:x, y:); x \<noteq> \<bottom>; y \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> Q\<rbrakk> \<Longrightarrow> Q"
   112 by (cut_tac z=p in Exh_Sprod2, auto)
   113 
   114 subsection {* Properties of @{term spair} *}
   115 
   116 lemma spair_strict1 [simp]: "(:\<bottom>, y:) = \<bottom>"
   117 by (simp add: spair_Abs_Sprod UU_Abs_Sprod strictify_conv_if)
   118 
   119 lemma spair_strict2 [simp]: "(:x, \<bottom>:) = \<bottom>"
   120 by (simp add: spair_Abs_Sprod UU_Abs_Sprod strictify_conv_if)
   121 
   122 lemma spair_strict: "x = \<bottom> \<or> y = \<bottom> \<Longrightarrow> (:x, y:) = \<bottom>"
   123 by auto
   124 
   125 lemma spair_strict_rev: "(:x, y:) \<noteq> \<bottom> \<Longrightarrow> x \<noteq> \<bottom> \<and> y \<noteq> \<bottom>"
   126 by (erule contrapos_np, auto)
   127 
   128 lemma spair_defined [simp]: 
   129   "\<lbrakk>x \<noteq> \<bottom>; y \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> (:x, y:) \<noteq> \<bottom>"
   130 apply (simp add: spair_Abs_Sprod UU_Abs_Sprod)
   131 apply (subst Abs_Sprod_inject)
   132 apply (simp add: Sprod_def)
   133 apply (simp add: Sprod_def inst_cprod_pcpo2)
   134 apply simp
   135 done
   136 
   137 lemma spair_defined_rev: "(:x, y:) = \<bottom> \<Longrightarrow> x = \<bottom> \<or> y = \<bottom>"
   138 by (erule contrapos_pp, simp)
   139 
   140 lemma spair_eq:
   141   "\<lbrakk>x \<noteq> \<bottom>; y \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> ((:x, y:) = (:a, b:)) = (x = a \<and> y = b)"
   142 apply (simp add: spair_Abs_Sprod)
   143 apply (simp add: Abs_Sprod_inject [OF _ spair_lemma] Sprod_def)
   144 apply (simp add: strictify_conv_if)
   145 done
   146 
   147 lemma spair_inject:
   148   "\<lbrakk>x \<noteq> \<bottom>; y \<noteq> \<bottom>; (:x, y:) = (:a, b:)\<rbrakk> \<Longrightarrow> x = a \<and> y = b"
   149 by (rule spair_eq [THEN iffD1])
   150 
   151 lemma inst_sprod_pcpo2: "UU = (:UU,UU:)"
   152 by simp
   153 
   154 subsection {* Properties of @{term sfst} and @{term ssnd} *}
   155 
   156 lemma sfst_strict [simp]: "sfst\<cdot>\<bottom> = \<bottom>"
   157 by (simp add: sfst_def cont_Rep_Sprod Rep_Sprod_strict)
   158 
   159 lemma ssnd_strict [simp]: "ssnd\<cdot>\<bottom> = \<bottom>"
   160 by (simp add: ssnd_def cont_Rep_Sprod Rep_Sprod_strict)
   161 
   162 lemma Rep_Sprod_spair:
   163   "Rep_Sprod (:a, b:) = <strictify\<cdot>(\<Lambda> b. a)\<cdot>b, strictify\<cdot>(\<Lambda> a. b)\<cdot>a>"
   164 apply (unfold spair_def)
   165 apply (simp add: cont_Abs_Sprod Abs_Sprod_inverse spair_lemma)
   166 done
   167 
   168 lemma sfst_spair [simp]: "y \<noteq> \<bottom> \<Longrightarrow> sfst\<cdot>(:x, y:) = x"
   169 by (simp add: sfst_def cont_Rep_Sprod Rep_Sprod_spair)
   170 
   171 lemma ssnd_spair [simp]: "x \<noteq> \<bottom> \<Longrightarrow> ssnd\<cdot>(:x, y:) = y"
   172 by (simp add: ssnd_def cont_Rep_Sprod Rep_Sprod_spair)
   173 
   174 lemma sfstssnd_defined: "p \<noteq> \<bottom> \<Longrightarrow> sfst\<cdot>p \<noteq> \<bottom> \<and> ssnd\<cdot>p \<noteq> \<bottom>"
   175 by (rule_tac p=p in sprodE, simp_all)
   176 
   177 lemma surjective_pairing_Sprod2: "(:sfst\<cdot>p, ssnd\<cdot>p:) = p"
   178 by (rule_tac p=p in sprodE, simp_all)
   179 
   180 lemma less_sprod: "p1 \<sqsubseteq> p2 = (sfst\<cdot>p1 \<sqsubseteq> sfst\<cdot>p2 \<and> ssnd\<cdot>p1 \<sqsubseteq> ssnd\<cdot>p2)"
   181 apply (simp add: less_sprod_def sfst_def ssnd_def cont_Rep_Sprod)
   182 apply (rule less_cprod)
   183 done
   184 
   185 lemma spair_less:
   186   "\<lbrakk>x \<noteq> \<bottom>; y \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> (:x, y:) \<sqsubseteq> (:a, b:) = (x \<sqsubseteq> a \<and> y \<sqsubseteq> b)"
   187 apply (case_tac "a = \<bottom>")
   188 apply (simp add: eq_UU_iff [symmetric])
   189 apply (case_tac "b = \<bottom>")
   190 apply (simp add: eq_UU_iff [symmetric])
   191 apply (simp add: less_sprod)
   192 done
   193 
   194 
   195 subsection {* Properties of @{term ssplit} *}
   196 
   197 lemma ssplit1 [simp]: "ssplit\<cdot>f\<cdot>\<bottom> = \<bottom>"
   198 by (simp add: ssplit_def)
   199 
   200 lemma ssplit2 [simp]: "\<lbrakk>x \<noteq> \<bottom>; y \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> ssplit\<cdot>f\<cdot>(:x, y:)= f\<cdot>x\<cdot>y"
   201 by (simp add: ssplit_def)
   202 
   203 lemma ssplit3 [simp]: "ssplit\<cdot>spair\<cdot>z = z"
   204 by (rule_tac p=z in sprodE, simp_all)
   205 
   206 end