structuring duals together
authorhaftmann
Sun Jul 17 20:29:54 2011 +0200 (2011-07-17)
changeset 4387092129f505125
parent 43869 58be172c6ca4
child 43871 79c3231e0593
structuring duals together
src/HOL/Complete_Lattice.thy
     1.1 --- a/src/HOL/Complete_Lattice.thy	Sun Jul 17 20:23:39 2011 +0200
     1.2 +++ b/src/HOL/Complete_Lattice.thy	Sun Jul 17 20:29:54 2011 +0200
     1.3 @@ -224,38 +224,75 @@
     1.4  lemma INF_empty: "(\<Sqinter>x\<in>{}. f x) = \<top>"
     1.5    by (simp add: INFI_def)
     1.6  
     1.7 +lemma SUP_empty: "(\<Squnion>x\<in>{}. f x) = \<bottom>"
     1.8 +  by (simp add: SUPR_def)
     1.9 +
    1.10  lemma INF_insert: "(\<Sqinter>x\<in>insert a A. f x) = f a \<sqinter> INFI A f"
    1.11    by (simp add: INFI_def Inf_insert)
    1.12  
    1.13 +lemma SUP_insert: "(\<Squnion>x\<in>insert a A. f x) = f a \<squnion> SUPR A f"
    1.14 +  by (simp add: SUPR_def Sup_insert)
    1.15 +
    1.16  lemma INF_leI: "i \<in> A \<Longrightarrow> (\<Sqinter>i\<in>A. f i) \<sqsubseteq> f i"
    1.17    by (auto simp add: INFI_def intro: Inf_lower)
    1.18  
    1.19 +lemma le_SUPI: "i \<in> A \<Longrightarrow> f i \<sqsubseteq> (\<Squnion>i\<in>A. f i)"
    1.20 +  by (auto simp add: SUPR_def intro: Sup_upper)
    1.21 +
    1.22  lemma INF_leI2: "i \<in> A \<Longrightarrow> f i \<sqsubseteq> u \<Longrightarrow> (\<Sqinter>i\<in>A. f i) \<sqsubseteq> u"
    1.23    using INF_leI [of i A f] by auto
    1.24  
    1.25 +lemma le_SUPI2: "i \<in> A \<Longrightarrow> u \<sqsubseteq> f i \<Longrightarrow> u \<sqsubseteq> (\<Squnion>i\<in>A. f i)"
    1.26 +  using le_SUPI [of i A f] by auto
    1.27 +
    1.28  lemma le_INFI: "(\<And>i. i \<in> A \<Longrightarrow> u \<sqsubseteq> f i) \<Longrightarrow> u \<sqsubseteq> (\<Sqinter>i\<in>A. f i)"
    1.29    by (auto simp add: INFI_def intro: Inf_greatest)
    1.30  
    1.31 +lemma SUP_leI: "(\<And>i. i \<in> A \<Longrightarrow> f i \<sqsubseteq> u) \<Longrightarrow> (\<Squnion>i\<in>A. f i) \<sqsubseteq> u"
    1.32 +  by (auto simp add: SUPR_def intro: Sup_least)
    1.33 +
    1.34  lemma le_INF_iff: "u \<sqsubseteq> (\<Sqinter>i\<in>A. f i) \<longleftrightarrow> (\<forall>i \<in> A. u \<sqsubseteq> f i)"
    1.35    by (auto simp add: INFI_def le_Inf_iff)
    1.36  
    1.37 +lemma SUP_le_iff: "(\<Squnion>i\<in>A. f i) \<sqsubseteq> u \<longleftrightarrow> (\<forall>i \<in> A. f i \<sqsubseteq> u)"
    1.38 +  by (auto simp add: SUPR_def Sup_le_iff)
    1.39 +
    1.40  lemma INF_const [simp]: "A \<noteq> {} \<Longrightarrow> (\<Sqinter>i\<in>A. f) = f"
    1.41    by (auto intro: antisym INF_leI le_INFI)
    1.42  
    1.43 +lemma SUP_const [simp]: "A \<noteq> {} \<Longrightarrow> (\<Squnion>i\<in>A. f) = f"
    1.44 +  by (auto intro: antisym SUP_leI le_SUPI)
    1.45 +
    1.46  lemma INF_cong:
    1.47    "A = B \<Longrightarrow> (\<And>x. x \<in> B \<Longrightarrow> C x = D x) \<Longrightarrow> (\<Sqinter>x\<in>A. C x) = (\<Sqinter>x\<in>B. D x)"
    1.48    by (simp add: INFI_def image_def)
    1.49  
    1.50 +lemma SUP_cong:
    1.51 +  "A = B \<Longrightarrow> (\<And>x. x \<in> B \<Longrightarrow> C x = D x) \<Longrightarrow> (\<Squnion>x\<in>A. C x) = (\<Squnion>x\<in>B. D x)"
    1.52 +  by (simp add: SUPR_def image_def)
    1.53 +
    1.54  lemma INF_mono:
    1.55    "(\<And>m. m \<in> B \<Longrightarrow> \<exists>n\<in>A. f n \<sqsubseteq> g m) \<Longrightarrow> (\<Sqinter>n\<in>A. f n) \<sqsubseteq> (\<Sqinter>n\<in>B. g n)"
    1.56    by (force intro!: Inf_mono simp: INFI_def)
    1.57  
    1.58 -lemma INF_subset:  "A \<subseteq> B \<Longrightarrow> INFI B f \<sqsubseteq> INFI A f"
    1.59 +lemma SUP_mono:
    1.60 +  "(\<And>n. n \<in> A \<Longrightarrow> \<exists>m\<in>B. f n \<sqsubseteq> g m) \<Longrightarrow> (\<Squnion>n\<in>A. f n) \<sqsubseteq> (\<Squnion>n\<in>B. g n)"
    1.61 +  by (force intro!: Sup_mono simp: SUPR_def)
    1.62 +
    1.63 +lemma INF_subset:
    1.64 +  "A \<subseteq> B \<Longrightarrow> INFI B f \<sqsubseteq> INFI A f"
    1.65    by (intro INF_mono) auto
    1.66  
    1.67 +lemma SUP_subset:
    1.68 +  "A \<subseteq> B \<Longrightarrow> SUPR A f \<sqsubseteq> SUPR B f"
    1.69 +  by (intro SUP_mono) auto
    1.70 +
    1.71  lemma INF_commute: "(\<Sqinter>i\<in>A. \<Sqinter>j\<in>B. f i j) = (\<Sqinter>j\<in>B. \<Sqinter>i\<in>A. f i j)"
    1.72    by (iprover intro: INF_leI le_INFI order_trans antisym)
    1.73  
    1.74 +lemma SUP_commute: "(\<Squnion>i\<in>A. \<Squnion>j\<in>B. f i j) = (\<Squnion>j\<in>B. \<Squnion>i\<in>A. f i j)"
    1.75 +  by (iprover intro: SUP_leI le_SUPI order_trans antisym)
    1.76 +
    1.77  lemma (in complete_lattice) INFI_empty:
    1.78    "(\<Sqinter>x\<in>{}. B x) = \<top>"
    1.79    by (simp add: INFI_def)
    1.80 @@ -298,41 +335,6 @@
    1.81    -- {* The last inclusion is POSITIVE! *}
    1.82    by (blast intro: INF_mono dest: subsetD)
    1.83  
    1.84 -lemma SUP_cong:
    1.85 -  "A = B \<Longrightarrow> (\<And>x. x \<in> B \<Longrightarrow> C x = D x) \<Longrightarrow> (\<Squnion>x\<in>A. C x) = (\<Squnion>x\<in>B. D x)"
    1.86 -  by (simp add: SUPR_def image_def)
    1.87 -
    1.88 -lemma le_SUPI: "i \<in> A \<Longrightarrow> f i \<sqsubseteq> (\<Squnion>i\<in>A. f i)"
    1.89 -  by (auto simp add: SUPR_def intro: Sup_upper)
    1.90 -
    1.91 -lemma le_SUPI2: "i \<in> A \<Longrightarrow> u \<sqsubseteq> f i \<Longrightarrow> u \<sqsubseteq> (\<Squnion>i\<in>A. f i)"
    1.92 -  using le_SUPI [of i A f] by auto
    1.93 -
    1.94 -lemma SUP_leI: "(\<And>i. i \<in> A \<Longrightarrow> f i \<sqsubseteq> u) \<Longrightarrow> (\<Squnion>i\<in>A. f i) \<sqsubseteq> u"
    1.95 -  by (auto simp add: SUPR_def intro: Sup_least)
    1.96 -
    1.97 -lemma SUP_le_iff: "(\<Squnion>i\<in>A. f i) \<sqsubseteq> u \<longleftrightarrow> (\<forall>i \<in> A. f i \<sqsubseteq> u)"
    1.98 -  unfolding SUPR_def by (auto simp add: Sup_le_iff)
    1.99 -
   1.100 -lemma SUP_const [simp]: "A \<noteq> {} \<Longrightarrow> (\<Squnion>i\<in>A. f) = f"
   1.101 -  by (auto intro: antisym SUP_leI le_SUPI)
   1.102 -
   1.103 -lemma SUP_mono:
   1.104 -  "(\<And>n. n \<in> A \<Longrightarrow> \<exists>m\<in>B. f n \<sqsubseteq> g m) \<Longrightarrow> (\<Squnion>n\<in>A. f n) \<sqsubseteq> (\<Squnion>n\<in>B. g n)"
   1.105 -  by (force intro!: Sup_mono simp: SUPR_def)
   1.106 -
   1.107 -lemma SUP_subset:  "A \<subseteq> B \<Longrightarrow> SUPR A f \<sqsubseteq> SUPR B f"
   1.108 -  by (intro SUP_mono) auto
   1.109 -
   1.110 -lemma SUP_commute: "(\<Squnion>i\<in>A. \<Squnion>j\<in>B. f i j) = (\<Squnion>j\<in>B. \<Squnion>i\<in>A. f i j)"
   1.111 -  by (iprover intro: SUP_leI le_SUPI order_trans antisym)
   1.112 -
   1.113 -lemma SUP_empty: "(\<Squnion>x\<in>{}. f x) = \<bottom>"
   1.114 -  by (simp add: SUPR_def)
   1.115 -
   1.116 -lemma SUP_insert: "(\<Squnion>x\<in>insert a A. f x) = f a \<squnion> SUPR A f"
   1.117 -  by (simp add: SUPR_def Sup_insert)
   1.118 -
   1.119  end
   1.120  
   1.121  lemma Inf_less_iff: