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)

Das Tupel ist eines der drei wichtigsten Containerarten der Mathematik und Informatik:

Containerart	Ordnung der Elemente	Duplikate erlaubt
Menge	ungeordnet	nein
Multimenge	ungeordnet	ja
Tupel	i. Allg. geordnet	ja

Es gibt verschiedene Arten von Tupeln und verschiedene Repräsentationsformen. Entsprechend gibt es auch diverse Definitionen und Namen: Liste, Familie, Folge, Komplex, Array, Hasharray, tuple, record, sequence, indexed family, property list, association list, row, array, map, hash map etc.

Ein Tupel ist ein Container (z. B. eine Menge, eine Klasse oder auch eine Kette von geordneten Paaren), der eine beliebige Anzahl von Schlüssel/Wert-Paaren enthält. Dabei darf kein Schlüssel doppelt vorkommen. Die Klasse aller Schlüssel heißt Indexbereich.

Die wichtigsten Tupelarten sind:

Name	Definition	Beispiel	Indexbereich
Liste	Kette von Paaren	$ (2, (3, (5, (7, \emptyset)))) $ Abkürzung; $ (2, 3, 5, 7) $	$ \{1, 2, 3, 4\} $ oder $ \{0, 1, 2, 3\} $
Familie	Menge von Paaren	$ \{(a, 2), (b, 3), (c, 5), (d, 7)\} $	$ \{a, b, c, d\} $
Assoziationsliste	Liste/Tupel von Paaren	$ ((a, 2), (b, 3), (c, 5), (d, 7)) $	$ \{a, b, c, d\} $ und $ \{1, 2, 3, 4\} $

Die Listendefinition hat den Nachteil, dass der Indexbereich stets endlich ist. Üblicherweise handelt es sich dabei um ein Intervall von natürlichen Zahlen: $ [0, n-1] $ oder $ [1, n] $. Der Indexbereich einer Familie kann dagegen beliebig viele Elemente enthalten. Es kann sich dabei auch um |[Komprehension|exklusive Container]] (echte Klassen, Unmengen) handeln, die so viele Elemente enthalten, dass deren Mächtigkeit gar nicht definiert ist.

Die Familendefinition hat dagegen den Nachteil, dass die Schlüssel/Wert-Paare Elemente eines Containers (z. B. einer Klasse) sind. Ein Container kann aber nur Individuen (einschließlich Individuen-Container wie Mengen) als Elemente enthalten, aber keine exklusiven Container. Das heißt, in einer Theorie, in der es exklusive Container gibt (wie {{zB]] in einer Klassentheorie), gibt es Objekte, die nicht in Familien gespeichert werden können.

Auf der anderen Seite bestehen Listen i. Allg. nur aus Paaren. Und Paare können so raffiniert definiert werden, dass nicht nur Individuen, sondern auch exklusive Container darin enthalten sein können. Das heißt, Listen können ebenfalls exklusive Container enthalten.

Name	Vorteil	Nachteil
Liste Assoziationsliste	Alle Individuen und Container als Tupel-Elemente möglich	Individuenbereich endlich
Familie	Individuenbereich beliebig	Exklusiver Container nicht als Tupel-Elemente möglich

Aus Sicht des (praktischen nicht des theoretischen) Informatikers ist diese Tabelle weniger interessant, da er sowieso nur mit endlichen Mengen arbeitet: Der Speicher ist im Gegensatz zum Speicher der Turingmaschine begrenzt. Für ihn ist vielmehr interessant, dass im endlichen Fall jede Tupelart durch jede andere ersetzt werden kann, da die verschiedenen Darstellungen (mehr oder minder gut) bijektiv aufeinander abgebildet werden können. Er ist wichtig, die Komplexität der CRUD-Operationen für die einzelnen Darstellungen zu kennen, um für den jeweiligen Anwendungsfall die beste Darstellungsart wählen zu können.

Anschauliche Definition (Kowarschick)

Ein Tupel ordnet jedem Element einer Klasse (oder Menge) von Schlüsseln oder Attributnamen jeweils einen Wert zu. Ein Tupel ist also eine Klasse von unterschiedlich benannten Attributen, d. h. eine Klasse von Schlüssel/Wert-Paaren, wobei jeder Schlüssel nur einmal vorkommen darf. Unterschiedlichen Schlüsseln kann jedoch durchaus derselbe Wert zugeordnet werden. Das heißt, ein Wert kann durchaus mehrfach vorkommen. Wert-Duplikate sind also erlaubt.

Die Klasse aller Schlüssel heißt Indexbereich oder auch – sofern es sich um eine Menge handelt – Indexmenge. Wenn auf dem Indexbereich eine totale Ordnung definiert ist, sind die Schlüssel/Wert-Paare des Tupels ebenfalls (bezüglich dieser Ordnungsrelation) geordnet. Unabhängig davon, ob eine Ordnung existiert oder nicht, sind die Elemente auf jeden Fall bezüglich des Indexbereichs indexiert.

Begriff	Alternativnamen	englische Bezeichnungen
Tupel	Liste, Familie, Folge, Komplex Array, Assoziationsliste, Hasharray etc.	tuple, record, sequence, indexed family, property list, association list, row, array, map, hash map
Indexbereich	Definitionsbereich, Indexmenge	domain, key set
Wertebereich	Wertemenge	value set
Attribut	Schlüssel/Wert-Paar	attribute, property, key/value pair
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.

Indexbereich und Indexmenge

Die Klasse aller Schlüssel eines Tupels wird Indexbereich des Tupels genannt. Wenn es sich beim Indexbereich um eine Menge handelt, kann man auch Indexmenge sagen.

Tupellänge

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

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

Gleichheit zweier Tupel

Zwei Tupel sind genau dann gleich, wenn die zugehörigen Indexbereiche gleich sind und wenn die Werte jeweils gleich benannter Elemente ebenfalls gleich sind.

Formale Definition (Kowarschick)

Siehe Tupel: Formale Definition.

Anmerkungen

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

Tupel können auch als geordnete Multimengen, d. h. als Listen aufgefasst werden, sofern für den Indexbereich 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 als Indexbereich eine Menge von aufeinanderfolgenden natürlichen Zahlenverwendet wird.

Beispiele

Tupelart	Tupelschema	Beispiel
Liste/Positionstupel Attributnotation Listennotation math. Notation	{1: String, 2: {'f','m','x'}} (String, {'f','m','x'})	{1: 'Anton', 2: 'm'} ('Anton', 'm') $ (\text{Anton}, \text{m}) $
Familie/Attributtupel Attributnotation math. Notation	{name: String, sex: {'f','m','x'}}	{name: 'Anton', sex: 'm'} $ \{(name,\text{Anton}), (sex,\text{m})\} $
Assoziationsliste/ Positionsattributtupel Attributnotation Listennotation math. Notation	{1/name: String,  2/sex:  {'f','m','x'} } (name: String, sex: {'f','m','x'})	{1/name: 'Anton',  2/sex:  'm' } (name: 'Anton', sex:'m') $ ((name,\text{Anton}), (sex,\text{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 Indexbereichen 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 Indexbereiche (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 Indexbereich 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 Indexbereiche ($ \{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 viele 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	Single	$ \{(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.

Geschichte

Definition „Tupel“ (Bourbaki (1939))

Die Mathematiker der Gruppe Bourbaki definieren zunächst das geordnete Paar (couple) nach Kazimierez Kuratowski und erwähnen, dass es das Paaraxiom erfüllt (S. E II.7):

On dit que le terme $ \{\{x\},\{x,y\}\} $ est le couple formé de $ x $ et de $ y $, et on le note de façon abrégée $ (x, y) $, de sorte que la relation $ (x, y) = (x', y') $ est equivalente a «$ x = x' $ et $ y = y' $».

Im Anschluss daran definieren sie das geordnete Tripel (triplet) mit Hilfe zweier Paare (S. E II.9):

... un élément $ ((x, y), z) $ de $ A \times B \times C $ s'écrit aussi $ (x, y, z) $ et s'appelle un triplet.

Sie weisen außerdem daraufhin, dass sich dies für vier und mehr Elemente verallgemeinern lässt.

Auf Seite E IV.5 führt Bourbaki den Begriff Tupel (multiplet) für den Term $ (s_1,\ldots,s_p) $ ein und verweisen dabei explizit auf die obige Definition.

Zusammenfassung: Der Begriff Tupel (multiplet) wird von Bourbaki folgendermaßen definiert:

$ (x,y) := \{\{x\},\{x,y\}\} $
Wenn $ n \ge 3 $, dann $ (x_1,\ldots,x_n) := ((x_1,\ldots,x_{n-1}), x_n) $

Definition „Familie“ (Bourbaki (1939))

Die Mathematikergruppe Bourbaki definiert zunächst funktionelle Relationen (Relations fonctionelles) als Relationen $ R $, die rechtseindeutig sind (S. E I.40):

$ (\forall y)(\forall z)(((y|x)R \,\text{et}\, (z|x)R) \Rightarrow (y = z)) $

Im Anschluss an die Paardefinition (siehe vorangegangenen Abschnitt) zeigt das Mathematikerteam, dass jede Relation eindeutig durch eine Menge von Paaren repräsentiert wird. Diese Menge bezeichnen sie als Graph (graphe) der Relation:

$ (\exists G)(G \,\text{est un graphe et}\, (\forall x)(\forall y)(R \Leftrightarrow ((x, y) \in G))) $ Le graphe $ G $ est alors unique en vertu de l'axiome d'extensionalite, et s'appelle le graphe de $ R $

Anschließend definieren sie die eigenlichen Funktionen (fonctions) als funktionelle Relationen mit Definitionsbereich $ A $ und Wertebereiche $ B $ (S. E II.13):

Autrement dit, une correspondance $ f = (F, A, B) $ est une fonction si, pour taut $ x $ appartenant à l' ensenzble de départ $ A $ de $ f $, la relation $ (x,y) \in F $ est fonctionnelle en $ y $ (I, p. 41);

$ F $ ist als Graph der Funktion eine Menge von Paaren. Dies ist die typische mengentheoretische Definition des Funktionsbegriffs.

Zu guter Letzt führt die Gruppe den Begriff Familie als Alternative für den Begriff Funktion ein (S. E II. 16):

Si $ f $ est une application de $ A $ dans $ B $, la fonction $ f $ est égale à la fonction $ x \rightarrow f(x) (x \in A, f(x) \in B) $, qu'on écrit sirnplement $ x \rightarrow f(x) $, ou aussi $ (f_x)_{x \in A} $ c'est surtout quand on utilise la dernière notation qu'on parle de « famille d'éléments » au lieu de « fonction ».

Die Begriffe Familie und Funktion unterscheiden sich nur syntaktisch. Die Syntax $ (f_x)_{x \in A} $ wurde in Anlehnung an die Tupelsyntax gewählt und betont damit die Verwandschaft zwischen diesen beiden Begriffen. Der Begriff Familie kann also als Alternative für den Begriff Tupel aufgefasst werden. Diese Definition hat den Vorteil, dass auch leere, einelementige und nicht-endliche Indexbereiche unterstützt werden.

Definition „Tupel“ (Gödel (1940))

Dfn $ <xy> = \{\{x\}\{xy\}\} $
Dfn $ <x_1,\ldots,x_n> = <x_1<x_2\ldots x_{n}>> $ [Anm. WK: wobei $ n \ge 3 $]
Dfn $ <x> = x $

Wegen der Rechtsassoziativität gilt folgender Satz (wie man laut Gödel per Induktion nachweist):

$ <x_1,\ldots,x_n<x_{n+1}\ldots x_{n+p}>> = <x_1\ldots x_{n}x_{n+1}\ldots x_{n+p}>> $

Anmerkung:
Diese Definition unterschiedet sich nicht wesentlich von der oben angeführten Tupel-Definition der Mathematikergruppe Bourbaki: Die Klammerung ist rechts- an Stelle von linksassoziativ und das einelementige Tupel wurde als Spezialfall ergänzt.

Definition „List“ (McCarthy (1960))

S-expressions are then defined as follows:

1. Atomic symbols are S-expressions.
2. If $ e_1 $ and $ e_2 $ are S-expressions, so is $ (e_1 \cdot e_2) $.

...

An S-expression is then simply an ordered pair, the terms of which may be atomic symbols or simpler S-expressions. We can represent a list of arbitrary length in terms of S-expressions as follows. The list

$ (m_1, m_2, \cdots, m_n) $

is represented by the S-expression

$ (m_1 \cdot (m_2 \cdot (\cdots (m_n \cdot \text{NIL}) \cdots ))) $

Here $ \text{NIL} $ is an atomic symbol used to terminate lists.

Anmerkung:
McCarthy erwähnt, dass es auch einelementige Listen gibt: $ (m) = (m \cdot \text{NIL}) $

Definition „List“ (McCarthy et al. (1965))

Seite 2:

An S-expression is either an atomic symbol or it is composed of these elements in the following order: a left parenthesis, an S-expression, a dot, an S-expression, and a right parenthesis.

Notice that this definition is recursive.

Seite 4:

Any S-expression can be expressed in terms of the dot notation. However, LISP has an alternative form of S-expression called the list notation. The list (m₁ m₂ . . . mₙ) can be defined in terms of dot notation. It is identical to (m₁ . (m₂ . ( . . . . (mₙ . NIL). . . ))).

The atomic symbol NIL serves as a terminator for lists. The null list ( ) is identical to NIL.

Definition „Property List“ (McCarthy et al. (1965))

Seite 39:

In LISP 1.5 wird eine (interne) Datenstruktur property list definiert, die dazu verwendet wird, atomaren Symbolen eine ganze Liste von Eigenschaften (properties) zuzuordnen. Dabei wird jede Eigenschaft (property) von einmem atomaren Symbol eingeleitet, welches Indikator (indicator) genannt wird.

Seite 58:

In LISP 1.5 gibt es eine Pseudofunktion „define“, um atomaren Symbolen Properties zuzuordnen:

The argument of define, x, is a list of pairs

((u₁ v₁) (u₂ v₂) ... (uₙ vₙ))

where each u is a name and each v is a λ-expression for a function. For each pair, define puts an EXPR on the property list for u pointing to v. The function of define puts things on at the front of the property list.

Common Lisp

Definition „Association List“ (Steele (1990), S431)

An association list, or a-list, is a data structure used very frequently in Lisp. An a-list is a list of pairs (conses); each pair is an association. The car of a pair is called the key, and the cdr is called the datum.

Übersetzung (W. Kowarschick):
Eine Assoziationsliste oder A-Liste ist eine Datenstruktur, die in Lisp sehr oft benutzt wird. Eine A-Liste ist eine Liste von Paaren (Cons-Zellen); jedes Paar ist eine Assoziation. Das car-Element [WK: das erste Element] eines Paare wird Schlüssel genannt und das cdr-Element [WK: das zweite Element] wird Datum genannt.

Definition „Property List“ (Steele (1990), S. 238 – 239)

Since its inception, Lisp has associated with each symbol a kind of tabular data structure called a property list (plist for short). A property list contains zero or more entries; each entry associates with a key (called the indicator), which is typically a symbol, an arbitrary Lisp object (called the value or, sometimes, the property). There are no duplications among the indicators; a property list may only have one property at a time with a given name. In this way, given a symbol and an indicator (another symbol), an associated value can be retrieved.

A property list is very similar in purpose to an association list. The difference is that a property list is an object with a unique identity; the operations for adding and removing property-list entries are destructive operations that alter the property list rather than making a new one. Association lists, on the other hand, are normally augmented non-destructively (without side effects) by adding new entries to the front (see acons and pairlis).

Übersetzung (W. Kowarschick):
Von Anfang an wurde in Lisp jedes Symbol mit einer Art tabellenartiger Datenstruktur verknüpft, die Propertyliste [WK: Eigenschaftsliste] genannt wird (kurz P-Liste). Eine Propertyliste enthält null oder mehr Einträge: Jeder Eintrag verknüpft einen Schlüssel (Indikator genannt), welcher typischerweise ein Symbol ist, mit einem beliebigen Lisp-Objekt (Wert genannt oder manchmal auch Property [WK: Eigenschaft]). Unter den Indikatoren gibt es keine Duplikate; eine Propertyliste kann zu jedem Zeitpunkt nur eine Eigenschaft mit einem gegebenen Namen haben. Auf diese Art kann für ein gegebenes Symbol und einen gegebenen Indikator (ein anderes Symbol) auf einen [WK: mit dem Symbol] verknüpften Wert zugegriffen werden.

Der Zweck einer Propertyliste ist dem einer Assoziationsliste sehr ähnlich. Der Unterschied ist, dass eine Propertyliste ein Objekt mit einer eindeutigen Identität ist; die Operationen zum Hinzufügen und Löschen von Propertylisten-Einträgen sind destruktive Operationen, die die Propertyliste verändern anstatt eine neue zu erstellen. Assoziationslisten werden demgegenüber nicht-destruktiv erweitert (ohne Seiteneffekte), indem neue Einträge vorne hinzugefügt werden (vgl. acons und pairlis).

Definition „Tupel“ (Schmidt (1966))

Schmidt definiert Tripel, Quadruppel ..., $ n $-Tupel genauso wie Bourbaki (siehe oben). Allerdings verwendet er eine eigene Definition des geordneten Paares, die auch echte Klassen zulässt:

$ (x,y) := \{\,\{\{x\}\}: x \in a\,\} \,\cup\, \{\,\{\emptyset, \{x\}\}: x \in b\,\} $
Wenn $ n \ge 3 $, dann $ (x_1,\ldots,x_n) := ((x_1,\ldots,x_{n-1}), x_n) $

Anmerkung:
Damit ist es z. B. möglich, das Monoid $ (\Omega, +, *) $ der Ordinalzahlen als Tupel zu definieren (die Klasse $ \Omega $ ist eine Unmege).

Definition „Familie“ (Schmidt (1966))

Schmidt definiert Funktionen $ f $ als Relation (d. h. als Teilklasse von $ \mathcal{V} \times \mathcal{V} $), die folgende Eindeutigkeitsbedingung erfüllt (S. 119):

$ \bigwedge x \bigwedge y \bigwedge z ((x,y) \in f \wedge (x,z) \in f \Rightarrow y=z) $

Den Wert der Funktion $ f $ an der Stelle $ x $ berechnet er folgendermaßen:

$ f(x) := \bigcap\{y|(x,y) \in f\} $

Das heißt, eine Funktion ist eine Klasse von geordneten Paaren (wobei die Paare selbst nur Mengen als Elemente enthalten können), bei denen kein Element des Definitionsbereichs doppelt vorkommt.

Er führt dann (S. 122) den Begriff Familie oder Folge als Synonym für den Begriff Funktion ein. Den Definitionsbereich nennt er in diesem Fall Indexbereich. Ein Element eines Indexbereichs heißt Index. An Stelle der Schreibweise $ f(x) $ verwendet er die Indexschreibweise $ f_x $.

Anmerkungen:
Im Prinzip unterscheidet sich diese Definition nicht wesenlich von der Definition von Bourbaki. Schmidt unterscheidet allerdings nicht zwischen Funktion und Funktionsgraph. Außerdeist sein Funktionsbegriff in der Hinsicht allgemeiner, dass eine Funktion nicht notwendigerweise eine Menge von Paaren ist, sondern auch eine echte Klasse von Paaren sein kann.

Auf der einen Seite ist der Begriff Schmidt-Familie universeller als der Begriff Schmidt-Tupel, da der Indexbereich auch leer, einelementig und beliebig groß sein kann. Auf der anderen Seite ist der Begriff Schmidt-Tupel universeller als der Begriff Schmidt-Familie, da ein Tupel auch echte Klassen als Elemente enthalten kann.

Definition „Tupel“ (Ebbinghaus (2003))

Ebbinghaus definiert zunächst das geordnete Paar

$ (x,y) := \{\{x\},\{x,y\}\} $

nach Kazimierez Kuratowski und verallgemeinert es dann für beliebige $ n $-Tupel ($ n \ge 1 $):

(i) $ (x) := x $
(ii) Für $ n \ge 1 $ sei $ (x_0,\ldots,x_n) := ((x_0,\ldots,x_{n-1}), x_n) $

Er formuliert den folgenden Satz:

$ (x_0,\ldots,x_n) = (y_0,\ldots,y_n) \leftrightarrow x_0 = y_0 \wedge \ldots \wedge x_n = y_n $

Einen Beweis gibt er nicht an, da sich dieser leicht durch metaprachliche Induktion ergäbe.

Anmerkung:
Diese Definition unterschiedet sich nicht von der Definition der Mathematikergruppe Bourbaki (siehe oben). Es wurde lediglich das einelementige Tupel als Spezialfall ergänzt, in derselben Weise, wie dies Gödel vorgeschlagen hat (siehe oben).

Definition „Familie“ (Ebbinghaus (2003))

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)