Endliche Mengen

Das kartesische Produkt ${\displaystyle A\times B}$ der beiden Mengen ${\displaystyle A=\{a,b,c\}}$ und ${\displaystyle B=\{x,y\}}$ ist

${\displaystyle A\times B=\left\{(a,x),(a,y),(b,x),(b,y),(c,x),(c,y)\right\}}$.

Das kartesische Produkt ${\displaystyle B\times A}$ ist hingegen eine andere Menge, und zwar

${\displaystyle B\times A=\left\{(x,a),(x,b),(x,c),(y,a),(y,b),(y,c)\right\}}$,

da bei geordneten Paaren die Reihenfolge der Elemente eine Rolle spielt. Das kartesische Produkt von ${\displaystyle A}$ mit sich selbst ist

${\displaystyle A\times A=\left\{(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)\right\}}$.

Reelle Zahlen

Die reelle Zahlenebene entsteht aus dem kartesischen Produkt der reellen Zahlen ${\displaystyle \mathbb {R} }$ mit sich selbst:

${\displaystyle \mathbb {R} \times \mathbb {R} =\mathbb {R} ^{2}=\{(x,y)\mid x,y\in \mathbb {R} \}}$.

Intervalle

Die Tupel ${\displaystyle (x,y)}$ nennt man auch kartesische Koordinaten. Das kartesische Produkt zweier reeller Intervalle ${\displaystyle [a,b]}$ und ${\displaystyle [c,d]}$ ergibt das Rechteck

${\displaystyle [a,b]\times [c,d]=\{(x,y)\in \mathbb {R} ^{2}\mid a\leq x\leq b,c\leq y\leq d\}}$.

Spielkarten

Spielkarten, wie sie zum Beispiel beim Texas Hold’em, beim Canasta, beim Doppelkopf und beim Skat verwendet werden, sind ein Beispiel für ein kartesisches Produkt. Die erste Menge ist in diesem Fall die Menge der Kartenwerte, zum Beispiel V = {A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2}, und die zweite Menge ist die Menge der Kartensymbole, zum Beispiel S = {♣, ♠, ♥, ♦}. Die Menge der Spielkarten ist dann das kartesische Produkt dieser beiden Mengen: V × S = {(A, ♣), (A, ♠), (A, ♥), (A, ♦), (K, ♣), ..., (3, ♦), (2, ♣), (2, ♠), (2, ♥), (2, ♦)}.

In diesem Beispiel hat die Menge ${\displaystyle V}$ der Kartenwerte 13 Elemente, also ${\displaystyle |V|=13}$, und die Menge ${\displaystyle S}$ der Kartensymbole hat 4 Elemente, also ${\displaystyle |S|=4}$. Daraus ergibt sich, dass die Menge ${\displaystyle V\times S}$ der Spielkarten ${\displaystyle |V\times S|=|V|\cdot |S|=13\cdot 4=52}$ Elemente hat.

Dieses kartesische Produkt kann mit einer Tabelle dargestellt werden:

kartesisches Produkt aus Kartenwerten und Kartensymbolen
${\displaystyle V\times S}$	♣	♠	♥	♦
A	(A, ♣)	(A, ♠)	(A, ♥)	(A, ♦)
K	(K, ♣)	(K, ♠)	(K, ♥)	(K, ♦)
Q	(Q, ♣)	(Q, ♠)	(Q, ♥)	(Q, ♦)
J	(J, ♣)	(J, ♠)	(J, ♥)	(J, ♦)
10	(10, ♣)	(10, ♠)	(10, ♥)	(10, ♦)
...	...	...	...	...
3	(3, ♣)	(3, ♠)	(3, ♥)	(3, ♦)
2	(2, ♣)	(2, ♠)	(2, ♥)	(2, ♦)

U-Bahnlinien oder S-Bahnlinien

Bei Verkehrsnetzen, die aus U-Bahnlinien und S-Bahnlinien bestehen, ist die Menge der Verkehrslinien ein kartesisches Produkt, das zum Beispiel aus der Menge L = {U, S} der Linienarten und der Menge N = {1, 2, 3, 4, 5, 6, 7} der Liniennummern gebildet werden kann. Hier ist ${\displaystyle |L\times N|=|L|\cdot |N|=2\cdot 7=14}$.

kartesisches Produkt aus Linienarten (U/S-Bahnlinien) und Liniennummern
${\displaystyle L\times N}$	1	2	3	4	5	6	7
	U1	U2	U3	U4	U5	U6	U7
	S1	S2	S3	S4	S5	S6	S7

Hinweise:

Es ergibt sich nur dann ein (vollständiges) kartesisches Produkt, wenn die Anzahl der U-Bahnlinien und S-Bahnlinien gleich ist. Ansonsten ergibt sich ein unvollständiges kartesisches Produkt, das grundsätzlich andere Eigenschaften hat. Im Bereich der Informatik und Programmierung ist dieses Thema zum Beispiel unter Array - Dimensionen zu finden.

Zahl der Elemente

Sind die Mengen ${\displaystyle A}$ und ${\displaystyle B}$ endlich, dann ist ihr kartesisches Produkt ${\displaystyle A\times B}$ eine endliche Menge geordneter Paare. Die Anzahl der Paare entspricht dabei dem Produkt der Anzahlen der Elemente der Ausgangsmengen, das heißt

${\displaystyle |A\times B|=|A|\cdot |B|}$

In dem Spezialfall, dass ${\displaystyle A=B}$ ist, gilt

${\displaystyle |A^{2}|=|A|^{2}}$.

Enthält zumindest eine der beiden Mengen ${\displaystyle A}$ und ${\displaystyle B}$ unendlich viele Elemente und ist die andere nicht leer, dann besteht ihr kartesisches Produkt ${\displaystyle A\times B}$ aus unendlich vielen Paaren. Das kartesische Produkt zweier abzählbar unendlicher Mengen ist dabei nach Cantors erstem Diagonalargument ebenfalls abzählbar. Ist zumindest eine der beiden Mengen überabzählbar, so ist auch ihre Produktmenge überabzählbar.

Leere Menge

Da aus der leeren Menge kein Element ausgewählt werden kann, ergibt das kartesische Produkt der leeren Menge mit einer beliebigen Menge wieder die leere Menge. Allgemeiner gilt

${\displaystyle A\times B=\emptyset ~\Longleftrightarrow ~A=\emptyset ~{\text{oder}}~B=\emptyset }$,

das heißt, das kartesische Produkt zweier Mengen ist genau dann leer, wenn zumindest eine der beiden Mengen leer ist.

Nichtkommutativität

Das kartesische Produkt ist nicht kommutativ, das heißt, für nichtleere Mengen ${\displaystyle A}$ und ${\displaystyle B}$ mit ${\displaystyle A\neq B}$ ist

${\displaystyle A\times B\neq B\times A}$,

denn in den Paaren der Menge ${\displaystyle A\times B}$ ist das erste Element aus ${\displaystyle A}$ und das zweite aus ${\displaystyle B}$, während in den Paaren der Menge ${\displaystyle B\times A}$ das erste Element aus ${\displaystyle B}$ und das zweite aus ${\displaystyle A}$ ist. Es gibt allerdings eine kanonische Bijektion zwischen den beiden Mengen, nämlich

${\displaystyle A\times B\to B\times A,\quad (a,b)\mapsto (b,a)}$,

mit der die Mengen miteinander identifiziert werden können.

Nichtassoziativität

Das kartesische Produkt ist auch nicht assoziativ, das heißt, für nichtleere Mengen ${\displaystyle A}$, ${\displaystyle B}$ und ${\displaystyle C}$ gilt im Allgemeinen

${\displaystyle A\times \left(B\times C\right)\neq \left(A\times B\right)\times C}$,

denn die Menge auf der linken Seite enthält Paare, deren erstes Element aus ${\displaystyle A}$ und deren zweites Element ein Paar aus ${\displaystyle B\times C}$ ist, wohingegen die Menge auf der rechten Seite Paare enthält, deren erstes Element ein Paar aus ${\displaystyle A\times B}$ und deren zweites Element aus ${\displaystyle C}$ ist. Auch hier gibt es eine kanonische Bijektion zwischen diesen beiden Mengen, nämlich

${\displaystyle A\times \left(B\times C\right)\to \left(A\times B\right)\times C,\quad (a,(b,c))\mapsto ((a,b),c)}$.

Manche Autoren identifizieren die Paare ${\displaystyle (a,(b,c))}$ und ${\displaystyle ((a,b),c)}$ mit dem geordneten Tripel ${\displaystyle (a,b,c)}$, wodurch das kartesische Produkt auch assoziativ wird.

Distributivität

Für das kartesische Produkt gelten die folgenden Distributivgesetze bezüglich Vereinigung, Schnitt und Differenzbildung von Mengen:

${\displaystyle {\begin{aligned}\left(A\cup B\right)\times C&=\left(A\times C\right)\cup \left(B\times C\right)\\\left(A\cap B\right)\times C&=\left(A\times C\right)\cap \left(B\times C\right)\\\left(A\setminus B\right)\times C&=\left(A\times C\right)\setminus \left(B\times C\right)\\A\times \left(B\cup C\right)&=\left(A\times B\right)\cup \left(A\times C\right)\\A\times \left(B\cap C\right)&=\left(A\times B\right)\cap \left(A\times C\right)\\A\times \left(B\setminus C\right)&=\left(A\times B\right)\setminus \left(A\times C\right)\end{aligned}}}$

Das vierte Gesetz kann verwendet werden, um die Distributivität bei den Natürlichen Zahlen zu beweisen, wenn diese über Kardinalzahlen definiert sind.

Monotonie und Komplement

Das kartesische Produkt verhält sich monoton bezüglich Teilmengenbildung, das heißt, sind die Mengen ${\displaystyle A_{1},A_{2},B_{1}}$ und ${\displaystyle B_{2}}$ nichtleer, dann gilt

${\displaystyle (A_{1}\times A_{2})\subseteq (B_{1}\times B_{2})~\Longleftrightarrow ~A_{1}\subseteq B_{1}~{\text{und}}~A_{2}\subseteq B_{2}}$.

Insbesondere gilt dabei Gleichheit

${\displaystyle (A_{1}\times A_{2})=(B_{1}\times B_{2})~\Longleftrightarrow ~A_{1}=B_{1}~{\text{und}}~A_{2}=B_{2}}$.

Betrachtet man die Menge ${\displaystyle B_{1}}$ als Grundmenge von ${\displaystyle A_{1}}$ und die Menge ${\displaystyle B_{2}}$ als Grundmenge von ${\displaystyle A_{2}}$, dann hat das Komplement von ${\displaystyle A_{1}\times A_{2}}$ in ${\displaystyle B_{1}\times B_{2}}$ die Darstellung

${\displaystyle (A_{1}\times A_{2})^{\mathsf {C}}=(A_{1}^{\mathsf {C}}\times A_{2}^{\mathsf {C}})\cup (A_{1}^{\mathsf {C}}\times A_{2})\cup (A_{1}\times A_{2}^{\mathsf {C}})}$.

Weitere Rechenregeln

Es gilt zwar

${\displaystyle \left(A_{1}\cap A_{2}\right)\times \left(B_{1}\cap B_{2}\right)=\left(A_{1}\times B_{1}\right)\cap \left(A_{2}\times B_{2}\right)}$,

aber im Allgemeinen ist

${\displaystyle \left(A_{1}\cup A_{2}\right)\times \left(B_{1}\cup B_{2}\right)\supseteq \left(A_{1}\times B_{1}\right)\cup \left(A_{2}\times B_{2}\right)}$,

da die Menge auf der linken Seite Paare aus ${\displaystyle A_{1}\times B_{2}}$ und ${\displaystyle A_{2}\times B_{1}}$ enthält, die in der Menge auf der rechten Seite nicht enthalten sind.

Leeres Produkt

Das kartesische Produkt von null Mengen ist die Menge, die als einziges Element das leere Tupel enthält, das heißt

${\displaystyle \prod _{i=1}^{0}A_{i}=\{()\}.}$

Insbesondere ist für eine beliebige Menge ${\displaystyle A}$

${\displaystyle A^{0}=\{()\}}$.

Davon wird Gebrauch gemacht, wenn Konstanten einer mathematischen Struktur als nullstellige Verknüpfungen betrachtet werden.

Vereinigung aller Produkte

Mit ${\displaystyle A^{*}}$ bezeichnet man die Vereinigung aller ${\displaystyle n}$-fachen kartesischen Produkte einer Menge ${\displaystyle A}$ mit sich selbst (für alle ${\displaystyle n\in \mathbb {N} }$), also die Menge aller Tupel mit Elementen aus A, einschließlich des leeren Tupels:

${\displaystyle A^{*}=\bigcup _{n=0}^{\infty }A^{n}}$.

Zahl der Elemente

Sind die Mengen ${\displaystyle A_{1},\dotsc ,A_{n}}$ alle endlich, dann ist ihr kartesisches Produkt ebenfalls eine endliche Menge, wobei die Anzahl der Elemente von ${\displaystyle A_{1}\times \dotsb \times A_{n}}$ gleich dem Produkt der Elementzahlen der Ausgangsmengen ist, das heißt

${\displaystyle |A_{1}\times \dotsb \times A_{n}|=|A_{1}|\cdot \ldots \cdot |A_{n}|}$

bzw. in anderer Schreibweise

${\displaystyle \left|\prod _{i=1}^{n}A_{i}\right|=\prod _{i=1}^{n}|A_{i}|}$.

In dem Spezialfall, dass alle Mengen ${\displaystyle A_{i}}$ gleich einer Menge ${\displaystyle A}$ sind, gilt

${\displaystyle |A^{n}|=|A|^{n}}$.

Das kartesische Produkt endlich vieler abzählbar unendlicher Mengen ist ebenfalls abzählbar, wie sich durch Iteration des Arguments für das kartesische Produkt zweier Mengen mit Hilfe der Cantorschen Tupelfunktion zeigen lässt.

Monotonie

Sind die Mengen ${\displaystyle A_{1},\ldots ,A_{n}}$ und ${\displaystyle B_{1},\ldots ,B_{n}}$ nichtleer, dann gilt wie beim kartesischen Produkt zweier Mengen Monotonie

${\displaystyle \prod _{i=1}^{n}A_{i}\subseteq \prod _{i=1}^{n}B_{i}~\Longleftrightarrow ~A_{i}\subseteq B_{i}~{\text{für}}~i=1,\ldots ,n}$

und Gleichheit

${\displaystyle \prod _{i=1}^{n}A_{i}=\prod _{i=1}^{n}B_{i}~\Longleftrightarrow ~A_{i}=B_{i}~{\text{für}}~i=1,\ldots ,n}$.