src/HOL/Set.thy
author nipkow
Wed Jul 15 10:58:44 1998 +0200 (1998-07-15)
changeset 5144 7ac22e5a05d7
parent 4761 1681b32dd134
child 5236 0cec0b591d4c
permissions -rw-r--r--
Minor tidying up.
     1 (*  Title:      HOL/Set.thy
     2     ID:         $Id$
     3     Author:     Tobias Nipkow
     4     Copyright   1993  University of Cambridge
     5 *)
     6 
     7 Set = Ord +
     8 
     9 
    10 (** Core syntax **)
    11 
    12 global
    13 
    14 types
    15   'a set
    16 
    17 arities
    18   set :: (term) term
    19 
    20 instance
    21   set :: (term) {ord, minus, power} (* only ('a * 'a) set should be in power! *)
    22 
    23 syntax
    24   "op :"        :: ['a, 'a set] => bool             ("op :")
    25 
    26 consts
    27   "{}"          :: 'a set                           ("{}")
    28   UNIV          :: 'a set
    29   insert        :: ['a, 'a set] => 'a set
    30   Collect       :: ('a => bool) => 'a set               (*comprehension*)
    31   Compl         :: ('a set) => 'a set                   (*complement*)
    32   Int           :: ['a set, 'a set] => 'a set       (infixl 70)
    33   Un            :: ['a set, 'a set] => 'a set       (infixl 65)
    34   UNION, INTER  :: ['a set, 'a => 'b set] => 'b set     (*general*)
    35   Union, Inter  :: (('a set) set) => 'a set             (*of a set*)
    36   Pow           :: 'a set => 'a set set                 (*powerset*)
    37   range         :: ('a => 'b) => 'b set                 (*of function*)
    38   Ball, Bex     :: ['a set, 'a => bool] => bool         (*bounded quantifiers*)
    39   "``"          :: ['a => 'b, 'a set] => ('b set)   (infixr 90)
    40   (*membership*)
    41   "op :"        :: ['a, 'a set] => bool             ("(_/ : _)" [50, 51] 50)
    42 
    43 
    44 
    45 (** Additional concrete syntax **)
    46 
    47 syntax
    48 
    49   (* Infix syntax for non-membership *)
    50 
    51   "op ~:"       :: ['a, 'a set] => bool               ("op ~:")
    52   "op ~:"       :: ['a, 'a set] => bool               ("(_/ ~: _)" [50, 51] 50)
    53 
    54   "@Finset"     :: args => 'a set                     ("{(_)}")
    55 
    56   "@Coll"       :: [pttrn, bool] => 'a set            ("(1{_./ _})")
    57   "@SetCompr"   :: ['a, idts, bool] => 'a set         ("(1{_ |/_./ _})")
    58 
    59   (* Big Intersection / Union *)
    60 
    61   INTER1        :: [pttrns, 'a => 'b set] => 'b set   ("(3INT _./ _)" 10)
    62   UNION1        :: [pttrns, 'a => 'b set] => 'b set   ("(3UN _./ _)" 10)
    63 
    64   "@INTER"      :: [pttrn, 'a set, 'b set] => 'b set  ("(3INT _:_./ _)" 10)
    65   "@UNION"      :: [pttrn, 'a set, 'b set] => 'b set  ("(3UN _:_./ _)" 10)
    66 
    67   (* Bounded Quantifiers *)
    68 
    69   "@Ball"       :: [pttrn, 'a set, bool] => bool      ("(3! _:_./ _)" [0, 0, 10] 10)
    70   "@Bex"        :: [pttrn, 'a set, bool] => bool      ("(3? _:_./ _)" [0, 0, 10] 10)
    71   "*Ball"       :: [pttrn, 'a set, bool] => bool      ("(3ALL _:_./ _)" [0, 0, 10] 10)
    72   "*Bex"        :: [pttrn, 'a set, bool] => bool      ("(3EX _:_./ _)" [0, 0, 10] 10)
    73 
    74   disjoint      :: 'a set => 'a set => bool
    75 
    76 translations
    77   "range f"     == "f``UNIV"
    78   "x ~: y"      == "~ (x : y)"
    79   "{x, xs}"     == "insert x {xs}"
    80   "{x}"         == "insert x {}"
    81   "{x. P}"      == "Collect (%x. P)"
    82   "UN x y. B"   == "UN x. UN y. B"
    83   "UN x. B"     == "UNION UNIV (%x. B)"
    84   "INT x y. B"   == "INT x. INT y. B"
    85   "INT x. B"    == "INTER UNIV (%x. B)"
    86   "UN x:A. B"   == "UNION A (%x. B)"
    87   "INT x:A. B"  == "INTER A (%x. B)"
    88   "! x:A. P"    == "Ball A (%x. P)"
    89   "? x:A. P"    == "Bex A (%x. P)"
    90   "ALL x:A. P"  => "Ball A (%x. P)"
    91   "EX x:A. P"   => "Bex A (%x. P)"
    92   "disjoint A B" == "A <= Compl B"
    93 
    94 syntax ("" output)
    95   "_setle"      :: ['a set, 'a set] => bool           ("op <=")
    96   "_setle"      :: ['a set, 'a set] => bool           ("(_/ <= _)" [50, 51] 50)
    97   "_setless"    :: ['a set, 'a set] => bool           ("op <")
    98   "_setless"    :: ['a set, 'a set] => bool           ("(_/ < _)" [50, 51] 50)
    99 
   100 syntax (symbols)
   101   "_setle"      :: ['a set, 'a set] => bool           ("op \\<subseteq>")
   102   "_setle"      :: ['a set, 'a set] => bool           ("(_/ \\<subseteq> _)" [50, 51] 50)
   103   "_setless"    :: ['a set, 'a set] => bool           ("op \\<subset>")
   104   "_setless"    :: ['a set, 'a set] => bool           ("(_/ \\<subset> _)" [50, 51] 50)
   105   "op Int"      :: ['a set, 'a set] => 'a set         (infixl "\\<inter>" 70)
   106   "op Un"       :: ['a set, 'a set] => 'a set         (infixl "\\<union>" 65)
   107   "op :"        :: ['a, 'a set] => bool               ("op \\<in>")
   108   "op :"        :: ['a, 'a set] => bool               ("(_/ \\<in> _)" [50, 51] 50)
   109   "op ~:"       :: ['a, 'a set] => bool               ("op \\<notin>")
   110   "op ~:"       :: ['a, 'a set] => bool               ("(_/ \\<notin> _)" [50, 51] 50)
   111   "UN "         :: [idts, bool] => bool               ("(3\\<Union> _./ _)" 10)
   112   "INT "        :: [idts, bool] => bool               ("(3\\<Inter> _./ _)" 10)
   113   "UNION1"      :: [pttrn, 'b set] => 'b set          ("(3\\<Union> _./ _)" 10)
   114   "INTER1"      :: [pttrn, 'b set] => 'b set          ("(3\\<Inter> _./ _)" 10)
   115   "@UNION"      :: [pttrn, 'a set, 'b set] => 'b set  ("(3\\<Union> _\\<in>_./ _)" 10)
   116   "@INTER"      :: [pttrn, 'a set, 'b set] => 'b set  ("(3\\<Inter> _\\<in>_./ _)" 10)
   117   Union         :: (('a set) set) => 'a set           ("\\<Union> _" [90] 90)
   118   Inter         :: (('a set) set) => 'a set           ("\\<Inter> _" [90] 90)
   119   "@Ball"       :: [pttrn, 'a set, bool] => bool      ("(3\\<forall> _\\<in>_./ _)" [0, 0, 10] 10)
   120   "@Bex"        :: [pttrn, 'a set, bool] => bool      ("(3\\<exists> _\\<in>_./ _)" [0, 0, 10] 10)
   121 
   122 syntax (symbols output)
   123   "*Ball"       :: [pttrn, 'a set, bool] => bool      ("(3\\<forall> _\\<in>_./ _)" [0, 0, 10] 10)
   124   "*Bex"        :: [pttrn, 'a set, bool] => bool      ("(3\\<exists> _\\<in>_./ _)" [0, 0, 10] 10)
   125 
   126 translations
   127   "op \\<subseteq>" => "op <= :: [_ set, _ set] => bool"
   128   "op \\<subset>" => "op <  :: [_ set, _ set] => bool"
   129 
   130 
   131 
   132 (** Rules and definitions **)
   133 
   134 local
   135 
   136 rules
   137 
   138   (* Isomorphisms between Predicates and Sets *)
   139 
   140   mem_Collect_eq    "(a : {x. P(x)}) = P(a)"
   141   Collect_mem_eq    "{x. x:A} = A"
   142 
   143 
   144 defs
   145 
   146   Ball_def      "Ball A P       == ! x. x:A --> P(x)"
   147   Bex_def       "Bex A P        == ? x. x:A & P(x)"
   148   subset_def    "A <= B         == ! x:A. x:B"
   149   psubset_def   "A < B          == (A::'a set) <= B & ~ A=B"
   150   Compl_def     "Compl A        == {x. ~x:A}"
   151   Un_def        "A Un B         == {x. x:A | x:B}"
   152   Int_def       "A Int B        == {x. x:A & x:B}"
   153   set_diff_def  "A - B          == {x. x:A & ~x:B}"
   154   INTER_def     "INTER A B      == {y. ! x:A. y: B(x)}"
   155   UNION_def     "UNION A B      == {y. ? x:A. y: B(x)}"
   156   Inter_def     "Inter S        == (INT x:S. x)"
   157   Union_def     "Union S        == (UN x:S. x)"
   158   Pow_def       "Pow A          == {B. B <= A}"
   159   empty_def     "{}             == {x. False}"
   160   UNIV_def      "UNIV           == {x. True}"
   161   insert_def    "insert a B     == {x. x=a} Un B"
   162   image_def     "f``A           == {y. ? x:A. y=f(x)}"
   163 
   164 end
   165 
   166 
   167 ML
   168 
   169 local
   170 
   171 (* Set inclusion *)
   172 
   173 fun le_tr' _ (*op <=*) (Type ("fun", (Type ("set", _) :: _))) ts =
   174       list_comb (Syntax.const "_setle", ts)
   175   | le_tr' _ (*op <=*) _ _ = raise Match;
   176 
   177 fun less_tr' _ (*op <*) (Type ("fun", (Type ("set", _) :: _))) ts =
   178       list_comb (Syntax.const "_setless", ts)
   179   | less_tr' _ (*op <*) _ _ = raise Match;
   180 
   181 
   182 (* Translates between { e | x1..xn. P} and {u. ? x1..xn. u=e & P}      *)
   183 (* {y. ? x1..xn. y = e & P} is only translated if [0..n] subset bvs(e) *)
   184 
   185 val ex_tr = snd(mk_binder_tr("? ","Ex"));
   186 
   187 fun nvars(Const("_idts",_) $ _ $ idts) = nvars(idts)+1
   188   | nvars(_) = 1;
   189 
   190 fun setcompr_tr[e,idts,b] =
   191   let val eq = Syntax.const("op =") $ Bound(nvars(idts)) $ e
   192       val P = Syntax.const("op &") $ eq $ b
   193       val exP = ex_tr [idts,P]
   194   in Syntax.const("Collect") $ Abs("",dummyT,exP) end;
   195 
   196 val ex_tr' = snd(mk_binder_tr' ("Ex","DUMMY"));
   197 
   198 fun setcompr_tr'[Abs(_,_,P)] =
   199   let fun ok(Const("Ex",_)$Abs(_,_,P),n) = ok(P,n+1)
   200         | ok(Const("op &",_) $ (Const("op =",_) $ Bound(m) $ e) $ _, n) =
   201             if n>0 andalso m=n andalso
   202               ((0 upto (n-1)) subset add_loose_bnos(e,0,[]))
   203             then () else raise Match
   204 
   205       fun tr'(_ $ abs) =
   206         let val _ $ idts $ (_ $ (_ $ _ $ e) $ Q) = ex_tr'[abs]
   207         in Syntax.const("@SetCompr") $ e $ idts $ Q end
   208   in ok(P,0); tr'(P) end;
   209 
   210 in
   211 
   212 val parse_translation = [("@SetCompr", setcompr_tr)];
   213 val print_translation = [("Collect", setcompr_tr')];
   214 val typed_print_translation = [("op <=", le_tr'), ("op <", less_tr')];
   215 val print_ast_translation =
   216   map HOL.alt_ast_tr' [("@Ball", "*Ball"), ("@Bex", "*Bex")];
   217 
   218 end;