Tupel/Formale Definition

Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nur teilweise:

Korrektheit: 3 (zu größeren Teilen überprüft)

Umfang: 4 (unwichtige Fakten fehlen)

Quellenangaben: 5 (vollständig vorhanden)

Quellenarten: 5 (ausgezeichnet)

Konformität: 5 (ausgezeichnet)

Eine informelle Definition des Begriffs Tupel wurde im zugehörigen Artikel angegeben. Dort findet man auch einen Überblick über die zugehörige Geschichte einschließlich unterschiedlicher Definitionen. Im Folgenden wird der Tupelbegriff auf Basis dieser Definitionen formalisiert. Dabei wird vorausgesetzt, dass der Term „geordnetes Paar“ $ [x,y] $ schon definiert oder axiomatisch eingeführt wurde.

Man beachte, dass sich das geordnete Paar $ [x,y] $ vom Tupel $ (x,y) $ (in Listennotation) unterscheidet, sofern Letzteres mit Hilfe von $ [x,y] $ definiert wird. Allerdings erfüllt $ (x,y) $ (nachdem es definiert wurde) ebenfalls das Paaraxiom und kann überall, wo ein geordnetes Paar benötigt wird, genauso gut wie $ [x,y] $ verwendet werden. In LISP sieht man den Unterschied sehr schön: Die „Cons-Zelle“ (x . y) unterscheidet sich von der Liste (x y), die als Abkürzung für (x . (y . NIL)) steht. Beide Definitionen erfüllen jedoch das Paaraxiom.

Definition (Kowarschick)

Attributtupel, Familie (in Anlehnung an Bourbaki und Schmidt)

Es sei $ t: I \rightarrow \mathcal{V} $ eine beliebige Funktion von einer Menge oder Klasse $ I $ in die Allklasse $ \mathcal{V} $:

$t \subseteq I \times \mathcal{V} \,\wedge\, \bigwedge x, y_1, y_2: [x,y_1] \in f \wedge [x,y_2] \in f \rightarrow y_1=y_2$

$ t $ wird nicht nur Funktion genannt, sondern, insbesondere wenn man sich mehr für den Definitionsbereich als für die Funktion selbst interessiert, auch (Attribut-)Tupel oder Familie über $ I $. Alternativ kann man auch $ I $-Tupel oder $ I $-Familie sagen.

$ \rm{TupA}(t) :\leftrightarrow \rm{Fkt}(t) $ (siehe Funktion)

Indexbereich und Indexmenge

Die Definitionsmenge $ I := I(t) = \rm{Def}(f) := \{x| \bigvee y: [x,y] \in t\} $ der Funktion $ t $ heißt in diesem Fall Indexbereich. Falls es sich bei $ I $ um eine echte Menge und nicht um eine Unmenge handelt, kann man auch Indexmenge sagen.

Länge eines Attributtupel

Die Mächtigkeit des Indexbereichs heißt Länge des Tupels:

$ \rm{lg}(t) := |I(t)| $

Ein Tupel der Länge $ n $ wird auch $ n $-Tupel genannt.

Schlüssel und Wert eines Attributtupels

Jedes Element $ i $ des Indexbereichs heißt Schlüssel oder Index.

Das zum Index $ i $ gehörende Element $ t_i := t(i) $ wird als Wert bezeichnet.

Anmerkungen zum Attributtupel)

Mit $ \rm{Fkt}(f) $ wird ausgedrückt, dass es sich bei einer Menge oder Klasse $ f $ um eine Funktion handelt, dass $ f $ also eine Menge oder Klasse von geordneten Paaren ist, die die Eindeutigkeitsbedingung

$\bigwedge x, y_1, y_2: [x,y_1] \in f \wedge [x,y_2] \in f \rightarrow y_1=y_2$

erfüllt.

Mit $ \rm{TupA}(t) $ wird ausgedrückt, dass es sich bei $ t $ um ein Attributtupel handelt.

Schmidt verwendet die Bezeichnung „Glied“ an Stelle von „Wert“.

Der Begriff „I-Tupel“ geht auf Ebbinghaus zurück.

Positionstupel (in Anlehnung an McCarthy et al.)

Der Begriff des geordneten Paars kann induktiv für eine beliebige endliche Anzahl von Elementen verallgemeinert werden:

Eine Menge oder Klasse $ t $ heißt (Positions-)Tupel – in Zeichen $ \rm{TupV}(t) $ – wenn entweder $ t=\emptyset $ gilt oder wenn $ t $ ein geordnetes Paar $ [x,t] $ ist, dessen erstes Element beliebig und dessen zweites Element ein Tupel ist:

$ \rm{TupV}(\emptyset) $

$ \bigwedge x, t: \rm{TupV}(t) \rightarrow \rm{TupV}([x,t]) $

Andere Positionstupel gibt es nicht. Das heißt, für jedes Tupel $ t \not= \emptyset $ gibt es ein Element $ x $
und ein Tupel $ t' $ mit $ t = [x,t'] $:

$ \bigwedge t: (\rm{TupV}(t) \wedge t \not= \emptyset \rightarrow \bigvee x, t': (\rm{TupV}(t') \wedge t = [x,t'])) $

Das Tupel $ t' $ ist wegen des Paaraxioms sogar eindeutig bestimmt:

$ \bigwedge t: (\rm{TupV}(t) \;\rightarrow\; \bigwedge x_1, x_2, t_1, t_2: (\rm{TupV}(t_1) \wedge \rm{TupV}(t_2) \wedge t = [x_1,t_1] \wedge t = [x_2,t_2] \,\rightarrow\, t_1=t_2 \wedge x_1=x_2)) $

In einem klassenbasierten Axiomen-System (wie es z.B. der Neumann-Bernays-Gödel-Mengenlehre zu Grunde liegt) ist diese Formel allerdings nur im Falle von Klassenpaaren gültig (vgl. Abschnitt „Reihenfolge der Elemente“ im Artikel geordnetes Paar). Für Mengenpaare müsste sie entsprechend auf Mengen eingeschränkt werden, da Mengenpaare keine Klassen enthalten können:

$ \bigwedge a,b: (\rm{UMg}(a) \vee \rm{UMg}(b)) \leftrightarrow (a,b) = \mathcal{V} $

In diesem Fall gilt nur:

$ \bigwedge t: (\rm{Mg}(t) \wedge \rm{TupV}(t) \;\rightarrow\; \bigwedge x_1, x_2, t_1, t_2: (\rm{TupV}(t_1) \wedge \rm{TupV}(t_2) \wedge t = [x_1,t_1] \wedge t = [x_2,t_2] \,\rightarrow\, t_1=t_2 \wedge x_1=x_2 \wedge \rm{Mg}(x_1) \wedge \rm{Mg}(x_2) \wedge \rm{Mg}(t_1) \wedge \rm{Mg}(t_2) )) $

Länge eines Positionstupels

Es sei $ t $ ein Positionstupel: $ TupV(t) $. Die Länge $ \rm{lg}(t) $ von $ t $ wird ebenfalls induktiv definiert:

$ \rm{lg}(\emptyset) := 0 $

$ \bigwedge x, t: \rm{TupV}(t) \rightarrow \rm{lg}([x,t]) := \rm{lg}(t)+1 $

Ein Tupel der Länge $ l $ heißt $ l $-Positionstupel.

Das 0-Tupel wird auch leeres Tupel genannt.

Lemma: Eindeutigkeit der Länge eines Positionstupels

Die Länge eines Positionstupels ist eindeutig bestimmt.

Beweis

Das leere Tupel ist das einzige Tupel der Länge $ 0 $. Für jedes andere Tupel $ t $ existiert genau ein Element $ x $ und ein Tupel $ t' $, für die $ t=[x,t'] $ gilt. Für $ t' $ ist die Länge laut Induktionsvoraussetzung eindeutig bestimmt und damit ist die Länge $ \rm{lg}(t) = \rm{lg}(t')+1 $ ebenfalls eindeutig bestimmt.

Indexbereich eines Positionstupels

Für ein Positionstupels $ t $ wird die Indexbereich $ I(t) $ folgendermaßen definiert :

$ I(t) := \{i \in \mathbb{N}: 0 < i \le \rm{lg}(t)\} $

Anmerkung
Die Zählung der Attribute beginnt laut dieser Definition bei $ 1 $ und endet bei $ \rm{lg}(t) $. Man könnte ohne Probleme auch die in der Informatik übliche Zählung von $ 0 $ bis$ \rm{lg}(t)-1 $ verwenden, müsste dann aber ein paar Anpassungen vornehmen (z. B. beim nachfolgenden Lemma).

Lemma: Länge eines Positionsupels

Die Länge eines Positionstupels $ t $ ist gleich der Mächtigkeit des Indexbereichs: $ \rm{lg}(t) = |I(t)| $

Beweis

$ |I(t)| = |\{i \in \mathbb{N}: 0 < i \le \rm{lg}(t)\}| = \rm{lg}(t) $

Schlüssel und Wert eines Positionstupels

Es seien $ t $ ein nicht-leeres Positionstupel und $ I := I(t) $ der zugehörige Indexbereich. Die Elemente $ i\in I $ des Indexbereichs heißen Schlüssel.

Jedem Schlüssel $ i\in I $ wird durch das Tupel $ t $ ein eindeutiger Wert $ t_i $ zugeordnet. $ t_i $ wird wieder induktiv definiert:

Da laut Voraussetzung $ t \not= \emptyset $ gilt, gibt es zwei (eindeutige) Elemente $ x $ und $ t' $ mit $ \rm{TupV}(t') $ und $ t=[x,t'] $.

$ t_i := \begin{cases} x & \mbox{wenn } i = 1\\ t'_{i-1} & \mbox{wenn } i > 1 \end{cases} $

Man beachte, dass aus $ i\in I $ stets $ 0 < i < \rm{lg}(t) $ folgt. Diese Invariante bleibt im rekursiven Zweig der Definition erhalten: $ i>1 \rightarrow 0 < i-1 < \rm{lg}(t)-1 = \rm{lg}(t') $. Das heißt, es gilt auch hier $ i-1 \in I(t') $.

Für $ i\notin I $ ist $ t_i $ nicht definiert. Man kann in diesem Fall allerdings $ t_i := \mathcal{V} $ setzen, um $ t_i $ für jede beliebige Klasse $ i $ zu definieren.

Listennotation

Für Positionstupel wird folgende abkürzende Schreibweise eingeführt:

$ () := \emptyset $

$ (x_1) := [\emptyset, x_1] $

$ (x_1,x_2) := [[\emptyset, x_1], x_2] $

$ (x_1,x_2,x_3) := [[[\emptyset, x_1], x_2], x_3] $

Allgemein für $ n \ge 2 $:

$ (x_1,\ldots,x_n) := [(x_1,\ldots,x_{n-1}), x_n] = [[[\ldots[\emptyset,x_1]\ldots], x_{n-1}], x_n] $

Anmerkungen zum Positionstupel

Ursprung und Varianten der Listennotation

Die obige Definition der Listennotation geht auf McCarthy zurück (wobei er die Liste allerdings vom letzten Element ausgehend aufbaut):

The list $ (m_1,m_2,···,m_n) $ is represented by the S-expression $ (m_1·(m_2·(···(m_n·\rm{NIL})···))) $.
Here $ \rm{NIL} $ is an atomic symbol used to terminate lists.

McCarthy definiert eine LISP-Liste als abkürzende Schreibweise für eine Folge von $ cons $-Zellen, d.h. als Folge von LISP-Paaren $ (a \cdot b) $. In LISP wird eine Liste also als verkette Liste implementiert: Jede $ cons $-Zelle enthält das eigentlich Listenelement sowie einen Verweis auf die Nachfolgerliste. Die letzte $ cons $-Zelle enthält keinen Verweis, sondern die LISP-Konstante $ \rm{NIL} $.

In seinen ursprünglichen Publikationen wie auch im Benutzerhandbuch von LISP I bezeichnet McCarthy $ \rm{NIL} $ lediglich als „atomares Symbol“, welches benutzt wird, um Listen zu terminieren. Erst im Benutzerhandbuch von LISP 1.5 legt er zusätzlich fest, dass $ \rm{NIL} $ identisch zur leeren Liste $ () $ ist.

Die Definition von McCarthy ist den Definitionen von anderen Autoren, wie z.B. Gödel oder Schmidt, vorzuziehen.

Definition von Schmidt (und diversen anderen Autoren):

$ (x_1, x_2) $ ist ein (Klassen-)Paar.

$ (x1, x2, x3) := ((x1, x2), x3) $ ist ein (Klassen-)Tripel.

$ (x1, x2, x3, x4) := ((x1, x2, x3), x4) = (((x1, x2), x3), x4) $ ist ein (Klassen-)Quadrupel.

Diese Definition hat zwei Nachteile:

• Es gibt kein 0- und keine 1-Tupel.
• Tupel unterschiedlicher Länge können gleich sein (jedes n-Tupel für n>2 ist gleichzeitig auch ein 2-Tupel; ein Beweis einer Aussage analog zu Lemma 4.2.1.1 scheitert daher beim Induktionsanfang).

Definition von Gödel (und diversen anderen Autoren):

Gödel hat Tupel im Prinzip genauso wie Schmidt definiert. Zusätzlich hat er allerdings noch 1-Tupel eingeführt:

$ (x_1) := x_1 $

Doch auch diese zusätzliche Festlegung löst die obigen Probleme nicht wirklich.

Mengen- und Klassen-Positionstupel

In einer klassenbasierten Mengenlehre erhält man mit Hilfe der obigen Definition so genannte Klassentupel, sofern man der Definition der Tupel Klassenpaare zugrunde legt. Bei Benutzung einer mengenbasierten Mengenlehre oder wenn man Tupel mit Hilfe von Mengenpaaren definiert, erhält man dagegen lediglich so genannte Mengentupel.

Ein Klassentupel kann nicht nur Mengen, sondern auch Unmengen als Elemente beinhalten.

Beispielsweise kann man das Monoid der Ordinalzahlen $ \Omega $ mit Addition $ + $ und neutralem Element $ 0 $ als Klassentupel $ (\Omega,+,0) $ definieren, obwohl es sich bei $ \Omega $ um eine Unmenge handelt. Für Mengentupel gilt dagegen, dass $ (\Omega,+,0) $ entweder nicht definiert ist oder gleich der Allklasse $ \mathcal{V} $ ist. Im letzteren Fall sind alle Mengentupel, die ein oder mehrere Unmengen enthalten, ebenfalls gleich $ \mathcal{V} $.

Objektsprache und Metasprache
Man beachte auch, dass hinsichtlich der Definitionen und Beweise ein wesentlicher Unterschied zwischen Mengen- und Klassentupeln besteht.

Für Mengen kann $ TupV $ als echte Funktion definiert werden. Die zugehörigen, auf vollständiger Induktion basierenden Beweise können daher innerhalb der formalen Sprache (Objektsprache) des jeweiligen Axiomensystems der Mengenlehre (unter Zuhilfenahme des Unendlichkeitaxioms) durchgeführt werden. In einem ersten Schritt formalisiert man innerhalb der Mengenlehre die natürlich Zahlen (samt vollständiger Induktion) und in einem zweiten Schritt wendet man diesen Formalismus bei den Beweisen der obigen Aussagen an.

Für Klassen kann $ TupV $ dagegen nicht als echte Funktion, sondern nur als Abkürzung, definiert werden, da eine Unmenge niemals in einer Funktion als Urbild oder Bildelement auftauchen kann. Es gilt nämlich

$\rm{UMg}(a) \rightarrow \{a\}= \mathcal{V}$ (Schmidt (1966), S. 73)

und damit auch

$\rm{UMg}(a) \vee \rm{UMg}(b) \rightarrow \rm{UMg}((a,b))$ (Schmidt (1966), S. 97)

$\rightarrow \{\ldots,(a,b),\ldots\}= \mathcal{V} $

Das heißt, sobald man versucht, eine Unmenge in die Definition einer Funktion $ f $ als Urbild oder Bildelement einzuschleusen, degeneriert $ f $ zur Allklasse.

$ TupV(t) $ ist also im Falle von Klassentupeln eine Abkürzung für eine mengentheoretische Formel, genauso wie $ Mg(m) $, als Abkürzung für die Formel $ \bigvee a: m \in a $ steht (siehe Klasse). Die zugehörigen Induktionsbeweise müssen in diesem Fall außerhalb des Axiomensystems der Mengenlehre auf geführt werden, also beispielsweise mit Hilfe der Metasprache, die zur Definition des formalen System verwendet wurde. Man beachte, dass die obigen Beweise genau genommen sogar innerhalb der Metametasprache „Deutsch“ geführt wurden.

Das Problem ist, dass man, obwohl man eine Arithmetik der natürlichen Zahlen formal mit Hilfe der Mengenlehre-Axiome – d.h. innerhalb der Objektsprache – definieren kann, dennoch eine Arithmetik außerhalb – d.h. innerhalb der Metasprache – des Systems braucht, um das formale System überhaupt definieren zu können. Metamathematische Induktionsbeweise beruhen auf „gesundem Menschenverstand“. Im Prinzip definiert man ein Beweisschema, aus dem man für jeden konkreten Einzelfall einen formalen Beweis ableiten kann. Dies war schon Gödel bekannt:

... einziger Zweck dieser allgemeinen metamathematischen Überlegungen ist es zu zeigen, wie die Beweise für Sätze von einem gewissen Typus nach einer allgemeinen Methode ausgeführt werden können; ... diese allgemeinen metamathematischen Überlegungen könnten ganz wegbleiben, wenn man sich die Mühe nähme, die Beweise in jedem Fall einzeln durchzuführen ...

Abbildung der Listen- auf die Attributnotation

Für jedes $ n $-Tupel $ t $ ($ n \in \mathbb N $) in Listennotation kann ein zugehöriges Tupel $ t' $ in Attributnotation definiert werden, sofern es sich bei $ t $ um ein „Mengentupel“ handelt, d. h., sofern das Tupel nur Mengen aber keine Unmengen enthält, d.h., sofern $ \rm{Mg}(t_i) $ für alle $ i \in I(t) $:

$ t' := \{[i,t_i]: i \in I(t)\} $

Anmerkung:
Diese Aussage kann mit ziemlicher Sicherheit für beliebige Ordinalzahlen verallgemeinert werden. Dazu müssen die Positionstupel mittels transfiniter Induktion an Stelle der natürlichen Induktion definiert werden, und für alle Aussagen, die zuvor induktiv bewiesen wurden oder die im Folgenden noch induktiv beweisen werden, muss ebenfalls die transfinite Induktion verwendet werden.

Lemma: Korrektheit der Abbildung der Listen- auf die Attributnotation

$ t $ und $ t' $ beschreiben dasselbe Tupel:

1. $ I(t) = I(t') = \{i \in \mathbb{N}: 0 < i \le \rm{lg}(t)\} $
2. $ \rm{lg}(t) = \rm{lg}(t') $
3. $ \bigwedge i \in I: t_i = t'_i $, wobei $ I := I(t) = I(t') $

Beweis

$I(t') = \{x: \bigvee y: [x,y] \in t'\}$ (Definition von $ I(t') $)

$I(t') = \{x: \bigvee y: [x,y] \in \{[i,t_i]: i \in I(t)\} \}$ (Definition von $ t' $)

Man kann die erste Aussage

$I(t') = I(t)$

beweisen, indem man

$I(t') \subseteq I(t)$ (*1)

$I(t') \supseteq I(t)$ (*2)

nachweist. ($ I(t) = \{i \in \mathbb{N}: 0 < i \le \rm{lg}(t)\} $ ist bereits laut Definition von $ I(t) $ richtig.)

Begründung für *1
Es sei $ x \in I(t') $, d.h., es gibt ein $ y $ mit $ [x,y] \in \{[i,t_i]: i \in I(t)\} $, d.h., es gibt ein $ i \in I(t) $ mit $ [x,y] = [i,t_i] $ und damit gilt $ x = i \in I(t) $, wegen des Paaraxioms.

Begründung für *2
Es sei $ i \in I(t) $. Wenn man $ [x,y] := [i, t_i] $ setzt, ist $ [x,y] \in \{[i,t_i]: i \in I(t)\} $. Und damit ist $ i \in I(t') $.

Die zweite Aussage folgt direkt aus der ersten Aussage, der Definition von $ \rm{lg}(t') $ und Lemma 4.2.2.1:

$ \rm{lg}(t) = |I(t)| = |I(t')| =: \rm{lg}(t') $

Die dritte Behauptung folgt direkt aus der ersten Aussage und der Definition von $ t'_i $ und $ t' $:

Es sei $ i \in I $, dann ist $ t'_i = t'(i) = t_i $

Anmerkungen

Ein geordnetes Paar $ [a,b] $ kann, wie bereits definiert wurde, als 2-Tupel aufgefasst werden.

Allerdings liefert die allgemeine Tupeldefinition, die i.Allg. auf dem geordneten Paar basiert, ihrerseits ein 2-Tupel, das heißt, ein geordnetes Paar: $ (a,b) $. Da dieses Paar ebenfalls das Paaraxiom erfüllt, wird das spezielle geordnete Paar $ [a,b] $ künftig nicht mehr benötigt. Es wird durch $ (a,b) $ ersetzt.

Gleichheit zweier Tupel

Die Gleichheit von Tupel wird – unabhängig von der Art der Definition – auf die Gleichheit von Klassen zurückgeführt:

Zwei Tupel $ t_1 $ und $ t_2 $ sind genau dann gleich, wenn $ t_1 $ und $ t_2 $ als Klassen gleich sind, d.h., wenn:

$ t_1 \subseteq t_2 \wedge t_2 \subseteq t_1 $

oder, anders formuliert:

$ \bigwedge x \in \mathcal{V}: x \in t_1 \Leftrightarrow x \in t_2 $

Lemma

Zwei gleiche Tupel (in Attribut- oder Listennotation) sind trivialerweise gleich lang :

$ t_1 = t_2 \Rightarrow \text{lg}(t_1) = \text{lg}(t_2) $

Beweis
Die Behauptung folgt direkt aus der Reflexivität der Gleichheit ($ \text{lg}(t_1) = \text{lg}(t_1) $) und der Leibnizschen Ersetzbarkeit.

Satz

Es seien $ t_1 $ und $ t_2 $ zwei Tupel (in Attribut- oder Listennotation).

$ t_1 $ und $ t_2 $ sind genau dann gleich, wenn die zugehörigen Indexbereiche $ I(t_1) $ und $ I(t_2) $ übereinstimmen und wenn die Funktionswerte für jedes Element des Indexbereichs ebenfalls übereinstimmen:

$ t_1 = t_2 \Leftrightarrow I(t_1) = I(t_2) \wedge \bigwedge i \in I(t_1): t_1(i) = t_2(i) $

Die Behauptung $ \Rightarrow $ folgt wieder direkt aus der Reflexivität der Gleichheit und der Leibnizschen Ersetzbarkeit.

Beweis für Attributnotation: siehe Schmidt (1966), S. 123, Aussagen 14.10 und 14.11

Beweis für Listennotation: mittels vollständiger Induktion.
Es sei $ I := I(t_1) = I(t_2) $.

Induktionsanfang: $ I = \emptyset $
Dann ist $ \rm{lg}(t_1) = \rm{lg}(t_2) = 0 $ und damit $ t_1 = t_2 = \emptyset $.

Induktionsvoraussetzung:
Es seien $ t_1 = t_2 $, $ I(t_1) = I(t_2) $, $ n := \rm{lg}(I(t_1)) = \rm{lg}(I(t_2)) $ und $ I' := I \cup \{n+1\} = \{\mathbb{N}: 0 < i \le n+1\} $. Dann ist $ |I'| = n+1 $.

Induktionsschritt:
Es seien überdies $ t'_1 = [x_1, t_1] $ und $ t'_2 = [x_2, t_2] $ (n+1 > 0!). Da laut Voraussetzung (rechte Seite von $ \Leftrightarrow $) $ x_1 = t'_1(n+1) = t'_2(n+1) = x_2 $ und laut Induktionsvoraussetzung $ t_1 = t_2 $, gilt wegen des Paaraxioms auch $ t'_1 = t'_2 $, was zu beweisen war.