operations on multisets
In this entry, we view multisets as functions whose ranges are the class K of cardinal numbers. We define operations on multisets that mirror the operations
on sets.
Definition. Let f:A→K and g:B→K be multisets.
-
•
The union of f and g, denoted by f∪g, is the multiset whose domain is A∪B, such that
(f∪g)(x):= keeping in mind that if is not in the domain of .
-
•
The intersection
of and , denoted by , is the multiset, whose domain is , such that
-
•
The sum (or disjoint union
) of and , denoted by , is the multiset whose domain is (not the disjoint union of and ), such that
again keeping in mind that if is not in the domain of .
Clearly, all of the operations described so far are commutative. Furthermore, if is cancellable on both sides: implies , and implies .
Subtraction on multisets can also be defined. Suppose and are multisets. Let be the set . Then
- •
For example, writing finite multisets (those with finite domains and finite multiplicities for all elements) in their usual notations, if and , then
-
•
-
•
-
•
-
•
We may characterize the union and intersection operations in terms of multisubsets.
Definition. A multiset is a multisubset of a multiset if
-
1.
is a subset of , and
-
2.
for all .
We write to mean that is a multisubset of .
Proposition 1.
Given multisets and .
-
•
is the smallest multiset such that and are multisubsets of it. In other words, if and , then .
-
•
is the largest multiset that is a multisubset of and . In other words, if and , then .
Remark. One may also define the powerset of a multiset : the multiset such that each of its elements is a multisubset of . However, the resulting multiset is just a set (the multiplicity of each element is ).
Title | operations on multisets |
---|---|
Canonical name | OperationsOnMultisets |
Date of creation | 2013-03-22 19:13:23 |
Last modified on | 2013-03-22 19:13:23 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 9 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 03E99 |
Defines | multisubset |