Tupel: Unterschied zwischen den Versionen
Kowa (Diskussion | Beiträge) (→Satz) |
Kowa (Diskussion | Beiträge) |
||
Zeile 292: | Zeile 292: | ||
Man beachte, dass sich das geordnete Paar <math>[x,y]</math> vom Tupel <math>(x,y)</math> (in Listennotation) unterscheidet, sofern | Man beachte, dass sich das geordnete Paar <math>[x,y]</math> vom Tupel <math>(x,y)</math> (in Listennotation) unterscheidet, sofern | ||
Letzteres mit Hilfe von <math>[x,y]</math> definiert wird. | Letzteres mit Hilfe von <math>[x,y]</math> definiert wird. | ||
Allerdings erfüllt <math>(x,y)</math> (nachdem es definiert wurde) | Allerdings erfüllt <math>(x,y)</math> (nachdem es definiert wurde) ebenfalls das [[Paaraxiom]] und kann überall, wo ein geordnetes Paar benötigt wird, genauso gut wie <math>[x,y]</math> | ||
verwendet werden. In [[LISP]] sieht man den Unterschied sehr schön: Die „Cons-Zelle“ <code>(x . y)</code> unterscheidet sich von der Liste | verwendet werden. In [[LISP]] sieht man den Unterschied sehr schön: Die „Cons-Zelle“ <code>(x . y)</code> unterscheidet sich von der Liste | ||
<code>(x y)</code>, die als Abkürzung für <code>(x . (y . NIL))</code> steht. Beide Definitionen erfüllen jedoch das | <code>(x y)</code>, die als Abkürzung für <code>(x . (y . NIL))</code> steht. Beide Definitionen erfüllen jedoch das Paaraxiom. | ||
===Attributtupel, Familie (in Anlehnung an Bourbaki<ref>{{Quelle|Bourbaki (1939)}}, S. E III.45</ref> und Schmidt<ref name="Schmidt">{{Quelle|Schmidt (1966)}}, S. 122</ref>)=== | ===Attributtupel, Familie (in Anlehnung an Bourbaki<ref>{{Quelle|Bourbaki (1939)}}, S. E III.45</ref> und Schmidt<ref name="Schmidt">{{Quelle|Schmidt (1966)}}, S. 122</ref>)=== |
Version vom 17. August 2019, 13:07 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: 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,
|
(name: 'Anton', sex:'m') {1/name: 'Anton',
|
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:
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:
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) 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.
Attributtupel, Familie (in Anlehnung an Bourbaki[1] und 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 (Attribut-)Tupel oder Familie über $ I $. Alternativ kann man auch $ I $-Tupel oder $ I $-Familie sagen.
Indexbereich und Indexmenge (Attributtupel)
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 (Attributtupel)
Die Mächtigkeit des Indexbereichs heißt Länge des Tupels:
Ein Tupel der Länge $ l $ wird auch $ l $-Tupel genannt.
Schlüssel und Wert (Attributtupel)
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 (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
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[3] zurück.
Positionstupel (in Anlehnung an McCarthy et al.[4])
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:
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'] $:
Das Tupel $ t' $ ist wegen des Paaraxioms sogar eindeutig bestimmt:
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:
In diesem Fall gilt nur:
Tupellänge (Positionstupel)
Es sei $ t $ ein Positionstupel: $ TupV(t) $. Die Länge $ \rm{lg}(t) $ von $ t $ wird ebenfalls induktiv definiert:
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.
Indexmenge (Positionstupel)
Für ein Positionstupels $ t $ wird die Indexmenge $ I(t) $ folgendermaßen definiert :
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 des Tupels
Die Länge eines Positionstupels $ t $ ist gleich der Mächtigkeit der Indexmenge: $ \rm{lg}(t) = |I(t)| $
Beweis
Schlüssel und Wert (Positionstupel)
Es seien $ t $ ein nicht-leeres Positionstupel 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'] $.
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:
Allgemein für $ n \ge 2 $:
Anmerkungen (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.[5]
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[6] bezeichnet McCarthy $ \rm{NIL} $ lediglich als „atomares Symbol“, welches benutzt wird, um Listen zu terminieren. Erst im Beutzerhandbuch von LISP 1.5[4] 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[2] (und diversen anderen Autoren):
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[7] (und diversen anderen Autoren):
Gödel hat Tupel im Prinzip genauso wie Schmidt definiert. Zusätzlich hat er allerdings noch 1-Tupel eingeführt:
Doch auch diese zusätzliche Festlegung löst die obigen Probleme nicht wirklich.
Mengentupel und Klassentupel (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
und damit auch
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 ...[8]
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) $:
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:
- $ I(t) = I(t') = \{i \in \mathbb{N}: 0 < i \le \rm{lg}(t)\} $
- $ \rm{lg}(t) = \rm{lg}(t') $
- $ \bigwedge i \in I: t_i = t'_i $, wobei $ I := I(t) = I(t') $
Beweis
Man kann die erste Aussage
beweisen, indem man
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:
Die dritte Behauptung folgt direkt aus der ersten Aussage und der Definition von $ t'_i $ und $ t' $:
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:
oder, anders formuliert:
Lemma
Zwei gleiche Tupel (in Attribut- oder Listennotation) sind trivialerweise gleich lang :
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 Indexmengen $ I(t_1) $ und $ I(t_2) $ übereinstimmen und wenn die Funktionswerte für jedes Element der Indexmenge ebenfalls übereinstimmen:
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.
Quellen
- ↑ Bourbaki (1939): Nicolas Bourbaki; Théorie des ensembles; Verlag: Hermann; Adresse: Paris; 1939; Quellengüte: 5 (Buch), S. E III.45
- ↑ 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
- ↑ 4,0 4,1 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)
- ↑ 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)
- ↑ , S. 11
- ↑ Gödel (1940): Kurt Gödel; The Consistency of the Continuum Hypothesis; Verlag: Princeton University Press; ISBN: 0-691-07927-7; Web-Link; 1940; Quellengüte: 5 (Buch)
- ↑ zitiert nach Schmidt (1966), S. 174
Siehe auch
- Kowarschick (MMDB-Skript): Wolfgang Kowarschick; Vorlesung Multimedia-Datenbanksysteme – Sommersemester 2018; Hochschule: Hochschule Augsburg; Adresse: Augsburg; Web-Link; 2018; Quellengüte: 4 (Skript)