Potenzmenge

Potenzmenge ⓘ

Die Elemente der Potenzmenge von {x, y, z}, geordnet im Hinblick auf die Inklusion.
Typ	Mengenoperation
Feld	Mengenlehre
Aussage	Die Potenzmenge ist die Menge, die alle Teilmengen einer gegebenen Menge enthält.
Symbolische Aussage	$x\in P(S)\iff x\subseteq S$

In der Mathematik ist die Potenzmenge (oder Potenzmenge) einer Menge S die Menge aller Teilmengen von S, einschließlich der leeren Menge und S selbst. In der axiomatischen Mengenlehre (wie sie z. B. in den ZFC-Axiomen entwickelt wurde) wird die Existenz der Potenzmenge einer beliebigen Menge durch das Axiom der Potenzmenge postuliert. Die Potenzmenge von S wird auf verschiedene Weise bezeichnet: P(S), 𝒫(S), P(S), $\mathbb {P} (S)$, oder 2S bezeichnet. Die Schreibweise 2S, d. h. die Menge aller Funktionen von S zu einer gegebenen Menge von zwei Elementen (z. B. {0, 1}), wird verwendet, weil die Potenzmenge von S mit der Menge aller Funktionen von S zu der gegebenen Menge von zwei Elementen identifiziert werden kann, äquivalent dazu ist oder bijektiv dazu ist. ⓘ

Jede Teilmenge von P(S) wird als Familie von Mengen über S bezeichnet. ⓘ

Die Potenzmenge von {x, y, z}, dargestellt als Hasse-Diagramm. ⓘ

Beispiel

Wenn S die Menge {x, y, z} ist, dann sind alle Teilmengen von S ⓘ

• {} (auch bezeichnet als $\varnothing$ oder $\emptyset$, die leere Menge oder die Nullmenge)
• {x}
• {y}
• {z}
• {x, y}
• {x, z}
• {y, z}
• {x, y, z}

und somit ist die Potenzmenge von S {{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}. ⓘ

Eigenschaften

Ist S eine endliche Menge mit der Kardinalität |S| = n (d. h., die Anzahl aller Elemente in der Menge S ist n), dann ist die Anzahl aller Teilmengen von S |P(S)| = 2n. Diese Tatsache sowie der Grund für die Schreibweise 2S, die die Potenzmenge P(S) bezeichnet, werden im Folgenden erläutert.

Eine Indikatorfunktion oder eine charakteristische Funktion einer Teilmenge A einer Menge S mit der Kardinalität |S| = n ist eine Funktion von S zu der aus zwei Elementen bestehenden Menge {0, 1}, bezeichnet als IA: S → {0, 1}, und sie gibt an, ob ein Element von S zu A gehört oder nicht; wenn x in S zu A gehört, dann ist IA(x) = 1, andernfalls 0. Jede Teilmenge A von S ist durch die Indikatorfunktion IA identifiziert oder äquivalent zu ihr, und {0,1}^S als Menge aller Funktionen von S nach {0,1} besteht aus allen Indikatorfunktionen aller Teilmengen von S. Mit anderen Worten: {0,1}^S ist äquivalent oder bijektiv zur Potenzmenge P(S). Da jedes Element in S unter jeder Funktion in {0,1}S entweder 0 oder 1 entspricht, ist die Anzahl aller Funktionen in {0,1}^S 2n. Da die Zahl 2 als {0,1} definiert werden kann (siehe z. B. von-Neumann-Ordinale), wird P(^S) auch als 2S bezeichnet. Es ist offensichtlich, dass |2S| = 2^|S| gilt. Allgemein gesprochen ist X^Y die Menge aller Funktionen von Y nach X und |X^Y| = |X|^|Y|.

Das Cantorsche Diagonalargument zeigt, dass die Potenzmenge einer Menge (ob unendlich oder nicht) immer eine streng höhere Kardinalität hat als die Menge selbst (oder informell: die Potenzmenge muss größer sein als die ursprüngliche Menge). Insbesondere zeigt das Cantor-Theorem, dass die Potenzmenge einer abzählbar unendlichen Menge nicht abzählbar unendlich ist. Die Potenzmenge der Menge der natürlichen Zahlen kann in eine Eins-zu-Eins-Korrespondenz mit der Menge der reellen Zahlen gebracht werden (siehe Kardinalität des Kontinuums). ⓘ

Die Potenzmenge einer Menge ^S kann zusammen mit den Operationen Vereinigung, Schnittmenge und Komplement als prototypisches Beispiel für eine Boolesche Algebra angesehen werden. In der Tat kann man zeigen, dass jede endliche Boolesche Algebra isomorph zur Booleschen Algebra der Potenzmenge einer endlichen Menge ist. Für unendliche Boolesche Algebren gilt dies nicht mehr, aber jede unendliche Boolesche Algebra kann als Unteralgebra einer Booleschen Algebra der Potenzmenge dargestellt werden (siehe Stone's Repräsentationstheorem). ⓘ

Die Potenzmenge einer Menge S bildet eine abelsche Gruppe, wenn sie mit der Operation der symmetrischen Differenz betrachtet wird (mit der leeren Menge als Identitätselement und jeder Menge als ihrem eigenen Inversen), und ein kommutatives Monoid, wenn sie mit der Operation der Schnittmenge betrachtet wird. Durch den Nachweis der Distributivgesetze lässt sich also zeigen, dass die Potenzmenge mit beiden Operationen zusammen einen Booleschen Ring bildet. ⓘ

Darstellung von Teilmengen als Funktionen

In der Mengenlehre ist X^Y die Notation für die Menge aller Funktionen von Y nach X. Da "2" als {0,1} definiert werden kann (siehe z. B. von-Neumann-Ordinale), ist 2S (d. h. {0,1}S) die Menge aller Funktionen von S nach {0,1}. Wie oben gezeigt, werden 2S und die Potenzmenge von S, P(S), mengentheoretisch als identisch betrachtet. ⓘ

Diese Äquivalenz kann auf das obige Beispiel angewendet werden, in dem S = {x, y, z} ist, um den Isomorphismus mit den binären Darstellungen der Zahlen von 0 bis 2n - 1 zu erhalten, wobei n die Anzahl der Elemente in der Menge S oder |S| = n ist. Zunächst wird die Aufzählungsmenge { (x, 1), (y, 2), (z, 3) } definiert, in der die Zahl in jedem geordneten Paar die Position des gepaarten Elements von S in einer Folge von Binärziffern darstellt, wie z. B. {x, y} = 011₍₂₎; x von S befindet sich an der ersten Stelle von rechts in dieser Folge und y an der zweiten von rechts, und 1 in der Folge bedeutet, dass das Element von S, das der Position in der Folge entspricht, in der Teilmenge von S für die Folge existiert, während 0 bedeutet, dass es nicht existiert. ⓘ

Für die gesamte Potenzmenge von S erhalten wir:

Teilmenge	Sequenz von binären Ziffern	Binär Deutung	Dezimal Äquivalent ⓘ
{ }	0, 0, 0	000(2)	0(10)
{ x }	0, 0, 1	001(2)	1(10)
{ y }	0, 1, 0	010(2)	2(10)
{ x, y }	0, 1, 1	011(2)	3(10)
{ z }	1, 0, 0	100(2)	4(10)
{ x, z }	1, 0, 1	101(2)	5(10)
{ y, z }	1, 1, 0	110(2)	6(10)
{ x, y, z }	1, 1, 1	111(2)	7(10)

Eine solche bijektive Abbildung von P(S) auf ganze Zahlen ist willkürlich, so dass diese Darstellung aller Teilmengen von S nicht eindeutig ist, aber die Sortierreihenfolge der aufgezählten Menge ändert ihre Kardinalität nicht. (Z.B. kann { (y, 1), (z, 2), (x, 3) } verwendet werden, um eine weitere Bijektive von P(S) zu den ganzen Zahlen zu konstruieren, ohne dass sich die Anzahl der Eins-zu-Eins-Entsprechungen ändert.) ⓘ

Eine solche endliche binäre Darstellung ist jedoch nur möglich, wenn S aufgezählt werden kann. (In diesem Beispiel werden x, y und z mit 1, 2 bzw. 3 als Position der binären Ziffernfolgen aufgezählt.) Die Aufzählung ist auch möglich, wenn S eine unendliche Kardinalität hat (d. h. die Anzahl der Elemente in S ist unendlich), wie z. B. die Menge der ganzen Zahlen oder der rationalen Zahlen, aber nicht möglich, wenn S z. B. die Menge der reellen Zahlen ist, in diesem Fall können wir nicht alle irrationalen Zahlen aufzählen. ⓘ

Beziehung zum Binomischen Lehrsatz

Der binomische Satz ist eng mit der Potenzmenge verwandt. Eine Kombination mit k Elementen aus einer Menge ist ein anderer Name für eine Teilmenge mit k Elementen, so dass die Anzahl der Kombinationen, bezeichnet als C(n, k) (auch Binomialkoeffizient genannt), die Anzahl der Teilmengen mit k Elementen in einer Menge mit n Elementen ist; mit anderen Worten ist es die Anzahl der Mengen mit k Elementen, die Elemente der Potenzmenge einer Menge mit n Elementen sind. ⓘ

Zum Beispiel hat die Potenzmenge einer Menge mit drei Elementen:

• C(3, 0) = 1 Teilmenge mit 0 Elementen (die leere Teilmenge),
• C(3, 1) = 3 Teilmengen mit 1 Element (die Singleton-Teilmengen),
• C(3, 2) = 3 Teilmengen mit 2 Elementen (die Komplemente der Singleton-Teilmengen),
• C(3, 3) = 1 Teilmenge mit 3 Elementen (die ursprüngliche Menge selbst). ⓘ

Mit dieser Beziehung können wir berechnen ${\textstyle \left|2^{S}\right|}$ mit Hilfe der Formel berechnen:

$$\left|2^{S}\right|=\sum _{k=0}^{|S|}{\binom {|S|}{k}}$$

ⓘ

Daher kann man die folgende Identität ableiten, wenn man annimmt ${\textstyle |S|=n}$:

$$\left|2^{S}\right|=2^{n}=\sum _{k=0}^{n}{\binom {n}{k}}$$

ⓘ

Rekursive Definition

Wenn $S$ eine endliche Menge ist, dann geht eine rekursive Definition von $P(S)$ wie folgt vor:

• Wenn $S=\{\}$, dann $P(S)=\{\,\{\}\,\}$.
• Andernfalls sei $e\in S$ und $T=S\setminus \{e\}$; dann $P(S)=P(T)\cup \{t\cup \{e\}:t\in P(T)\}$. ⓘ

In Worten:

• Die Potenzmenge der leeren Menge ist ein Singleton, dessen einziges Element die leere Menge ist.
• Für eine nicht leere Menge $S$sei $e$ ein beliebiges Element der Menge und $T$ sein relatives Komplement; dann ist die Potenzmenge von $S$ ist eine Vereinigung einer Potenzmenge von $T$ und einer Potenzmenge von $T$ deren jedes Element mit dem $e$ Element erweitert ist. ⓘ

Teilmengen mit begrenzter Kardinalität

Die Menge der Teilmengen von S mit einer Kardinalität kleiner oder gleich κ wird manchmal mit P_κ(S) oder [S]^κ bezeichnet, und die Menge der Teilmengen mit einer Kardinalität streng kleiner als κ wird manchmal mit P_{< κ}(S) oder [S]^<κ bezeichnet. In ähnlicher Weise kann die Menge der nicht leeren Teilmengen von S mit P_{≥ 1}(S) oder P⁺(S) bezeichnet werden. ⓘ

Potenz-Objekt

Eine Menge kann als eine Algebra betrachtet werden, die keine nichttrivialen Operationen oder Definitionsgleichungen hat. Aus dieser Sicht verallgemeinert sich die Idee der Potenzmenge von X als die Menge der Untermengen von X natürlich auf die Unteralgebren einer algebraischen Struktur oder Algebra. ⓘ

Die Potenzmenge einer Menge ist, wenn sie durch Einschluss geordnet ist, immer eine vollständige atomare boolesche Algebra, und jede vollständige atomare boolesche Algebra entsteht als Gitter aller Teilmengen einer Menge. Die Verallgemeinerung auf beliebige Algebren besteht darin, dass die Menge der Unteralgebren einer Algebra, wiederum durch Einschluss geordnet, immer ein algebraisches Gitter ist, und jedes algebraische Gitter ergibt sich als Gitter von Unteralgebren einer Algebra. In dieser Hinsicht verhalten sich Unteralgebren also analog zu Teilmengen. ⓘ

Es gibt jedoch zwei wichtige Eigenschaften von Teilmengen, die sich nicht auf Unteralgebren im Allgemeinen übertragen lassen. Erstens: Obwohl die Teilmengen einer Menge eine Menge (und ein Gitter) bilden, kann es in einigen Klassen nicht möglich sein, die Unteralgebren einer Algebra als Algebra in dieser Klasse zu organisieren, obwohl sie immer als Gitter organisiert werden können. Zweitens: Während die Teilmengen einer Menge in Bijektion mit den Funktionen von dieser Menge zur Menge {0,1} = 2 stehen, gibt es keine Garantie, dass eine Klasse von Algebren eine Algebra enthält, die auf diese Weise die Rolle von 2 spielen kann. ⓘ

Bestimmte Klassen von Algebren weisen beide Eigenschaften auf. Die erste Eigenschaft ist häufiger anzutreffen, der Fall, dass beide Eigenschaften vorhanden sind, ist relativ selten. Eine Klasse, die beide Eigenschaften besitzt, ist die der Multigraphen. Bei zwei Multigraphen G und H besteht ein Homomorphismus h: G → H aus zwei Funktionen, von denen eine die Knoten auf die Knoten und die andere die Kanten auf die Kanten abbildet. Die Menge HG der Homomorphismen von G nach H kann dann als der Graph organisiert werden, dessen Scheitelpunkte und Kanten jeweils die in dieser Menge vorkommenden Scheitelpunkt- und Kantenfunktionen sind. Außerdem sind die Teilgraphen eines Multigraphen G in Bijektion mit den Graphenhomomorphismen von G zu dem Multigraphen Ω, der als vollständiger gerichteter Graph mit zwei Scheitelpunkten (also vier Kanten, nämlich zwei Selbstschleifen und zwei weitere Kanten, die einen Zyklus bilden) definiert werden kann, der um eine fünfte Kante, nämlich eine zweite Selbstschleife an einem der Scheitelpunkte, erweitert wird. Wir können also die Untergraphen von G als Multigraph ΩG organisieren, der als Potenzobjekt von G bezeichnet wird. ⓘ

Das Besondere an einem Multigraphen als Algebra ist, dass seine Operationen unär sind. Ein Multigraph hat zwei Arten von Elementen, die eine Menge V von Knoten und E von Kanten bilden, und hat zwei unäre Operationen s,t: E → V, die die Ausgangs- (Start) und Zielpunkte (Ende) jeder Kante angeben. Eine Algebra, deren Operationen alle unär sind, wird als Presheaf bezeichnet. Jede Klasse von Presheaves enthält eine Presheaf Ω, die für Unteralgebren die Rolle spielt, die 2 für Teilmengen spielt. Eine solche Klasse ist ein Spezialfall des allgemeineren Begriffs des elementaren Topos als einer Kategorie, die geschlossen (und darüber hinaus kartesisch geschlossen) ist und ein Objekt Ω, genannt Unterobjektklassifikator, besitzt. Obwohl der Begriff "Potenzobjekt" manchmal synonym mit dem Exponentialobjekt Y^X verwendet wird, wird in der Topostheorie gefordert, dass Y Ω ist. ⓘ

Funktoren und Quantoren

In der Kategorientheorie und der Theorie der elementaren Topoi kann der universelle Quantor als das rechte Adjungierte eines Funktors zwischen Potenzmengen verstanden werden, als inverser Bildfunktor einer Funktion zwischen Mengen; ebenso ist der Existenzquantor das linke Adjungierte. ⓘ

Beispiele

• ${\mathcal {P}}(\emptyset )=\{\emptyset \}$
• ${\mathcal {P}}(\{a\})={\bigl \{}\emptyset ,\{a\}{\bigr \}}$
• ${\mathcal {P}}(\{a,b\})={\bigl \{}\emptyset ,\{a\},\{b\},\{a,b\}{\bigr \}}$
• ${\mathcal {P}}(\{a,b,c\})={\bigl \{}\emptyset ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}{\bigr \}}$
• ${\mathcal {P}}({\mathcal {P}}(\emptyset ))={\bigl \{}\emptyset ,\{\emptyset \}{\bigr \}}$
• ${\mathcal {P}}({\mathcal {P}}(\{a\}))={\bigl \{}\emptyset ,\{\emptyset \},\{\{a\}\},\{\emptyset ,\{a\}\}{\bigr \}}$ ⓘ

Strukturen auf der Potenzmenge

Boolescher Verband

Zieht man noch die Komplementabbildung ${}^{\mathrm {c} }:{\mathcal {P}}(X)\rightarrow {\mathcal {P}}(X)$ heran, ist $({\mathcal {P}}(X),\cap ,\cup ,^{\mathrm {c} },\emptyset ,X)$ ein boolescher Verband, also ein distributiver und komplementärer Verband. ⓘ

Kommutativer Ring

Jeder boolesche Verband induziert eindeutig eine kommutative Ringstruktur, den sogenannten booleschen Ring. Hier auf ${\mathcal {P}}(X)$ ist die Ringaddition gegeben durch die symmetrische Differenz von Mengen, die Ringmultiplikation ist der Durchschnitt. Die leere Menge ist neutral für die Addition und $X$ ist neutral für die Multiplikation. ⓘ