Tupel
Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nur teilweise:
| Korrektheit: 4 (großteils überprüft) |
Umfang: 3 (einige wichtige Fakten fehlen) |
Quellenangaben: 2 (wichtige Quellen fehlen) |
Quellenarten: 3 (gut) |
Konformität: 5 (ausgezeichnet) |
Anschauliche Definition (nach Kowarschick)
Ein Tupel ist eine Menge (oder gar eine Klasse) von unterschiedlich benannten Werten, d.h. eine Menge von Schlüssel/Wert-Paaren, wobei jeder Schlüssel nur einmal vorkommen darf.
| Begriff | Alternativnamen | englische Bezeichnungen |
|---|---|---|
| Tupel | Familie, Folge | tuple, indexed family, sequence |
| Schlüssel/Wert-Paar | Attribut | key/value pair, attribute, property |
| Schlüssel | Index | key, index |
| Wert | Glied | value |
Indexmenge
Die Menge aller Schlüssel eines Tupels wird Indexmenge des Tupels genannt.
Länge eines Tupels
Die Länge eines Tupel ist gleich der Mächtigkeit der zugehörigen Indexmenge.
Ein Tupel der Länge $n$ wird auch $n$-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 Definitionsbreichs einen Wert zu, entsprechend ordnet ein Tupel jedem Schlüssel, also jedem Element der Indexmenge einen Wert zu.
Tupel können als geordnete Multimengen, d.h. als Listen aufgefasst werden (zumindest, sofern für die Elementnamen eine Ordnung definiert ist):
- Elementwerte können mehrfach vorkommen (im Gegensatz zu normalen Mengen, aber in Einklang mit Multimengen).
- Die Elemente sind gemäß den Elementnamen angeordnet (im Gegensatz zu Mengen und Multimengen).
Üblicherweise spielt allerdings (zumindest in der Informatik) die Ordnung der Tupelelemente nur dann eine Rolle, wenn eine Menge von aufeinanderfolgenden natürlichen Zahlen als Indexmenge verwendet wird.
Beispiele
Beispiele in Attribut-Notation
Im Fall von endlichen Indexmengen kann ein Tupel einfach durch die explizite Angabe von Schlüssel/Wert-Paaren erfolgen. In der Informatik wird ein Schlüssel/Wert-Paar häufig als Attribut (attribute, property) bezeichnet, bestehend aus Attributnamen (attribute name, property name) und Attributwert (attribute value, property value). Daher wird folgende Notation auch Attribut-Notation genannt:
Nur Tupel $t_2$ und $t_4$ sind gleich, alle anderen Tupel unterscheiden sich. Entweder stimmen nicht alle gleich benannten Elemente überein (Tupel $t_1$ und $t_3$) oder die Indexmengen unterscheiden sich (alle übrigen Tupelpaare).
Die Länge der ersten vier Tupel beträgt 3, die Länge des fünften Tupels beträgt 4.
Folgendes ist kein Tupel (und auch keine Funktion), da zwei Elemente gleich benannt sind:
Die Attribut-Notation kömmt in der Informatik häufiger 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. Der zugehörige Attributwert wird vom Attributnamen durch einen Doppelpunkt abgetrennt.
t1 = {"name": "Wolfgang", "geburtsjahr": 1961, "hochschule": "HSA"}t2 = {"name": "Wolfgang", "geburtsjahr": 1961, "ehefrau": "Marianne"}t3 = {"name": "Wolfgang", "geburtsjahr": 1962, "hochschule": "HSA"}t4 = {"ehefrau": "Marianne", "geburtsjahr": 1961, "name": "Wolfgang", }t5 = {"name": "Wolfgang", "geburtsjahr": 1961, "ehefrau": "Marianne", "hochschule": "HSA"}Weitere Beispiele für Datenstrukturen, in denen Mengen von Schlüssel/Wert-Paaren zum Einsatz kommen.
- C/C++: Datentyp
struct(zur Laufzeit nicht erweiterbar oder kürzbar) - Pascal: Datentyp
record(zur Laufzeit nicht erweiterbar oder kürzbar) - diverse Sprachen: Hashtabelle (auch hash map, hash Array, assoziatives Array etc.; zur Laufzeit erweiterbar und kürzbar)
- SQL: Tabellenzeilen, d.h. Elemente von Relationen (zur Laufzeit durch Schema-Evolution erweiterbar und kürzbar)
- JavaScript: Objekte (zur Laufzeit erweiterbar oder kürzbar, sofern dies nicht explizit mittels
Object.freeze„untersagt“ wird) - Java und viele andere Sprachen: Objekte (zur Laufzeit i. Allg. nicht erweiterbar oder kürzbar)
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.ehefrauetc.
Beispiele in Vektor-Notation
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 Vektor-Notation an. Bei dieser werden die Elementnamen nicht explizit angegeben, sondern implizit durch die Position der Elemente festgelegt:
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 ω (abzählbar unendlich). Tupel $t_9$ ist also ein ω-Tupel. 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.
In JSON kommt die Vektor-Notation ebenfalls zu Einsatz:
t6 = [555, 333]t7 = [333, 555]t8 = [555, 333, 555]Unendliche lange Tupel können in JSON nicht angegeben werden, wohl aber beispielsweise
in JavaScript mit Hilfe der Bibliothek stream.js[1],
die ein Element eines Streams (= Tupel) mittels Lazy Evaluation erst dann ermittelt, wenn es wirklich benötigt wird:
var nat = Stream.range(0); // nat = (0, 1, 2, 3, ...)
var t9 = nat.map(function(x){ return 2*x; }); // t9 = (0, 2, 4, 6, ...)
t9.take(3).print(); // Gibt 0, 2, 4 auf der Konsole aus.
In der Informatik finden sich weitere Datenstrukturen, in denen Elemente sequenziell abgespeichert werden, d.h., in 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)
Um mittels der Attributposition auf einen Attributwert zuzugreifen, hat sich in der Informatik ein syntaktisches Konstrukt etabliert:
- Die Indexnotation:
t6[1],t8[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 von einem Element zu nächsten „hangelt“, bis man beim gewünschten Element angekommen ist.
Spezielle Tupel
| Länge $n$ | Name | Attribut-Notation | Vektor-Notation |
|---|---|---|---|
| 0 | Leeres Tupel | $\{\}$ | $()$ |
| 1 | Singel | $\{(a,5)\}$ | $(5)$ |
| 2 | (geordnetes) Paar | $\{(a,5), (b,3)\}$ | $(5,3)$ |
| 3 | Triple | $\{(a,5), (b,3), (c,8)\}$ | $(5,3,8)$ |
| 4 | Quadrupel | $\{(a,5), (b,3), (c,8), (d,π)\}$ | $(5,3,8,π)$ |
| 5 | Quintupel | $\vdots$ | $\vdots$ |
| 6 | Sextupel | ||
| 7 | Septupel | ||
| 8 | Oktupel | ||
| $\vdots$ | $\vdots$ | ||
| 100 | Centupel | ||
| $n$ | $n$-Tupel | ||
| ω | ω-Tupel, Folge, Reihe, Familie | $\{(i,i^2): i \in \mathbb N\}$ | $(i^2)_{i \in \mathbb N}$ |
Formale Definitionen
Familie (in Anlehnung an Schmidt[2])
Es sei $f: I \rightarrow \mathcal{V}$ eine beliebige Funktion von einer Menge oder Klasse $I$ in die Allklasse $\mathcal{V}$.
$t$ wird alternativ auch Familie oder Tupel genannt oder, genauer, $I$-Familie oder $I$-Tupel der Länge $n := |I|$ über $I$.
Die Definitionsmenge $I = \rm{Def}(f):= \{x: \exists y: (x,y) \in t\}$ der Funktion $f$ heißt in diesem Fall Indexbereich oder, falls es sich bei $I$ um eine echte Menge und nicht um eine Unmenge handelt, Indexmenge.
Jedes Element $i$ des Indexbereichs heißt Schlüssel oder Index, das zum Index $i$ gehörende Element $f_i := f(i)$ wird als Wert bezeichnet.
Anmerkung
Schmidt verwendet die Bezeichnung „Glied“ an Stelle von „Wert“.
Der Begriff „$I$-Tupel“ geht auf Ebbinghaus[3] zurück.
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:
oder, anders fomuliert:
Lemma
Zwei gleiche gleiche Familien sind trivialerweise gleichlang:
Beweis
Die Behauptung folgt direkt aus der Reflexivität der Gleichheit ($|\text{Def}(t_1)| = |\text{Def}(t_1)|$) und der Leibnitzschen 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 Familien.
$t_1$ und $t_2$ sind genau dann gleich, wenn die zugehörigen Indexmengen übereinstimmen und wenn die Funktionswerte für jedes Element der Indexmenge ebenfalls übereinstimmen:
Beweis: siehe Schmidt, J. (1966): Mengenlehre, S. 122, Aussagen 14.10 und 14.11[2]
Quellen
- ↑ http://streamjs.org/
- ↑ 2,0 2,1 Schmidt (1966): Jürgen Schmidt; Mengenlehre – Grundbegriffe; Reihe: B.I.Hochschultaschenbücher; Band: 1; Nummer: 56; Verlag: Bibliographisches Institut AG; Adresse: Mannheim; ISBN: B0000BUJC6; 1966; Quellengüte: 5 (Buch), S. 122
- ↑ Ebbinghaus (2003): Heinz-Dieter Ebbinghaus; Einführung in die Mengenlehre; Reihe: Hochschultaschenbuch; Auflage: 4; Verlag: Spektrum Akademischer Verlag; Adresse: Heidelberg, Berlin; ISBN: 3-8274-1411-3; 2003; Quellengüte: 5 (Buch), S. 59–60
