115 named after David Park, is weaker but sufficient for this proof: |
115 named after David Park, is weaker but sufficient for this proof: |
116 \begin{center} |
116 \begin{center} |
117 @{thm lfp_lowerbound[of _ "S",no_vars]} \hfill (@{thm[source]lfp_lowerbound}) |
117 @{thm lfp_lowerbound[of _ "S",no_vars]} \hfill (@{thm[source]lfp_lowerbound}) |
118 \end{center} |
118 \end{center} |
119 The instance of the premise @{prop"f S \<subseteq> S"} is proved pointwise, |
119 The instance of the premise @{prop"f S \<subseteq> S"} is proved pointwise, |
120 a decision that clarification takes for us: |
120 a decision that \isa{auto} takes for us: |
121 *}; |
121 *}; |
122 apply(rule lfp_lowerbound); |
122 apply(rule lfp_lowerbound); |
123 apply(clarsimp simp add: af_def Paths_def); |
123 apply(auto simp add: af_def Paths_def); |
124 |
124 |
125 txt{* |
125 txt{* |
126 @{subgoals[display,indent=0,margin=70,goals_limit=1]} |
126 @{subgoals[display,indent=0,margin=70,goals_limit=1]} |
127 Now we eliminate the disjunction. The case @{prop"p(0::nat) \<in> A"} is trivial: |
127 In this remaining case, we set @{term t} to @{term"p(1::nat)"}. |
128 *}; |
128 The rest is automatic. |
129 |
|
130 apply(erule disjE); |
|
131 apply(blast); |
|
132 |
|
133 txt{*\noindent |
|
134 In the other case we set @{term t} to @{term"p(1::nat)"} and simplify matters: |
|
135 *}; |
129 *}; |
136 |
130 |
137 apply(erule_tac x = "p 1" in allE); |
131 apply(erule_tac x = "p 1" in allE); |
138 apply(clarsimp); |
132 apply(auto); |
139 |
|
140 txt{* |
|
141 @{subgoals[display,indent=0,margin=70,goals_limit=1]} |
|
142 It merely remains to set @{term pa} to @{term"\<lambda>i. p(i+1::nat)"}, that is, |
|
143 @{term p} without its first element. The rest is automatic: |
|
144 *}; |
|
145 |
|
146 apply(erule_tac x = "\<lambda>i. p(i+1)" in allE); |
|
147 apply force; |
|
148 done; |
133 done; |
149 |
134 |
150 |
135 |
151 text{* |
136 text{* |
152 The opposite inclusion is proved by contradiction: if some state |
137 The opposite inclusion is proved by contradiction: if some state |
387 eufix :: "state set \<Rightarrow> state set \<Rightarrow> state set \<Rightarrow> state set" |
372 eufix :: "state set \<Rightarrow> state set \<Rightarrow> state set \<Rightarrow> state set" |
388 "eufix A B T \<equiv> B \<union> A \<inter> (M\<inverse> `` T)" |
373 "eufix A B T \<equiv> B \<union> A \<inter> (M\<inverse> `` T)" |
389 |
374 |
390 lemma "lfp(eufix A B) \<subseteq> eusem A B" |
375 lemma "lfp(eufix A B) \<subseteq> eusem A B" |
391 apply(rule lfp_lowerbound) |
376 apply(rule lfp_lowerbound) |
392 apply(clarsimp simp add: eusem_def eufix_def); |
377 apply(auto simp add: eusem_def eufix_def); |
393 apply(erule disjE); |
|
394 apply(rule_tac x = "[]" in exI); |
378 apply(rule_tac x = "[]" in exI); |
395 apply simp |
379 apply simp |
396 apply(clarsimp); |
|
397 apply(rule_tac x = "y#xc" in exI); |
380 apply(rule_tac x = "y#xc" in exI); |
398 apply simp; |
381 apply simp; |
399 done |
382 done |
400 |
383 |
401 lemma mono_eufix: "mono(eufix A B)"; |
384 lemma mono_eufix: "mono(eufix A B)"; |