Tupel: Unterschied zwischen den Versionen
Kowa (Diskussion | Beiträge) |
Kowa (Diskussion | Beiträge) |
||
| Zeile 337: | Zeile 337: | ||
Diese Definition geht auf McCarthy zurück:<ref>{{Quelle|McCarthy, J. (1960): Recursive Functions of Symbolic Expressions and Their Computation by Machine}}</ref> | Diese Definition geht auf McCarthy zurück:<ref>{{Quelle|McCarthy, J. (1960): Recursive Functions of Symbolic Expressions and Their Computation by Machine}}</ref> | ||
<div class="quote">The list $(m_1,m_2,···,m_n)$ is represented by the S-expression $(m_1·(m_2·(···(m_n·\rm{NIL})···)))$. | <div class="quote">The list $(m_1,m_2,···,m_n)$ is represented by the S-expression $(m_1·(m_2·(···(m_n·\rm{NIL})···)))$.<br/> | ||
Here $\rm{NIL}$ is an atomic symbol used to terminate lists.</div> | Here $\rm{NIL}$ is an atomic symbol used to terminate lists.</div> | ||
Version vom 22. Mai 2013, 11:15 Uhr
Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nur teilweise:
| Korrektheit: 3 (zu größeren Teilen überprüft) |
Umfang: 4 (unwichtige Fakten fehlen) |
Quellenangaben: 3 (wichtige Quellen vorhanden) |
Quellenarten: 4 (sehr 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 oder Klasse 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, Attributname | key, index, attribute/property name, attribute/property key |
| Wert | Glied, Attributwert | value, attribute/property 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 die Ordnung der Tupelelemente nur dann eine Rolle (zumindest in der Informatik), 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 unterscheiden sich die Indexmengen ($t_1$ bis $t_4$ haben die Länge 3, Tupel $t_5$ hat dagegen die Länge 4) oder es stimmen nicht alle gleich benannten Elemente überein (alle übrigen Tupelpaare).
Folgendes ist kein Tupel (und auch keine Funktion), da zwei Elemente gleich benannt sind:
Die Attribut-Notation kömmt 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. 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 erweiter- oder kürzbar) - Pascal: Datentyp
record(zur Laufzeit nicht erweiter- 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
Tupel in Indexnotation, Familie (in Anlehnung an Schmidt[2])
Es sei $t: I \rightarrow \mathcal{V}$ eine beliebige Funktion von einer Menge oder Klasse $I$ in die Allklasse $\mathcal{V}$.
$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, genauer: $I$-Tupel oder $I$-Familie der Länge $n := |I|$ über $I$.
Indexmenge
Die Definitionsmenge $I(t) := I = \rm{Def}(f) = \{x: \exists 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
Die Mächtigkeit des Indexbereichs heißt Länge des Tupels:
Schlüssel und Wert
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.
Anmerkung
Schmidt verwendet die Bezeichnung „Glied“ an Stelle von „Wert“.
Der Begriff „$I$-Tupel“ geht auf Ebbinghaus[3] zurück.
Geordnete Paare, 2-Tupel
Der Term $[a,b]$, wobei $a$ und $b$ zwei Mengen oder Klassen sind, heißt geordnetes Paar oder $2$-Tupel, wenn für den Operator $[\cdot,\cdot]$ das Peanosche Paaraxiom erfüllt ist:
In Anlehnung an McCarthy[4] werden für Paare folgende beiden Operationen definiert, um das erste bzw. das zweite Element des Paars zu extrahieren:
Anmerkungen
Beispiele für mögliche Definitionen von $[a,b]$ sind[2]:
Im Falle der ersten Definition müssen $a$ und $b$ Mengen sein ($\rm{Mg}(a) \wedge \rm{Mg}(b)$), damit das Paaraxiom erfüllt ist. Im Falle der zweiten Definition ist das Paaraxiom für beliebige Klassen $a$ und $b$ erfüllt.[2]
Bei McCarthy werden geordnete Paare in der Form $(a \cdot b)$ notiert und mit der Funktion $\rm{cons}$ erzeugt.[4]
Geordnete Paare sind im Gegensatz zu Mengen tatsächlich geordnet:
In einem mengebasiertes Axiomen-System (wie es z.B. der Zermelo-Fraenkel-Mengenlehre zu Grunde liegt) ist die vorangehende Formel sowohl für Mengenpaare, als auch für Klassenpaare unbeschränkt gültig, da in diesem Fall $\forall$ als „Für alle Mengen innerhalb des Mengenuniversums“ interpretiert wird.
In einem klassenbasierten Axiomen-System (wie es z.B. der Neumann-Bernays-Gödel-Mengenlehre zu Grunde liegt) ist die Formel allerdings nur im Falle von Klassenpaaren gültig, da hier $\forall$ als „Für alle Klassen, d.h. für alle Mengen und Unmengen innerhalb des Klassenuniversums“ interpretiert wird.. Bei Mengenpaaren gilt lediglich:
Für Unmengen ist ein Mengenpaar dagegen stets gleich der Allklasse $\mathcal{V}$, unabhängig von der Reihenfolge der Elemente:
Das heißt, im Falle eines klassenbasierten Axiomen-Systems sollte man eine Klassenpaar-Definition an Stelle einer Mengenpaar-Definition verwenden.
Tupel in Vektornotation (in Anlehnung an McCarthy et al.[4])
Der Paar-Begriff kann induktiv für eine beliebige endliche Anzahl von Elementen verallgemeinert werden. Eine Menge oder Klasse $t$ heißt Tupel (in Vektornotation) – in Zeichen $\rm{TupV}(t)$ – wenn entweder $t=\emptyset$ gilt oder wenn $t$ ein Paar ist, dessen erstes Element beliebig und dessen zweites Element ein Tupel ist:
Andere Tupel in Vektornotation 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']$:
Das Tupel $t'$ ist wegen des Paaraxioms sogar eindeutig bestimmt:
Man beachte, dass die Formel in einem klassenbasiertem Axiomensystem wiederum nur für Klassenpaare gilt und für Mengenpaare entsprechend eingeschränkt werden müsste.
Länge eines Tupels
Es sei $t$ ein Tupel in Vektornotation: $TupV(t)$. Die Länge $\rm{lg}(t)$ von $t$ wird ebenfalls induktiv definiert:
Ein Tupel der Länge $n$ heißt $n$-Tupel in Vektornotation.
Das $0$-Tupel wird auch leeres Tupel genannt.
Lemma
Die Länge eines Tupels in Vektornotation ist eindeutig bestimmt
Beweis
Das leere Tupel das einzige Tupel der Länge $0$ ist. 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
Für ein Tupel $t$ in Vektornotation wird die Indexmenge $I(t)$ folgendermaßen definiert:
Schlüssel und Wert
Es seien $t$ ein nicht-leeres Tupel in Vektornotation und $I := I(t)$ die zugehörige Indexmenge. Die Elemente $i\in I$ der Indexmenge heißen Schlüssel. Jedem Schlüssel wird durch das Tupel 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']$.
\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.
Vektornotation
Für Tupel in Vektornotation wird Folgende abkürzende Schreibweise eingeführt:
Allgemein für $n \ge 1$:
Diese Definition geht auf McCarthy zurück:[5]
Here $\rm{NIL}$ is an atomic symbol used to terminate lists.
TO BE DONE
Abbildung der Vektor- auf Attributnotation
TO BE DONE
Für jedes $n$-Tupel $t = (x_1,\ldots,x_n)$ in Vektornotation kann ein zugehöriges Tupel $t'$ in Attributnotation ebenfalls induktiv definiert, sofern das Tupel nur Mengen und damit keine Unmengen enthält, d.h., sofern $\rm{Mg}(x_1),\ldots,\rm{Mg}(x_n)$:
Einem $n$-Tupel $t = (x_1,\ldots,x_n)$ ist die Indexmenge $I(t) := \rm{Def}(t')$
und damit die Länge $\rm{lg}(t) := |\rm{Def}(t')|$ zugeordnet.
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.
TO BE DONE
Lemma
Für jedes $n$-Tupel $t = (x_1,\ldots,x_n)$, das keine Unmengen enthält, gilt: $I(t) = I(t')$ und $\rm{lg}(t) = \rm{lg}(t')$
Beweis: durch vollständige Induktion
Lemma
Die Indexmenge $I(t)$ eines $n$-Tupels $t = (x_1,\ldots,x_n)$ ist gleich $\{1,\ldots,n\}$ und die Länge beträgt $n$.
Beweis: durch vollständige Induktion
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 Tupel (in Attribut- oder Vektor-Notation) sind trivialerweise gleichlang:
Beweis
Die Behauptung folgt direkt aus der Reflexivität der Gleichheit ($\text{lg}(t_1) = \text{lg}(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 Tupel (in Attribut- oder Vektor-Notation).
$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:
Beweis für Attribut-Notation: siehe Schmidt, J. (1966): Mengenlehre, S. 122, Aussagen 14.10 und 14.11[2]
Beweis für Vektor-Notation: mittels vollständiger Induktion.
TO BE DONE
Quellen
- ↑ http://streamjs.org/
- ↑ 2,0 2,1 2,2 2,3 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
- ↑ 4,0 4,1 4,2 McCarthy et. al. (1965): John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart und Michael I. Levin; LISP 1.5 Programmer's Manual; Verlag: The MIT Press; Adresse: Cambridge, Massachusetts; Web-Link; 1965 (Buch), S. 4
- ↑ McCarthy (1960): John McCarthy; Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I; in: Communications of the ACM; Band: 3; Nummer: 4; Seite(n): 184-195; Verlag: Association for Computing Machinery; Adresse: New York; Web-Link 0, Web-Link 1; 1960; Quellengüte: 5 (Artikel)
