src/HOLCF/Sprod.thy
author wenzelm
Wed May 25 09:44:34 2005 +0200 (2005-05-25)
changeset 16070 4a83dd540b88
parent 16059 dab0d004732f
child 16082 ebb53ebfd4e2
permissions -rw-r--r--
removed LICENCE note -- everything is subject to Isabelle licence as
stated in COPYRIGHT file;
     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 subsection {* Definition of strict product type *}
    15 
    16 typedef (Sprod)  ('a, 'b) "**" (infixr 20) =
    17         "{p::'a \<times> 'b. p = \<bottom> \<or> (cfst\<cdot>p \<noteq> \<bottom> \<and> csnd\<cdot>p \<noteq> \<bottom>)}"
    18 by (auto simp add: inst_cprod_pcpo)
    19 
    20 syntax (xsymbols)
    21   "**"		:: "[type, type] => type"	 ("(_ \<otimes>/ _)" [21,20] 20)
    22 syntax (HTML output)
    23   "**"		:: "[type, type] => type"	 ("(_ \<otimes>/ _)" [21,20] 20)
    24 
    25 subsection {* Class instances *}
    26 
    27 instance "**" :: (pcpo, pcpo) sq_ord ..
    28 defs (overloaded)
    29   less_sprod_def: "op \<sqsubseteq> \<equiv> \<lambda>x y. Rep_Sprod x \<sqsubseteq> Rep_Sprod y"
    30 
    31 lemma adm_Sprod: "adm (\<lambda>x. x \<in> Sprod)"
    32 by (simp add: Sprod_def)
    33 
    34 lemma UU_Sprod: "\<bottom> \<in> Sprod"
    35 by (simp add: Sprod_def)
    36 
    37 instance "**" :: (pcpo, pcpo) po
    38 by (rule typedef_po [OF type_definition_Sprod less_sprod_def])
    39 
    40 instance "**" :: (pcpo, pcpo) cpo
    41 by (rule typedef_cpo [OF type_definition_Sprod less_sprod_def adm_Sprod])
    42 
    43 instance "**" :: (pcpo, pcpo) pcpo
    44 by (rule typedef_pcpo_UU [OF type_definition_Sprod less_sprod_def UU_Sprod])
    45 
    46 lemmas cont_Rep_Sprod =
    47   typedef_cont_Rep [OF type_definition_Sprod less_sprod_def adm_Sprod]
    48 
    49 lemmas cont_Abs_Sprod = 
    50   typedef_cont_Abs [OF type_definition_Sprod less_sprod_def adm_Sprod]
    51 
    52 lemmas strict_Rep_Sprod =
    53   typedef_strict_Rep [OF type_definition_Sprod less_sprod_def UU_Sprod]
    54 
    55 lemmas strict_Abs_Sprod =
    56   typedef_strict_Abs [OF type_definition_Sprod less_sprod_def UU_Sprod]
    57 
    58 lemma UU_Abs_Sprod: "\<bottom> = Abs_Sprod <\<bottom>, \<bottom>>"
    59 by (simp add: strict_Abs_Sprod inst_cprod_pcpo2 [symmetric])
    60 
    61 lemma spair_lemma:
    62   "<strictify\<cdot>(\<Lambda> b. a)\<cdot>b, strictify\<cdot>(\<Lambda> a. b)\<cdot>a> \<in> Sprod"
    63 apply (simp add: Sprod_def inst_cprod_pcpo2)
    64 apply (case_tac "a = \<bottom>", case_tac [!] "b = \<bottom>", simp_all)
    65 done
    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: strict_Abs_Sprod)
   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 strict_spair1 [simp]: "(:\<bottom>, b:) = \<bottom>"
   117 apply (simp add: spair_Abs_Sprod UU_Abs_Sprod)
   118 apply (case_tac "b = \<bottom>", simp_all)
   119 done
   120 
   121 lemma strict_spair2 [simp]: "(:a, \<bottom>:) = \<bottom>"
   122 apply (simp add: spair_Abs_Sprod UU_Abs_Sprod)
   123 apply (case_tac "a = \<bottom>", simp_all)
   124 done
   125 
   126 lemma strict_spair: "a = \<bottom> \<or> b = \<bottom> \<Longrightarrow> (:a, b:) = \<bottom>"
   127 by auto
   128 
   129 lemma strict_spair_rev: "(:x, y:) \<noteq> \<bottom> \<Longrightarrow> x \<noteq> \<bottom> \<and> y \<noteq> \<bottom>"
   130 by (erule contrapos_np, auto)
   131 
   132 lemma defined_spair [simp]: 
   133   "\<lbrakk>a \<noteq> \<bottom>; b \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> (:a, b:) \<noteq> \<bottom>"
   134 apply (simp add: spair_Abs_Sprod UU_Abs_Sprod)
   135 apply (subst Abs_Sprod_inject)
   136 apply (simp add: Sprod_def)
   137 apply (simp add: Sprod_def inst_cprod_pcpo2)
   138 apply simp
   139 done
   140 
   141 lemma defined_spair_rev: "(:a, b:) = \<bottom> \<Longrightarrow> a = \<bottom> \<or> b = \<bottom>"
   142 by (erule contrapos_pp, simp)
   143 
   144 lemma inject_spair: 
   145   "\<lbrakk>aa \<noteq> \<bottom>; ba \<noteq> \<bottom>; (:a,b:) = (:aa,ba:)\<rbrakk> \<Longrightarrow> a = aa \<and> b = ba"
   146 apply (simp add: spair_Abs_Sprod)
   147 apply (simp add: Abs_Sprod_inject [OF spair_lemma] Sprod_def)
   148 apply (case_tac "a = \<bottom>", simp_all)
   149 apply (case_tac "b = \<bottom>", simp_all)
   150 done
   151 
   152 lemma inst_sprod_pcpo2: "UU = (:UU,UU:)"
   153 by simp
   154 
   155 subsection {* Properties of @{term sfst} and @{term ssnd} *}
   156 
   157 lemma strict_sfst [simp]: "sfst\<cdot>\<bottom> = \<bottom>"
   158 by (simp add: sfst_def cont_Rep_Sprod strict_Rep_Sprod)
   159 
   160 lemma strict_ssnd [simp]: "ssnd\<cdot>\<bottom> = \<bottom>"
   161 by (simp add: ssnd_def cont_Rep_Sprod strict_Rep_Sprod)
   162 
   163 lemma Rep_Sprod_spair:
   164   "Rep_Sprod (:a, b:) = <strictify\<cdot>(\<Lambda> b. a)\<cdot>b, strictify\<cdot>(\<Lambda> a. b)\<cdot>a>"
   165 apply (unfold spair_def)
   166 apply (simp add: cont_Abs_Sprod Abs_Sprod_inverse spair_lemma)
   167 done
   168 
   169 lemma sfst2 [simp]: "y \<noteq> \<bottom> \<Longrightarrow> sfst\<cdot>(:x, y:) = x"
   170 by (simp add: sfst_def cont_Rep_Sprod Rep_Sprod_spair)
   171 
   172 lemma ssnd2 [simp]: "x \<noteq> \<bottom> \<Longrightarrow> ssnd\<cdot>(:x, y:) = y"
   173 by (simp add: ssnd_def cont_Rep_Sprod Rep_Sprod_spair)
   174 
   175 lemma defined_sfstssnd: "p \<noteq> \<bottom> \<Longrightarrow> sfst\<cdot>p \<noteq> \<bottom> \<and> ssnd\<cdot>p \<noteq> \<bottom>"
   176 by (rule_tac p=p in sprodE, simp_all)
   177  
   178 lemma surjective_pairing_Sprod2: "(:sfst\<cdot>p, ssnd\<cdot>p:) = p"
   179 by (rule_tac p=p in sprodE, simp_all)
   180 
   181 subsection {* Properties of @{term ssplit} *}
   182 
   183 lemma ssplit1 [simp]: "ssplit\<cdot>f\<cdot>\<bottom> = \<bottom>"
   184 by (simp add: ssplit_def)
   185 
   186 lemma ssplit2 [simp]: "\<lbrakk>x \<noteq> \<bottom>; y \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> ssplit\<cdot>f\<cdot>(:x, y:)= f\<cdot>x\<cdot>y"
   187 by (simp add: ssplit_def)
   188 
   189 lemma ssplit3: "ssplit\<cdot>spair\<cdot>z = z"
   190 by (rule_tac p=z in sprodE, simp_all)
   191 
   192 end