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 :
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
Section A.1. Membership
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 , .
Section A.2. Cardinality
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:
From these definitions, we can immediately show that
Four operations are defined on bags. For two bags
and , we define
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 ,
For finite domain ,
there is a natural correspondence between each bag over and
Let be a domain.
Then for the following bags,