Home | Up | Questions? |

*Set theory* has long been useful in mathematics and
computer science. *Bag theory* is a natural extension
of set theory. A bag, like a set, is a collection
of elements over some domain. However, unlike a set,
bags allow *multiple* occurrences of elements. In set
theory, an element is either a member of a set or
not a member of a set. In bag theory, an element may
be in a bag zero times (not in the bag) or
one time, two times, three times, or any specified number of
times.

Bag theory has been developed in [Cerf et al. 1971] and [Peterson 1976].

As examples, consider the following bags
over the domain :

Some bags are sets ( and , for example). Also, as with sets, the order of the elements is not important, so and are the same bag. (Ordered bags are sequences.)

In set theory, the basic concept is the *is a member of*
relationship. This relationship is between elements and sets
and defines which elements are members of which sets. The basic
concept of bag theory is the *number of occurrences* function.
This function defines the number of occurrences of an element
in a bag. For an element and a bag , we denote the number
of occurrences of in by
(pronounced ``the number of in '').

With this conceptual basis, we can define the fundamentals of bag theory. Most of the concepts and notation are borrowed from set theory in the obvious way. If we restrict the number of elements in a bag such that , then set theory results.

The function defines the number of occurrences
of an element in a bag . From this it follows that
for all and .
We distinguish the zero and the nonzero cases. An element
is a *member* of a bag if . This
is denoted . Similarly, if
, then .

We define the empty bag with no members: For all , .

The *cardinality* of a bag is the total number of occurrences
of elements in the bag:

A bag is a *subbag* of a bag (denoted )
if every element of is also an element of at
least as many times:

Two bags are

From these definitions, we can immediately show that

A bag is

Four operations are defined on bags. For two bags
and , we define

These operators have most of the properties that would be expected. Union, intersection, and sum are commutative and associative. In addition, the expected inclusions hold:

The distinction between union and sum is clearly stated by

Unfortunately no such simple statement distinguishes from . The latter is complicated by the impossibility of removing elements from a bag which are not there.

We define a *domain* as a set of elements from which bags are
constructed. The bag space is the set of all bags whose elements
are in such that no element occurs more than times. That is,
for all ,

- implies .
- for all .

The set is the set of all bags over a domain ; there is no limit on the number of occurrences of an element in a bag.

For finite domain ,
there is a natural correspondence between each bag over and
the -vector
defined by

This vector is known as the Parikh mapping [Parikh 1966].

Let be a domain.
Then for the following bags,

we have

Home | Comments? |