Kartesisches Produkt

Grundidee und Definition

Das kartesische Produkt ist eine grundlegende Konstruktion der Mengenlehre: Aus gegebenen Mengen wird eine neue Menge gebildet. Beim Produkt zweier Mengen A und B entstehen alle geordneten Paare (a,b), bei denen a aus A und b aus B stammt. Formal gilt:

A × B := {(a,b) | a ∈ A, b ∈ B}.

Dabei wird jedes Element der ersten Menge mit jedem Element der zweiten Menge kombiniert. Die Reihenfolge ist festgelegt: Die erste Komponente kommt aus A, die zweite aus B. Deshalb wird A × B im Allgemeinen von B × A unterschieden. Das Produkt wird auch Produktmenge, Kreuzmenge oder Verbindungsmenge genannt; die Bezeichnung „Kreuzprodukt“ ist allerdings mehrdeutig.

Eine Menge kann auch mit sich selbst multipliziert werden:

A² = A × A = {(a,a′) | a,a′ ∈ A}.

Allgemeiner besteht das kartesische Produkt von n Mengen A₁,…,Aₙ aus allen n-Tupeln (a₁,…,aₙ), wobei jeweils aᵢ ∈ Aᵢ gilt:

A₁ × … × Aₙ := {(a₁,…,aₙ) | aᵢ ∈ Aᵢ für i = 1,…,n}.

Mit dem Produktzeichen schreibt man auch ∏ᵢ₌₁ⁿ Aᵢ = A₁ × … × Aₙ. Für das n-fache Produkt einer Menge A mit sich selbst gilt Aⁿ = A × … × A, wobei A insgesamt n-mal vorkommt.

Typische Beispiele und Anzahl der Elemente

Für A = {a,b,c} und B = {x,y} lautet das kartesische Produkt:

A × B = {(a,x),(a,y),(b,x),(b,y),(c,x),(c,y)}.

Dagegen ist B × A = {(x,a),(x,b),(x,c),(y,a),(y,b),(y,c)} eine andere Menge. Das Produkt A × A enthält alle neun möglichen Paare aus A.

Die reelle Zahlenebene ist das Produkt ℝ × ℝ = ℝ² = {(x,y) | x,y ∈ ℝ}. Die Paare (x,y) heißen kartesische Koordinaten. Für zwei reelle Intervalle entsteht ein Rechteck:

[a,b] × [c,d] = {(x,y) ∈ ℝ² | a ≤ x ≤ b, c ≤ y ≤ d}.

Entsprechend ergibt [a,b] × [c,d] × [e,f] einen Quader im dreidimensionalen Raum ℝ³. Allgemein ist ℝⁿ das n-fache kartesische Produkt der reellen Zahlen; das Produkt von n reellen Intervallen ergibt ein Hyperrechteck.

Auch Spielkarten lassen sich als Produkt beschreiben. Die Kartenwerte V = {A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2} haben 13 Elemente, die Kartensymbole S = {♣, ♠, ♥, ♦} haben 4 Elemente. Daher besteht V × S aus 13 · 4 = 52 Kartenpaaren, zum Beispiel (A,♣) oder (2,♦).

Bei einem Verkehrsnetz mit Linienarten L = {U,S} und Liniennummern N = {1,2,3,4,5,6,7} entstehen die 14 Kombinationen U1 bis U7 und S1 bis S7. Laut Artikel liegt ein vollständiges kartesisches Produkt nur vor, wenn die Anzahl der U-Bahnlinien und S-Bahnlinien gleich ist; andernfalls entsteht ein unvollständiges Produkt mit grundsätzlich anderen Eigenschaften.

Sind A und B endlich, gilt für die Anzahl der Elemente:

|A × B| = |A| · |B|.

Für A = B folgt |A²| = |A|². Allgemein gilt für endlich viele endliche Mengen:

|A₁ × … × Aₙ| = |A₁| · … · |Aₙ| = ∏ᵢ₌₁ⁿ |Aᵢ|.

Sind alle Mengen gleich A, gilt |Aⁿ| = |A|ⁿ. Ein Schachbrett besitzt beispielsweise 8² = 64 Felder, die durch ein Paar aus Buchstabe und Zahl identifiziert werden.

Leere Menge, Reihenfolge und Rechenregeln

Das kartesische Produkt ist genau dann leer, wenn mindestens eine der beteiligten Mengen leer ist:

A × B = ∅ ⇔ A = ∅ oder B = ∅.

Für nichtleere Mengen A und B mit A ≠ B ist das Produkt nicht kommutativ, also A × B ≠ B × A. Es gibt jedoch eine kanonische Bijektion, die die Paare vertauscht: (a,b) ↦ (b,a).

Auch die Assoziativität gilt im Allgemeinen nicht. Für nichtleere Mengen A, B und C sind

A × (B × C) ≠ (A × B) × C,

weil die Elemente links die Form (a,(b,c)) und rechts die Form ((a,b),c) haben. Die Abbildung (a,(b,c)) ↦ ((a,b),c) ist eine kanonische Bijektion. Manche Autoren identifizieren beide Schreibweisen mit dem geordneten Tripel (a,b,c); in diesem Sinn wirkt das Produkt assoziativ.

Das kartesische Produkt ist bezüglich Vereinigung, Schnitt und Differenz distributiv:

(A ∪ B) × C = (A × C) ∪ (B × C), (A ∩ B) × C = (A × C) ∩ (B × C), (A \ B) × C = (A × C) \ (B × C),

A × (B ∪ C) = (A × B) ∪ (A × C), A × (B ∩ C) = (A × B) ∩ (A × C), A × (B \ C) = (A × B) \ (A × C).

Für nichtleere Mengen gilt außerdem die Monotonie:

(A₁ × A₂) ⊆ (B₁ × B₂) ⇔ A₁ ⊆ B₁ und A₂ ⊆ B₂.

Ebenso gilt (A₁ × A₂) = (B₁ × B₂) genau dann, wenn A₁ = B₁ und A₂ = B₂. Das Komplement von A₁ × A₂ in B₁ × B₂ ist

(A₁ × A₂)ᶜ = (A₁ᶜ × A₂ᶜ) ∪ (A₁ᶜ × A₂) ∪ (A₁ × A₂ᶜ).

Für Schnitte gilt:

(A₁ ∩ A₂) × (B₁ ∩ B₂) = (A₁ × B₁) ∩ (A₂ × B₂).

Bei Vereinigungen gilt im Allgemeinen nur die Inklusion

(A₁ ∪ A₂) × (B₁ ∪ B₂) ⊇ (A₁ × B₁) ∪ (A₂ × B₂),

weil die linke Seite zusätzlich Paare aus A₁ × B₂ und A₂ × B₁ enthalten kann.

Endliche, leere und unendliche Produkte

Das Produkt von null Mengen ist nicht leer, sondern enthält genau ein Element: das leere Tupel (). Daher gilt

∏ᵢ₌₁⁰ Aᵢ = {()} und insbesondere A⁰ = {()}.

Die Vereinigung aller endlichen Produkte einer Menge A wird mit A* bezeichnet:

A* = ⋃ₙ₌₀∞ Aⁿ.

Sie enthält alle Tupel aus Elementen von A, einschließlich des leeren Tupels. Für A = {0,1} besteht A³ beispielsweise aus den acht 3-Tupeln (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0) und (1,1,1).

Enthält mindestens eine von zwei Mengen unendlich viele Elemente und ist die andere nicht leer, besitzt ihr Produkt unendlich viele Paare. Das Produkt zweier abzählbar unendlicher Mengen ist nach Cantors erstem Diagonalargument ebenfalls abzählbar. Ist mindestens eine Menge überabzählbar, ist auch das Produkt überabzählbar. Das Produkt endlich vieler abzählbar unendlicher Mengen ist ebenfalls abzählbar.

Für unendlich viele Mengen verwendet man eine Indexmenge I und eine Mengenfamilie (Aᵢ)ᵢ∈I:

∏ᵢ∈I Aᵢ = {f: I → ⋃ᵢ∈I Aᵢ | für alle i ∈ I gilt f(i) ∈ Aᵢ}.

Das Produkt besteht also aus allen Funktionen, die jedem Index i ein Element aus Aᵢ zuordnen. Sind alle Aᵢ gleich A, ist Aᴵ die Menge aller Funktionen von I nach A.

Für I = ℕ erhält man Folgen:

∏ᵢ₌₁∞ Aᵢ = {(a₁,a₂,…) | aᵢ ∈ Aᵢ für i ∈ ℕ}.

Sind alle Aᵢ = ℝ, entsteht ℝᴺ, die Menge aller Folgen reeller Zahlen. Jede solche Folge entspricht bijektiv einer Funktion f mit f(1) = a₁, f(2) = a₂ usw.

Die Frage, ob jedes kartesische Produkt nichtleerer Mengen selbst nichtleer ist, ist in der Zermelo-Fraenkel-Mengenlehre ZF nicht entscheidbar. Die Behauptung, dass dies gilt, ist eine Formulierung des Auswahlaxioms. Fügt man es zu ZF hinzu, erhält man ZFC („Zermelo-Fraenkel + Choice“).

Projektionen und abgeleitete Begriffe

Zu P = ∏ᵢ∈I Aᵢ gehören die Projektionen πᵢ: P → Aᵢ, die ein Tupel beziehungsweise eine Funktion α auf seine i-te Komponente abbilden: πᵢ(α) = α(i). Das Produkt besitzt eine universelle Eigenschaft: Für jede Menge X und jede Familie von Abbildungen fᵢ: X → Aᵢ gibt es genau eine Abbildung f: X → ∏ᵢ∈I Aᵢ, sodass für alle i gilt πᵢ ∘ f = fᵢ. Ist Q mit Abbildungen pᵢ: Q → Aᵢ ebenfalls durch diese Eigenschaft bestimmt, gibt es eine bijektive Abbildung P → Q.

Aus kartesischen Produkten ergeben sich mehrere wichtige Begriffe:

• Eine binäre Relation zwischen zwei Mengen ist eine Teilmenge ihres kartesischen Produkts. Eine n-stellige Relation ist entsprechend eine Teilmenge eines Produkts von n Mengen.
• Eine Projektion wählt aus einem Tupel eine oder mehrere Komponenten aus.
• Eine zweistellige Verknüpfung ist eine Abbildung vom kartesischen Produkt zweier Mengen in eine weitere Menge. Allgemein ist eine n-stellige Verknüpfung eine Abbildung von einem Produkt von n Mengen in eine weitere Menge.
• Ein direktes Produkt algebraischer Strukturen, etwa von Gruppen oder Vektorräumen, verwendet das kartesische Produkt der Trägermengen und versieht es mit komponentenweisen Verknüpfungen. Die direkte Summe ist bei unendlich vielen Mengen eine Teilmenge, deren Tupel nur an endlich vielen Stellen von einem bestimmten Element abweichen.
• Das kategorielle Produkt entspricht in der Kategorie der Mengen dem kartesischen Produkt und in der Kategorie der Gruppen sowie anderen Kategorien algebraischer Strukturen dem direkten Produkt.
• In relationalen Datenbanken werden kartesische Produkte von Tabellen und darauf aufbauende Join-Operationen zur Verknüpfung von Datenbanktabellen eingesetzt.