Bag (mathematics)
From Wikipedia, the free encyclopedia.

In mathematics, a bag (also called multi set) is a collection of objects that is unordered and can contain objects more than once. It is the latter aspect that distinguishes bags from sets, which can contain objects at most once. An example of a bag would be which contains a once and b twice, and a different bag would be which contains a twice and b once, and finally the bag which is yet another bag and in fact a set.

Formal definition

Formally bags can be defined in set theory as partial functions that map objects to a positive natural number. So in terms of sets

• the bag is defined as {(a, 1), (b, 2)},
• the bag is defined as {(a, 2), (b, 1)}, and
• the bag is defined as {(a, 1), (b, 1)}.

Bag operations

The usual set operations such as set union, set intersection and cartesian product can be easily generalized for bags.

• the union of bags A and B can be defined as the function F on the union of the domain of A and B such that F(x) = A(x) + B(x)
• the intersection of bags A and B can be defined as the function F on the intersection of the domain of A and B such that F(x) = MIN(A(x), B(x))
• the cartesian product of bags A and B can be defined as the function F on the cartesian product of the domains of A and B such that F((x,y)) = A(x).B(y)

The original article can be found at: http://en.wikipedia.org/wiki/Bag_(mathematics).
All text is available under the terms of the GNU Free Documentation License.