Kartesisches Produkt

Menge aller geordneten Paare von Elementen zweier Mengen

Das kartesische Produkt oder Mengenprodukt ist in der Mengenlehre eine grundlegende Konstruktion, aus gegebenen Mengen eine neue Menge zu erzeugen. Gelegentlich wird für das kartesische Produkt auch die mehrdeutige Bezeichnung „Kreuzprodukt“ verwendet. Das kartesische Produkt zweier Mengen ist die Menge aller geordneten Paare von Elementen der beiden Mengen, wobei die erste Komponente ein Element der ersten Menge und die zweite Komponente ein Element der zweiten Menge ist. Allgemeiner besteht das kartesische Produkt mehrerer Mengen aus der Menge aller Tupel von Elementen der Mengen, wobei die Reihenfolge der Mengen und damit der entsprechenden Elemente fest vorgegeben ist. Die Ergebnismenge des kartesischen Produkts wird auch Produktmenge, Kreuzmenge oder Verbindungsmenge genannt. Das kartesische Produkt ist nach dem französischen Mathematiker René Descartes benannt, der es zur Beschreibung des kartesischen Koordinatensystems verwendete und damit die analytische Geometrie begründete.

Das kartesische Produkt der beiden Mengen und

Produkt zweier Mengen

Bearbeiten

Definition

Bearbeiten

Das kartesische Produkt   (lies „A kreuz B“) zweier Mengen   und   ist definiert als die Menge aller geordneten Paare  , wobei   ein Element aus   und   ein Element aus   ist. Dabei wird jedes Element aus   mit jedem Element aus   kombiniert. Formal ist das kartesische Produkt durch

 

definiert. Insbesondere ist es auch möglich, das kartesische Produkt einer Menge mit sich selbst zu bilden und man schreibt dann

 .

Gelegentlich wird für das kartesische Produkt auch der Begriff „Kreuzprodukt“ verwendet, der jedoch weitere Bedeutungen hat, siehe Kreuzprodukt.

Die obige Definition ist problemlos auf (echte) Klassen   und   erweiterbar. Insbesondere erfolgt die Paarbildung nur für Elemente von   und  ; diese können keine echten Klassen sein und stellen an die Paarbildung keine besonderen Anforderungen.

Beispiele

Bearbeiten

Endliche Mengen

Bearbeiten
 
Das kartesische Produkt zweier Mengen   und   besteht aus allen möglichen geordneten Paaren von Elementen der Mengen.

Das kartesische Produkt   der beiden Mengen   und   ist

 .

Das kartesische Produkt   ist hingegen eine andere Menge, und zwar

 ,

da bei geordneten Paaren die Reihenfolge der Elemente eine Rolle spielt. Das kartesische Produkt von   mit sich selbst ist

 .

Reelle Zahlen

Bearbeiten

Die reelle Zahlenebene entsteht aus dem kartesischen Produkt der reellen Zahlen   mit sich selbst:

 .

Intervalle

Bearbeiten

Die Tupel   nennt man auch kartesische Koordinaten. Das kartesische Produkt zweier reeller Intervalle   und   ergibt das Rechteck

 .

Spielkarten

Bearbeiten

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   der Kartenwerte 13 Elemente, also  , und die Menge   der Kartensymbole hat 4 Elemente, also  . Daraus ergibt sich, dass die Menge   der Spielkarten   Elemente hat.

Dieses kartesische Produkt kann mit einer Tabelle dargestellt werden:

kartesisches Produkt aus Kartenwerten und Kartensymbolen
 
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

Bearbeiten

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  .

kartesisches Produkt aus Linienarten (U/S-Bahnlinien) und Liniennummern
  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.

Eigenschaften

Bearbeiten

Zahl der Elemente

Bearbeiten
  a b c d e f g h  
8                 8
7                 7
6                 6
5                 5
4                 4
3                 3
2                 2
1                 1
  a b c d e f g h  

Ein Schachbrett besitzt   Felder, die durch ein Paar aus Buchstaben der Linie und Zahl der Reihe identifiziert werden.

Sind die Mengen   und   endlich, dann ist ihr kartesisches Produkt   eine endliche Menge geordneter Paare. Die Anzahl der Paare entspricht dabei dem Produkt der Anzahlen der Elemente der Ausgangsmengen, das heißt

 

In dem Spezialfall, dass   ist, gilt

 .

Enthält zumindest eine der beiden Mengen   und   unendlich viele Elemente und ist die andere nicht leer, dann besteht ihr kartesisches Produkt   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

Bearbeiten

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

 ,

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

Nichtkommutativität

Bearbeiten

Das kartesische Produkt ist nicht kommutativ, das heißt, für nichtleere Mengen   und   mit   ist

 ,

denn in den Paaren der Menge   ist das erste Element aus   und das zweite aus  , während in den Paaren der Menge   das erste Element aus   und das zweite aus   ist. Es gibt allerdings eine kanonische Bijektion zwischen den beiden Mengen, nämlich

 ,

mit der die Mengen miteinander identifiziert werden können.

Nichtassoziativität

Bearbeiten

Das kartesische Produkt ist auch nicht assoziativ, das heißt, für nichtleere Mengen  ,   und   gilt im Allgemeinen

 ,

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

 .

Manche Autoren identifizieren die Paare   und   mit dem geordneten Tripel  , wodurch das kartesische Produkt auch assoziativ wird.

Distributivität

Bearbeiten
 
Illustration des ersten Distributivgesetzes

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

 

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

Bearbeiten

Das kartesische Produkt verhält sich monoton bezüglich Teilmengenbildung, das heißt, sind die Mengen   und   nichtleer, dann gilt

 .

Insbesondere gilt dabei Gleichheit

 .

Betrachtet man die Menge   als Grundmenge von   und die Menge   als Grundmenge von  , dann hat das Komplement von   in   die Darstellung

 .

Weitere Rechenregeln

Bearbeiten
 
Kartesische Produkte je zweier Intervalle, ihrer Schnitte und ihrer Vereinigungen

Es gilt zwar

 ,

aber im Allgemeinen ist

 ,

da die Menge auf der linken Seite Paare aus   und   enthält, die in der Menge auf der rechten Seite nicht enthalten sind.

Produkt endlich vieler Mengen

Bearbeiten

Definition

Bearbeiten

Allgemeiner ist das kartesische Produkt   von   Mengen   definiert als die Menge aller  -Tupel  , wobei   für   jeweils ein Element aus der Menge   ist. Formal ist das mehrfache kartesische Produkt durch

 

definiert. Mit Hilfe des Produktzeichens wird das mehrfache kartesische Produkt auch durch

 

notiert. Das  -fache kartesische Produkt einer Menge   mit sich selbst schreibt man auch als

 .

Leeres Produkt

Bearbeiten

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

 

Insbesondere ist für eine beliebige Menge  

 .

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

Vereinigung aller Produkte

Bearbeiten

Mit   bezeichnet man die Vereinigung aller  -fachen kartesischen Produkte einer Menge   mit sich selbst (für alle  ), also die Menge aller Tupel mit Elementen aus A, einschließlich des leeren Tupels:

 .

Beispiele

Bearbeiten

Ist  , dann ist

 .
 
In einem dreidimensionalen kartesischen Koordinatensystem wird jeder Punkt als Tripel   von Koordinaten dargestellt.

Der euklidische Raum   besteht aus dem dreifachen kartesischen Produkt der reellen Zahlen  :

 .

Die 3-Tupel   sind die dreidimensionalen kartesischen Koordinaten. Das kartesische Produkt dreier reeller Intervalle  ,   und   ergibt den Quader

 .

Allgemein ergibt das  -fache kartesische Produkt der reellen Zahlen den Raum   und das kartesische Produkt von   reellen Intervallen ein Hyperrechteck.

Eigenschaften

Bearbeiten

Zahl der Elemente

Bearbeiten

Sind die Mengen   alle endlich, dann ist ihr kartesisches Produkt ebenfalls eine endliche Menge, wobei die Anzahl der Elemente von   gleich dem Produkt der Elementzahlen der Ausgangsmengen ist, das heißt

 

bzw. in anderer Schreibweise

 .

In dem Spezialfall, dass alle Mengen   gleich einer Menge   sind, gilt

 .

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

Bearbeiten

Sind die Mengen   und   nichtleer, dann gilt wie beim kartesischen Produkt zweier Mengen Monotonie

 

und Gleichheit

 .

Produkt unendlich vieler Mengen

Bearbeiten

Definition

Bearbeiten

Es ist auch möglich, das kartesische Produkt unendlich vieler Mengen zu definieren. Ist dazu   eine Indexmenge und   eine Familie von Mengen, dann definiert man das kartesische Produkt der Mengen   durch

 .

Dies ist die Menge aller Abbildungen   von   in die Vereinigung der Mengen  , für die das Bild   in   liegt. Sind alle   gleich einer Menge  , dann ist das kartesische Produkt

 

die Menge aller Funktionen von   nach  . Sind die Mengen   unterschiedlich, so ist das kartesische Produkt allerdings weit weniger anschaulich. Bereits die Frage, ob ein beliebiges kartesisches Produkt nichtleerer Mengen nichtleer ist, ist mit der Zermelo-Fraenkel-Mengenlehre ZF nicht entscheidbar; die Behauptung, dass es nichtleer ist, ist eine Formulierung des Auswahlaxioms, welches zu ZF hinzugefügt wird, um die Mengenlehre ZFC („Zermelo-Fraenkel + Choice“) zu erhalten.

Spezialfälle

Bearbeiten

Ein wichtiger Spezialfall eines unendlichen kartesischen Produkts entsteht durch die Wahl der natürlichen Zahlen   als Indexmenge. Das kartesische Produkt einer Folge von Mengen  

 

entspricht dann der Menge aller Folgen, deren  -tes Folgenglied in der Menge   liegt. Sind beispielsweise alle  , dann ist

 

die Menge aller reeller Zahlenfolgen. Das abzählbare kartesische Produkt lässt sich bijektiv auf das allgemein definierte kartesische Produkt abbilden, denn jede Folge   definiert eine Funktion   mit   und umgekehrt lässt sich jede solche Funktion als Folge   schreiben. Auch das kartesische Produkt endlich vieler Mengen lässt sich unter Verwendung endlicher Folgen als Spezialfall der allgemeinen Definition auffassen.

Universelle Eigenschaft des kartesischen Produktes

Bearbeiten

Zu dem kartesischen Produkt   gehört die Familie der Projektionen  . Das kartesische Produkt   zusammen mit der Familie   hat die folgende Eigenschaft: Ist   eine beliebige Menge und ist   eine Familie von Abbildungen, so gibt es genau eine Abbildung   mit   für alle  . Das heißt, folgendes Diagramm ist kommutativ:

 
Es gibt genau ein  , so dass für alle   gilt:  

Ist   zusammen mit der Familie   auch diese Eigenschaft, so gibt es eine bijektive Abbildung  .

Abgeleitete Begriffe

Bearbeiten
  • Eine binäre Relation zwischen zwei Mengen ist eine Teilmenge des kartesischen Produkts der beiden Mengen. Insbesondere ist damit jede Abbildung eine Teilmenge des kartesischen Produkts aus Definitions- und Zielmenge der Abbildung. Allgemeiner ist eine  -stellige Relation eine Teilmenge des kartesischen Produkts von   Mengen.
  • Eine Projektion ist eine Abbildung von dem kartesischen Produkt zweier Mengen zurück in eine dieser Mengen. Allgemeiner ist eine Projektion eine Abbildung von dem kartesischen Produkt einer Familie von Mengen auf das kartesische Produkt einer Teilfamilie dieser Mengen, die Elemente mit bestimmten Indizes auswählt.
  • Eine zweistellige Verknüpfung ist eine Abbildung von dem kartesischen Produkt zweier Mengen in eine weitere Menge. Allgemeiner ist eine  -stellige Verknüpfung eine Abbildung von dem kartesischen Produkt von   Mengen in eine weitere Menge. Jede  -stellige Verknüpfung kann somit auch als  -stellige Relation aufgefasst werden.
  • Ein direktes Produkt ist ein Produkt algebraischer Strukturen, wie zum Beispiel von Gruppen oder Vektorräumen, das aus dem kartesischen Produkt der Trägermengen besteht und zusätzlich mit ein oder mehreren komponentenweisen Verknüpfungen versehen ist. Eine direkte Summe ist eine Teilmenge des direkten Produkts, die sich nur für Produkte unendlich vieler Mengen vom direkten Produkt unterscheidet; sie besteht aus allen Tupeln, die nur an endlich vielen Stellen von einem bestimmten Element (meist dem neutralen Element einer Verknüpfung) verschieden sind.
  • Das kategorielle Produkt entspricht in der Kategorie der Mengen dem kartesischen Produkt und in der Kategorie der Gruppen sowie in anderen Kategorien algebraischer Strukturen dem direkten Produkt.
  • In relationalen Datenbanken werden das kartesische Produkt von Tabellen und die darauf aufbauenden Join-Operationen zur Verknüpfung von Datenbanktabellen eingesetzt.

Literatur

Bearbeiten
Bearbeiten