src/HOL/Library/Glbs.thy
author chaieb
Mon Feb 09 16:19:46 2009 +0000 (2009-02-09)
changeset 29838 a562ca0c408d
child 30267 171b3bd93c90
permissions -rw-r--r--
A theory of greatest lower bounds
     1 (* Title:      Glbs
     2    ID:         $Id: 
     3    Author:     Amine Chaieb, University of Cambridge
     4 *)
     5 
     6 header{*Definitions of Lower Bounds and Greatest Lower Bounds, analogous to Lubs*}
     7 
     8 theory Glbs
     9 imports Lubs
    10 begin
    11 
    12 definition
    13   greatestP      :: "['a =>bool,'a::ord] => bool" where
    14   "greatestP P x = (P x & Collect P *<=  x)"
    15 
    16 definition
    17   isLb        :: "['a set, 'a set, 'a::ord] => bool" where
    18   "isLb R S x = (x <=* S & x: R)"
    19 
    20 definition
    21   isGlb       :: "['a set, 'a set, 'a::ord] => bool" where
    22   "isGlb R S x = greatestP (isLb R S) x"
    23 
    24 definition
    25   lbs         :: "['a set, 'a::ord set] => 'a set" where
    26   "lbs R S = Collect (isLb R S)"
    27 
    28 subsection{*Rules about the Operators @{term greatestP}, @{term isLb}
    29     and @{term isGlb}*}
    30 
    31 lemma leastPD1: "greatestP P x ==> P x"
    32 by (simp add: greatestP_def)
    33 
    34 lemma greatestPD2: "greatestP P x ==> Collect P *<= x"
    35 by (simp add: greatestP_def)
    36 
    37 lemma greatestPD3: "[| greatestP P x; y: Collect P |] ==> x >= y"
    38 by (blast dest!: greatestPD2 setleD)
    39 
    40 lemma isGlbD1: "isGlb R S x ==> x <=* S"
    41 by (simp add: isGlb_def isLb_def greatestP_def)
    42 
    43 lemma isGlbD1a: "isGlb R S x ==> x: R"
    44 by (simp add: isGlb_def isLb_def greatestP_def)
    45 
    46 lemma isGlb_isLb: "isGlb R S x ==> isLb R S x"
    47 apply (simp add: isLb_def)
    48 apply (blast dest: isGlbD1 isGlbD1a)
    49 done
    50 
    51 lemma isGlbD2: "[| isGlb R S x; y : S |] ==> y >= x"
    52 by (blast dest!: isGlbD1 setgeD)
    53 
    54 lemma isGlbD3: "isGlb R S x ==> greatestP(isLb R S) x"
    55 by (simp add: isGlb_def)
    56 
    57 lemma isGlbI1: "greatestP(isLb R S) x ==> isGlb R S x"
    58 by (simp add: isGlb_def)
    59 
    60 lemma isGlbI2: "[| isLb R S x; Collect (isLb R S) *<= x |] ==> isGlb R S x"
    61 by (simp add: isGlb_def greatestP_def)
    62 
    63 lemma isLbD: "[| isLb R S x; y : S |] ==> y >= x"
    64 by (simp add: isLb_def setge_def)
    65 
    66 lemma isLbD2: "isLb R S x ==> x <=* S "
    67 by (simp add: isLb_def)
    68 
    69 lemma isLbD2a: "isLb R S x ==> x: R"
    70 by (simp add: isLb_def)
    71 
    72 lemma isLbI: "[| x <=* S ; x: R |] ==> isLb R S x"
    73 by (simp add: isLb_def)
    74 
    75 lemma isGlb_le_isLb: "[| isGlb R S x; isLb R S y |] ==> x >= y"
    76 apply (simp add: isGlb_def)
    77 apply (blast intro!: greatestPD3)
    78 done
    79 
    80 lemma isGlb_ubs: "isGlb R S x ==> lbs R S *<= x"
    81 apply (simp add: lbs_def isGlb_def)
    82 apply (erule greatestPD2)
    83 done
    84 
    85 end