„Multimenge“ – Versionsunterschied

Multimenge ist ein Begriff, der den Mengenbegriff aus der Mengenlehre variiert. Die Besonderheit von Multimengen gegenüber dem gewöhnlichen Mengenbegriff besteht darin, dass die Elemente einer Multimenge mehrfach vorkommen können. Dementsprechend haben auch die für Multimengen verwendeten Mengenoperationen eine modifizierte Bedeutung.

In der Informatik stellen Multimengen (dort auch engl. Bag genannt) eine nützliche Datenstruktur dar. Beispielsweise behandelt die Datenbanksprache SQL Tabellen standardmäßig als Multimengen.

Eine Multimenge ${\displaystyle M}$ über einer Menge ${\displaystyle A}$ ist eine Abbildung von ${\displaystyle A}$ in die Menge der natürlichen Zahlen ${\displaystyle \mathbb {N} _{0}}$. Die Zahl ${\displaystyle M(x),x\in A}$ gibt an, wie oft das Element ${\displaystyle x}$ in der Multimenge ${\displaystyle M}$ vorkommt. Die Menge aller Multimengen über ${\displaystyle A}$ kann als ${\displaystyle \mathbb {N} _{0}^{A}}$ geschrieben werden. Im Weiteren wird jedoch, um vertikalen Platz zu sparen, ${\displaystyle \operatorname {MS} (A)}$ verwendet.

Die reduzierte Grundmenge (engl. „support“) einer Multimenge ${\displaystyle M}$ über ${\displaystyle A}$ ist die Menge ${\displaystyle \operatorname {supp} (M)}$ der relevanten Elemente von ${\displaystyle A}$, in Formeln:

${\displaystyle \operatorname {supp} (M):=\left\{x\in A\mid M(x)>0\right\}}$.

Eine Multimenge ${\displaystyle M}$ heißt Teil(multi)menge einer Multimenge ${\displaystyle N}$, wenn jedes Element der reduzierten Grundmenge von ${\displaystyle M}$ in ${\displaystyle N}$ mindestens so häufig vorkommt wie in ${\displaystyle M}$. Formal:

${\displaystyle M\subseteq N\quad \Longleftrightarrow \quad \forall x\in \operatorname {supp} (M):M(x)\leq N(x)}$.

Zwei Multimengen ${\displaystyle M}$ und ${\displaystyle N}$ sind gleich, wenn ihre reduzierten Grundmengen gleich sind und die Vielfachheiten übereinstimmen. Sie sind dann auch in beiden Richtungen Teilmultimengen voneinander.

Obige Definition mit Zulassung des (eigentlich irrelevanten) 0-Wertes ist eine Verallgemeinerung der Indikatorfunktion bei den gewöhnlichen Mengen. Sie ermöglicht die Bereitstellung eines „Universums“ als Grundmenge, auf welches alle fraglichen Multimengen bezogen werden, und vereinfacht in der Folge Handhabung und Vergleich.

Anschaulich ist eine Multimenge eine Menge, in der jedes Element beliebig oft vorkommen kann. Mengen sind in diesem Sinne ein Spezialfall von Multimengen, bei denen jeder Wert nur genau einmal vorkommt.

Man notiert Multimengen wie Mengen explizit mit geschweiften Klammern und schreibt ein Element so oft hinein, wie es in der Multimenge vorkommt. Um Multimengen von normalen Mengen zu unterscheiden, wird bei ihrer Aufzählung gelegentlich auch ein kleines ${\displaystyle _{b}}$ (für engl. bag) als Index angefügt. Einige Autoren benutzen stattdessen modifizierte Klammern: ${\displaystyle \{\!\vert \;\;\;\vert \!\}}$.^[1]

Es sei ${\displaystyle M}$ die Multimenge über ${\displaystyle \{a,b,c\}}$ mit ${\displaystyle M(a)=1}$, ${\displaystyle M(b)=3}$ und ${\displaystyle M(c)=0}$. Dann schreibt man also ${\displaystyle M=\lbrace a,b,b,b\rbrace }$ oder ${\displaystyle M=\lbrace a,b,b,b\rbrace _{b}}$ oder ${\displaystyle M=\{\!\vert a,b,b,b\vert \!\}}$.

Man nehme einen Würfel und würfele 20-mal hintereinander. Dann kann es sein, dass man

3 mal eine 1

2 mal eine 2

4 mal eine 3

5 mal eine 4

3 mal eine 5 und

3 mal eine 6

geworfen hat. Die Grundmenge ist dann ${\displaystyle \{1,2,3,4,5,6\}}$; die Vielfachheit der ${\displaystyle 3}$ ist 4; also ${\displaystyle M(3)=4}$. Die Multimenge listet jeden Wurf auf, wobei die Reihenfolge außer Acht gelassen wird:

${\displaystyle M=\{1,1,1,2,2,3,3,3,3,4,4,4,4,4,5,5,5,6,6,6\}.}$

Ein anderes Beispiel ist etwa die Primfaktorzerlegung von 120:

${\displaystyle 120=2^{3}3^{1}5^{1}}$

Sie lässt sich als Multimenge ${\displaystyle \{2,2,2,3,5\}}$ interpretieren.

Gegeben sei eine Menge ${\displaystyle A}$ mit ${\displaystyle n}$ Elementen. Die Anzahl der Multimengen über ${\displaystyle A}$, die ${\displaystyle k}$ Elemente enthalten, wird dann (analog zu den Binomialkoeffizienten ${\displaystyle {\tbinom {n}{k}}}$) als

${\displaystyle \left(\!\!{n \choose k}\!\!\right)}$

bezeichnet. Er lässt sich gut als Binomialkoeffizient ausdrücken:

${\displaystyle \left(\!\!{n \choose k}\!\!\right)={n+k-1 \choose k}={n+k-1 \choose n-1}={n(n+1)(n+2)\cdots (n+k-1) \over k!}}$

Dies gibt die Anzahl der möglichen Ausgänge beim Ziehen von unterscheidbaren Kugeln aus einer Urne an, wenn die Reihenfolge nicht beachtet wird und jede gezogene Kugel wieder in die Urne zurückgelegt wird, nachdem sie gezogen wurde (siehe Kombination mit Wiederholung).

Werden aus einer Urne mit 5 Kugeln nacheinander 10 gezogen, wobei jede gezogene Kugel wieder zurückgelegt wird, so gibt es

${\displaystyle \left(\!\!{5 \choose 10}\!\!\right)={5+10-1 \choose 10}=1001}$

mögliche Kombinationen, wenn die Reihenfolge der gezogenen Kugeln nicht beachtet wird.

Eine Multimenge über Multimengen über ${\displaystyle A}$ kann unter Beachtung der Vielfachheiten vereinigt werden. Dies leistet ${\displaystyle \mu \colon \operatorname {MS} (\operatorname {MS} (A))\to \operatorname {MS} (A)}$, mit

${\displaystyle \mu (M)(a)=\sum _{N\in supp(M)}M(N)\cdot N(a).}$

Eine Funktion ${\displaystyle f\colon A\to B}$ kann erweitert werden zu einer Funktion ${\displaystyle \operatorname {MS} (f)\colon \operatorname {MS} (A)\to \operatorname {MS} (B)}$, wobei

${\displaystyle \operatorname {MS} (f)(M)(b)=\sum _{a\in f^{-1}(b)}M(a).}$

Zusammen mit ${\displaystyle \eta \colon A\to \operatorname {MS} (A)}$ mit

${\displaystyle \eta (a)(a')={\begin{cases}1&a=a'\\0&{\text{sonst}}\end{cases}}}$

haben wir es mit einer Monadenstruktur zu tun.

Der Funktor ${\displaystyle \operatorname {MS} }$ sowie ${\displaystyle \mu }$ lassen sich auch auf eine andere nützliche Operation zurückführen. ${\displaystyle \operatorname {lift} }$ erweitert eine Funktion ${\displaystyle f\colon A\to \operatorname {MS} (B)}$ zu einer Funktion ${\displaystyle \operatorname {lift} (f)\colon \operatorname {MS} (A)\to \operatorname {MS} (B)}$, und zwar durch

${\displaystyle \operatorname {lift} (f)(M)(b)=\sum _{a\in supp(M)}M(a)\cdot f(a)(b).}$

Mit Hilfe dieser Operation kann ${\displaystyle \mu =\operatorname {lift} (\operatorname {id} )}$ und ${\displaystyle \operatorname {MS} (f)=\operatorname {lift} (\eta \circ f)}$ gesetzt werden.

Die (große) Vereinigung zweier Multimengen über derselben Grundmenge ${\displaystyle A}$ kann entweder direkt als

${\displaystyle (M\uplus N)(a)=M(a)+N(a),}$

oder mittels ${\displaystyle \mu }$

${\displaystyle M\uplus N=\mu (\{M,N\}_{b})}$

angegeben werden.

Als kleine Vereinigung zweier Multimengen wird die kleinste Multimenge

${\displaystyle (M\cup N)(a)=\operatorname {max} (M(a),N(a))}$,

die beide umfasst, angesehen.

Der Durchschnitt zweier Multimengen über derselben Grundmenge ${\displaystyle A}$ ist anwendungsspezifisch. Es gibt

1. ${\displaystyle (M\cap N)(a)=\operatorname {min} (M(a),N(a))}$, sowie
2. ${\displaystyle (M\cap N)(a)=M(a)\cdot N(a).}$

Die zweite Definition lässt sich auf obiges ${\displaystyle \operatorname {lift} }$ zurückführen, wenn zusätzlich eine weitere Operation eingeführt wird. Sei ${\displaystyle f\colon A\times B\to \operatorname {MS} (C)}$, dann ist ${\displaystyle \operatorname {lift} _{2}(f)\colon \operatorname {MS} (A)\times \operatorname {MS} (B)\to \operatorname {MS} (C)}$ definiert durch

${\displaystyle \operatorname {lift} _{2}(f)(M,N)=\operatorname {lift} (a\mapsto \operatorname {lift} (b\mapsto f(a,b))(N))(M)}$.

Der Durchschnitt im zweiten Sinne ergibt sich dann als ${\displaystyle M\cap N=\operatorname {lift} _{2}(h)(M,N)}$ mit

${\displaystyle h(a,a')={\begin{cases}\{a\}_{b}&a=a'\\\emptyset &{\text{sonst}}.\end{cases}}}$

Für die Differenz zweier Multimengen über derselben Grundmenge ${\displaystyle A}$ gibt es ebenfalls mindestens zwei sinnvolle Definitionen.

1. ${\displaystyle (M\setminus N)(a)={\begin{cases}0&M(a)<N(a)\\M(a)-N(a)&{\text{sonst}}\end{cases}}}$
2. ${\displaystyle (M\setminus N)(a)={\begin{cases}0&N(a)\neq 0\\M(a)&{\text{sonst}}.\end{cases}}}$

Für beide gilt ${\displaystyle X\setminus \emptyset =X}$ und ${\displaystyle X\setminus X=\emptyset }$. Welche die "richtige" ist, hängt vom Anwendungsfall ab.

Bemerkung:
Seien ${\displaystyle M,N}$ Multimengen über den Primzahlen. Mit ${\displaystyle m:=\Pi M}$ und ${\displaystyle n:=\Pi N}$ als ausmultiplizierten Multimengen haben wir:

• Die große Vereinigung entspricht dem Produkt ${\displaystyle m\cdot n}$.
• Die kleine Vereinigung entspricht dem kgV, d. h. ${\displaystyle \operatorname {kgV} (m,n)=\Pi {M\cup N}}$.
• Die erste Version des Durchschnitts entspricht dem ggT, d. h. ${\displaystyle \operatorname {ggT} (m,n)=\Pi {M\cap N}}$.
• Die erste Version der Differenz entspricht ${\displaystyle m/\operatorname {ggT} (m,n)}$.

Behält man die im vorangegangenen Abschnitt definierten Operationen bei, erhält man durch Variation der Vielfachheitenmenge verwandte Strukturen.

• Reelle Vielfachheiten im Intervall ${\displaystyle [0,1]}$ ergeben Wahrscheinlichkeitsverteilungen. Die Multimengen-Grundmenge wird zur Menge möglicher Ereignisse. Die ${\displaystyle \operatorname {lift} }$-Operation rechnet Funktionen, die auf der Basis von eingetretenen Ereignissen Wahrscheinlichkeitsverteilungen anderer Ereignismengen erzeugen, in solche um, die mit Wahrscheinlichkeitsverteilungen als Eingabe umgehen können.
• Lässt man für die Vielfachheiten Körperelemente zu und definiert zusätzlich eine Skalierung, werden Multimengen über A zu Vektoren eines Vektorraums mit einer Basis, die durch A indiziert wird. ${\displaystyle \operatorname {lift} }$ verkörpert dabei die Tatsache, dass es für die Festlegung einer linearen Abbildung ausreicht, die Bilder der Basisvektoren festzulegen. Auf ähnliche Weise rechnet ${\displaystyle \operatorname {lift} _{2}}$ Funktionen auf Basisindexpaaren in bilineare Abbildungen um.

• Apostolos Syropoulos: Mathematics of Multisets. In: Multiset Processing. Lecture Notes in Computer Science. Band 2235/2001. Springer, 2001, ISBN 978-3-540-43063-6, S. 347–358, doi:10.1007/3-540-45523-X_17 (PDF). 

1. ↑ Cristian S. Calude, Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa, Multiset Processing: Mathematical, Computer Science, and Molecular Computing Points of View Springer Verlag 2001, ISBN 3-540-43063-6 S. 105