Tupel/Formale Definition - Versionsgeschichte

Kowa: /* Ursprung und Varianten der Listennotation */

2020-09-22T12:16:28Z

Ursprung und Varianten der Listennotation

← Nächstältere Version		Version vom 22. September 2020, 12:16 Uhr
Zeile 192:		Zeile 192:
	<div class="formula"><math>(x_1) := x_1</math></div>		<div class="formula"><math>(x_1) := x_1</math></div>

	Doch auch diese zusätzliche Festlegung löst die obigen Probleme nicht wirklich.		Doch auch diese zusätzliche Festlegung löst die obigen Probleme nicht wirklich, insbesondere, da ein einelementiges Tupel und sein Element nicht unterschieden werden.

	=====Mengen- und Klassen-Positionstupel=====		=====Mengen- und Klassen-Positionstupel=====

Kowa: /* Listennotation */

2020-09-22T12:14:59Z

Listennotation

← Nächstältere Version		Version vom 22. September 2020, 12:14 Uhr
Zeile 150:		Zeile 150:
	====Listennotation====		====Listennotation====

	Für Positionstupel ~~wird~~ folgende ~~abkürzende Schreibweise~~ eingeführt:		Für Positionstupel werden folgende abkürzenden Schreibweisen eingeführt:

	<div class="formula"><math>() := \emptyset</math></div>		<div class="formula"><math>() := \emptyset</math></div>

Kowa: /* Positionstupel (in Anlehnung an McCarthy et al.{{Quelle|McCarthy et. al. (1965)}}) */

2020-09-22T12:14:26Z

Positionstupel (in Anlehnung an McCarthy et al.{{Quelle|McCarthy et. al. (1965)}})

← Nächstältere Version		Version vom 22. September 2020, 12:14 Uhr
Zeile 91:		Zeile 91:
	<div class="formula"><math>\bigwedge x, t: \rm{TupV}(t) \rightarrow \rm{lg}([x,t]) := \rm{lg}(t)+1</math></div>		<div class="formula"><math>\bigwedge x, t: \rm{TupV}(t) \rightarrow \rm{lg}([x,t]) := \rm{lg}(t)+1</math></div>

	Ein Tupel der Länge <math>l</math> heißt '''<math>l</math>-Positionstupel'''.		Ein Tupel der Länge <math>n</math> heißt '''<math>n</math>-Positionstupel'''.

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

Kowa: /* Anmerkungen zum Attributtupel) */

2020-09-22T12:13:24Z

Anmerkungen zum Attributtupel)

← Nächstältere Version		Version vom 22. September 2020, 12:13 Uhr
Zeile 54:		Zeile 54:
	Schmidt verwendet die Bezeichnung „''Glied''“ an Stelle von „''Wert''“.		Schmidt verwendet die Bezeichnung „''Glied''“ an Stelle von „''Wert''“.

	Der Begriff „I-Tupel“ geht auf Ebbinghaus<ref name="Ebbinghaus">{{Quelle\|Ebbinghaus (2003)}}, S. 59–60</ref> zurück.		Der Begriff „<math>I</math>-Tupel“ geht auf Ebbinghaus<ref name="Ebbinghaus">{{Quelle\|Ebbinghaus (2003)}}, S. 59–60</ref> zurück.

	===Positionstupel (in Anlehnung an McCarthy et al.<ref name="McCarthy (1965)">{{Quelle\|McCarthy et. al. (1965)}}</ref>)===		===Positionstupel (in Anlehnung an McCarthy et al.<ref name="McCarthy (1965)">{{Quelle\|McCarthy et. al. (1965)}}</ref>)===

Kowa am 22. September 2020 um 12:11 Uhr

2020-09-22T12:11:01Z

Kowa: /* Länge eines Attributtupel */

2020-09-22T12:10:07Z

Länge eines Attributtupel

← Nächstältere Version		Version vom 22. September 2020, 12:10 Uhr
Zeile 35:		Zeile 35:
	<div class="formula"><math>\rm{lg}(t) := \|I(t)\|</math></div>		<div class="formula"><math>\rm{lg}(t) := \|I(t)\|</math></div>

	Ein Tupel der Länge <math>l</math> wird auch <math>l</math>-'''Tupel''' genannt.		Ein Tupel der Länge <math>n</math> wird auch <math>n</math>-'''Tupel''' genannt.

	====Schlüssel und Wert eines Attributtupels====		====Schlüssel und Wert eines Attributtupels====

Kowa am 22. September 2020 um 12:07 Uhr

2020-09-22T12:07:50Z

← Nächstältere Version		Version vom 22. September 2020, 12:07 Uhr
Zeile 6:		Zeile 6:
	\|conformance = 5		\|conformance = 5
	}}		}}
	Eine informelle Definition des Begriffs [[Tupel]] wurde im [[Tupel\|zugehörigen Artikel]] angegeben. Dort findet man auch einen ~~Überblck~~ über die		Eine informelle Definition des Begriffs [[Tupel]] wurde im [[Tupel\|zugehörigen Artikel]] angegeben. Dort findet man auch einen Überblick über die
	zugehörige Geschichte einschließlich unterschiedlicher Definitionen. Im Folgenden wird der ~~tupelbegriff~~ auf Basis dieser Definitionen formalisiert.		zugehörige Geschichte einschließlich unterschiedlicher Definitionen. Im Folgenden wird der Tupelbegriff auf Basis dieser Definitionen formalisiert.
	Dabei wird vorausgesetzt, dass der Term „[[geordnetes Paar]]“ <math>[x,y]</math> schon definiert oder axiomatisch eingeführt wurde.		Dabei wird vorausgesetzt, dass der Term „[[geordnetes Paar]]“ <math>[x,y]</math> schon definiert oder axiomatisch eingeführt wurde.

Zeile 31:		Zeile 31:
	in diesem Fall '''Indexbereich'''. Falls es sich bei <math>I</math> um eine echte {{Menge}} und nicht um eine {{Unmenge}} handelt, kann man auch '''Indexmenge''' sagen.		in diesem Fall '''Indexbereich'''. Falls es sich bei <math>I</math> um eine echte {{Menge}} und nicht um eine {{Unmenge}} handelt, kann man auch '''Indexmenge''' sagen.

	====~~Tupellänge (~~Attributtupel)====		====Länge eines Attributtupel====
	Die [[Mächtigkeit]] des Indexbereichs heißt '''Länge des Tupels''':		Die [[Mächtigkeit]] des Indexbereichs heißt '''Länge des Tupels''':
	<div class="formula"><math>\rm{lg}(t) := \|I(t)\|</math></div>		<div class="formula"><math>\rm{lg}(t) := \|I(t)\|</math></div>
Zeile 37:		Zeile 37:
	Ein Tupel der Länge <math>l</math> wird auch <math>l</math>-'''Tupel''' genannt.		Ein Tupel der Länge <math>l</math> wird auch <math>l</math>-'''Tupel''' genannt.

	====Schlüssel und Wert ~~(Attributtupel)~~====		====Schlüssel und Wert eines Attributtupels====
	Jedes Element <math>i</math> des Indexbereichs heißt '''Schlüssel''' oder '''Index'''.		Jedes Element <math>i</math> des Indexbereichs heißt '''Schlüssel''' oder '''Index'''.

	Das zum Index <math>i</math> gehörende Element <math>t_i := t(i)</math> wird als '''Wert''' bezeichnet.		Das zum Index <math>i</math> gehörende Element <math>t_i := t(i)</math> wird als '''Wert''' bezeichnet.

	====Anmerkungen (Attributtupel)====		====Anmerkungen zum Attributtupel)====

	Mit <math>\rm{Fkt}(f)</math> wird ausgedrückt, dass es sich bei einer Menge oder Klasse <math>f</math> um eine Funktion handelt, dass <math>f</math> also eine Menge oder Klasse von		Mit <math>\rm{Fkt}(f)</math> wird ausgedrückt, dass es sich bei einer Menge oder Klasse <math>f</math> um eine Funktion handelt, dass <math>f</math> also eine Menge oder Klasse von
Zeile 83:		Zeile 83:
	<div class="formula"><math>\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) ))</math></div>		<div class="formula"><math>\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) ))</math></div>

	====~~Tupellänge (Positionstupel)~~====		====Länge eines Positionstupels====

	Es sei <math>t</math> ein Positionstupel: <math>TupV(t)</math>.		Es sei <math>t</math> ein Positionstupel: <math>TupV(t)</math>.
Zeile 106:		Zeile 106:
	ebenfalls eindeutig bestimmt.		ebenfalls eindeutig bestimmt.

	====Indexbereich ~~(Positionstupel)~~====		====Indexbereich eines Positionstupels====

	Für ein Positionstupels <math>t</math> wird die '''Indexbereich''' <math>I(t)</math> folgendermaßen definiert :		Für ein Positionstupels <math>t</math> wird die '''Indexbereich''' <math>I(t)</math> folgendermaßen definiert :
Zeile 116:		Zeile 116:
	verwenden, müsste dann aber ein paar Anpassungen vornehmen ({{zB}} beim nachfolgenden Lemma).		verwenden, müsste dann aber ein paar Anpassungen vornehmen ({{zB}} beim nachfolgenden Lemma).

	=====Lemma: Länge ~~des Tupels~~=====		=====Lemma: Länge eines Positionsupels=====

	Die Länge eines Positionstupels <math>t</math> ist gleich der Mächtigkeit des Indexbereichs: <math>\rm{lg}(t) = \|I(t)\|</math>		Die Länge eines Positionstupels <math>t</math> ist gleich der Mächtigkeit des Indexbereichs: <math>\rm{lg}(t) = \|I(t)\|</math>
Zeile 123:		Zeile 123:
	<div class="formula"><math>\|I(t)\| = \|\{i \in \mathbb{N}: 0 < i \le \rm{lg}(t)\}\| = \rm{lg}(t)</math></div>		<div class="formula"><math>\|I(t)\| = \|\{i \in \mathbb{N}: 0 < i \le \rm{lg}(t)\}\| = \rm{lg}(t)</math></div>

	====Schlüssel und Wert ~~(Positionstupel)~~====		====Schlüssel und Wert eines Positionstupels====

	Es seien <math>t</math> ein nicht-leeres Positionstupel und <math>I := I(t)</math> der zugehörige Indexbereich.		Es seien <math>t</math> ein nicht-leeres Positionstupel und <math>I := I(t)</math> der zugehörige Indexbereich.
Zeile 160:		Zeile 160:
	<div class="formula"><math>(x_1,\ldots,x_n) := [(x_1,\ldots,x_{n-1}), x_n] = [[[\ldots[\emptyset,x_1]\ldots], x_{n-1}], x_n]</math></div>		<div class="formula"><math>(x_1,\ldots,x_n) := [(x_1,\ldots,x_{n-1}), x_n] = [[[\ldots[\emptyset,x_1]\ldots], x_{n-1}], x_n]</math></div>

	====Anmerkungen (Positionstupel)====		====Anmerkungen zum Positionstupel====
	=====Ursprung und Varianten der 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):		Die obige Definition der Listennotation geht auf McCarthy zurück (wobei er die Liste allerdings vom letzten Element ausgehend aufbaut):
Zeile 171:		Zeile 171:

	In seinen ursprünglichen Publikationen wie auch im Benutzerhandbuch von LISP I<ref>{{Quelle\|McCarthy et. al. (1960)}}, S. 11</ref>		In seinen ursprünglichen Publikationen wie auch im Benutzerhandbuch von LISP I<ref>{{Quelle\|McCarthy et. al. (1960)}}, S. 11</ref>
	bezeichnet McCarthy <math>\rm{NIL}</math> lediglich als „atomares Symbol“, welches benutzt wird, um Listen zu terminieren. Erst im ~~Beutzerhandbuch~~ von		bezeichnet McCarthy <math>\rm{NIL}</math> lediglich als „atomares Symbol“, welches benutzt wird, um Listen zu terminieren. Erst im Benutzerhandbuch von
	LISP 1.5<ref name="McCarthy (1965)" /> legt er zusätzlich		LISP 1.5<ref name="McCarthy (1965)" /> legt er zusätzlich
	fest, dass <math>\rm{NIL}</math> identisch zur leeren Liste <math>()</math> ist.		fest, dass <math>\rm{NIL}</math> identisch zur leeren Liste <math>()</math> ist.
Zeile 194:		Zeile 194:
	Doch auch diese zusätzliche Festlegung löst die obigen Probleme nicht wirklich.		Doch auch diese zusätzliche Festlegung löst die obigen Probleme nicht wirklich.

	=====~~Mengentupel~~ und ~~Klassentupel (~~Positionstupel)=====		=====Mengen- und Klassen-Positionstupel=====

	In einer klassenbasierten Mengenlehre erhält man mit Hilfe der obigen Definition so genannte '''Klassentupel''',		In einer klassenbasierten Mengenlehre erhält man mit Hilfe der obigen Definition so genannte '''Klassentupel''',
Zeile 228:		Zeile 228:
	Die zugehörigen Induktionsbeweise müssen in diesem Fall außerhalb des Axiomensystems der Mengenlehre auf geführt werden,		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.		also beispielsweise mit Hilfe der [[Metasprache]], die zur Definition des formalen System verwendet wurde.
	Man beachte, dass die obigen Beweise ~~genaugenommen~~ sogar innerhalb der [[Metasprache#Metametasprache\|Metametasprache]] „Deutsch“ geführt wurden.		Man beachte, dass die obigen Beweise genau genommen sogar innerhalb der [[Metasprache#Metametasprache\|Metametasprache]] „Deutsch“ geführt wurden.

	Das Problem ist, dass man, obwohl man eine Arithmetik der natürlichen Zahlen formal mit Hilfe der Mengenlehre-Axiome		Das Problem ist, dass man, obwohl man eine Arithmetik der natürlichen Zahlen formal mit Hilfe der Mengenlehre-Axiome

Kowa am 17. August 2019 um 17:10 Uhr

2019-08-17T17:10:10Z

Kowa am 17. August 2019 um 11:44 Uhr

2019-08-17T11:44:41Z

← Nächstältere Version		Version vom 17. August 2019, 11:44 Uhr
Zeile 27:		Zeile 27:
	<div class="formula"><math>\rm{TupA}(t) :\leftrightarrow \rm{Fkt}(t)</math> (siehe [[Funktion (Mathematik)\|Funktion]])</div>		<div class="formula"><math>\rm{TupA}(t) :\leftrightarrow \rm{Fkt}(t)</math> (siehe [[Funktion (Mathematik)\|Funktion]])</div>

	====Indexbereich und Indexmenge ~~(Attributtupel)~~====		====Indexbereich und Indexmenge====
	Die Definitionsmenge <math>I := I(t) = \rm{Def}(f) := \{x\| \bigvee y: [x,y] \in t\}</math> der Funktion <math>t</math> heißt		Die Definitionsmenge <math>I := I(t) = \rm{Def}(f) := \{x\| \bigvee y: [x,y] \in t\}</math> der Funktion <math>t</math> heißt
	in diesem Fall '''Indexbereich''' ~~oder, falls~~ es sich bei <math>I</math> um eine echte {{Menge}} und nicht um eine {{Unmenge}} handelt, '''Indexmenge'''.		in diesem Fall '''Indexbereich'''. Falls es sich bei <math>I</math> um eine echte {{Menge}} und nicht um eine {{Unmenge}} handelt, kann man auch '''Indexmenge''' sagen.

	====Tupellänge (Attributtupel)====		====Tupellänge (Attributtupel)====
Zeile 106:		Zeile 106:
	ebenfalls eindeutig bestimmt.		ebenfalls eindeutig bestimmt.

	====~~Indexmenge~~ (Positionstupel)====		====Indexbereich (Positionstupel)====

	Für ein Positionstupels <math>t</math> wird die '''~~Indexmenge~~''' <math>I(t)</math> folgendermaßen definiert :		Für ein Positionstupels <math>t</math> wird die '''Indexbereich''' <math>I(t)</math> folgendermaßen definiert :
	<div class="formula"><math>I(t) := \{i \in \mathbb{N}: 0 < i \le \rm{lg}(t)\}</math></div>		<div class="formula"><math>I(t) := \{i \in \mathbb{N}: 0 < i \le \rm{lg}(t)\}</math></div>

Zeile 118:		Zeile 118:
	=====Lemma: Länge des Tupels=====		=====Lemma: Länge des Tupels=====

	Die Länge eines Positionstupels <math>t</math> ist gleich der Mächtigkeit ~~der Indexmenge~~: <math>\rm{lg}(t) = \|I(t)\|</math>		Die Länge eines Positionstupels <math>t</math> ist gleich der Mächtigkeit des Indexbereichs: <math>\rm{lg}(t) = \|I(t)\|</math>

	'''Beweis'''		'''Beweis'''
Zeile 125:		Zeile 125:
	====Schlüssel und Wert (Positionstupel)====		====Schlüssel und Wert (Positionstupel)====

	Es seien <math>t</math> ein nicht-leeres Positionstupel und <math>I := I(t)</math> ~~die~~ zugehörige ~~Indexmenge~~.		Es seien <math>t</math> ein nicht-leeres Positionstupel und <math>I := I(t)</math> der zugehörige Indexbereich.
	Die Elemente <math>i\in I</math> ~~der Indexmenge~~ heißen '''Schlüssel'''.		Die Elemente <math>i\in I</math> des Indexbereichs heißen '''Schlüssel'''.

	Jedem Schlüssel <math>i\in I</math> wird durch das		Jedem Schlüssel <math>i\in I</math> wird durch das
Zeile 318:		Zeile 318:
	Es seien <math>t_1</math> und <math>t_2</math> zwei Tupel (in Attribut- oder Listennotation).		Es seien <math>t_1</math> und <math>t_2</math> zwei Tupel (in Attribut- oder Listennotation).

	<math>t_1</math> und <math>t_2</math> sind genau dann gleich, wenn die zugehörigen ~~Indexmengen~~ <math>I(t_1)</math> und <math>I(t_2)</math> übereinstimmen und wenn die Funktionswerte		<math>t_1</math> und <math>t_2</math> sind genau dann gleich, wenn die zugehörigen Indexbereiche <math>I(t_1)</math> und <math>I(t_2)</math> übereinstimmen und wenn die Funktionswerte
	für jedes Element ~~der Indexmenge~~ ebenfalls übereinstimmen:		für jedes Element des Indexbereichs ebenfalls übereinstimmen:
	<div class="formula"><math>t_1 = t_2 \Leftrightarrow I(t_1) = I(t_2) \wedge \bigwedge i \in I(t_1): t_1(i) = t_2(i)</math></div>		<div class="formula"><math>t_1 = t_2 \Leftrightarrow I(t_1) = I(t_2) \wedge \bigwedge i \in I(t_1): t_1(i) = t_2(i)</math></div>

Kowa: Die Seite wurde neu angelegt: „{{Qualität |correctness = 3 |extent = 4 |numberOfReferences = 5 |qualityOfReferences = 5 |conformance = 5 }} Eine informelle Def…“

2019-08-17T11:17:12Z

Die Seite wurde neu angelegt: „{{Qualität |correctness = 3 |extent = 4 |numberOfReferences = 5 |qualityOfReferences = 5 |conformance = 5 }} Eine informelle Def…“

Neue Seite

{{Qualität
|correctness = 3
|extent = 4
|numberOfReferences = 5
|qualityOfReferences = 5
|conformance = 5
}}
Eine informelle Definition des Begriffs [[Tupel]] wurde im [[Tupel|zugehörigen Artikel]] angegeben. Dort findet man auch einen Überblck über die
zugehörige Geschichte einschließlich unterschiedlicher Definitionen. Im Folgenden wird der tupelbegriff auf Basis dieser Definitionen formalisiert.
Dabei wird vorausgesetzt, dass der Term „[[geordnetes Paar]]“ <math>[x,y]</math> schon definiert oder axiomatisch eingeführt wurde.

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.
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
<code>(x y)</code>, die als Abkürzung für <code>(x . (y . NIL))</code> steht. Beide Definitionen erfüllen jedoch das Paaraxiom.

==Definition ([[Wolfgang Kowarschick|Kowarschick]])==
===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>)===

Es sei <math>t: I \rightarrow \mathcal{V}</math> eine beliebige [[Funktion (Mathematik)|Funktion]] von einer {{Menge}} oder {{Klasse}} <math>I</math> in die [[Allklasse]] <math>\mathcal{V}</math>:
{{Formel|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}}

<math>t</math> 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 <math>I</math>'''. Alternativ kann man auch <math>I</math>'''-Tupel''' oder <math>I</math>'''-Familie''' sagen.

<div class="formula"><math>\rm{TupA}(t) :\leftrightarrow \rm{Fkt}(t)</math> (siehe [[Funktion (Mathematik)|Funktion]])</div>

====Indexbereich und Indexmenge (Attributtupel)====
Die Definitionsmenge <math>I := I(t) = \rm{Def}(f) := \{x| \bigvee y: [x,y] \in t\}</math> der Funktion <math>t</math> heißt
in diesem Fall '''Indexbereich''' oder, falls es sich bei <math>I</math> 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''':
<div class="formula"><math>\rm{lg}(t) := |I(t)|</math></div>

Ein Tupel der Länge <math>l</math> wird auch <math>l</math>-'''Tupel''' genannt.

====Schlüssel und Wert (Attributtupel)====
Jedes Element <math>i</math> des Indexbereichs heißt '''Schlüssel''' oder '''Index'''.

Das zum Index <math>i</math> gehörende Element <math>t_i := t(i)</math> wird als '''Wert''' bezeichnet.

====Anmerkungen (Attributtupel)====

Mit <math>\rm{Fkt}(f)</math> wird ausgedrückt, dass es sich bei einer Menge oder Klasse <math>f</math> um eine Funktion handelt, dass <math>f</math> also eine Menge oder Klasse von
[[geordnetes Paar|geordneten Paaren]] ist, die die Eindeutigkeitsbedingung

{{Formel|\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 <math>\rm{TupA}(t)</math> wird ausgedrückt, dass es sich bei <math>t</math> um ein Attributtupel handelt.

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

Der Begriff „I-Tupel“ geht auf Ebbinghaus<ref name="Ebbinghaus">{{Quelle|Ebbinghaus (2003)}}, S. 59–60</ref> zurück.

===Positionstupel (in Anlehnung an McCarthy et al.<ref name="McCarthy (1965)">{{Quelle|McCarthy, J. et. al. (1965): LISP 1.5 Programmer's Manual}}</ref>)===

Der Begriff des [[geordnetes Paar|geordneten Paars]] kann induktiv für eine beliebige endliche Anzahl von Elementen verallgemeinert werden:

Eine Menge oder Klasse <math>t</math> heißt '''(Positions-)Tupel''' – in Zeichen <math>\rm{TupV}(t)</math> – wenn entweder <math>t=\emptyset</math> gilt
oder wenn <math>t</math> ein [[geordnetes Paar]] <math>[x,t]</math> ist, dessen erstes Element beliebig und dessen zweites Element ein Tupel ist:

<div class="formula"><math>\rm{TupV}(\emptyset)</math> </div>
<div class="formula"><math>\bigwedge x, t: \rm{TupV}(t) \rightarrow \rm{TupV}([x,t])</math></div>

Andere Positionstupel gibt es nicht.
Das heißt, für jedes Tupel <math>t \not= \emptyset</math> gibt es ein Element <math>x</math> <br />und ein Tupel <math>t'</math> mit <math>t = [x,t']</math>:
<div class="formula"><math>\bigwedge t: (\rm{TupV}(t) \wedge t \not= \emptyset \rightarrow \bigvee x, t': (\rm{TupV}(t') \wedge t = [x,t']))</math></div>

Das Tupel <math>t'</math> ist wegen des [[geordnetes Paar#Definition_.28Kowarschick.29|Paaraxioms]] sogar eindeutig bestimmt:
<div class="formula"><math>\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))</math></div>

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 [[geordnetes Paar#Mengen-.2C_Unmengen-_und_Klassenpaare|Klassenpaaren]] gültig (vgl. [[geordnetes Paar#Reihenfolge der Elemente|Abschnitt „Reihenfolge der Elemente“]] im Artikel [[geordnetes Paar]]).
Für [[geordnetes Paar#Mengen-.2C_Unmengen-_und_Klassenpaare|Mengenpaare]] müsste sie entsprechend auf Mengen eingeschränkt werden, da
Mengenpaare keine Klassen enthalten können:

<div class="formula"><math>\bigwedge a,b: (\rm{UMg}(a) \vee \rm{UMg}(b)) \leftrightarrow (a,b) = \mathcal{V}</math> </div>

In diesem Fall gilt nur:
<div class="formula"><math>\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) ))</math></div>

====Tupellänge (Positionstupel)====

Es sei <math>t</math> ein Positionstupel: <math>TupV(t)</math>.
Die Länge <math>\rm{lg}(t)</math> von <math>t</math> wird ebenfalls induktiv definiert:

<div class="formula"><math>\rm{lg}(\emptyset) := 0</math> </div>
<div class="formula"><math>\bigwedge x, t: \rm{TupV}(t) \rightarrow \rm{lg}([x,t]) := \rm{lg}(t)+1</math></div>

Ein Tupel der Länge <math>l</math> heißt '''<math>l</math>-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 <math>0</math>.
Für jedes andere Tupel <math>t</math> existiert genau ein Element <math>x</math> und ein Tupel <math>t'</math>, für die <math>t=[x,t']</math> gilt.
Für <math>t'</math> ist die Länge laut Induktionsvoraussetzung eindeutig bestimmt und damit ist die Länge <math>\rm{lg}(t) = \rm{lg}(t')+1</math>
ebenfalls eindeutig bestimmt.

====Indexmenge (Positionstupel)====

Für ein Positionstupels <math>t</math> wird die '''Indexmenge''' <math>I(t)</math> folgendermaßen definiert :
<div class="formula"><math>I(t) := \{i \in \mathbb{N}: 0 < i \le \rm{lg}(t)\}</math></div>

'''Anmerkung'''<br/>
Die Zählung der Attribute beginnt laut dieser Definition bei <math>1</math> und endet bei <math>\rm{lg}(t)</math>.
Man könnte ohne Probleme auch die in der Informatik übliche Zählung von <math>0</math> bis<math>\rm{lg}(t)-1</math>
verwenden, müsste dann aber ein paar Anpassungen vornehmen ({{zB}} beim nachfolgenden Lemma).

=====Lemma: Länge des Tupels=====

Die Länge eines Positionstupels <math>t</math> ist gleich der Mächtigkeit der Indexmenge: <math>\rm{lg}(t) = |I(t)|</math>

'''Beweis'''
<div class="formula"><math>|I(t)| = |\{i \in \mathbb{N}: 0 < i \le \rm{lg}(t)\}| = \rm{lg}(t)</math></div>

====Schlüssel und Wert (Positionstupel)====

Es seien <math>t</math> ein nicht-leeres Positionstupel und <math>I := I(t)</math> die zugehörige Indexmenge.
Die Elemente <math>i\in I</math> der Indexmenge heißen '''Schlüssel'''.

Jedem Schlüssel <math>i\in I</math> wird durch das
Tupel <math>t</math> ein eindeutiger '''Wert''' <math>t_i</math> zugeordnet. <math>t_i</math> wird wieder induktiv definiert:

Da laut Voraussetzung <math>t \not= \emptyset</math> gilt, gibt es zwei (eindeutige) Elemente
<math>x</math> und <math>t'</math> mit <math>\rm{TupV}(t')</math> und <math>t=[x,t']</math>.
<div class="formula"><math>t_i :=
\begin{cases}
x & \mbox{wenn } i = 1\\
t'_{i-1} & \mbox{wenn } i > 1
\end{cases}
</math></div>

Man beachte, dass aus <math>i\in I</math> stets <math>0 < i < \rm{lg}(t)</math> folgt.
Diese [[Invariante]] bleibt im rekursiven Zweig der Definition
erhalten: <math>i>1 \rightarrow 0 < i-1 < \rm{lg}(t)-1 = \rm{lg}(t')</math>.
Das heißt, es gilt auch hier <math>i-1 \in I(t')</math>.

Für <math>i\notin I</math> ist <math>t_i</math> nicht definiert. Man kann in diesem Fall allerdings
<math>t_i := \mathcal{V}</math> setzen, um <math>t_i</math> für jede beliebige Klasse <math>i</math> zu definieren.

====Listennotation====

Für Positionstupel wird folgende abkürzende Schreibweise eingeführt:

<div class="formula"><math>() := \emptyset</math></div>
<div class="formula"><math>(x_1) := [\emptyset, x_1]</math></div>
<div class="formula"><math>(x_1,x_2) := [[\emptyset, x_1], x_2]</math></div>
<div class="formula"><math>(x_1,x_2,x_3) := [[[\emptyset, x_1], x_2], x_3]</math></div>

Allgemein für <math>n \ge 2</math>:
<div class="formula"><math>(x_1,\ldots,x_n) := [(x_1,\ldots,x_{n-1}), x_n] = [[[\ldots[\emptyset,x_1]\ldots], x_{n-1}], x_n]</math></div>

====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):
{{Quote|The list <math>(m_1,m_2,···,m_n)</math> is represented by the S-expression <math>(m_1·(m_2·(···(m_n·\rm{NIL})···)))</math>.<br/>
Here <math>\rm{NIL}</math> is an atomic symbol used to terminate lists.<ref>{{Quelle|McCarthy, J. (1960): Recursive Functions of Symbolic Expressions and Their Computation by Machine}}</ref>}}

McCarthy definiert eine [[LISP]]-Liste als abkürzende Schreibweise für eine Folge von <math>cons</math>-Zellen, d.h. als Folge von LISP-Paaren <math>(a \cdot b)</math>.
In LISP wird eine Liste also als [[verkette Liste]] implementiert: Jede <math>cons</math>-Zelle enthält das eigentlich Listenelement sowie einen Verweis auf die Nachfolgerliste.
Die letzte <math>cons</math>-Zelle enthält keinen Verweis, sondern die LISP-Konstante <math>\rm{NIL}</math>.

In seinen ursprünglichen Publikationen wie auch im Benutzerhandbuch von LISP I<ref>{{Quelle|McCarthy, J. et. al. (1960): LISP I Programmer's Manual}}, S. 11</ref>
bezeichnet McCarthy <math>\rm{NIL}</math> lediglich als „atomares Symbol“, welches benutzt wird, um Listen zu terminieren. Erst im Beutzerhandbuch von
LISP 1.5<ref name="McCarthy (1965)" /> legt er zusätzlich
fest, dass <math>\rm{NIL}</math> identisch zur leeren Liste <math>()</math> ist.

Die Definition von McCarthy ist den Definitionen von anderen Autoren, wie z.B. [[Kurt Gödel|Gödel]] oder Schmidt, vorzuziehen.

'''Definition von Schmidt<ref name="Schmidt"/> (und diversen anderen Autoren):'''
<div class="formula"><math>(x_1, x_2)</math> ist ein (Klassen-)Paar.</div>
<div class="formula"><math>(x1, x2, x3) := ((x1, x2), x3)</math> ist ein (Klassen-)Tripel.</div>
<div class="formula"><math>(x1, x2, x3, x4) := ((x1, x2, x3), x4) = (((x1, x2), x3), x4)</math> ist ein (Klassen-)Quadrupel.</div>

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<ref>{{Quelle|Gödel (1940)}}</ref> (und diversen anderen Autoren):'''

Gödel hat Tupel im Prinzip genauso wie Schmidt definiert.
Zusätzlich hat er allerdings noch 1-Tupel eingeführt:
<div class="formula"><math>(x_1) := x_1</math></div>

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]] <math>\Omega</math> mit Addition <math>+</math> und neutralem Element <math>0</math> als Klassentupel <math>(\Omega,+,0)</math> definieren, obwohl es sich bei <math>\Omega</math> um eine Unmenge handelt.
Für Mengentupel gilt dagegen, dass <math>(\Omega,+,0)</math> entweder nicht definiert ist oder gleich der Allklasse <math>\mathcal{V}</math> ist. Im letzteren Fall sind alle Mengentupel, die ein oder mehrere Unmengen enthalten, ebenfalls
gleich <math>\mathcal{V}</math>.

'''Objektsprache und Metasprache'''<br/>
Man beachte auch, dass hinsichtlich der Definitionen und Beweise ein wesentlicher Unterschied zwischen
Mengen- und Klassentupeln besteht.

Für Mengen kann <math>TupV</math> als echte [[Funktion (Mathematik)|Funktion]] definiert werden. Die zugehörigen, auf [[vollständige Induktion|vollständiger Induktion]] basierenden Beweise
können daher innerhalb der formalen Sprache ([[Metasprache|Objektsprache]]) des jeweiligen Axiomensystems der Mengenlehre (unter Zuhilfenahme des [[Unendlichkeitaxiom]]s) 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 <math>TupV</math> 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
{{Formel|\rm{UMg}(a) \rightarrow \{a\}{{=}} \mathcal{V}|([[Schmidt (1966)]], S. 73)}}
und damit auch
{{Formel|\rm{UMg}(a) \vee \rm{UMg}(b) \rightarrow \rm{UMg}((a,b))|([[Schmidt (1966)]], S. 97)}}
{{Formel|\rightarrow \{\ldots,(a,b),\ldots\}{{=}} \mathcal{V} }}
Das heißt, sobald man versucht, eine Unmenge in die Definition einer Funktion <math>f</math> als Urbild oder Bildelement einzuschleusen, degeneriert <math>f</math> zur Allklasse.

<math>TupV(t)</math> ist also im Falle von Klassentupeln eine Abkürzung für eine mengentheoretische Formel, genauso wie <math>Mg(m)</math>, als Abkürzung für die Formel <math>\bigvee a: m \in a</math> 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 [[Metasprache#Metametasprache|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:
{{Quote|... 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 ...<ref>zitiert nach [[Schmidt (1966)]], S. 174</ref>
}}

===Abbildung der Listen- auf die Attributnotation===

Für jedes <math>n</math>-Tupel <math>t</math> (<math>n \in \mathbb N</math>) in Listennotation
kann ein zugehöriges Tupel <math>t'</math> in Attributnotation definiert werden,
sofern es sich bei <math>t</math> um ein „Mengentupel“ handelt, {{dh}}, sofern das Tupel nur {{Menge}}n aber keine {{Unmenge}}n enthält, d.h., sofern <math>\rm{Mg}(t_i)</math> für alle <math>i \in I(t)</math>:

<div class="formula"><math>t' := \{[i,t_i]: i \in I(t)\}</math></div>

'''Anmerkung:'''<br/>
Diese Aussage kann mit ziemlicher Sicherheit für beliebige [[Ordinalzahl]]en verallgemeinert werden.
Dazu müssen die Positionstupel mittels [[transfinite Induktion|transfiniter Induktion]] an Stelle der [[natürliche Induktion|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====

<math>t</math> und <math>t'</math> beschreiben dasselbe Tupel:

#<div class="formula"><math>I(t) = I(t') = \{i \in \mathbb{N}: 0 < i \le \rm{lg}(t)\}</math></div>
#<div class="formula"><math>\rm{lg}(t) = \rm{lg}(t')</math></div>
#<div class="formula"><math>\bigwedge i \in I: t_i = t'_i</math>, wobei <math>I := I(t) = I(t')</math></div>

'''Beweis'''
{{Formel|I(t') {{=}} \{x: \bigvee y: [x,y] \in t'\}|(Definition von <math>I(t')</math>)}}
{{Formel|I(t') {{=}} \{x: \bigvee y: [x,y] \in \{[i,t_i]: i \in I(t)\} \}|(Definition von <math>t'</math>)}}

Man kann die erste Aussage
{{Formel|I(t') {{=}} I(t)}}
beweisen, indem man
{{Formel|I(t') \subseteq I(t)|(*1)}}
{{Formel|I(t') \supseteq I(t)|(*2)}}
nachweist. (<math>I(t) = \{i \in \mathbb{N}: 0 < i \le \rm{lg}(t)\}</math> ist bereits laut Definition von <math>I(t)</math> richtig.)

''Begründung für *1''<br/>
Es sei <math>x \in I(t')</math>, d.h., es gibt ein <math>y</math> mit <math>[x,y] \in \{[i,t_i]: i \in I(t)\}</math>,
d.h., es gibt ein <math>i \in I(t)</math> mit <math>[x,y] = [i,t_i]</math> und damit gilt <math>x = i \in I(t)</math>,
wegen des [[Geordnetes Paar|Paaraxioms]].

''Begründung für *2''<br/>
Es sei <math>i \in I(t)</math>. Wenn man <math>[x,y] := [i, t_i]</math> setzt, ist <math>[x,y] \in \{[i,t_i]: i \in I(t)\}</math>.
Und damit ist <math>i \in I(t')</math>.

Die zweite Aussage folgt direkt aus der ersten Aussage, der Definition von <math>\rm{lg}(t')</math> und Lemma 4.2.2.1:
<div class="formula"><math>\rm{lg}(t) = |I(t)| = |I(t')| =: \rm{lg}(t')</math></div>

Die dritte Behauptung folgt direkt aus der ersten Aussage und der Definition von <math>t'_i</math> und <math>t'</math>:
<div class="formula">Es sei <math>i \in I</math>, dann ist <math>t'_i = t'(i) = t_i</math></div>

====Anmerkungen====

Ein geordnetes Paar <math>[a,b]</math> 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: <math>(a,b)</math>. Da dieses Paar ebenfalls das Paaraxiom erfüllt,
wird das spezielle geordnete Paar <math>[a,b]</math> künftig nicht mehr benötigt. Es wird durch <math>(a,b)</math> 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 <math>t_1</math> und <math>t_2</math> sind genau dann gleich, wenn <math>t_1</math> und <math>t_2</math> als {{Klasse}}n gleich sind,
d.h., wenn:
<div class="formula"><math>t_1 \subseteq t_2 \wedge t_2 \subseteq t_1</math></div>
oder, anders formuliert:
<div class="formula"><math>\bigwedge x \in \mathcal{V}: x \in t_1 \Leftrightarrow x \in t_2</math></div>

====Lemma====
Zwei gleiche Tupel (in Attribut- oder Listennotation) sind trivialerweise gleich lang :

<div class="formula"><math>t_1 = t_2 \Rightarrow \text{lg}(t_1) = \text{lg}(t_2)</math></div>

'''Beweis'''<br/>
Die Behauptung folgt direkt aus der [[Reflexivität]] der Gleichheit (<math>\text{lg}(t_1) = \text{lg}(t_1)</math>)
und der [[Leibnizsche Ersetzbarkeit|Leibnizschen Ersetzbarkeit]].

====Satz====
Es seien <math>t_1</math> und <math>t_2</math> zwei Tupel (in Attribut- oder Listennotation).

<math>t_1</math> und <math>t_2</math> sind genau dann gleich, wenn die zugehörigen Indexmengen <math>I(t_1)</math> und <math>I(t_2)</math> übereinstimmen und wenn die Funktionswerte
für jedes Element der Indexmenge ebenfalls übereinstimmen:
<div class="formula"><math>t_1 = t_2 \Leftrightarrow I(t_1) = I(t_2) \wedge \bigwedge i \in I(t_1): t_1(i) = t_2(i)</math></div>

Die Behauptung <math>\Rightarrow</math> folgt wieder direkt aus der [[Reflexivität]] der Gleichheit
und der [[Leibnizsche Ersetzbarkeit|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.<br/>
Es sei <math>I := I(t_1) = I(t_2)</math>.

Induktionsanfang: <math>I = \emptyset</math><br/>
Dann ist <math>\rm{lg}(t_1) = \rm{lg}(t_2) = 0</math> und damit <math>t_1 = t_2 = \emptyset</math>.

Induktionsvoraussetzung: <br/>
Es seien <math>t_1 = t_2</math>, <math>I(t_1) = I(t_2)</math>, <math>n := \rm{lg}(I(t_1)) = \rm{lg}(I(t_2))</math>
und <math>I' := I \cup \{n+1\} = \{\mathbb{N}: 0 < i \le n+1\}</math>.
Dann ist <math>|I'| = n+1</math>.

Induktionsschritt: <br/>
Es seien überdies <math>t'_1 = [x_1, t_1]</math> und <math>t'_2 = [x_2, t_2]</math> (<code>n+1 > 0</code>!). Da laut Voraussetzung (rechte Seite von <math>\Leftrightarrow</math>) <math>x_1 = t'_1(n+1) = t'_2(n+1) = x_2</math> und laut Induktionsvoraussetzung <math>t_1 = t_2</math>,
gilt wegen des [[Paaraxiom]]s auch <math>t'_1 = t'_2</math>, was zu beweisen war.

==Quellen==

<references />

[[Kategorie:Mengenlehre]]
[[Kategorie:Datenmanagement]]
[[Kategorie:Glossar]]

← Nächstältere Version		Version vom 22. September 2020, 12:11 Uhr
Zeile 73:		Zeile 73:
	<div class="formula"><math>\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))</math></div>		<div class="formula"><math>\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))</math></div>

	In einem klassenbasierten Axiomen-System (wie es ~~z.B.~~ der [[Neumann-Bernays-Gödel-Mengenlehre]] zu Grunde liegt)		In einem klassenbasierten Axiomen-System (wie es {{zB}} der [[Neumann-Bernays-Gödel-Mengenlehre]] zu Grunde liegt)
	ist diese Formel allerdings nur im Falle von [[geordnetes Paar#Mengen-.2C_Unmengen-_und_Klassenpaare\|Klassenpaaren]] gültig (vgl. [[geordnetes Paar#Reihenfolge der Elemente\|Abschnitt „Reihenfolge der Elemente“]] im Artikel [[geordnetes Paar]]).		ist diese Formel allerdings nur im Falle von [[geordnetes Paar#Mengen-.2C_Unmengen-_und_Klassenpaare\|Klassenpaaren]] gültig (vgl. [[geordnetes Paar#Reihenfolge der Elemente\|Abschnitt „Reihenfolge der Elemente“]] im Artikel [[geordnetes Paar]]).
	Für [[geordnetes Paar#Mengen-.2C_Unmengen-_und_Klassenpaare\|Mengenpaare]] müsste sie entsprechend auf Mengen eingeschränkt werden, da		Für [[geordnetes Paar#Mengen-.2C_Unmengen-_und_Klassenpaare\|Mengenpaare]] müsste sie entsprechend auf Mengen eingeschränkt werden, da
Zeile 175:		Zeile 175:
	fest, dass <math>\rm{NIL}</math> identisch zur leeren Liste <math>()</math> ist.		fest, dass <math>\rm{NIL}</math> identisch zur leeren Liste <math>()</math> ist.

	Die Definition von McCarthy ist den Definitionen von anderen Autoren, wie ~~z.B.~~ [[Kurt Gödel\|Gödel]] oder Schmidt, vorzuziehen.		Die Definition von McCarthy ist den Definitionen von anderen Autoren, wie {{zB}} [[Kurt Gödel\|Gödel]] oder Schmidt, vorzuziehen.

	'''Definition von Schmidt<ref name="Schmidt"/> (und diversen anderen Autoren):'''		'''Definition von Schmidt<ref name="Schmidt"/> (und diversen anderen Autoren):'''
Zeile 293:		Zeile 293:
	Ein geordnetes Paar <math>[a,b]</math> kann, wie bereits definiert wurde, als 2-Tupel aufgefasst werden.		Ein geordnetes Paar <math>[a,b]</math> kann, wie bereits definiert wurde, als 2-Tupel aufgefasst werden.

	Allerdings liefert die allgemeine Tupeldefinition, die ~~i.Allg.~~ auf dem geordneten Paar basiert,		Allerdings liefert die allgemeine Tupeldefinition, die {{iAllg}} auf dem geordneten Paar basiert,
	ihrerseits ein 2-Tupel, das heißt, ein geordnetes Paar: <math>(a,b)</math>. Da dieses Paar ebenfalls das Paaraxiom erfüllt,		ihrerseits ein 2-Tupel, das heißt, ein geordnetes Paar: <math>(a,b)</math>. Da dieses Paar ebenfalls das Paaraxiom erfüllt,
	wird das spezielle geordnete Paar <math>[a,b]</math> künftig nicht mehr benötigt. Es wird durch <math>(a,b)</math> ersetzt.		wird das spezielle geordnete Paar <math>[a,b]</math> künftig nicht mehr benötigt. Es wird durch <math>(a,b)</math> ersetzt.

← Nächstältere Version		Version vom 17. August 2019, 17:10 Uhr
Zeile 56:		Zeile 56:
	Der Begriff „I-Tupel“ geht auf Ebbinghaus<ref name="Ebbinghaus">{{Quelle\|Ebbinghaus (2003)}}, S. 59–60</ref> zurück.		Der Begriff „I-Tupel“ geht auf Ebbinghaus<ref name="Ebbinghaus">{{Quelle\|Ebbinghaus (2003)}}, S. 59–60</ref> zurück.

	===Positionstupel (in Anlehnung an McCarthy et al.<ref name="McCarthy (1965)">{{Quelle\|McCarthy~~, J.~~ et. al. (1965)~~: LISP 1.5 Programmer's Manual~~}}</ref>)===		===Positionstupel (in Anlehnung an McCarthy et al.<ref name="McCarthy (1965)">{{Quelle\|McCarthy et. al. (1965)}}</ref>)===

	Der Begriff des [[geordnetes Paar\|geordneten Paars]] kann induktiv für eine beliebige endliche Anzahl von Elementen verallgemeinert werden:		Der Begriff des [[geordnetes Paar\|geordneten Paars]] kann induktiv für eine beliebige endliche Anzahl von Elementen verallgemeinert werden:
Zeile 164:		Zeile 164:
	Die obige Definition der Listennotation geht auf McCarthy zurück (wobei er die Liste allerdings vom letzten Element ausgehend aufbaut):		Die obige Definition der Listennotation geht auf McCarthy zurück (wobei er die Liste allerdings vom letzten Element ausgehend aufbaut):
	{{Quote\|The list <math>(m_1,m_2,···,m_n)</math> is represented by the S-expression <math>(m_1·(m_2·(···(m_n·\rm{NIL})···)))</math>.<br/>		{{Quote\|The list <math>(m_1,m_2,···,m_n)</math> is represented by the S-expression <math>(m_1·(m_2·(···(m_n·\rm{NIL})···)))</math>.<br/>
	Here <math>\rm{NIL}</math> is an atomic symbol used to terminate lists.<ref>{{Quelle\|McCarthy~~, J.~~ (1960)~~: Recursive Functions of Symbolic Expressions and Their Computation by Machine~~}}</ref>}}		Here <math>\rm{NIL}</math> is an atomic symbol used to terminate lists.<ref>{{Quelle\|McCarthy (1960)}}</ref>}}

	McCarthy definiert eine [[LISP]]-Liste als abkürzende Schreibweise für eine Folge von <math>cons</math>-Zellen, d.h. als Folge von LISP-Paaren <math>(a \cdot b)</math>.		McCarthy definiert eine [[LISP]]-Liste als abkürzende Schreibweise für eine Folge von <math>cons</math>-Zellen, d.h. als Folge von LISP-Paaren <math>(a \cdot b)</math>.
Zeile 170:		Zeile 170:
	Die letzte <math>cons</math>-Zelle enthält keinen Verweis, sondern die LISP-Konstante <math>\rm{NIL}</math>.		Die letzte <math>cons</math>-Zelle enthält keinen Verweis, sondern die LISP-Konstante <math>\rm{NIL}</math>.

	In seinen ursprünglichen Publikationen wie auch im Benutzerhandbuch von LISP I<ref>{{Quelle\|McCarthy~~, J.~~ et. al. (1960)~~: LISP I Programmer's Manual~~}}, S. 11</ref>		In seinen ursprünglichen Publikationen wie auch im Benutzerhandbuch von LISP I<ref>{{Quelle\|McCarthy et. al. (1960)}}, S. 11</ref>
	bezeichnet McCarthy <math>\rm{NIL}</math> lediglich als „atomares Symbol“, welches benutzt wird, um Listen zu terminieren. Erst im Beutzerhandbuch von		bezeichnet McCarthy <math>\rm{NIL}</math> lediglich als „atomares Symbol“, welches benutzt wird, um Listen zu terminieren. Erst im Beutzerhandbuch von
	LISP 1.5<ref name="McCarthy (1965)" /> legt er zusätzlich		LISP 1.5<ref name="McCarthy (1965)" /> legt er zusätzlich