class complete_linorder
authorhaftmann
Wed Jul 20 22:14:39 2011 +0200 (2011-07-20)
changeset 4394026ca0bad226a
parent 43935 aa04d1e1e2cc
child 43941 481566bc20e4
class complete_linorder
NEWS
src/HOL/Complete_Lattice.thy
     1.1 --- a/NEWS	Wed Jul 20 16:15:33 2011 +0200
     1.2 +++ b/NEWS	Wed Jul 20 22:14:39 2011 +0200
     1.3 @@ -63,15 +63,16 @@
     1.4  * Classes bot and top require underlying partial order rather than preorder:
     1.5  uniqueness of bot and top is guaranteed.  INCOMPATIBILITY.
     1.6  
     1.7 -* Class 'complete_lattice': generalized a couple of lemmas from sets;
     1.8 -generalized theorems INF_cong and SUP_cong.  More consistent and less
     1.9 -misunderstandable names:
    1.10 +* Class complete_lattice: generalized a couple of lemmas from sets;
    1.11 +generalized theorems INF_cong and SUP_cong.  New type classes for complete
    1.12 +boolean algebras and complete linear orderes.  Lemmas Inf_less_iff,
    1.13 +less_Sup_iff, INF_less_iff, less_SUP_iff now reside in class complete_linorder.
    1.14 +More consistent and less misunderstandable names:
    1.15    INFI_def ~> INF_def
    1.16    SUPR_def ~> SUP_def
    1.17    le_SUPI ~> le_SUP_I
    1.18    le_SUPI2 ~> le_SUP_I2
    1.19    le_INFI ~> le_INF_I
    1.20 -  INF_subset ~> INF_superset_mono
    1.21    INFI_bool_eq ~> INF_bool_eq
    1.22    SUPR_bool_eq ~> SUP_bool_eq
    1.23    INFI_apply ~> INF_apply
     2.1 --- a/src/HOL/Complete_Lattice.thy	Wed Jul 20 16:15:33 2011 +0200
     2.2 +++ b/src/HOL/Complete_Lattice.thy	Wed Jul 20 22:14:39 2011 +0200
     2.3 @@ -292,12 +292,13 @@
     2.4    by (force intro!: Sup_mono simp: SUP_def)
     2.5  
     2.6  lemma INF_superset_mono:
     2.7 -  "B \<subseteq> A \<Longrightarrow> INFI A f \<sqsubseteq> INFI B f"
     2.8 -  by (rule INF_mono) auto
     2.9 +  "B \<subseteq> A \<Longrightarrow> (\<And>x. x \<in> B \<Longrightarrow> f x \<sqsubseteq> g x) \<Longrightarrow> (\<Sqinter>x\<in>A. f x) \<sqsubseteq> (\<Sqinter>x\<in>B. g x)"
    2.10 +  -- {* The last inclusion is POSITIVE! *}
    2.11 +  by (blast intro: INF_mono dest: subsetD)
    2.12  
    2.13  lemma SUP_subset_mono:
    2.14 -  "A \<subseteq> B \<Longrightarrow> SUPR A f \<sqsubseteq> SUPR B f"
    2.15 -  by (rule SUP_mono) auto
    2.16 +  "A \<subseteq> B \<Longrightarrow> (\<And>x. x \<in> A \<Longrightarrow> f x \<sqsubseteq> g x) \<Longrightarrow> (\<Squnion>x\<in>A. f x) \<sqsubseteq> (\<Squnion>x\<in>B. g x)"
    2.17 +  by (blast intro: SUP_mono dest: subsetD)
    2.18  
    2.19  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)"
    2.20    by (iprover intro: INF_leI le_INF_I order_trans antisym)
    2.21 @@ -371,38 +372,8 @@
    2.22    "(\<Squnion>b. A b) = A True \<squnion> A False"
    2.23    by (simp add: UNIV_bool SUP_empty SUP_insert sup_commute)
    2.24  
    2.25 -lemma INF_mono':
    2.26 -  "B \<subseteq> A \<Longrightarrow> (\<And>x. x \<in> B \<Longrightarrow> f x \<sqsubseteq> g x) \<Longrightarrow> (\<Sqinter>x\<in>A. f x) \<sqsubseteq> (\<Sqinter>x\<in>B. g x)"
    2.27 -  -- {* The last inclusion is POSITIVE! *}
    2.28 -  by (rule INF_mono) auto
    2.29 -
    2.30 -lemma SUP_mono':
    2.31 -  "A \<subseteq> B \<Longrightarrow> (\<And>x. x \<in> A \<Longrightarrow> f x \<sqsubseteq> g x) \<Longrightarrow> (\<Squnion>x\<in>A. f x) \<sqsubseteq> (\<Squnion>x\<in>B. g x)"
    2.32 -  -- {* The last inclusion is POSITIVE! *}
    2.33 -  by (blast intro: SUP_mono dest: subsetD)
    2.34 -
    2.35  end
    2.36  
    2.37 -lemma Inf_less_iff:
    2.38 -  fixes a :: "'a\<Colon>{complete_lattice,linorder}"
    2.39 -  shows "\<Sqinter>S \<sqsubset> a \<longleftrightarrow> (\<exists>x\<in>S. x \<sqsubset> a)"
    2.40 -  unfolding not_le [symmetric] le_Inf_iff by auto
    2.41 -
    2.42 -lemma less_Sup_iff:
    2.43 -  fixes a :: "'a\<Colon>{complete_lattice,linorder}"
    2.44 -  shows "a \<sqsubset> \<Squnion>S \<longleftrightarrow> (\<exists>x\<in>S. a \<sqsubset> x)"
    2.45 -  unfolding not_le [symmetric] Sup_le_iff by auto
    2.46 -
    2.47 -lemma INF_less_iff:
    2.48 -  fixes a :: "'a::{complete_lattice,linorder}"
    2.49 -  shows "(\<Sqinter>i\<in>A. f i) \<sqsubset> a \<longleftrightarrow> (\<exists>x\<in>A. f x \<sqsubset> a)"
    2.50 -  unfolding INF_def Inf_less_iff by auto
    2.51 -
    2.52 -lemma less_SUP_iff:
    2.53 -  fixes a :: "'a::{complete_lattice,linorder}"
    2.54 -  shows "a \<sqsubset> (\<Squnion>i\<in>A. f i) \<longleftrightarrow> (\<exists>x\<in>A. a \<sqsubset> f x)"
    2.55 -  unfolding SUP_def less_Sup_iff by auto
    2.56 -
    2.57  class complete_boolean_algebra = boolean_algebra + complete_lattice
    2.58  begin
    2.59  
    2.60 @@ -430,6 +401,27 @@
    2.61  
    2.62  end
    2.63  
    2.64 +class complete_linorder = linorder + complete_lattice
    2.65 +begin
    2.66 +
    2.67 +lemma Inf_less_iff:
    2.68 +  "\<Sqinter>S \<sqsubset> a \<longleftrightarrow> (\<exists>x\<in>S. x \<sqsubset> a)"
    2.69 +  unfolding not_le [symmetric] le_Inf_iff by auto
    2.70 +
    2.71 +lemma less_Sup_iff:
    2.72 +  "a \<sqsubset> \<Squnion>S \<longleftrightarrow> (\<exists>x\<in>S. a \<sqsubset> x)"
    2.73 +  unfolding not_le [symmetric] Sup_le_iff by auto
    2.74 +
    2.75 +lemma INF_less_iff:
    2.76 +  "(\<Sqinter>i\<in>A. f i) \<sqsubset> a \<longleftrightarrow> (\<exists>x\<in>A. f x \<sqsubset> a)"
    2.77 +  unfolding INF_def Inf_less_iff by auto
    2.78 +
    2.79 +lemma less_SUP_iff:
    2.80 +  "a \<sqsubset> (\<Squnion>i\<in>A. f i) \<longleftrightarrow> (\<exists>x\<in>A. a \<sqsubset> f x)"
    2.81 +  unfolding SUP_def less_Sup_iff by auto
    2.82 +
    2.83 +end
    2.84 +
    2.85  
    2.86  subsection {* @{typ bool} and @{typ "_ \<Rightarrow> _"} as complete lattice *}
    2.87  
    2.88 @@ -688,7 +680,7 @@
    2.89  lemma INT_anti_mono:
    2.90    "A \<subseteq> B \<Longrightarrow> (\<And>x. x \<in> A \<Longrightarrow> f x \<subseteq> g x) \<Longrightarrow> (\<Inter>x\<in>B. f x) \<subseteq> (\<Inter>x\<in>A. g x)"
    2.91    -- {* The last inclusion is POSITIVE! *}
    2.92 -  by (fact INF_mono')
    2.93 +  by (fact INF_superset_mono)
    2.94  
    2.95  lemma Pow_INT_eq: "Pow (\<Inter>x\<in>A. B x) = (\<Inter>x\<in>A. Pow (B x))"
    2.96    by blast
    2.97 @@ -922,7 +914,7 @@
    2.98  lemma UN_mono:
    2.99    "A \<subseteq> B \<Longrightarrow> (\<And>x. x \<in> A \<Longrightarrow> f x \<subseteq> g x) \<Longrightarrow>
   2.100      (\<Union>x\<in>A. f x) \<subseteq> (\<Union>x\<in>B. g x)"
   2.101 -  by (fact SUP_mono')
   2.102 +  by (fact SUP_subset_mono)
   2.103  
   2.104  lemma vimage_Union: "f -` (\<Union>A) = (\<Union>X\<in>A. f -` X)"
   2.105    by blast
   2.106 @@ -1083,7 +1075,11 @@
   2.107  lemmas (in complete_lattice) le_SUPI = le_SUP_I
   2.108  lemmas (in complete_lattice) le_SUPI2 = le_SUP_I2
   2.109  lemmas (in complete_lattice) le_INFI = le_INF_I
   2.110 -lemmas (in complete_lattice) INF_subset = INF_superset_mono 
   2.111 +
   2.112 +lemma (in complete_lattice) INF_subset:
   2.113 +  "B \<subseteq> A \<Longrightarrow> INFI A f \<sqsubseteq> INFI B f"
   2.114 +  by (rule INF_superset_mono) auto
   2.115 +
   2.116  lemmas INFI_apply = INF_apply
   2.117  lemmas SUPR_apply = SUP_apply
   2.118