--- a/src/HOL/HOLCF/Porder.thy Mon Jan 01 21:17:28 2018 +0100
+++ b/src/HOL/HOLCF/Porder.thy Mon Jan 01 23:07:24 2018 +0100
@@ -5,7 +5,7 @@
section \<open>Partial orders\<close>
theory Porder
-imports Main
+ imports Main
begin
declare [[typedef_overloaded]]
@@ -23,17 +23,16 @@
notation
below (infix "\<sqsubseteq>" 50)
-abbreviation
- not_below :: "'a \<Rightarrow> 'a \<Rightarrow> bool" (infix "\<notsqsubseteq>" 50)
+abbreviation not_below :: "'a \<Rightarrow> 'a \<Rightarrow> bool" (infix "\<notsqsubseteq>" 50)
where "not_below x y \<equiv> \<not> below x y"
notation (ASCII)
not_below (infix "~<<" 50)
-lemma below_eq_trans: "\<lbrakk>a \<sqsubseteq> b; b = c\<rbrakk> \<Longrightarrow> a \<sqsubseteq> c"
+lemma below_eq_trans: "a \<sqsubseteq> b \<Longrightarrow> b = c \<Longrightarrow> a \<sqsubseteq> c"
by (rule subst)
-lemma eq_below_trans: "\<lbrakk>a = b; b \<sqsubseteq> c\<rbrakk> \<Longrightarrow> a \<sqsubseteq> c"
+lemma eq_below_trans: "a = b \<Longrightarrow> b \<sqsubseteq> c \<Longrightarrow> a \<sqsubseteq> c"
by (rule ssubst)
end
@@ -72,8 +71,8 @@
subsection \<open>Upper bounds\<close>
-definition is_ub :: "'a set \<Rightarrow> 'a \<Rightarrow> bool" (infix "<|" 55) where
- "S <| x \<longleftrightarrow> (\<forall>y\<in>S. y \<sqsubseteq> x)"
+definition is_ub :: "'a set \<Rightarrow> 'a \<Rightarrow> bool" (infix "<|" 55)
+ where "S <| x \<longleftrightarrow> (\<forall>y\<in>S. y \<sqsubseteq> x)"
lemma is_ubI: "(\<And>x. x \<in> S \<Longrightarrow> x \<sqsubseteq> u) \<Longrightarrow> S <| u"
by (simp add: is_ub_def)
@@ -102,13 +101,14 @@
lemma is_ub_upward: "\<lbrakk>S <| x; x \<sqsubseteq> y\<rbrakk> \<Longrightarrow> S <| y"
unfolding is_ub_def by (fast intro: below_trans)
+
subsection \<open>Least upper bounds\<close>
-definition is_lub :: "'a set \<Rightarrow> 'a \<Rightarrow> bool" (infix "<<|" 55) where
- "S <<| x \<longleftrightarrow> S <| x \<and> (\<forall>u. S <| u \<longrightarrow> x \<sqsubseteq> u)"
+definition is_lub :: "'a set \<Rightarrow> 'a \<Rightarrow> bool" (infix "<<|" 55)
+ where "S <<| x \<longleftrightarrow> S <| x \<and> (\<forall>u. S <| u \<longrightarrow> x \<sqsubseteq> u)"
-definition lub :: "'a set \<Rightarrow> 'a" where
- "lub S = (THE x. S <<| x)"
+definition lub :: "'a set \<Rightarrow> 'a"
+ where "lub S = (THE x. S <<| x)"
end
@@ -119,14 +119,13 @@
"_BLub" :: "[pttrn, 'a set, 'b] \<Rightarrow> 'b" ("(3\<Squnion>_\<in>_./ _)" [0,0, 10] 10)
translations
- "LUB x:A. t" == "CONST lub ((%x. t) ` A)"
+ "LUB x:A. t" \<rightleftharpoons> "CONST lub ((\<lambda>x. t) ` A)"
context po
begin
-abbreviation
- Lub (binder "\<Squnion>" 10) where
- "\<Squnion>n. t n == lub (range t)"
+abbreviation Lub (binder "\<Squnion>" 10)
+ where "\<Squnion>n. t n \<equiv> lub (range t)"
notation (ASCII)
Lub (binder "LUB " 10)
@@ -147,7 +146,7 @@
text \<open>lubs are unique\<close>
-lemma is_lub_unique: "\<lbrakk>S <<| x; S <<| y\<rbrakk> \<Longrightarrow> x = y"
+lemma is_lub_unique: "S <<| x \<Longrightarrow> S <<| y \<Longrightarrow> x = y"
unfolding is_lub_def is_ub_def by (blast intro: below_antisym)
text \<open>technical lemmas about @{term lub} and @{term is_lub}\<close>
@@ -170,16 +169,17 @@
lemma lub_bin: "x \<sqsubseteq> y \<Longrightarrow> lub {x, y} = y"
by (rule is_lub_bin [THEN lub_eqI])
-lemma is_lub_maximal: "\<lbrakk>S <| x; x \<in> S\<rbrakk> \<Longrightarrow> S <<| x"
+lemma is_lub_maximal: "S <| x \<Longrightarrow> x \<in> S \<Longrightarrow> S <<| x"
by (erule is_lubI, erule (1) is_ubD)
-lemma lub_maximal: "\<lbrakk>S <| x; x \<in> S\<rbrakk> \<Longrightarrow> lub S = x"
+lemma lub_maximal: "S <| x \<Longrightarrow> x \<in> S \<Longrightarrow> lub S = x"
by (rule is_lub_maximal [THEN lub_eqI])
+
subsection \<open>Countable chains\<close>
-definition chain :: "(nat \<Rightarrow> 'a) \<Rightarrow> bool" where
- \<comment> \<open>Here we use countable chains and I prefer to code them as functions!\<close>
+definition chain :: "(nat \<Rightarrow> 'a) \<Rightarrow> bool"
+ where \<comment> \<open>Here we use countable chains and I prefer to code them as functions!\<close>
"chain Y = (\<forall>i. Y i \<sqsubseteq> Y (Suc i))"
lemma chainI: "(\<And>i. Y i \<sqsubseteq> Y (Suc i)) \<Longrightarrow> chain Y"
@@ -190,11 +190,11 @@
text \<open>chains are monotone functions\<close>
-lemma chain_mono_less: "\<lbrakk>chain Y; i < j\<rbrakk> \<Longrightarrow> Y i \<sqsubseteq> Y j"
+lemma chain_mono_less: "chain Y \<Longrightarrow> i < j \<Longrightarrow> Y i \<sqsubseteq> Y j"
by (erule less_Suc_induct, erule chainE, erule below_trans)
-lemma chain_mono: "\<lbrakk>chain Y; i \<le> j\<rbrakk> \<Longrightarrow> Y i \<sqsubseteq> Y j"
- by (cases "i = j", simp, simp add: chain_mono_less)
+lemma chain_mono: "chain Y \<Longrightarrow> i \<le> j \<Longrightarrow> Y i \<sqsubseteq> Y j"
+ by (cases "i = j") (simp_all add: chain_mono_less)
lemma chain_shift: "chain Y \<Longrightarrow> chain (\<lambda>i. Y (i + j))"
by (rule chainI, simp, erule chainE)
@@ -204,20 +204,18 @@
lemma is_lub_rangeD1: "range S <<| x \<Longrightarrow> S i \<sqsubseteq> x"
by (rule is_lubD1 [THEN ub_rangeD])
-lemma is_ub_range_shift:
- "chain S \<Longrightarrow> range (\<lambda>i. S (i + j)) <| x = range S <| x"
-apply (rule iffI)
-apply (rule ub_rangeI)
-apply (rule_tac y="S (i + j)" in below_trans)
-apply (erule chain_mono)
-apply (rule le_add1)
-apply (erule ub_rangeD)
-apply (rule ub_rangeI)
-apply (erule ub_rangeD)
-done
+lemma is_ub_range_shift: "chain S \<Longrightarrow> range (\<lambda>i. S (i + j)) <| x = range S <| x"
+ apply (rule iffI)
+ apply (rule ub_rangeI)
+ apply (rule_tac y="S (i + j)" in below_trans)
+ apply (erule chain_mono)
+ apply (rule le_add1)
+ apply (erule ub_rangeD)
+ apply (rule ub_rangeI)
+ apply (erule ub_rangeD)
+ done
-lemma is_lub_range_shift:
- "chain S \<Longrightarrow> range (\<lambda>i. S (i + j)) <<| x = range S <<| x"
+lemma is_lub_range_shift: "chain S \<Longrightarrow> range (\<lambda>i. S (i + j)) <<| x = range S <<| x"
by (simp add: is_lub_def is_ub_range_shift)
text \<open>the lub of a constant chain is the constant\<close>
@@ -231,61 +229,60 @@
lemma lub_const [simp]: "(\<Squnion>i. c) = c"
by (rule is_lub_const [THEN lub_eqI])
+
subsection \<open>Finite chains\<close>
-definition max_in_chain :: "nat \<Rightarrow> (nat \<Rightarrow> 'a) \<Rightarrow> bool" where
- \<comment> \<open>finite chains, needed for monotony of continuous functions\<close>
+definition max_in_chain :: "nat \<Rightarrow> (nat \<Rightarrow> 'a) \<Rightarrow> bool"
+ where \<comment> \<open>finite chains, needed for monotony of continuous functions\<close>
"max_in_chain i C \<longleftrightarrow> (\<forall>j. i \<le> j \<longrightarrow> C i = C j)"
-definition finite_chain :: "(nat \<Rightarrow> 'a) \<Rightarrow> bool" where
- "finite_chain C = (chain C \<and> (\<exists>i. max_in_chain i C))"
+definition finite_chain :: "(nat \<Rightarrow> 'a) \<Rightarrow> bool"
+ where "finite_chain C = (chain C \<and> (\<exists>i. max_in_chain i C))"
text \<open>results about finite chains\<close>
lemma max_in_chainI: "(\<And>j. i \<le> j \<Longrightarrow> Y i = Y j) \<Longrightarrow> max_in_chain i Y"
unfolding max_in_chain_def by fast
-lemma max_in_chainD: "\<lbrakk>max_in_chain i Y; i \<le> j\<rbrakk> \<Longrightarrow> Y i = Y j"
+lemma max_in_chainD: "max_in_chain i Y \<Longrightarrow> i \<le> j \<Longrightarrow> Y i = Y j"
unfolding max_in_chain_def by fast
-lemma finite_chainI:
- "\<lbrakk>chain C; max_in_chain i C\<rbrakk> \<Longrightarrow> finite_chain C"
+lemma finite_chainI: "chain C \<Longrightarrow> max_in_chain i C \<Longrightarrow> finite_chain C"
unfolding finite_chain_def by fast
-lemma finite_chainE:
- "\<lbrakk>finite_chain C; \<And>i. \<lbrakk>chain C; max_in_chain i C\<rbrakk> \<Longrightarrow> R\<rbrakk> \<Longrightarrow> R"
+lemma finite_chainE: "\<lbrakk>finite_chain C; \<And>i. \<lbrakk>chain C; max_in_chain i C\<rbrakk> \<Longrightarrow> R\<rbrakk> \<Longrightarrow> R"
unfolding finite_chain_def by fast
-lemma lub_finch1: "\<lbrakk>chain C; max_in_chain i C\<rbrakk> \<Longrightarrow> range C <<| C i"
-apply (rule is_lubI)
-apply (rule ub_rangeI, rename_tac j)
-apply (rule_tac x=i and y=j in linorder_le_cases)
-apply (drule (1) max_in_chainD, simp)
-apply (erule (1) chain_mono)
-apply (erule ub_rangeD)
-done
+lemma lub_finch1: "chain C \<Longrightarrow> max_in_chain i C \<Longrightarrow> range C <<| C i"
+ apply (rule is_lubI)
+ apply (rule ub_rangeI, rename_tac j)
+ apply (rule_tac x=i and y=j in linorder_le_cases)
+ apply (drule (1) max_in_chainD, simp)
+ apply (erule (1) chain_mono)
+ apply (erule ub_rangeD)
+ done
-lemma lub_finch2:
- "finite_chain C \<Longrightarrow> range C <<| C (LEAST i. max_in_chain i C)"
-apply (erule finite_chainE)
-apply (erule LeastI2 [where Q="\<lambda>i. range C <<| C i"])
-apply (erule (1) lub_finch1)
-done
+lemma lub_finch2: "finite_chain C \<Longrightarrow> range C <<| C (LEAST i. max_in_chain i C)"
+ apply (erule finite_chainE)
+ apply (erule LeastI2 [where Q="\<lambda>i. range C <<| C i"])
+ apply (erule (1) lub_finch1)
+ done
lemma finch_imp_finite_range: "finite_chain Y \<Longrightarrow> finite (range Y)"
- apply (erule finite_chainE)
- apply (rule_tac B="Y ` {..i}" in finite_subset)
- apply (rule subsetI)
- apply (erule rangeE, rename_tac j)
- apply (rule_tac x=i and y=j in linorder_le_cases)
- apply (subgoal_tac "Y j = Y i", simp)
- apply (simp add: max_in_chain_def)
+ apply (erule finite_chainE)
+ apply (rule_tac B="Y ` {..i}" in finite_subset)
+ apply (rule subsetI)
+ apply (erule rangeE, rename_tac j)
+ apply (rule_tac x=i and y=j in linorder_le_cases)
+ apply (subgoal_tac "Y j = Y i", simp)
+ apply (simp add: max_in_chain_def)
+ apply simp
apply simp
- apply simp
-done
+ done
lemma finite_range_has_max:
- fixes f :: "nat \<Rightarrow> 'a" and r :: "'a \<Rightarrow> 'a \<Rightarrow> bool"
+ fixes f :: "nat \<Rightarrow> 'a"
+ and r :: "'a \<Rightarrow> 'a \<Rightarrow> bool"
assumes mono: "\<And>i j. i \<le> j \<Longrightarrow> r (f i) (f j)"
assumes finite_range: "finite (range f)"
shows "\<exists>k. \<forall>i. r (f i) (f k)"
@@ -307,38 +304,35 @@
finally show "r (f i) (f ?k)" .
qed
-lemma finite_range_imp_finch:
- "\<lbrakk>chain Y; finite (range Y)\<rbrakk> \<Longrightarrow> finite_chain Y"
- apply (subgoal_tac "\<exists>k. \<forall>i. Y i \<sqsubseteq> Y k")
- apply (erule exE)
- apply (rule finite_chainI, assumption)
- apply (rule max_in_chainI)
- apply (rule below_antisym)
+lemma finite_range_imp_finch: "chain Y \<Longrightarrow> finite (range Y) \<Longrightarrow> finite_chain Y"
+ apply (subgoal_tac "\<exists>k. \<forall>i. Y i \<sqsubseteq> Y k")
+ apply (erule exE)
+ apply (rule finite_chainI, assumption)
+ apply (rule max_in_chainI)
+ apply (rule below_antisym)
+ apply (erule (1) chain_mono)
+ apply (erule spec)
+ apply (rule finite_range_has_max)
apply (erule (1) chain_mono)
- apply (erule spec)
- apply (rule finite_range_has_max)
- apply (erule (1) chain_mono)
- apply assumption
-done
+ apply assumption
+ done
lemma bin_chain: "x \<sqsubseteq> y \<Longrightarrow> chain (\<lambda>i. if i=0 then x else y)"
- by (rule chainI, simp)
+ by (rule chainI) simp
-lemma bin_chainmax:
- "x \<sqsubseteq> y \<Longrightarrow> max_in_chain (Suc 0) (\<lambda>i. if i=0 then x else y)"
- unfolding max_in_chain_def by simp
+lemma bin_chainmax: "x \<sqsubseteq> y \<Longrightarrow> max_in_chain (Suc 0) (\<lambda>i. if i=0 then x else y)"
+ by (simp add: max_in_chain_def)
-lemma is_lub_bin_chain:
- "x \<sqsubseteq> y \<Longrightarrow> range (\<lambda>i::nat. if i=0 then x else y) <<| y"
-apply (frule bin_chain)
-apply (drule bin_chainmax)
-apply (drule (1) lub_finch1)
-apply simp
-done
+lemma is_lub_bin_chain: "x \<sqsubseteq> y \<Longrightarrow> range (\<lambda>i::nat. if i=0 then x else y) <<| y"
+ apply (frule bin_chain)
+ apply (drule bin_chainmax)
+ apply (drule (1) lub_finch1)
+ apply simp
+ done
text \<open>the maximal element in a chain is its lub\<close>
-lemma lub_chain_maxelem: "\<lbrakk>Y i = c; \<forall>i. Y i \<sqsubseteq> c\<rbrakk> \<Longrightarrow> lub (range Y) = c"
+lemma lub_chain_maxelem: "Y i = c \<Longrightarrow> \<forall>i. Y i \<sqsubseteq> c \<Longrightarrow> lub (range Y) = c"
by (blast dest: ub_rangeD intro: lub_eqI is_lubI ub_rangeI)
end