src/HOLCF/Sprod.thy
author huffman
Fri Jun 03 23:29:48 2005 +0200 (2005-06-03)
changeset 16212 422f836f6b39
parent 16082 ebb53ebfd4e2
child 16317 868eddbcaf6e
permissions -rw-r--r--
renamed strict, defined, and inject lemmas; renamed sfst2, ssnd2 to sfst_spair, ssnd_spair
     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>, b:) = \<bottom>"
   117 by (simp add: spair_Abs_Sprod UU_Abs_Sprod strictify_conv_if)
   118 
   119 lemma spair_strict2 [simp]: "(:a, \<bottom>:) = \<bottom>"
   120 by (simp add: spair_Abs_Sprod UU_Abs_Sprod strictify_conv_if)
   121 
   122 lemma spair_strict: "a = \<bottom> \<or> b = \<bottom> \<Longrightarrow> (:a, b:) = \<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>a \<noteq> \<bottom>; b \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> (:a, b:) \<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: "(:a, b:) = \<bottom> \<Longrightarrow> a = \<bottom> \<or> b = \<bottom>"
   138 by (erule contrapos_pp, simp)
   139 
   140 lemma spair_inject:
   141   "\<lbrakk>aa \<noteq> \<bottom>; ba \<noteq> \<bottom>; (:a,b:) = (:aa,ba:)\<rbrakk> \<Longrightarrow> a = aa \<and> b = ba"
   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 split: split_if_asm)
   145 done
   146 
   147 lemma inst_sprod_pcpo2: "UU = (:UU,UU:)"
   148 by simp
   149 
   150 subsection {* Properties of @{term sfst} and @{term ssnd} *}
   151 
   152 lemma sfst_strict [simp]: "sfst\<cdot>\<bottom> = \<bottom>"
   153 by (simp add: sfst_def cont_Rep_Sprod Rep_Sprod_strict)
   154 
   155 lemma ssnd_strict [simp]: "ssnd\<cdot>\<bottom> = \<bottom>"
   156 by (simp add: ssnd_def cont_Rep_Sprod Rep_Sprod_strict)
   157 
   158 lemma Rep_Sprod_spair:
   159   "Rep_Sprod (:a, b:) = <strictify\<cdot>(\<Lambda> b. a)\<cdot>b, strictify\<cdot>(\<Lambda> a. b)\<cdot>a>"
   160 apply (unfold spair_def)
   161 apply (simp add: cont_Abs_Sprod Abs_Sprod_inverse spair_lemma)
   162 done
   163 
   164 lemma sfst_spair [simp]: "y \<noteq> \<bottom> \<Longrightarrow> sfst\<cdot>(:x, y:) = x"
   165 by (simp add: sfst_def cont_Rep_Sprod Rep_Sprod_spair)
   166 
   167 lemma ssnd_spair [simp]: "x \<noteq> \<bottom> \<Longrightarrow> ssnd\<cdot>(:x, y:) = y"
   168 by (simp add: ssnd_def cont_Rep_Sprod Rep_Sprod_spair)
   169 
   170 lemma sfstssnd_defined: "p \<noteq> \<bottom> \<Longrightarrow> sfst\<cdot>p \<noteq> \<bottom> \<and> ssnd\<cdot>p \<noteq> \<bottom>"
   171 by (rule_tac p=p in sprodE, simp_all)
   172  
   173 lemma surjective_pairing_Sprod2: "(:sfst\<cdot>p, ssnd\<cdot>p:) = p"
   174 by (rule_tac p=p in sprodE, simp_all)
   175 
   176 subsection {* Properties of @{term ssplit} *}
   177 
   178 lemma ssplit1 [simp]: "ssplit\<cdot>f\<cdot>\<bottom> = \<bottom>"
   179 by (simp add: ssplit_def)
   180 
   181 lemma ssplit2 [simp]: "\<lbrakk>x \<noteq> \<bottom>; y \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> ssplit\<cdot>f\<cdot>(:x, y:)= f\<cdot>x\<cdot>y"
   182 by (simp add: ssplit_def)
   183 
   184 lemma ssplit3: "ssplit\<cdot>spair\<cdot>z = z"
   185 by (rule_tac p=z in sprodE, simp_all)
   186 
   187 end