Note: I adapted this description from the header comments for the Scala CookieJar trait developed in March 2010 and modified in January 2012 for the course Mulitparadigm Programming (CSci 556).
I use notation that can be typed into comments for computer programs, not the notation that would be used in a typeset mathematics textbook.
A mathematical bag is an unordered collection of values in which each value may occur one or more times.
The bag notation used in this documentation includes:
{| |} denotes empty bag.
{| 2, 3, 2, 1 |} denotes a bag with four elements
including two 2's, one 3, and one 1. The order is not
significant! There may be one or more occurrences of an element.
IN denotes the bag membership operation. x IN
B if there are one or more occurrences of the value
x in bag B.
UNION denotes bag union. The resulting bag has the
total number of occurrences of elements from the two bags. ode>.
(Remember order is not significant.) {| 3, 1, 1, 3 |} UNION {| 1, 2 |} = {|
1,1,1,2,3,3|}.
DIFF denotes bag difference. A DIFF B
removes each occurrence of elements in B from A. The resulting
bag has the number of occurrences in bag A minus the number of
occurrences in bag B. If there are more occurrence in B than A,
then the result has no occurrences. {| 1, 1, 2, 1 }} DIFF {| 2,1,1 |} = {| 1 |}.
OCCURRENCES denotes occurrence counting.
OCCURENCES(x,B) returns the number of times element
x appears in bag B.