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