src/HOL/Induct/Multiset.thy
changeset 10258 d549f2534e6d
parent 10257 21055ac27708
child 10259 93ec82d535f2
     1.1 --- a/src/HOL/Induct/Multiset.thy	Wed Oct 18 23:35:56 2000 +0200
     1.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.3 @@ -1,65 +0,0 @@
     1.4 -(*  Title:      HOL/Induct/Multiset.thy
     1.5 -    ID:         $Id$
     1.6 -    Author:     Tobias Nipkow
     1.7 -    Copyright   1998 TUM
     1.8 -
     1.9 -A definitional theory of multisets,
    1.10 -including a wellfoundedness proof for the multiset order.
    1.11 -*)
    1.12 -
    1.13 -Multiset = Multiset0 + Acc +
    1.14 -
    1.15 -typedef
    1.16 -  'a multiset = "{f :: 'a => nat . finite{x . 0 < f x}}" (multiset_witness)
    1.17 -
    1.18 -instance multiset :: (term){ord,zero,plus,minus}
    1.19 -
    1.20 -consts
    1.21 -  "{#}"  :: 'a multiset                        ("{#}")
    1.22 -  single :: 'a                => 'a multiset   ("{#_#}")
    1.23 -  count  :: ['a multiset, 'a] => nat
    1.24 -  set_of :: 'a multiset => 'a set
    1.25 -  MCollect :: ['a multiset, 'a => bool] => 'a multiset (*comprehension*)
    1.26 -
    1.27 -
    1.28 -syntax
    1.29 -  elem     :: ['a, 'a multiset] => bool              ("(_/ :# _)" [50, 51] 50)
    1.30 -  "@MColl" :: [pttrn, 'a multiset, bool] => 'a multiset ("(1{# _ : _./ _#})")
    1.31 -
    1.32 -translations
    1.33 -  "a :# M"     == "0 < count M a"
    1.34 -  "{#x:M. P#}" == "MCollect M (%x. P)"
    1.35 -
    1.36 -defs
    1.37 -  count_def  "count == Rep_multiset"
    1.38 -  empty_def  "{#}   == Abs_multiset(%a. 0)"
    1.39 -  single_def "{#a#} == Abs_multiset(%b. if b=a then 1 else 0)"
    1.40 -  union_def  "M+N   == Abs_multiset(%a. Rep_multiset M a + Rep_multiset N a)"
    1.41 -  diff_def   "M-N    == Abs_multiset(%a. Rep_multiset M a - Rep_multiset N a)"
    1.42 -  MCollect_def "MCollect M P ==
    1.43 -		Abs_multiset(%x. if P x then Rep_multiset M x else 0)"
    1.44 -  set_of_def "set_of M == {x. x :# M}"
    1.45 -  size_def   "size (M) == setsum (count M) (set_of M)"
    1.46 -  Zero_def   "0 == {#}"
    1.47 -
    1.48 -constdefs
    1.49 -  mult1 :: "('a * 'a)set => ('a multiset * 'a multiset)set"
    1.50 - "mult1(r) == {(N,M) . ? a M0 K. M = M0 + {#a#} & N = M0 + K &
    1.51 -                                 (!b. b :# K --> (b,a) : r)}"
    1.52 -
    1.53 -  mult :: "('a * 'a)set => ('a multiset * 'a multiset)set"
    1.54 - "mult(r) == (mult1 r)^+"
    1.55 -
    1.56 -locale MSOrd =
    1.57 -  fixes
    1.58 -    r :: "('a * 'a)set"
    1.59 -    W :: "'a multiset set"
    1.60 -
    1.61 -  defines
    1.62 -    W_def       "W == acc(mult1 r)"
    1.63 -
    1.64 -defs
    1.65 -  mult_less_def  "M' < M  ==  (M',M) : mult {(x',x). x'<x}"
    1.66 -  mult_le_def    "M' <= M  ==  M'=M | M' < (M :: 'a multiset)"
    1.67 -
    1.68 -end