Tupel

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)

Anschauliche Definition (Kowarschick)

Ein Tupel ist eine Menge oder gar eine Klasse von unterschiedlich benannten Attributen, d.h. eine Menge oder Klasse von Schlüssel/Wert-Paaren, wobei jeder Schlüssel nur einmal vorkommen darf.

Begriff	Alternativnamen	englische Bezeichnungen
Tupel	Familie, Folge	tuple, sequence, indexed family,
Attribut	Schlüssel/Wert-Paar	attribute, key/value pair, property
Attributname	Schlüssel, Index	key, index, attribute/property name, attribute/property key
Attributwert	Wert, Glied	value, attribute/property value

Attribute können auch mehr als einen Attributnamen haben. Diese werden dann mit Schlüssel-Schlüssel-Wert-Tripeln etc. dargestellt.

Indexmenge

Die Menge aller Schlüssel eines Tupels wird Indexmenge des Tupels genannt.

Tupellänge

Die Länge eines Tupel ist gleich der Mächtigkeit der zugehörigen Indexmenge.

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

Gleichheit zweier Tupel

Zwei Tupel sind genau dann gleich, wenn die zugehörigen Indexmengen gleich sind und wenn die jeweils gleich benannten Elemente ebenfalls gleich sind.

Anmerkungen

Tupel sind im Prinzip nichts anderes als Funktionen, deren Definitionsbereich Indexmenge genannt wird. Eine Funktion ordnet jedem Element des Definitionsbereichs einen Wert zu, entsprechend ordnet ein Tupel jedem Schlüssel, also jedem Element der Indexmenge einen Wert zu.

Tupel können auch als geordnete Multimengen, d.h. als Listen aufgefasst werden, sofern für die Indexmenge eine Ordnung definiert ist:

• Werte können mehrfach vorkommen (im Gegensatz zu normalen Mengen, aber in Einklang mit Multimengen).
• Die Werte sind (gemäß der auf den Schlüsseln definierten Ordnung) angeordnet (im Gegensatz zu Mengen und Multimengen).

Üblicherweise spielt in der Informatik die Ordnung der Tupelelemente nur dann eine Rolle , wenn eine Menge von aufeinanderfolgenden natürlichen Zahlen als Indexmenge verwendet wird.

Beispiele

Tupelart	Tupelschema	Beispiel
Attributtupel Attributnotation	{name: String, sex: {'f','m','x'}}	{name: 'Anton', sex: 'm'}
Positionstupel Listennotation Attributnotation	(String, {'f','m','x'}) {1: String, 2: {'f','m','x'}}	('Anton', 'm') {1: 'Anton', 2: 'm'}
Positionsattributtupel Listennotation Attributnotation	(name: String, sex: {'f','m','x'}) {1/name: String,  2/sex:  {'f','m','x'} }	(name: 'Anton', sex:'m') {1/name: 'Anton',  2/sex:  'm' }

Positionsattributtupel sind Tupel, deren Attribute zwei unterschiedliche Attributnamen haben: Eine Zeichenkette und einen Positionsbezeichner. Dies ist die ideale Darstellung für Tupel, die durch Tabellenzeilen repräsentiert werden:

name	sex	spouse
'Anton'	'm'	'Berta'
'Berta'	'f'	'Anton'
'Cäsar'	'm'	null

Jedes Attribut dieser drei Tupel hat sowohl einen Namen, der über der jeweiligen Spalte notiert wird, sowie eine Position, die sich durch die Spaltenposition ergibt.

In den folgenden Beispielen werden Attribute teils mittels Attributnotation a:v, i/a:v und teils mittels Listennotation $ (a,v) $, $ (i,a,v) $ dargestellt.

Attributnotation

Im Fall von endlichen Indexmengen kann ein Tupel einfach durch die explizite Angabe von Schlüssel/Wert-Paaren erfolgen.

t1 = {name: 'Anton', geburtsjahr: 1961, ehefrau: 'Berta'}
t2 = {ehefrau: 'Berta', geburtsjahr: 1961, name: 'Anton'}
t3 = {name: 'Anton', geburtsjahr: 1961, hochschule: 'HSA'}
t4 = {name: 'Anton', geburtsjahr: 1962, hochschule: 'HSA'}
t5 = {name: 'Anton', geburtsjahr: 1961, ehefrau: 'Berta', hochschule: 'HSA'}

Nur Tupel t1 und t2 sind gleich, alle anderen Tupel unterscheiden sich. Entweder unterscheiden sich die Indexmengen (t1 bis t4 haben die Länge 3, Tupel t5 hat dagegen die Länge 4) oder es stimmen nicht alle gleich benannten Elemente überein (alle übrigen Tupelpaare).

Folgendes ist kein Tupel (und damit auch keine Funktion), da zwei Elemente gleich benannt sind:

{name: 'Anton', name: 'Cäsar', hochschule: 'HSA'}

Attributnotation in der Informatik

Die Attributnotation kommt in der Informatik häufig zum Einsatz. Beispielsweise können in JSON innerhalb einer Mengenklammer beliebig viele (jedoch nur endlich viele) Attribute angeben werden. Als Attributnamen werden Zeichenketten (Strings) verwendet, die mit Anführungszeichen " markiert sind. Der zugehörige Attributwert wird vom Attributnamen durch einen Doppelpunkt abgetrennt.

{"name": "Anton", "geburtsjahr": 1961, "ehefrau": "Berta"}
...

Weitere Beispiele für Datenstrukturen, in denen Mengen von Schlüssel/Wert-Paaren zum Einsatz kommen:

• C/C++: Datentyp struct (die Länge kann zur Laufzeit nicht verändert werden)
• Pascal: Datentyp record (die Länge kann zur Laufzeit nicht verändert werden)
• diverse Sprachen: Hashtabelle (auch hash map, hash array, assoziatives Array etc.; die Länge kann zur Laufzeit verändert werden)
• SQL: Tabellenzeilen, d.h. Elemente von Relationen (die Länge kann zur Laufzeit durch Schema-Evolution verändert werden)
• JavaScript: Objekte (die Länge kann zur Laufzeit verändert werden, sofern dies nicht explizit mittels Object.freeze „untersagt“ wird)
• Java und viele andere Sprachen: Objekte (die Länge kann zur Laufzeit i. Allg. nicht verändert werden)

Attributzugriff

Um mittels des Attributnamens auf einen Attributwert zuzugreifen, haben sich in der Informatik zwei syntaktische Konstrukte etabliert (obwohl es durchaus noch Sprachen gibt, die andere syntaktische Konstrukte verwenden):

• Die Indexnotation: t1["name"], t5["ehefrau"] etc.
• Die Punktnotation: t1.name, t5.ehefrau etc.

In der Mathematik sind dagegen folgende Konstrukte üblich:

• Die Funktionsauswertung: $ \rm{t1}(\rm{name}) $, $ \rm{t5}(\rm{ehefrau}) $ etc.
• Die Projektionsfunktion $ π $: $ π_{\rm{name}}(\rm{t1}) $, $ π_{\rm{ehefrau}}(\rm{t5}) $ etc.
• Die Indexnotation: $ \rm{t1}_{\rm{name}} $, $ \rm{t5}_{\rm{ehefrau}} $ etc.

Listennotation

Für Tupel, deren Indexmenge eine Menge von $ n $ aufeinanderfolgenden natürlichen Zahlen ist (i. Allg. $ \{i| 0 < i \le n\} $, oder, wie in vielen Programmiersprachen üblich, $ \{i| 0 \le i < n\} $), bietet sich die in der Mathematik gebräuchliche Listennotation an. Bei dieser werden die Schlüssel nicht explizit angegeben, sondern implizit durch die Position der Elemente festgelegt:

$ t_6 := (555, 333) $

$ t_7 := (333, 555) $

$ t_8 := (555, 333, 555) $

$ t_9 := (0, 1, 1, 2, 3, 5, 8, \ldots) $ (Fibonacci-Zahlen)

Die Tupel $ t_6 $ bis $ t_9 $ unterscheiden sich alle voneinander. In Tupel $ t_6 $ steht an Position 1 das Element $ 555 $, während in Tupel $ t_7 $ an Position 1 das Element $ 333 $ steht. Tupel $ t_8 $ unterscheidet sich von Tupel $ t_6 $ und $ t_7 $, da die Indexmengen ($ \{1,2\} $ bei Tupel $ t_6 $ und $ t_7 $; $ \{1,2,3\} $ bei Tupel $ t_8 $) nicht übereinstimmen.

Tupel $ t_6 $ und $ t_7 $ sind $ 2 $-Tupel, Tupel $ t_8 $ ist um ein Element länger, die Länge von Tupel $ t_9 $ beträgt ω. Tupel $ t_9 $ enthält also abzählbar unendlich Elemente. Da ein unendlich großes Tupel nicht mehr explizit angegeben werden kann, muss die Definition entweder anschaulich erfolgen (siehe obige Definition von Tupel $ t_9 $) oder mittels einer Rechenvorschrift:

$ \rm{fib(n)} := \begin{cases} 0 & n = 0\\ 1 & n = 1\\ \rm{fib}(n-1) + \rm{fib}(n-2) & \text{otherwise} \end{cases}\\ t_9 := (\rm{fib}(0), \rm{fib}(1), \rm{fib}(2), \rm{fib}(3), \ldots)\\ t_9(i) := \rm{fib}(i) $

Listennotation in der Informatik

In der Informatik, wie beispielsweise in JSON, kommt die Listennotation ebenfalls zu Einsatz:

t6 = [555, 333]
t7 = [333, 555]
t8 = [555, 333, 555]

Unendliche lange Tupel können in JSON nicht definiert werden. Allerdings ist es in JavaScript möglich, mittels Generatoren beliebig große Tupel zu generieren. Der Generator selbst kann als unendlich langes Tupel aufgefasst werden:

// Generator für Fibonacci-Zahlen (BigInt).
function* fib() 
{ let a = 0n, b = 1n; // 0n = BigInt(0), 1n = BigInt(1), ...
  yield a;
  yield b;
  while (true) 
  { [a, b] = [b, a+b];
    yield b;
  }
}

// Hilfsfunktion zum Materialisieren der
// ersten n Elemente eines Generators. 
function take(n, p_iterable) 
{ let tuple = [], i = 0;
  while (i++ < n) 
  { tuple.push(p_iterable.next().value);  }
  return tuple;
}

let f = fib();
console.log(f.next().value, f.next().value, f.next().value, f.next().value, f.next().value);
// -> 0n, 1n, 1n, 2n, 3n
console.log(take(1000, fib()));
// -> [0n, 1n, 1n, 2n, 3n, 5n, 8n, 13n, 21n ...] // tausend Elemente

In der Informatik finden sich weitere Datenstrukturen, in denen Elemente sequenziell abgespeichert werden, d.h., bei denen Tupel nicht als Menge von Attributen, sondern als Folge von Elementen aufgefasst werden:

• Arrays oder Felder (häufig mit fixer Länge)
• Listen in zahlreichen Ausprägungen (i. Allg. mit variabler Länge)
• Streams (evtl. sogar unendlich lang)

Attributzugriff

Um mittels der Attributposition auf einen Attributwert zuzugreifen, hat sich in der Informatik ein syntaktisches Konstrukt etabliert:

• Die Indexnotation: t[1], t[2] etc.

Bei verketteten Listen, Streams etc. ist der Zugriff auf ein Element an einer bestimmten Position dagegen manchmal nur dadurch möglich, dass man sich mittels einer Funktion oder Methode (z. B. next) von einem Element zu nächsten „hangelt“ (Traversierung), bis man beim gewünschten Element angekommen ist (siehe z. B. die Funktion take im vorangegangenen Abschnitt).

In der Mathematik sind dagegen folgende Konstrukte üblich:

• Die Funktionsauswertung: $ t(1) $, $ t(2) $ etc.
• Die Indexnotation: $ t_1 $, $ t_2 $ etc.
• Die Projektionsfunktion $ π $: $ π_1(t) $, $ π_2(t) $ etc.

Spezielle Tupel mit Positionsattributen

Länge $ n $	Name	Attributnotation	Listennotation
0	Leeres Tupel	$ \{\} $	$ () $
1	Singel	$ \{(1,5)\} $	$ (5) $
2	(geordnetes) Paar	$ \{(1,5), (2,3)\} $	$ (5,3) $
3	Triple	$ \{(1,5), (2,3), (3,8)\} $	$ (5,3,8) $
4	Quadrupel	$ \{(1,5), (2,3), (3,8), (4,π)\} $	$ (5,3,8,π) $
5	Quintupel	$ \vdots $	$ \vdots $
6	Sextupel
7	Septupel
8	Oktupel
$ \vdots $	$ \vdots $
100	Centupel
$ n $	$ n $-Tupel
ω oder $ \aleph_0 $	ω- oder oder $ \aleph_0 $-Tupel	$ \{(i,i^2)| i \in \mathbb N\} $	$ (i^2)_{i \in \mathbb N} $
$ 2^{\aleph_0} $	$ 2^{\aleph_0} $-Tupel	$ \{(r,r^2)| i \in \mathbb R\} $	$ (r^2)_{r \in \mathbb R} $

Jede endliche oder abzählbar unendliche Folge, Sequenz oder Familie kann als Tupel in Listennotation aufgefasst werden. Jede (mathematische) Funktion kann als Tupel aufgefasst werden.

Formale Definitionen

Im Folgenden wird vorausgesetzt, dass der Term „geordnetes Paar“ $ [x,y] $ schon existiert, aufgrund einer Definition oder auch, weil er 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) auch 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.

Tupel in Attributnotation, 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 Tupel oder Familie über $ I $ (in Attributnotation). Alternativ kann man auch $ I $-Tupel oder $ I $-Familie (in Attributnotation) sagen.

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

Indexbereich und Indexmenge (Tupel in Attributnotation)

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

Tupellänge (Tupel in Attributnotation)

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

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

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

Schlüssel und Wert (Tupel in Attributnotation)

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 (Tupel in Attributnotation)

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 Tupel in Attributnotation handelt.

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

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

Tupel in Listennotation (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 Tupel (in Listennotation) – 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 Tupel in Listennotation 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) )) $

Tupellänge (Tupel in Listennotation)

Es sei $ t $ ein Tupel in Listennotation: $ 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 $-Tupel in Listennotation.

Das $ 0 $-Tupel wird auch leeres Tupel genannt.

Lemma: Eindeutigkeit der Länge eines Tupels in Listennotation

Die Länge eines Tupels in Listennotation 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.

Indexmenge (Tupel in Listennotation)

Für ein Tupel $ t $ in Listennotation wird die Indexmenge $ I(t) $ folgendermaßen definiert:

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

Lemma: Länge des Tupels

Die Länge eines Tupels $ t $ in Listennotation ist gleich der Mächtigkeit der Indexmenge: $ \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 (Tupel in Listennotation)

Es seien $ t $ ein nicht-leeres Tupel in Listennotation und $ I := I(t) $ die zugehörige Indexmenge. Die Elemente $ i\in I $ der Indexmenge 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 Tupel in Listennotation 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 (Tupel in Listennotation)

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 Beutzerhandbuch 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 gleich einem $ 2 $-Tupel; ein Beweis einer Aussage analog zu Lemma 5.3.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.

Mengentupel und Klassentupel (Tupel in Listennotation)

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 genaugenommen 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 $ 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)\} $

Lemma: Korrektheit der Abbildung der Listen- auf die Attributnotation

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

1. $ I(t) = I(t') $
2. $ \rm{lg}(t) = \rm{lg}(t') $
3. $ \bigwedge i \in I: t_i = t'_i $

Beweis

TO BE DONE

$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' $)

Nun gelten folgende zwei Beziehungen:

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

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

Insgesamt gilt also, sofern man *1 und *2 nachweisen kann:

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

Damit wäre die erste Aussage bewiesen.

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:

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

Dritte Aussage

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

TO BE DONE

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 gleich Tupel (in Attribut- oder Listennotation) sind trivialerweise gleichlang:

$ 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 Leipnizschen Ersetzbarkeit, die aussagt, das in Formeln ein Element stets durch ein dazu gleiches Element ersetzt werden kann.

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 Indexmengen $ I(t_1) $ und $ I(t_2) $ übereinstimmen und wenn die Funktionswerte für jedes Element der Indexmenge 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) $

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

Beweis für Listennotation: mittels vollständiger Induktion.

TO BE DONE

Siehe auch

1. Kowarschick (MMDB-Skript): Wolfgang Kowarschick; Vorlesung Multimedia-Datenbanksysteme – Sommersemester 2018; Hochschule: Hochschule Augsburg; Adresse: Augsburg; Web-Link; 2018; Quellengüte: 4 (Skript)