Mathe für Nicht-Freaks: Abstellraum/ Tupelmodellierung 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\leq k\leq 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)}}\\[0.5em]=\ &\{(),\,\{1\}\}&\left|\ ()=\emptyset \right.&{\text{(Rekursionsanfang)}}\\[0.5em]=\ &\{\emptyset ,\,\{1\}\}\end{array}}$

Tupel $(a,b)$:

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

Tupel $(())$:

${\begin{array}{llll}&(())&\left|\ ()=\emptyset \right.&{\text{(Rekursionsanfang)}}\\[0.5em]=\ &(\emptyset )&\left|\ (\emptyset )=\{(),\,\{\emptyset \}\}\right.&{\text{(Rekursionsschritt)}}\\[0.5em]=\ &\{(),\,\{\emptyset \}\}&\left|\ ()=\emptyset \right.&{\text{(Rekursionsanfang)}}\\[0.5em]=\ &\{\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\,\land \,\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\,\land \,\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\,\land \,\underbrace {\forall k\in \underbrace {\{1,\,2,\,\dots ,\,0\}} _{\text{leere Menge}}:\,x_{k}=y_{k}} _{\text{immer erfü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\,\land \,\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\,\land \,\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\,\land \,\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})\neq \{x_{n+1}\}$ und $(x_{1},\,x_{2},\,\dots ,\,x_{n})\neq \{y_{m}\}$. Analog ist $(y_{1},\,y_{2},\,\dots ,\,y_{m-1})\neq \{x_{n+1}\}$ und $(y_{1},\,y_{2},\,\dots ,\,y_{m-1})\neq \{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\geq k\geq n$. Aus $\{x_{n+1}\}=\{y_{m}\}$ folgt $x_{n+1}=y_{m}$ und damit $x_{k}=y_{k}$ für alle $1\geq k\geq n+1$.