src/HOLCF/Sprod.thy
author huffman
Tue May 24 05:52:48 2005 +0200 (2005-05-24)
changeset 16059 dab0d004732f
parent 15930 145651bc64a8
child 16070 4a83dd540b88
permissions -rw-r--r--
Simplified version of strict product theory, using TypedefPcpo
     1 (*  Title:      HOLCF/Sprod.thy
     2     ID:         $Id$
     3     Author:     Franz Regensburger and Brian Huffman
     4     License:    GPL (GNU GENERAL PUBLIC LICENSE)
     5 
     6 Strict product with typedef.
     7 *)
     8 
     9 header {* The type of strict products *}
    10 
    11 theory Sprod
    12 imports Cprod TypedefPcpo
    13 begin
    14 
    15 subsection {* Definition of strict product type *}
    16 
    17 typedef (Sprod)  ('a, 'b) "**" (infixr 20) =
    18         "{p::'a \<times> 'b. p = \<bottom> \<or> (cfst\<cdot>p \<noteq> \<bottom> \<and> csnd\<cdot>p \<noteq> \<bottom>)}"
    19 by (auto simp add: inst_cprod_pcpo)
    20 
    21 syntax (xsymbols)
    22   "**"		:: "[type, type] => type"	 ("(_ \<otimes>/ _)" [21,20] 20)
    23 syntax (HTML output)
    24   "**"		:: "[type, type] => type"	 ("(_ \<otimes>/ _)" [21,20] 20)
    25 
    26 subsection {* Class instances *}
    27 
    28 instance "**" :: (pcpo, pcpo) sq_ord ..
    29 defs (overloaded)
    30   less_sprod_def: "op \<sqsubseteq> \<equiv> \<lambda>x y. Rep_Sprod x \<sqsubseteq> Rep_Sprod y"
    31 
    32 lemma adm_Sprod: "adm (\<lambda>x. x \<in> Sprod)"
    33 by (simp add: Sprod_def)
    34 
    35 lemma UU_Sprod: "\<bottom> \<in> Sprod"
    36 by (simp add: Sprod_def)
    37 
    38 instance "**" :: (pcpo, pcpo) po
    39 by (rule typedef_po [OF type_definition_Sprod less_sprod_def])
    40 
    41 instance "**" :: (pcpo, pcpo) cpo
    42 by (rule typedef_cpo [OF type_definition_Sprod less_sprod_def adm_Sprod])
    43 
    44 instance "**" :: (pcpo, pcpo) pcpo
    45 by (rule typedef_pcpo_UU [OF type_definition_Sprod less_sprod_def UU_Sprod])
    46 
    47 lemmas cont_Rep_Sprod =
    48   typedef_cont_Rep [OF type_definition_Sprod less_sprod_def adm_Sprod]
    49 
    50 lemmas cont_Abs_Sprod = 
    51   typedef_cont_Abs [OF type_definition_Sprod less_sprod_def adm_Sprod]
    52 
    53 lemmas strict_Rep_Sprod =
    54   typedef_strict_Rep [OF type_definition_Sprod less_sprod_def UU_Sprod]
    55 
    56 lemmas strict_Abs_Sprod =
    57   typedef_strict_Abs [OF type_definition_Sprod less_sprod_def UU_Sprod]
    58 
    59 lemma UU_Abs_Sprod: "\<bottom> = Abs_Sprod <\<bottom>, \<bottom>>"
    60 by (simp add: strict_Abs_Sprod inst_cprod_pcpo2 [symmetric])
    61 
    62 lemma spair_lemma:
    63   "<strictify\<cdot>(\<Lambda> b. a)\<cdot>b, strictify\<cdot>(\<Lambda> a. b)\<cdot>a> \<in> Sprod"
    64 apply (simp add: Sprod_def inst_cprod_pcpo2)
    65 apply (case_tac "a = \<bottom>", case_tac [!] "b = \<bottom>", simp_all)
    66 done
    67 
    68 subsection {* Definitions of constants *}
    69 
    70 consts
    71   sfst :: "('a ** 'b) \<rightarrow> 'a"
    72   ssnd :: "('a ** 'b) \<rightarrow> 'b"
    73   spair :: "'a \<rightarrow> 'b \<rightarrow> ('a ** 'b)"
    74   ssplit :: "('a \<rightarrow> 'b \<rightarrow> 'c) \<rightarrow> ('a ** 'b) \<rightarrow> 'c"
    75 
    76 defs
    77   sfst_def: "sfst \<equiv> \<Lambda> p. cfst\<cdot>(Rep_Sprod p)"
    78   ssnd_def: "ssnd \<equiv> \<Lambda> p. csnd\<cdot>(Rep_Sprod p)"
    79   spair_def: "spair \<equiv> \<Lambda> a b. Abs_Sprod
    80                 <strictify\<cdot>(\<Lambda> b. a)\<cdot>b, strictify\<cdot>(\<Lambda> a. b)\<cdot>a>"
    81   ssplit_def: "ssplit \<equiv> \<Lambda> f. strictify\<cdot>(\<Lambda> p. f\<cdot>(sfst\<cdot>p)\<cdot>(ssnd\<cdot>p))"
    82 
    83 syntax  
    84   "@stuple"	:: "['a, args] => 'a ** 'b"	("(1'(:_,/ _:'))")
    85 
    86 translations
    87         "(:x, y, z:)"   == "(:x, (:y, z:):)"
    88         "(:x, y:)"      == "spair$x$y"
    89 
    90 subsection {* Case analysis *}
    91 
    92 lemma spair_Abs_Sprod:
    93   "(:a, b:) = Abs_Sprod <strictify\<cdot>(\<Lambda> b. a)\<cdot>b, strictify\<cdot>(\<Lambda> a. b)\<cdot>a>"
    94 apply (unfold spair_def)
    95 apply (simp add: cont_Abs_Sprod spair_lemma)
    96 done
    97 
    98 lemma Exh_Sprod2:
    99   "z = \<bottom> \<or> (\<exists>a b. z = (:a, b:) \<and> a \<noteq> \<bottom> \<and> b \<noteq> \<bottom>)"
   100 apply (rule_tac x=z in Abs_Sprod_cases)
   101 apply (simp add: Sprod_def)
   102 apply (erule disjE)
   103 apply (simp add: strict_Abs_Sprod)
   104 apply (rule disjI2)
   105 apply (rule_tac x="cfst\<cdot>y" in exI)
   106 apply (rule_tac x="csnd\<cdot>y" in exI)
   107 apply (simp add: spair_Abs_Sprod Abs_Sprod_inject spair_lemma)
   108 apply (simp add: surjective_pairing_Cprod2)
   109 done
   110 
   111 lemma sprodE:
   112   "\<lbrakk>p = \<bottom> \<Longrightarrow> Q; \<And>x y. \<lbrakk>p = (:x, y:); x \<noteq> \<bottom>; y \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> Q\<rbrakk> \<Longrightarrow> Q"
   113 by (cut_tac z=p in Exh_Sprod2, auto)
   114 
   115 subsection {* Properties of @{term spair} *}
   116 
   117 lemma strict_spair1 [simp]: "(:\<bottom>, b:) = \<bottom>"
   118 apply (simp add: spair_Abs_Sprod UU_Abs_Sprod)
   119 apply (case_tac "b = \<bottom>", simp_all)
   120 done
   121 
   122 lemma strict_spair2 [simp]: "(:a, \<bottom>:) = \<bottom>"
   123 apply (simp add: spair_Abs_Sprod UU_Abs_Sprod)
   124 apply (case_tac "a = \<bottom>", simp_all)
   125 done
   126 
   127 lemma strict_spair: "a = \<bottom> \<or> b = \<bottom> \<Longrightarrow> (:a, b:) = \<bottom>"
   128 by auto
   129 
   130 lemma strict_spair_rev: "(:x, y:) \<noteq> \<bottom> \<Longrightarrow> x \<noteq> \<bottom> \<and> y \<noteq> \<bottom>"
   131 by (erule contrapos_np, auto)
   132 
   133 lemma defined_spair [simp]: 
   134   "\<lbrakk>a \<noteq> \<bottom>; b \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> (:a, b:) \<noteq> \<bottom>"
   135 apply (simp add: spair_Abs_Sprod UU_Abs_Sprod)
   136 apply (subst Abs_Sprod_inject)
   137 apply (simp add: Sprod_def)
   138 apply (simp add: Sprod_def inst_cprod_pcpo2)
   139 apply simp
   140 done
   141 
   142 lemma defined_spair_rev: "(:a, b:) = \<bottom> \<Longrightarrow> a = \<bottom> \<or> b = \<bottom>"
   143 by (erule contrapos_pp, simp)
   144 
   145 lemma inject_spair: 
   146   "\<lbrakk>aa \<noteq> \<bottom>; ba \<noteq> \<bottom>; (:a,b:) = (:aa,ba:)\<rbrakk> \<Longrightarrow> a = aa \<and> b = ba"
   147 apply (simp add: spair_Abs_Sprod)
   148 apply (simp add: Abs_Sprod_inject [OF spair_lemma] Sprod_def)
   149 apply (case_tac "a = \<bottom>", simp_all)
   150 apply (case_tac "b = \<bottom>", simp_all)
   151 done
   152 
   153 lemma inst_sprod_pcpo2: "UU = (:UU,UU:)"
   154 by simp
   155 
   156 subsection {* Properties of @{term sfst} and @{term ssnd} *}
   157 
   158 lemma strict_sfst [simp]: "sfst\<cdot>\<bottom> = \<bottom>"
   159 by (simp add: sfst_def cont_Rep_Sprod strict_Rep_Sprod)
   160 
   161 lemma strict_ssnd [simp]: "ssnd\<cdot>\<bottom> = \<bottom>"
   162 by (simp add: ssnd_def cont_Rep_Sprod strict_Rep_Sprod)
   163 
   164 lemma Rep_Sprod_spair:
   165   "Rep_Sprod (:a, b:) = <strictify\<cdot>(\<Lambda> b. a)\<cdot>b, strictify\<cdot>(\<Lambda> a. b)\<cdot>a>"
   166 apply (unfold spair_def)
   167 apply (simp add: cont_Abs_Sprod Abs_Sprod_inverse spair_lemma)
   168 done
   169 
   170 lemma sfst2 [simp]: "y \<noteq> \<bottom> \<Longrightarrow> sfst\<cdot>(:x, y:) = x"
   171 by (simp add: sfst_def cont_Rep_Sprod Rep_Sprod_spair)
   172 
   173 lemma ssnd2 [simp]: "x \<noteq> \<bottom> \<Longrightarrow> ssnd\<cdot>(:x, y:) = y"
   174 by (simp add: ssnd_def cont_Rep_Sprod Rep_Sprod_spair)
   175 
   176 lemma defined_sfstssnd: "p \<noteq> \<bottom> \<Longrightarrow> sfst\<cdot>p \<noteq> \<bottom> \<and> ssnd\<cdot>p \<noteq> \<bottom>"
   177 by (rule_tac p=p in sprodE, simp_all)
   178  
   179 lemma surjective_pairing_Sprod2: "(:sfst\<cdot>p, ssnd\<cdot>p:) = p"
   180 by (rule_tac p=p in sprodE, simp_all)
   181 
   182 subsection {* Properties of @{term ssplit} *}
   183 
   184 lemma ssplit1 [simp]: "ssplit\<cdot>f\<cdot>\<bottom> = \<bottom>"
   185 by (simp add: ssplit_def)
   186 
   187 lemma ssplit2 [simp]: "\<lbrakk>x \<noteq> \<bottom>; y \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> ssplit\<cdot>f\<cdot>(:x, y:)= f\<cdot>x\<cdot>y"
   188 by (simp add: ssplit_def)
   189 
   190 lemma ssplit3: "ssplit\<cdot>spair\<cdot>z = z"
   191 by (rule_tac p=z in sprodE, simp_all)
   192 
   193 end