src/HOL/UNITY/Transformers.thy
author paulson
Mon Mar 17 17:37:48 2003 +0100 (2003-03-17)
changeset 13866 b42d7983a822
parent 13861 0c18f31d901a
child 13874 0da2141606c6
permissions -rw-r--r--
More "progress set" material
     1 (*  Title:      HOL/UNITY/Transformers
     2     ID:         $Id$
     3     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
     4     Copyright   2003  University of Cambridge
     5 
     6 Predicate Transformers.  From 
     7 
     8     David Meier and Beverly Sanders,
     9     Composing Leads-to Properties
    10     Theoretical Computer Science 243:1-2 (2000), 339-361.
    11 
    12     David Meier,
    13     Progress Properties in Program Refinement and Parallel Composition
    14     Swiss Federal Institute of Technology Zurich (1997)
    15 *)
    16 
    17 header{*Predicate Transformers*}
    18 
    19 theory Transformers = Comp:
    20 
    21 subsection{*Defining the Predicate Transformers @{term wp},
    22    @{term awp} and  @{term wens}*}
    23 
    24 constdefs
    25   wp :: "[('a*'a) set, 'a set] => 'a set"  
    26     --{*Dijkstra's weakest-precondition operator (for an individual command)*}
    27     "wp act B == - (act^-1 `` (-B))"
    28 
    29   awp :: "['a program, 'a set] => 'a set"  
    30     --{*Dijkstra's weakest-precondition operator (for a program)*}
    31     "awp F B == (\<Inter>act \<in> Acts F. wp act B)"
    32 
    33   wens :: "['a program, ('a*'a) set, 'a set] => 'a set"  
    34     --{*The weakest-ensures transformer*}
    35     "wens F act B == gfp(\<lambda>X. (wp act B \<inter> awp F (B \<union> X)) \<union> B)"
    36 
    37 text{*The fundamental theorem for wp*}
    38 theorem wp_iff: "(A <= wp act B) = (act `` A <= B)"
    39 by (force simp add: wp_def) 
    40 
    41 lemma Compl_Domain_subset_wp: "- (Domain act) \<subseteq> wp act B"
    42 by (force simp add: wp_def) 
    43 
    44 lemma wp_empty [simp]: "wp act {} = - (Domain act)"
    45 by (force simp add: wp_def)
    46 
    47 text{*The identity relation is the skip action*}
    48 lemma wp_Id [simp]: "wp Id B = B"
    49 by (simp add: wp_def) 
    50 
    51 lemma wp_totalize_act:
    52      "wp (totalize_act act) B = (wp act B \<inter> Domain act) \<union> (B - Domain act)"
    53 by (simp add: wp_def totalize_act_def, blast)
    54 
    55 lemma awp_subset: "(awp F A \<subseteq> A)"
    56 by (force simp add: awp_def wp_def)
    57 
    58 lemma awp_Int_eq: "awp F (A\<inter>B) = awp F A \<inter> awp F B"
    59 by (simp add: awp_def wp_def, blast) 
    60 
    61 text{*The fundamental theorem for awp*}
    62 theorem awp_iff_constrains: "(A <= awp F B) = (F \<in> A co B)"
    63 by (simp add: awp_def constrains_def wp_iff INT_subset_iff) 
    64 
    65 lemma awp_iff_stable: "(A \<subseteq> awp F A) = (F \<in> stable A)"
    66 by (simp add: awp_iff_constrains stable_def) 
    67 
    68 lemma stable_imp_awp_ident: "F \<in> stable A ==> awp F A = A"
    69 apply (rule equalityI [OF awp_subset]) 
    70 apply (simp add: awp_iff_stable) 
    71 done
    72 
    73 lemma awp_mono: "(A \<subseteq> B) ==> awp F A \<subseteq> awp F B"
    74 by (simp add: awp_def wp_def, blast)
    75 
    76 lemma wens_unfold:
    77      "wens F act B = (wp act B \<inter> awp F (B \<union> wens F act B)) \<union> B"
    78 apply (simp add: wens_def) 
    79 apply (rule gfp_unfold) 
    80 apply (simp add: mono_def wp_def awp_def, blast) 
    81 done
    82 
    83 lemma wens_Id [simp]: "wens F Id B = B"
    84 by (simp add: wens_def gfp_def wp_def awp_def, blast)
    85 
    86 text{*These two theorems justify the claim that @{term wens} returns the
    87 weakest assertion satisfying the ensures property*}
    88 lemma ensures_imp_wens: "F \<in> A ensures B ==> \<exists>act \<in> Acts F. A \<subseteq> wens F act B"
    89 apply (simp add: wens_def ensures_def transient_def, clarify) 
    90 apply (rule rev_bexI, assumption) 
    91 apply (rule gfp_upperbound)
    92 apply (simp add: constrains_def awp_def wp_def, blast)
    93 done
    94 
    95 lemma wens_ensures: "act \<in> Acts F ==> F \<in> (wens F act B) ensures B"
    96 by (simp add: wens_def gfp_def constrains_def awp_def wp_def
    97               ensures_def transient_def, blast) 
    98 
    99 text{*These two results constitute assertion (4.13) of the thesis*}
   100 lemma wens_mono: "(A \<subseteq> B) ==> wens F act A \<subseteq> wens F act B"
   101 apply (simp add: wens_def wp_def awp_def) 
   102 apply (rule gfp_mono, blast) 
   103 done
   104 
   105 lemma wens_weakening: "B \<subseteq> wens F act B"
   106 by (simp add: wens_def gfp_def, blast)
   107 
   108 text{*Assertion (6), or 4.16 in the thesis*}
   109 lemma subset_wens: "A-B \<subseteq> wp act B \<inter> awp F (B \<union> A) ==> A \<subseteq> wens F act B" 
   110 apply (simp add: wens_def wp_def awp_def) 
   111 apply (rule gfp_upperbound, blast) 
   112 done
   113 
   114 text{*Assertion 4.17 in the thesis*}
   115 lemma Diff_wens_constrains: "F \<in> (wens F act A - A) co wens F act A" 
   116 by (simp add: wens_def gfp_def wp_def awp_def constrains_def, blast)
   117 
   118 text{*Assertion (7): 4.18 in the thesis.  NOTE that many of these results
   119 hold for an arbitrary action.  We often do not require @{term "act \<in> Acts F"}*}
   120 lemma stable_wens: "F \<in> stable A ==> F \<in> stable (wens F act A)"
   121 apply (simp add: stable_def)
   122 apply (drule constrains_Un [OF Diff_wens_constrains [of F act A]]) 
   123 apply (simp add: Un_Int_distrib2 Compl_partition2) 
   124 apply (erule constrains_weaken, blast) 
   125 apply (simp add: Un_subset_iff wens_weakening) 
   126 done
   127 
   128 text{*Assertion 4.20 in the thesis.*}
   129 lemma wens_Int_eq_lemma:
   130       "[|T-B \<subseteq> awp F T; act \<in> Acts F|]
   131        ==> T \<inter> wens F act B \<subseteq> wens F act (T\<inter>B)"
   132 apply (rule subset_wens) 
   133 apply (rule_tac P="\<lambda>x. ?f x \<subseteq> ?b" in ssubst [OF wens_unfold])
   134 apply (simp add: wp_def awp_def, blast)
   135 done
   136 
   137 text{*Assertion (8): 4.21 in the thesis. Here we indeed require
   138       @{term "act \<in> Acts F"}*}
   139 lemma wens_Int_eq:
   140       "[|T-B \<subseteq> awp F T; act \<in> Acts F|]
   141        ==> T \<inter> wens F act B = T \<inter> wens F act (T\<inter>B)"
   142 apply (rule equalityI)
   143  apply (simp_all add: Int_lower1 Int_subset_iff) 
   144  apply (rule wens_Int_eq_lemma, assumption+) 
   145 apply (rule subset_trans [OF _ wens_mono [of "T\<inter>B" B]], auto) 
   146 done
   147 
   148 
   149 subsection{*Defining the Weakest Ensures Set*}
   150 
   151 consts
   152   wens_set :: "['a program, 'a set] => 'a set set"
   153 
   154 inductive "wens_set F B"
   155  intros 
   156 
   157   Basis: "B \<in> wens_set F B"
   158 
   159   Wens:  "[|X \<in> wens_set F B; act \<in> Acts F|] ==> wens F act X \<in> wens_set F B"
   160 
   161   Union: "W \<noteq> {} ==> \<forall>U \<in> W. U \<in> wens_set F B ==> \<Union>W \<in> wens_set F B"
   162 
   163 lemma wens_set_imp_co: "A \<in> wens_set F B ==> F \<in> (A-B) co A"
   164 apply (erule wens_set.induct) 
   165   apply (simp add: constrains_def)
   166  apply (drule_tac act1=act and A1=X 
   167         in constrains_Un [OF Diff_wens_constrains]) 
   168  apply (erule constrains_weaken, blast) 
   169  apply (simp add: Un_subset_iff wens_weakening) 
   170 apply (rule constrains_weaken) 
   171 apply (rule_tac I=W and A="\<lambda>v. v-B" and A'="\<lambda>v. v" in constrains_UN, blast+)
   172 done
   173 
   174 lemma wens_set_imp_leadsTo: "A \<in> wens_set F B ==> F \<in> A leadsTo B"
   175 apply (erule wens_set.induct)
   176   apply (rule leadsTo_refl)  
   177  apply (blast intro: wens_ensures leadsTo_Trans) 
   178 apply (blast intro: leadsTo_Union) 
   179 done
   180 
   181 lemma leadsTo_imp_wens_set: "F \<in> A leadsTo B ==> \<exists>C \<in> wens_set F B. A \<subseteq> C"
   182 apply (erule leadsTo_induct_pre)
   183   apply (blast dest!: ensures_imp_wens intro: wens_set.Basis wens_set.Wens) 
   184  apply (clarify, drule ensures_weaken_R, assumption)  
   185  apply (blast dest!: ensures_imp_wens intro: wens_set.Wens)
   186 apply (case_tac "S={}") 
   187  apply (simp, blast intro: wens_set.Basis)
   188 apply (clarsimp dest!: bchoice simp: ball_conj_distrib Bex_def) 
   189 apply (rule_tac x = "\<Union>{Z. \<exists>U\<in>S. Z = f U}" in exI)
   190 apply (blast intro: wens_set.Union) 
   191 done
   192 
   193 text{*Assertion (9): 4.27 in the thesis.*}
   194 lemma leadsTo_iff_wens_set: "(F \<in> A leadsTo B) = (\<exists>C \<in> wens_set F B. A \<subseteq> C)"
   195 by (blast intro: leadsTo_imp_wens_set leadsTo_weaken_L wens_set_imp_leadsTo) 
   196 
   197 text{*This is the result that requires the definition of @{term wens_set} to
   198   require @{term W} to be non-empty in the Unio case, for otherwise we should
   199   always have @{term "{} \<in> wens_set F B"}.*}
   200 lemma wens_set_imp_subset: "A \<in> wens_set F B ==> B \<subseteq> A"
   201 apply (erule wens_set.induct) 
   202   apply (blast intro: wens_weakening [THEN subsetD])+
   203 done
   204 
   205 
   206 subsection{*Properties Involving Program Union*}
   207 
   208 text{*Assertion (4.30) of thesis, reoriented*}
   209 lemma awp_Join_eq: "awp (F\<squnion>G) B = awp F B \<inter> awp G B"
   210 by (simp add: awp_def wp_def, blast)
   211 
   212 lemma wens_subset: "wens F act B - B \<subseteq> wp act B \<inter> awp F (B \<union> wens F act B)"
   213 by (subst wens_unfold, fast) 
   214 
   215 text{*Assertion (4.31)*}
   216 lemma subset_wens_Join:
   217       "[|A = T \<inter> wens F act B;  T-B \<subseteq> awp F T; A-B \<subseteq> awp G (A \<union> B)|] 
   218        ==> A \<subseteq> wens (F\<squnion>G) act B"
   219 apply (subgoal_tac "(T \<inter> wens F act B) - B \<subseteq> 
   220                     wp act B \<inter> awp F (B \<union> wens F act B) \<inter> awp F T") 
   221  apply (rule subset_wens) 
   222  apply (simp add: awp_Join_eq awp_Int_eq Int_subset_iff Un_commute)
   223  apply (simp add: awp_def wp_def, blast) 
   224 apply (insert wens_subset [of F act B], blast) 
   225 done
   226 
   227 text{*Assertion (4.32)*}
   228 lemma wens_Join_subset: "wens (F\<squnion>G) act B \<subseteq> wens F act B"
   229 apply (simp add: wens_def) 
   230 apply (rule gfp_mono)
   231 apply (auto simp add: awp_Join_eq)  
   232 done
   233 
   234 text{*Lemma, because the inductive step is just too messy.*}
   235 lemma wens_Union_inductive_step:
   236   assumes awpF: "T-B \<subseteq> awp F T"
   237       and awpG: "!!X. X \<in> wens_set F B ==> (T\<inter>X) - B \<subseteq> awp G (T\<inter>X)"
   238   shows "[|X \<in> wens_set F B; act \<in> Acts F; Y \<subseteq> X; T\<inter>X = T\<inter>Y|]
   239          ==> wens (F\<squnion>G) act Y \<subseteq> wens F act X \<and>
   240              T \<inter> wens F act X = T \<inter> wens (F\<squnion>G) act Y"
   241 apply (subgoal_tac "wens (F\<squnion>G) act Y \<subseteq> wens F act X")  
   242  prefer 2
   243  apply (blast dest: wens_mono intro: wens_Join_subset [THEN subsetD], simp)
   244 apply (rule equalityI) 
   245  prefer 2 apply blast
   246 apply (simp add: Int_lower1 Int_subset_iff) 
   247 apply (frule wens_set_imp_subset) 
   248 apply (subgoal_tac "T-X \<subseteq> awp F T")  
   249  prefer 2 apply (blast intro: awpF [THEN subsetD]) 
   250 apply (rule_tac B = "wens (F\<squnion>G) act (T\<inter>X)" in subset_trans) 
   251  prefer 2 apply (blast intro!: wens_mono)
   252 apply (subst wens_Int_eq, assumption+) 
   253 apply (rule subset_wens_Join [of _ T], simp, blast)
   254 apply (subgoal_tac "T \<inter> wens F act (T\<inter>X) \<union> T\<inter>X = T \<inter> wens F act X")
   255  prefer 2
   256  apply (subst wens_Int_eq [symmetric], assumption+) 
   257  apply (blast intro: wens_weakening [THEN subsetD], simp) 
   258 apply (blast intro: awpG [THEN subsetD] wens_set.Wens)
   259 done
   260 
   261 theorem wens_Union:
   262   assumes awpF: "T-B \<subseteq> awp F T"
   263       and awpG: "!!X. X \<in> wens_set F B ==> (T\<inter>X) - B \<subseteq> awp G (T\<inter>X)"
   264       and major: "X \<in> wens_set F B"
   265   shows "\<exists>Y \<in> wens_set (F\<squnion>G) B. Y \<subseteq> X & T\<inter>X = T\<inter>Y"
   266 apply (rule wens_set.induct [OF major])
   267   txt{*Basis: trivial*}
   268   apply (blast intro: wens_set.Basis)
   269  txt{*Inductive step*}
   270  apply clarify 
   271  apply (rule_tac x = "wens (F\<squnion>G) act Y" in rev_bexI)
   272   apply (force intro: wens_set.Wens)
   273  apply (simp add: wens_Union_inductive_step [OF awpF awpG]) 
   274 txt{*Union: by Axiom of Choice*}
   275 apply (simp add: ball_conj_distrib Bex_def) 
   276 apply (clarify dest!: bchoice) 
   277 apply (rule_tac x = "\<Union>{Z. \<exists>U\<in>W. Z = f U}" in exI)
   278 apply (blast intro: wens_set.Union) 
   279 done
   280 
   281 theorem leadsTo_Join:
   282   assumes leadsTo: "F \<in> A leadsTo B"
   283       and awpF: "T-B \<subseteq> awp F T"
   284       and awpG: "!!X. X \<in> wens_set F B ==> (T\<inter>X) - B \<subseteq> awp G (T\<inter>X)"
   285   shows "F\<squnion>G \<in> T\<inter>A leadsTo B"
   286 apply (rule leadsTo [THEN leadsTo_imp_wens_set, THEN bexE]) 
   287 apply (rule wens_Union [THEN bexE]) 
   288    apply (rule awpF) 
   289   apply (erule awpG, assumption)
   290 apply (blast intro: wens_set_imp_leadsTo [THEN leadsTo_weaken_L])  
   291 done
   292 
   293 
   294 subsection {*The Set @{term "wens_set F B"} for a Single-Assignment Program*}
   295 text{*Thesis Section 4.3.3*}
   296 
   297 text{*We start by proving laws about single-assignment programs*}
   298 lemma awp_single_eq [simp]:
   299      "awp (mk_program (init, {act}, allowed)) B = B \<inter> wp act B"
   300 by (force simp add: awp_def wp_def) 
   301 
   302 lemma wp_Un_subset: "wp act A \<union> wp act B \<subseteq> wp act (A \<union> B)"
   303 by (force simp add: wp_def)
   304 
   305 lemma wp_Un_eq: "single_valued act ==> wp act (A \<union> B) = wp act A \<union> wp act B"
   306 apply (rule equalityI)
   307  apply (force simp add: wp_def single_valued_def) 
   308 apply (rule wp_Un_subset) 
   309 done
   310 
   311 lemma wp_UN_subset: "(\<Union>i\<in>I. wp act (A i)) \<subseteq> wp act (\<Union>i\<in>I. A i)"
   312 by (force simp add: wp_def)
   313 
   314 lemma wp_UN_eq:
   315      "[|single_valued act; I\<noteq>{}|]
   316       ==> wp act (\<Union>i\<in>I. A i) = (\<Union>i\<in>I. wp act (A i))"
   317 apply (rule equalityI)
   318  prefer 2 apply (rule wp_UN_subset) 
   319  apply (simp add: wp_def Image_INT_eq) 
   320 done
   321 
   322 lemma wens_single_eq:
   323      "wens (mk_program (init, {act}, allowed)) act B = B \<union> wp act B"
   324 by (simp add: wens_def gfp_def wp_def, blast)
   325 
   326 
   327 text{*Next, we express the @{term "wens_set"} for single-assignment programs*}
   328 
   329 constdefs
   330   wens_single_finite :: "[('a*'a) set, 'a set, nat] => 'a set"  
   331     "wens_single_finite act B k == \<Union>i \<in> atMost k. ((wp act)^i) B"
   332 
   333   wens_single :: "[('a*'a) set, 'a set] => 'a set"  
   334     "wens_single act B == \<Union>i. ((wp act)^i) B"
   335 
   336 lemma wens_single_Un_eq:
   337       "single_valued act
   338        ==> wens_single act B \<union> wp act (wens_single act B) = wens_single act B"
   339 apply (rule equalityI)
   340  apply (simp_all add: Un_upper1 Un_subset_iff) 
   341 apply (simp add: wens_single_def wp_UN_eq, clarify) 
   342 apply (rule_tac a="Suc(i)" in UN_I, auto) 
   343 done
   344 
   345 lemma atMost_nat_nonempty: "atMost (k::nat) \<noteq> {}"
   346 by force
   347 
   348 lemma wens_single_finite_0 [simp]: "wens_single_finite act B 0 = B"
   349 by (simp add: wens_single_finite_def)
   350 
   351 lemma wens_single_finite_Suc:
   352       "single_valued act
   353        ==> wens_single_finite act B (Suc k) =
   354            wens_single_finite act B k \<union> wp act (wens_single_finite act B k)"
   355 apply (simp add: wens_single_finite_def image_def 
   356                  wp_UN_eq [OF _ atMost_nat_nonempty]) 
   357 apply (force elim!: le_SucE)
   358 done
   359 
   360 lemma wens_single_finite_Suc_eq_wens:
   361      "single_valued act
   362        ==> wens_single_finite act B (Suc k) =
   363            wens (mk_program (init, {act}, allowed)) act 
   364                 (wens_single_finite act B k)"
   365 by (simp add: wens_single_finite_Suc wens_single_eq) 
   366 
   367 lemma def_wens_single_finite_Suc_eq_wens:
   368      "[|F = mk_program (init, {act}, allowed); single_valued act|]
   369        ==> wens_single_finite act B (Suc k) =
   370            wens F act (wens_single_finite act B k)"
   371 by (simp add: wens_single_finite_Suc_eq_wens) 
   372 
   373 lemma wens_single_finite_Un_eq:
   374       "single_valued act
   375        ==> wens_single_finite act B k \<union> wp act (wens_single_finite act B k)
   376            \<in> range (wens_single_finite act B)"
   377 by (simp add: wens_single_finite_Suc [symmetric]) 
   378 
   379 lemma wens_single_eq_Union:
   380       "wens_single act B = \<Union>range (wens_single_finite act B)" 
   381 by (simp add: wens_single_finite_def wens_single_def, blast) 
   382 
   383 lemma wens_single_finite_eq_Union:
   384      "wens_single_finite act B n = (\<Union>k\<in>atMost n. wens_single_finite act B k)"
   385 apply (auto simp add: wens_single_finite_def) 
   386 apply (blast intro: le_trans) 
   387 done
   388 
   389 lemma wens_single_finite_mono:
   390      "m \<le> n ==> wens_single_finite act B m \<subseteq> wens_single_finite act B n"
   391 by (force simp add:  wens_single_finite_eq_Union [of act B n]) 
   392 
   393 lemma wens_single_finite_subset_wens_single:
   394       "wens_single_finite act B k \<subseteq> wens_single act B"
   395 by (simp add: wens_single_eq_Union, blast) 
   396 
   397 lemma subset_wens_single_finite:
   398       "[|W \<subseteq> wens_single_finite act B ` (atMost k); single_valued act; W\<noteq>{}|]
   399        ==> \<exists>m. \<Union>W = wens_single_finite act B m"
   400 apply (induct k)
   401  apply (rule_tac x=0 in exI, simp, blast) 
   402 apply (auto simp add: atMost_Suc) 
   403 apply (case_tac "wens_single_finite act B (Suc n) \<in> W") 
   404  prefer 2 apply blast 
   405 apply (drule_tac x="Suc n" in spec)
   406 apply (erule notE, rule equalityI)
   407  prefer 2 apply blast 
   408 apply (subst wens_single_finite_eq_Union) 
   409 apply (simp add: atMost_Suc, blast) 
   410 done
   411 
   412 text{*lemma for Union case*}
   413 lemma Union_eq_wens_single:
   414       "\<lbrakk>\<forall>k. \<not> W \<subseteq> wens_single_finite act B ` {..k};
   415         W \<subseteq> insert (wens_single act B)
   416             (range (wens_single_finite act B))\<rbrakk>
   417        \<Longrightarrow> \<Union>W = wens_single act B"
   418 apply (case_tac "wens_single act B \<in> W")
   419  apply (blast dest: wens_single_finite_subset_wens_single [THEN subsetD]) 
   420 apply (simp add: wens_single_eq_Union) 
   421 apply (rule equalityI, blast) 
   422 apply (simp add: UN_subset_iff, clarify)
   423 apply (subgoal_tac "\<exists>y\<in>W. \<exists>n. y = wens_single_finite act B n & i\<le>n")  
   424  apply (blast intro: wens_single_finite_mono [THEN subsetD]) 
   425 apply (drule_tac x=i in spec)
   426 apply (force simp add: atMost_def)
   427 done
   428 
   429 lemma wens_set_subset_single:
   430       "single_valued act
   431        ==> wens_set (mk_program (init, {act}, allowed)) B \<subseteq> 
   432            insert (wens_single act B) (range (wens_single_finite act B))"
   433 apply (rule subsetI)  
   434 apply (erule wens_set.induct)
   435   txt{*Basis*} 
   436   apply (force simp add: wens_single_finite_def)
   437  txt{*Wens inductive step*}
   438  apply (case_tac "acta = Id", simp)   
   439  apply (simp add: wens_single_eq)
   440  apply (elim disjE)   
   441  apply (simp add: wens_single_Un_eq)
   442  apply (force simp add: wens_single_finite_Un_eq)
   443 txt{*Union inductive step*}
   444 apply (case_tac "\<exists>k. W \<subseteq> wens_single_finite act B ` (atMost k)")
   445  apply (blast dest!: subset_wens_single_finite, simp) 
   446 apply (rule disjI1 [OF Union_eq_wens_single], blast+)
   447 done
   448 
   449 lemma wens_single_finite_in_wens_set:
   450       "single_valued act \<Longrightarrow>
   451          wens_single_finite act B k
   452          \<in> wens_set (mk_program (init, {act}, allowed)) B"
   453 apply (induct_tac k) 
   454  apply (simp add: wens_single_finite_def wens_set.Basis)
   455 apply (simp add: wens_set.Wens
   456                  wens_single_finite_Suc_eq_wens [of act B _ init allowed]) 
   457 done
   458 
   459 lemma single_subset_wens_set:
   460       "single_valued act
   461        ==> insert (wens_single act B) (range (wens_single_finite act B)) \<subseteq> 
   462            wens_set (mk_program (init, {act}, allowed)) B"
   463 apply (simp add: wens_single_eq_Union UN_eq) 
   464 apply (blast intro: wens_set.Union wens_single_finite_in_wens_set)
   465 done
   466 
   467 text{*Theorem (4.29)*}
   468 theorem wens_set_single_eq:
   469      "[|F = mk_program (init, {act}, allowed); single_valued act|]
   470       ==> wens_set F B =
   471           insert (wens_single act B) (range (wens_single_finite act B))"
   472 apply (rule equalityI)
   473  apply (simp add: wens_set_subset_single) 
   474 apply (erule ssubst, erule single_subset_wens_set) 
   475 done
   476 
   477 text{*Generalizing Misra's Fixed Point Union Theorem (4.41)*}
   478 
   479 lemma fp_leadsTo_Join:
   480     "[|T-B \<subseteq> awp F T; T-B \<subseteq> FP G; F \<in> A leadsTo B|] ==> F\<squnion>G \<in> T\<inter>A leadsTo B"
   481 apply (rule leadsTo_Join, assumption, blast)
   482 apply (simp add: FP_def awp_iff_constrains stable_def constrains_def, blast) 
   483 done
   484 
   485 end