Mathe für Nicht-Freaks: Mengenlehre: Kartesisches Produkt

Geordnetes Paar und Tupel

Wie können Listen in der Mathematik beschrieben werden? Im Abschnitt „Mengenlehre“ hast du erfahren, wie du in der Mathematik Ansammlungen von Objekten mit Hilfe von Mengen beschreiben kannst. Nun möchte ich dir zeigen, wie du endliche Listen von Objekten beschreiben kannst, welche man als Tupel bezeichnet. Der wesentliche Unterschied von Listen zu Mengen ist der, dass bei Listen auch die Reihenfolge der Objekte entscheidend ist. So sind zwei Listen dann und nur dann gleich, wenn sie dieselben Objekte in derselben Reihenfolge und Anzahl besitzen. Zur Erinnerung: Bei Mengen (aufgeschrieben in der aufzählenden Mengenschreibweise) ist die Reihenfolge ihrer Elemente für die Identität zweier Mengen irrelevant. So ist etwa $\{1,2,3,4\} = \{3,4,2,1\}$.

Eine Liste von Objekten wird Tupel genannt. Die einzelnen Objekte eines Tupels sind seine Komponenten. Die Schreibweise für eine endliche Liste von $n$ Objekten $x_1$ bis $x_n$ ist $(x_1,\, x_2,\, \dots,\, x_n)$. Die einzelnen Komponenten eines Tupels werden also durch Kommata „,“ (oder auch Semikolons „;“ getrennt) und in runden Klammern $()$ zusammengefasst. Wie bereits gesagt, ist die Reihenfolge der Komponenten eines Tupels wichtig. So sind zwei Tupel dann und nur dann gleich, wenn sie dieselben Objekte in derselben Reihenfolge und Anzahl besitzen. Dies bedeutet:

$(x_1,\, x_2,\, \dots,\, x_n) = (y_1,\, y_2,\, \dots,\, y_m) :\Leftrightarrow n = m \,\and\, x_1 = y_1 \,\and\, x_2 = y_2 \,\and\, \dots \,\and\, x_n = y_m$

In Übersetzung:

$\underbrace{(x_1,\, x_2,\, \dots,\, x_n) = (y_1,\, y_2,\, \dots,\, y_m)}_{\text{Tupel }(x_1,\, x_2,\, \dots,\, x_n)\text{ ist gleich dem Tupel }(y_1,\, y_2,\, \dots,\, y_m)} \underbrace{:\Leftrightarrow{\color{White})}}_{\text{ genau dann, wenn }} \underbrace{n = m{\color{White})}}_\text{sie dieselbe Anzahl von Objekten} \underbrace{\,\and\,{\color{White})}}_\text{und} \underbrace{x_1 = y_1 \,\and\, x_2 = y_2 \,\and\, \dots \,\and\, x_n = y_m{\color{White})}}_\text{dieselben Objekte in derselben Reihenfolge besitzen.}$

Wenn du deutlich machen möchtest, dass ein Tupel $n$ Komponenten besitzt, so kannst du ihn $n$-Tupel nennen. So nennt man ein Tupel mit 2 Komponenten „2-Tupel“, ein Tupel mit 3 Komponenten „3-Tupel“ und so weiter.

Es gibt einen besonderen Name für 2-Tupel. Sie werden geordnetes Paar oder kurz Paar genannt. Geordnete Paare $(a,\,b)$ sind also 2-komponentige Listen mit der ersten Komponente $a$ und der zweiten Komponente $b$.

Verständnisfrage: Welche Bedingungen müssen $x$ und $y$ besitzen, damit folgende Paare gleich sind?

1. $(x,x)$ und $(x)$
2. $(x,y)$ und $(y,x)$
3. $(1,2)$ und $(x,y)$

1. Für alle $x$ ist $(x,x) \ne (x)$, da zwei Tupel nur dann identisch sein können, wenn sie dieselbe Anzahl an Elementen besitzen.
2. Es ist $(x,y)=(y,x)$ genau dann, wenn $x=y$.
3. Es ist $(1,2)=(x,y)$ genau dann, wenn $x=1$ und $y=2$.

Verständnisfrage: Welche Bedingungen müssen die Objekte $a$, $b$, $c$ und $d$ erfüllen, damit die Paare $(a,b)$ und $(c,d)$ gleich sind?

Damit zwei Paare $(a,b)$ und $(c,d)$ gleich sind, muss $a=c$ und $b=d$ sein:

$(a,b) = (c,d) :\Leftrightarrow a=c \and b=d$

Wir fassen zusammen:

Definition (Tupel): Ein Tupel $(x_1,\, x_2,\, \dots ,\, x_n)$ ist eine endliche Liste der $n$ Objekte $x_1$ bis $x_n$. Das Objekt $x_k$ des Tupels wird seine $k$te Komponente genannt. Zwei Tupel $(x_1,\, x_2,\, \dots,\, x_n)$ und $(y_1,\, y_2,\, \dots,\, y_m)$ sind dann und nur dann identisch, wenn sie dieselben Objekte in derselben Reihenfolge und Anzahl besitzen: $(x_1,\, x_2,\, \dots,\, x_n) = (y_1,\, y_2,\, \dots,\, y_m) :\Leftrightarrow n = m \,\and\, \forall k\in\{1,\,2,\,\dots ,\,n\}:\, x_k = y_k$

Definition (geordnetes Paar): Ein geordnetes Paar $(a,b)$ ist ein 2-Tupel, also eine Liste mit genau 2 Komponenten. Zwei geordnete Paare $(a,b)$ und $(c,d)$ sind genau dann gleich, wenn $a=c$ und $b=d$ ist.

Modellierung durch Mengen

Oft werden neu eingeführte Objekte auf bereits bekannte Objekte zurückgeführt, indem die neuen Objekte mit Hilfe der bereits bekannten Objekte definiert werden. Diese Zurückführung kann später in Beweisen genutzt werden.

Bisher haben wir nur Mengen als Objekte der Mathematik kennen gelernt. Wie können also geordnete Paare und Tupel im Allgemeinen als Mengen definiert werden? Die wesentliche Eigenschaft von Tupeln ist die, dass $(x_1,\, x_2,\, \dots,\, x_n) = (y_1,\, y_2,\, \dots,\, y_m)$ dann und nur dann ist, wenn $n=m$ und $x_k=y_k$ für alle natürlichen Zahlen $k$ mit $1\le k \le n = m$ ist. Diese Eigenschaft muss auch eine Definition von Tupeln mit Hilfe von Mengen erfüllen.

Hierzu gibt es folgende rekursive Definition des Tupels:

Definition (Definition von Tupel durch Mengen): Tupel sind rekursiv definiert durch: Rekursionsanfang: $() := \emptyset$ Rekursionsschritt: $(x_1,\, x_2,\, \dots,\, x_n,\,x_{n+1}) = \{ (x_1,\, x_2,\, \dots,\, x_n),\, \{x_{n+1}\} \}$

Die Wirkungsweise dieser rekursiven Definition lässt mit Hilfe der folgenden Animation nachvollziehen:

Verständnisfrage: Wie sind folgende Tupel durch obige Definition durch Mengen ausdrückbar?

1. $(1)$
2. $(a,b)$
3. $(())$

Tupel $(1)$:

$\begin{array}{llll} & (1) & \left|\ (1) = \{ (),\, \{ 1 \} \} \right. & \text{(Rekursionsschritt)} \\[5px] =\ & \{ (),\, \{ 1 \} \} & \left|\ () = \emptyset \right. & \text{(Rekursionsanfang)} \\[5px] =\ & \{ \emptyset,\, \{ 1 \} \} \end{array}$

Tupel $(a,b)$:

$\begin{array}{llll} & (a,b) & \left|\ (a,b) = \{ (a),\, \{ b \} \} \right. & \text{(Rekursionsschritt)} \\[5px] =\ & \{ (a),\, \{ b \} \} & \left|\ (a) = \{ (),\, \{ a \} \} \right. & \text{(Rekursionsschritt)} \\[5px] =\ & \{ \{ (),\, \{ a \} \},\, \{ b \} \} & \left|\ () = \emptyset \right. & \text{(Rekursionsanfang)} \\[5px] =\ & \{ \{ \emptyset,\, \{ a \} \},\, \{ b \} \} \end{array}$

Tupel $(())$:

$\begin{array}{llll} & (()) & \left|\ () = \emptyset \right. & \text{(Rekursionsanfang)} \\[5px] =\ & (\emptyset) & \left|\ (\emptyset) = \{ (),\, \{ \emptyset \} \} \right. & \text{(Rekursionsschritt)} \\[5px] =\ & \{ (),\, \{ \emptyset \} \} & \left|\ () = \emptyset \right. & \text{(Rekursionsanfang)} \\[5px] =\ & \{ \emptyset,\, \{ \emptyset \} \} \end{array}$

Wir haben noch nicht gezeigt, dass unsere obige Definition von Tupel über Mengen auch die wesentliche Eigenschaft von Tupel erfüllt, nämlich dass zwei Tupel dann und nur dann identisch sind, wenn sie dieselben Objekte in derselben Anzahl und Reihenfolge besitzen. Wir müssen also noch folgenden Satz zeigen:

Satz (Identität von Tupeln): Zwei Tupel $(x_1,\, x_2,\, \dots,\, x_n)$ und $(y_1,\, y_2,\, \dots,\, y_m)$ sind dann und nur dann identisch, wenn sie dieselben Objekte in derselben Reihenfolge und Anzahl besitzen: $(x_1,\, x_2,\, \dots,\, x_n) = (y_1,\, y_2,\, \dots,\, y_m) :\Leftrightarrow n = m \,\and\, \forall k\in\{1,\,2,\,\dots ,\,n\}:\, x_k = y_k$

Diesen Satz werden wir über vollständige Induktion beweisen:

Beweis (Identität von Tupeln): Zu beweisende Aussage: $(x_1,\, x_2,\, \dots,\, x_n) = (y_1,\, y_2,\, \dots,\, y_m) \Leftrightarrow n = m \,\and\, \forall k\in\{1,\,2,\,\dots ,\,n\}:\, x_k = y_k$ Induktionsvariable: $n$ Induktionsanfang: Sei $n=0$. Wir müssen zeigen $() = (y_1,\, y_2,\, \dots,\, y_m) \Leftrightarrow 0 = m \,\and\, \underbrace{\forall k\in\underbrace{\{1,\,2,\,\dots ,\,0\}}_\text{leere Menge}:\, x_k = y_k}_{\text{immer erf}\ddot \mathrm u\text{llt}}$ also $() = (y_1,\, y_2,\, \dots,\, y_m) \Leftrightarrow 0 = m$ Für $m=0$ ist $() = (y_1,\, y_2,\, \dots,\, y_m)$ eine direkte Folgerung, so dass wir nur noch die Implikation $() = (y_1,\, y_2,\, \dots,\, y_m) \Rightarrow 0 = m$ zeigen müssen. Nun ist nach Rekursionsanfang $() = \emptyset$, so dass wir die Implikation $\emptyset = (y_1,\, y_2,\, \dots,\, y_m) \Rightarrow 0 = m$ zeigen müssen (die Implikation $\emptyset = (y_1,\, y_2,\, \dots,\, y_m) \Leftarrow 0 = m$ haben wir gerade gezeigt). Sei also $\emptyset = (y_1,\, y_2,\, \dots,\, y_m)$. Da für $m>0$ nach dem Rekursionsschritt $(y_1,\, y_2,\, \dots,\, y_m)=\{ (y_1,\, y_2,\, \dots,\, y_{m-1}),\, \{y_m\}\}$ ist, ist für $m>0$ die Menge $(y_1,\, y_2,\, \dots,\, y_m)$ zweielementig und somit nicht leer. Weil aber nach Voraussetzung $\emptyset = (y_1,\, y_2,\, \dots,\, y_m)$ ist, kann $m$ nicht größer als 0 sein, da wir sonst einen Widerspruch erhalten würden. Damit ist $m=0$, da $m$ nur natürliche Zahlen größer gleich 0 annehmen kann. nice. Induktionsschritt: Nun müssen wir folgende Aussage beweisen $(x_1,\, x_2,\, \dots,\, x_{n+1}) = (y_1,\, y_2,\, \dots,\, y_m) \Leftrightarrow n+1 = m \,\and\, \forall k\in\{1,\,2,\,\dots ,\,n+1\}:\, x_k = y_k$ Auch hier ist folgende Implikation eine direkte Folgerung: $(x_1,\, x_2,\, \dots,\, x_{n+1}) = (y_1,\, y_2,\, \dots,\, y_m) \Leftarrow n+1 = m \,\and\, \forall k\in\{1,\,2,\,\dots ,\,n+1\}:\, x_k = y_k$ Damit müssen wir noch beweisen: $(x_1,\, x_2,\, \dots,\, x_{n+1}) = (y_1,\, y_2,\, \dots,\, y_m) \Rightarrow n+1 = m \,\and\, \forall k\in\{1,\,2,\,\dots ,\,n+1\}:\, x_k = y_k$ Sei also $(x_1,\, x_2,\, \dots,\, x_{n+1}) = (y_1,\, y_2,\, \dots,\, y_m)$. Da $n+1>0$ ist, ist nach dem Rekursionsschritt $(x_1,\, x_2,\, \dots,\, x_{n+1}) = \{ (x_1,\, x_2,\, \dots,\, x_{n}),\, \{x_{n+1}\}\}$ und damit nicht leer. Da $(y_1,\, y_2,\, \dots,\, y_m)$ für $m=0$ leer wäre, muss $m>0$ sein. Nach Anwendung des Rekursionsschritt erhalten wir aus der Voraussetzung $(x_1,\, x_2,\, \dots,\, x_{n+1}) = (y_1,\, y_2,\, \dots,\, y_m)$ die Gleichung: $\{ (x_1,\, x_2,\, \dots,\, x_{n}),\, \{x_{n+1}\}\} = \{ (y_1,\, y_2,\, \dots,\, y_{m-1}),\, \{y_m\}\}$ Weil $(x_1,\, x_2,\, \dots,\, x_n)$ für $n>0$ zweielementig und für $n=0$ leer ist, ist $(x_1,\, x_2,\, \dots,\, x_n)\ne \{x_{n+1}\}$ und $(x_1,\, x_2,\, \dots,\, x_n)\ne \{y_m\}$. Analog ist $(y_1,\, y_2,\, \dots,\, y_{m-1})\ne \{x_{n+1}\}$ und $(y_1,\, y_2,\, \dots,\, y_{m-1})\ne \{y_m\}$. Damit gilt obige Gleichung nur dann, wenn $(x_1,\, x_2,\, \dots,\, x_{n}) = (y_1,\, y_2,\, \dots,\, y_{m-1})$ und $\{x_{n+1}\}=\{y_m\}$. Aus $(x_1,\, x_2,\, \dots,\, x_{n}) = (y_1,\, y_2,\, \dots,\, y_{m-1})$ folgt $n=m-1$ also $n+1=m$ und $x_k=y_k$ für alle natürlichen $k$ mit $1\ge k\ge n$. Aus $\{x_{n+1}\}=\{y_m\}$ folgt $x_{n+1}=y_m$ und damit $x_k=y_k$ für alle $1\ge k \ge n+1$.

Kartesisches Produkt

Das kartesische Produkt ist eine besondere Verknüpfung zwischen zwei Mengen. Die Schreibweise für das kartesische Produkt zwischen den Mengen $A$ und $B$ ist $A \times B$ (ausgesprochen: „$A$ kreuz $B$“). Das kartesische Produkt $A\times B$ ist die Menge aller geordneten Paar $(a,b)$ mit $a\in A$ und $b\in B$. So ist beispielsweise:

$\begin{align} \{1,\,2\} \times \{ 3,\, 4,\, 5\} = \{ & (1,\,3);\, (1,\,4);\, (1,\,5);\, \\ & (2,\,3);\,(2,\,4);\,(2,\,5) \}\end{align}$

Beispiele/Übungsaufgabe: Schreibe folgende kartesische Produkte aus.

• $\{ 1,2,3\} \times \{1,2,3\}$
• $\{ x \} \times \{ y \}$
• $\emptyset \times \{ 1, 2, 3\}$

• $\begin{align} \{ 1,2,3\} \times \{1,2,3\} = \{ & (1,1);\, (1,2);\, (1,3);\, \\ & (2,1);\, (2,2);\, (2,3);\, \\ & (3,1);\, (3,2);\, (3,3) \} \end{align}$

• $\{ x \} \times \{ y \} = \{ (x,y) \}$

• $\emptyset \times \{ 1, 2, 3\} = \emptyset$

Definition (kartesisches Produkt): Das kartesische Produkt $A\times B$ zweier Mengen $A$ und $B$ ist die Menge aller geordneten Paare $(a,b)$ wobei $a$ ein Element der Menge $A$ und $b$ ein Element der Menge $B$ ist: $A\times B := \{(x,y)\,|\,x\in A \and y\in B\}$

Verständnisfrage: Sei $A$ eine endliche Menge mit $a$ Elementen und $B$ eine endliche Menge mit $b$ Elementen. Wie viele Elemente enthält die Menge $A\times B$?

Seien $x_1$ bis $x_a$ die Elemente der Menge $A$ und $y_1$ bis $y_b$ die Elemente der Menge $B$. Dann sieht $A\times B$ so aus:

$\begin{array}{lc} \underbrace{\{x_1,\,x_2,\,\ldots,\, x_a\}}_{=\ A} \times \underbrace{\{y_1,\,y_2,\,\ldots,\, y_b\}}_{=\ B} = \{ & (x_1,y_1);\, (x_1,y_2);\, \dots;\, (x_1,y_b);\\ & (x_2,y_1);\, (x_2,y_2);\, \dots;\, (x_2,y_b);\\ & \vdots \\ & (x_a,y_1);\, (x_a,y_2);\, \dots;\, (x_a,y_b)\}\\ \end{array}$

Man sieht, dass es für jedes $x\in A$ genau $b$ verschiedene $y\in B$ mit $(x,y)\in A\times B$ gibt. Damit enthält $A\times B$ genau $a\cdot b$ verschiedene geordnete Paare als Elemente.

Man kann auch das kartesische Produkt von mehr als zwei Mengen bilden. Analog zum Fall von zwei Mengen ist das kartesische Produkt $A\times B\times C$ der drei Mengen $A$, $B$ und $C$ gleich der Menge aller 3-Tripel $(a,b,c)$ mit $a\in A$, $b\in B$ und $c\in C$:

$A\times B\times C := \{ (a,b,c)\,|\,a\in A,\, b\in B,\,c\in C\}$

Verständnisfrage: Was ist $\{ 1,\, 2 \} \times \{3,\, 4\} \times \{5,\, 6\}$?

$\begin{align} \{ 1,\, 2 \} \times \{3,\, 4\} \times \{5,\, 6\} = \{ & (1,\, 3,\, 5);\, (1,\, 3,\, 6); \\[3px] & (1,\, 4,\, 5);\, (1,\, 4,\, 6); \\[3px] & (2,\, 3,\, 5);\, (2,\, 3,\, 6); \\[3px] & (2,\, 4,\, 5);\, (2,\, 4,\, 6)\} \\[3px] \end{align}$

Allgemein ist das kartesische Produkt $A_1 \times A_2 \times \dots \times A_n$ der $n$ Mengen $A_1$ bis $A_n$ die Menge aller n-Tupeln $(a_1,\, a_2,\, \dots ,\, a_n)$ mit $a_1 \in A_1$, $a_2 \in A_2$ und so weiter bis $a_n \in A_n$:

$A_1 \times A_2 \times \dots \times A_n := \{ (a_1,\, a_2,\, \dots ,\, a_n)\,|\, a_1 \in A_1 \and a_2 \in A_2 \and \dots \and a_n \in A_n \}$

Für kartesische Produkte von Mengen mit sich selber gibt es eine abkürzende Schreibweise: Es ist $M^2 := M \times M$, $M^3:=M \times M \times M$ und so weiter. Allgemein ist

$M^n := \underbrace{M\times M \times \dots \times M}_{n\text{-mal}}$.

Verständnisfrage: Was ist $\{ 1,\, 2 \}^3$?

$\begin{align} \{1,\,2\}^3 = \{ 1,\, 2 \} \times \{1,\, 2\} \times \{1,\, 2\} = \{ & (1,\, 1,\, 1);\, (1,\, 1,\, 2); \\[3px] & (1,\, 2,\, 1);\, (1,\, 2,\, 2); \\[3px] & (2,\, 1,\, 1);\, (2,\, 1,\, 2); \\[3px] & (2,\, 2,\, 1);\, (2,\, 2,\, 2)\} \\[3px] \end{align}$