Geordnetes Paar
Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nur teilweise:
Korrektheit: 3 (zu größeren Teilen überprüft) |
Umfang: 3 (einige wichtige Fakten fehlen) |
Quellenangaben: 5 (vollständig vorhanden) |
Quellenarten: 5 (ausgezeichnet) |
Konformität: 5 (ausgezeichnet) |
Es fehlen wichtige Fakten zur Geschichte des Begriffes.
Ein geordnetes Paar
„Geordnetes Paar“ ist ein elementarer Grundbegiff und ein zentrales Hilfsmittel der Mathematik und der Informatik, um Beziehungen zwischen Objekten beschreiben zu können, d. h., um Relationen und Funktionen oder andere komplexe Datenstrukturen definieren zu können.
Vorbemerkung
Im alltäglichen Leben trifft man auf zwei Arten von Paaren: ungeordnete und geordnete Paare. Beispielsweise handelt es sich bei einem üblichen Paar Socken um ein ungeordnetes Paar (es ist egal, welche Socke man links und welche rechts anzieht), ein Paar Schuhe ist dagegen geordnet. Ehepaare sind – zumindest im aktuellen deutschen Rechtssystem – ungeordnet (auch wenn mir kein behördliches Formular bekannt ist, auf dem die Ehefrau vor dem Ehemann genannt wird), noch mehr trifft dies auf gleichgeschlechtliche Partnerschaften zu. Mutter-Kind-/Vater-Kind-Beziehungen sind dagegen geordnet. Etc. pp.
In der Mathematik unterscheidet man ebenfalls zwischen ungeordneten und geordneten Paaren.
Bei „ungeordneten Paaren“ (Paarmengen)
Damit es sich bei „ungeordneten Paaren“ wirklich um Paare handelt, muss man
Im Gegensatz dazu sind bei „geordneten Paaren“
Das Paaraxiom (genauer: das Gleichheitsaxiom für geordnete Paare) von Hamilton lautet[1]:
Es garantiert, dass stets entschieden werden kann, welches das erste und welches das zweite Element eines geordneten Paares ist.
Geordnete Paare und deren Verallgemeinerung, die Tupel, sind sowohl in der Mathematik als auch in der Informatik von zentraler Bedeutung:
- In der Analysis werden sie verwendet, um beispielsweise ganze Zahlen, rationale Zahlen, komplexe Zahlen oder Quaternionen zu definieren.
- In der Geometrie kommen sie zum Einsatz, um mehrdimensionale Räume (insbesondere Vektorräume) zu beschreiben.
- In der Mengenlehre definiert man mit ihrer Hilfe Relationen und Funktionen.
- In LISP sind geordnet Paare die zentrale Datenstruktur, mit deren Hilfe alle komplexen Elemente (Listen und Lambda-Operationen) der Sprache realisiert werden.
- Relationen, d. h. Mengen (und Multimengen) von Tupeln, sind die zentrale Datenstruktur von relationalen Datenbanken.
- Viele komplexe Datenstrukturen der Informatik basieren auf geordneten Paaren und Tupeln: verkettete Listen, Bäume, gerichtete Graphen, Objekte etc.
Die Geschichte der Definition des Begriffs „geordnetes Paar“ ist erstaunlich komplex. Zum einen besteht ein inhärentes Henne-Ei-Problem:
Es ist nicht möglich, einen Ordnungsbegriff zu definieren, wenn man nicht schon einen Ordnungsbegriff hat.
Wenn man beispielsweise das geordnete Paar mit Hilfe von Mengen, d. h. mit Hilfe des Elementoperators
Das zweite große Problem der Paar-Definition ist, dass jede Rückführung des Begriffs auf schon bekannte Begriffe den Paaren zusätzliche Eigenschaften beschert, die eigentlich nichts mit dem Paarbegriff an sich zu tun haben, sondern nur mit der jeweiligen Definition. Die wesentliche Frage ist nun: Welche Eigenschaften sind vorteilhaft? Welche Eigenschaften sind nachteilig? Welches ist für die jeweilige Anwendung die beste Definition? Auch diese Fragen lassen sich nicht abschließend klären, sondern hängen vom jeweiligen Anwendungsfall ab.
Container
In der Mathemtik und der Informatik ist es von fundamentaler Bedeutung, bestimmte Objekte zu größeren Einheiten zusammenzufassen. In diesem Wiki werden Objekte, die andere Objekte enthalten können, als Container bezeichnet und Objekte, die in Containern enthalten sein können, als Elemente.
Geordnete Paare sind per Definitionem Container, da sie genau zwei Objekte als Elemente
enthalten, die so genannten Paarelemente. Auch die Verallgemeinerung der geordneten Paare, die Tupel sind Container.
Ein
In der Mengenlehre gibt es diverse weitere Arten von Objekten, die entweder als Container und/oder als Elemente auftreten können:
- Klassen sind Container: Sie können Elemente enthalten (und zwar Urelemente und Mengen).
- Urelemente können in Klassen als Elemente enthalten sein, können selbst aber keine Elemente enthalten. Typische Urelemente sind Zahlen, Zeichenketten, Boolesche Werte etc.
- Mengen sind spezielle Klassen (können also Elemente enthalten); sie können auch in Klassen als Elemente enthalten sein.
- Unmengen sind spezielle Klassen (können also Elemente enthalten); sie sind aber so umfangreich, dass sie nicht in irgendwelchen Klassen als Elemente enthalten sein können.
TO BE DONE
- Glubrecht, Oberschelp, Todt: Individuen, reale und virtuelle Objekte [2]
Zwischen Klassen und Klassenpaaren gibt es einen wichtigen Unterschied: Unmengen können keine Elemente von irgendwelchen Klassen sein, wohl aber (Paar-)Elemente von Klassenpaaren. Das heißt, mit Hilfe Klassenpaaren (und Klassentupeln) kann man auch Unmengen zu größeren Einheiten zusammenfassen. Mit Mengenpaaren geht dies nicht.
Allerdings gibt es nicht nur Mengen- und Klassenpaare. Ein geordnetes Paar kann – in speziellen formalen Systemen – an Stelle von Klassen und Urelementen auch andere Arten von Elementen enthalten. Gottlob Frege erlaubt beispielsweise „Gegenstände“, „Funktionen“ und „Werthverläufe“ als Elemente.[3] John von Neumann erlaubt „Argumente“ (und damit insbesondere auch spezielle Funktionen, die sogenannten „Argument-Funktionen“)[4] und in LISP sind nur Atome (Urelemente) und Paare als Elemente erlaubt.[5]
Definitionen
Definition (Dipert (1982)[6])
An ordered pair is, roughly speaking, (a) an entity which contains
two other entities and (b) is such that one of these two entities is identifiable as the 'first', the other as the
'second'. More precisely, the individuating criterion for ordered pairs is: two ordered pairs are
identical just when their respective elements are identical. That ist, if
Übersetzung (W. Kowarschick)
Ein geordnetes Paar ist, grob gesprochen, (a) eine Entität, die zwei andere Entitäten enthält und (b) zwar so, dass
eine von diesen beiden Entitäten als die 'erste' identifiziert werden kann und die andere als die 'zweite'.
Genauer gesagt, das individuierende Kriterium für geordnete Paare ist: zwei geordnete Paare sind
genau dann identisch, wenn die entsprechenden Elemente identisch sind. Das heißt, wenn
Anmerkung (von Dipert)
No other property of ordered pairs has ever been shown to be necessary or desirable. This single property is sufficient.
Übersetzung (W. Kowarschick)
Von keiner anderen Eigenschaft geordneter Paare wurde jemals gezeigt,
dass sie notwendig oder wünschenswert wäre. Diese eine Eigenschaft ist ausreichend.
Definition (Brockhaus (1991)[7])
Paar [ahd. par ›zwei Dinge von gleicher Beschaffenheit‹, von lat. par ›gleich‹] Mathematik: eine Menge, die aus zwei Elementen (der ersten und der zweiten Komponente) besteht,
die zusätzlich in einer Ordnung stehen:
Definition (Kowarschick (2014))
Der Term
Mengenpaare
Ein geordnetes Paar
Klassenpaare
Ein geordnetes Paar
Anforderungen an den Paarbegriff
Dipert betont im Anschluss an seine Definition, dass das Paaraxiom zur Charakterisierung des Begriffs „geordnetes Paar“ ausreichend sei. Er ist der Meinung, dass von keiner anderen Eigenschaft geordneter Paare jemals gezeigt wurde, dass sie notwendig oder zumindest wünschenswert wäre.[6]
Glubrecht, Oberschelp und Todt stellen die noch allgemeinere Forderung auf, dass die Definition des Paarbegriffs „adäquat“ sein müsse (Glubrecht, Oberschelp, Todt (1983), S. 203)[2]. Darunter verstehen sie, dass nicht nur das Paaraxiom erfüllt sein muss, sondern dass, falls Paare klassentheoretisch definiert werden, Paare von „ realen Objekten“ stets auch selbst „reale Objekte“ sind. Die Unterscheidung zwischen realen und virtuellen Objekten wurde zur Vermeidung von Antinomien wie der Russellschen Antinomie eingeführt. Sie geht auf Quine (1963) zurück.[8]
Da reale Objekte gemäß ihrer Definition Elemente von anderen Objekten sein können, hat die Forderung von Glubrecht, Oberschelp und Todt zur Folge, dass Paare von realen Objekten ebenfalls Elemente anderer Objekte sein können. Dies ist für klassentheoretische Systeme sicherlich eine zumindest „wünschenswerte“ Zusatzforderung. Ob dagegen Paare von virtuellen Objekten überhaupt definiert werden können und falls „ja“, ob diese dann auch Elemente von anderen Objekten sein können, steht zunächst noch auf einem ganz anderen Blatt.
Schmidt hatte bereits 1966 gefordert, dass Paare nicht nur für Mengen (reale Objekte), sondern auch für Unmengen (echte Klassen, virtuelle Objekte) definiert sein müssen.[9]
Zusammenfassend ergeben sich also folgende notwendigen bzw. wünschenswerte Forderungen, die eine formale Definition von geordneten Paaren erfüllen muss bzw. sollte:
- Das Paaraxiom muss erfüllt sein.
- Möglichst viele, am Besten natürlich alle Objekte des zugrundeliegenden Universiums sollten als Paarelemente erlaubt sein. Insbesondere sollten Paare selbst Elemente von Paaren sein können.
- Der Paarbegriff sollte problemlos zum Begriff des n-Tupels verallgemeinert werden können. Dies ist ganz einfach möglich, falls Paare Elemente von Paaren sein können, falls also die vorangegangene Forderung erfüllt wird.
- Möglichst viele Paare sollten in Containern wie Mengen, Klassen etc. zusammengefasst werden können. Wünschenswert wäre sicherlich, dass auch diese Forderung von allen Paaren erfüllt werden würde. Das ist aber aufgrund von Antinomien, die sich daraus i. Allg. ergeben würden, ein unrealistischer Wunsch.
Projektionsoperatoren
Für geordnete Paare gibt es – wegen des Paaraxioms – zwei Projektionsoperatoren
Definition (Kowarschick (2014))
Operatoren
Anmerkung
Die hier verwendeten Bezeichnungen
Außerhalb der Datenbankwelt haben sich für diese Operatoren noch keine Standardbezeichnungen durchgesetzt. Daher gibt es in der Literatur ganz unterschiedliche Namen, wie man an folgender kleinen, aber sicher unvollständigen Liste erkennt:
- Rosser (1953)[12]:
und - McCarthy (1960)[5]:
car
undcdr
- Morse (1965)[13]:
und - Schmidt (1966)[9]:
und - Ebbinghaus (2003)[14]:
und
Eigenschaften der Projektionsoperatoren
Da die Projektionsoperatoren zuvor nur metasprachlich definiert wurden,
kann man Eigenschaften von
Existenz und Eindeutigkeit der Projektionsoperatoren
Wenn das Paaraxiom erfüllt ist und alle Paare
und sind nur für Paare definiert
Insbesondere gilt damit für jedes Paar
Beweis
siehe Satz „Existenz und Eindeutigkeit der Projektionsoperatoren“
Anmerkung
Der Satz sagt nicht aus, dass es nicht zwei unterschiedliche Projektionsoperatoren
Für jedes Paar
Aus der Existenz der Projektionsoperatoren folgt das Paaraxiom
Wenn zwei Projektionsoperatoren
erfüllen, dann ist auch das Paaraxiom erfüllt.
Beweis
siehe Satz „Aus der Existenz der Projektionsoperatoren folgt das Paaraxiom“
Anmerkung
Dieser Satz ist die Umkehrung des vorangegangen Satzes. Außerdem folgt aus dem vorangegangen Satz sofort, dass zwei Projektionsoperatoren, wenn sie auf das „Universum“ aller Paare eingeschränkt werden, eindeutig sind, sofern sie überhaupt existieren.
Geschichte des Paarbegriffs
TO BE DONE
- Paaraxiom von Hamilton, Hamilton (1837), S. 300 und nachfolgende Geschichte
Der Mathematiker und Philosoph Charles Sanders Peirce merkt 1870 als Erster an, dass eine Relation (die bei Peirce “relative” heißt) als Klasse von “elementary relatives” aufgefasst werden kann, wobei er unter “elementary relatives” Beziehungen zwischen Paaren, Tripletts, Quartetten etc. von Individuen versteht. Die Bedeutung der Begriffe „Paar“, „Triplett“, „Quartett“ etc. setzt er dabei allerdings als bekannt voraus.[15][16]
Die symbolische Schreibweise
Sint
Übersetzung (W. Kowarschick)
Es seien
Allerdings hat Peano in dieser bahnbrechenden Arbeit – hier wurden erstmals die so genannten Peano-Axiome zur Definition der Natürlichen Zahlen formuliert – weder das Paaraxiom noch den eigentlichen Begriff „Paar“ eingeführt.
Im Jahr 1893 definiert Gottlob Frege geordnete Paare funktional mit Hilfe der von ihm zuvor eingeführten Element- und „Werthverlauf“-Operatoren – also mit Hilfe anderer „Grundbegriffe“ – und beweist diejenigen Eigenschaften, die das – vier Jahre später von Peano formulierte – Paaraxiom für den Paarbegriff fordert (siehe Abschnitt Frege (1893)).[3] Allerdings blieb die Wirkung von Frege gering, „auch wegen seiner Verwendung zahlreicher und ungewöhnlicher Symbole“, wie Wußing in seiner „kulturhistorischen Zeitreise“ anmerkt.[18] Es dauert 38 Jahre, bis Alonzo Church 1941 im Rahmen des Lamda-Kalküls abermals eine funktionale Definition des Paarbegriffs vorschlägt.[19] Diese unterschiedet sich im Prinzip nicht von Freges Definition (siehe Geordnetes Paar: Definition von Frege).
In zwei Veröffentlichungen von 1897 formuliert Giuseppe Peano erstmals das Paaraxiom.[20][21]
70.
71.
Übersetzung (W. Kowarschick)
70.
71.
Außerdem führt er aus, dass die Idee eines geordneten Zahlenpaars von grundsätzlicher Bedeutung sei, er aber nicht wisse,
wie er es durch die von ihm zuvor definierten Symbole ausdrücken könne.[20] Ihm war also bereits bewusst,
dass es vorteilhaft wäre, wenn man den Paarbegriff auf andere Grundbegriffe zurückführen könnte. (Im selben Aufsatz führt Peano
übrigens kurz nach dem Paaraxiom auch noch den Existenzoperator
Dreizehn Jahre später veröffentlichen Alfred North Whitehead und Bertrand Russell den ersten Band der Principia Mathematica.[22] Ihr Ziel war es, „die Mathematik vollständig auf eine formal-logische Grundlage zu stellen“.[18] (Der Versuch musste allerdings fehlschlagen, wie Kurt Gödel 1931 eindrucksvoll bewies.[23]) In diesem ersten Band versuchen die beiden Autoren, die von Russell entdeckte Anitomie zu vermeiden, indem sie für Mengen, Relationen und Funktionen spezielle Typhierarchien einführen. Da sie zu dieser Zeit noch nicht wissen, wie man Relationen und Funktionen auf Mengen zurückführen kann, bleibt ihnen nichts weiter übrig, als alle drei Grundbegriffe der Mathematik separat zu behandeln. Geordnete Paare definieren sie im Anschluss an diese Grundbegriffe mit Hilfe des kartesischen Produktes von einelementigen Mengen.
1914 gelingt es Felix Hausdorff und Norbert Wiener unabhängig voneinander, erstmals geordnete (Mengen-)Paare durch Mengen auszudrücken.[24][25] Damit war es möglich, den Begriff „Relation“ und damit insbesondere auch den Begriff „Funktion“ (da Funktionen spezielle Relationen sind) auf den Mengenbegriff zurückzuführen. Eine Relation kann – wie von Peirce bereits 1870 erkannt wurde (siehe oben) – als Menge bzw. Klasse von Paaren oder – allgemeiner – von Tupeln aufgefasst werden. Das heißt, man konnte von 1914 an auf spezielle Typisierung von und spezielle Axiome für Relationen und Funktionen verzichten. Nun definierte man das kartesische Produkt mit Hilfe von geordneten Paaren und nicht umgekehrt, wie es noch Russell und Whitehead getan hatten.
Sieben Jahre später findet Kazimierez Kuratowski eine Definition, die einfacher ist als Wieners Definition und im Gegenstatz zu Huasdorffs Definition ohne Spezialelemente auskommt.[26] Heute findet man oftmals Autoren, die von „Wiener-Paaren“ sprechen, aber „Kuratowki-Paare“ meinen.
Die Weiterentwicklung des Paarbegriffs
Wenn man irgendeinen Grundbegriff mit Hilfe anderer Grundbegriffe definiert, dann hat der so definierte
Grundbegriff zusätzliche Eigenschaften.
Wenn man beispielsweise die Ordinalzahlen auf die von John von Neumann vorgeschlagene Weise definiert[4][27], gilt für alle Ordinalzahlen
Diese Eigenschaft hat sich als vorteilhaft erwiesen, gilt aber nicht im Axiomensystem der natürlichen Zahlen von Peano[17], da dort der
Elementoperator für natürliche Zahlen gar nicht definiert ist. Dass alle Hausdorff-Paare
ist dagegen eher nachteilig.
Man benötigt allerdings keine dieser beiden hier beispielshaft aufgeführten Zusatzeigenschaften wirklich, um wesentliche Eigenschaften von natürlichen Zahlen bzw. geordneten Paaren zu zeigen.
Eine negative Eigenschaft der Kuratowski-Paare beschäftigt Willard Quine Ende der 30er-Jahre und in den 40er-Jahren. Wenn man der Mengenlehre eine Typhierarchie zugrunde legt, liegt ein Kuratowski-Paar um mindestens zwei Ebenen höher als jedes seiner beiden Elemente. (Das gilt auch für Hausdorff-Paare. Wiener-Paare liegen sogar mindestens drei Ebenen höher.) Gerade bei einer reinen, d. h. nicht-kumulativen Typhierachie ist dies lästig. Aber auch bei der von Quine im Jahre 1937 vorgeschlagenen Art der Typisierung[28] ist dies sehr unpraktisch.
Eine weiteres Problem der Kuratowski-Paare ist, dass sie nur Mengen, aber keine Unmengen als Paarelemente enthalten können. Quine verwendet in seinem Lehrbuch „Mathematical Logic“[29] von 1940 zwar noch die Kuratowski-Paare, gibt aber bereits eine alternative Paar-Definition an, bei der geordnete Paare auch Unmengen enthalten können. Allerdings erkennt er bald, dass diese Definition fehlerhaft ist, und diskutiert mit Nelson Goodman über dieses Problem:
[...] Quine suggested an alternative to the definition of ordered couple [...],
but later discovered that this alternative definition would fail to distinguish
Übersetzung (W. Kowarschick)
[...] Quine schlug eine Alternative für die Definition von geordneten Paaren vor [...],
bemerkte aber später, dass diese Alternative daran scheitert
Goodman merkt jedoch kritisch an, dass diese Definition nicht problemlos verallgemeinert werden kann, um „längere Sequenzen“
(d. h.
Dies wiederum stachelt Quine an, Goodmans Definition zu
verbessern. 1945 präsentiert er eine Paardefinition, bei der jedes Paar
auf derselben Ebene liegt wie ihre Elemente
und die für beliebige
Quines primäres Ziel war es, eine Paardefinition anzugeben, die sich bezüglich der von ihm definierten Typhierarchie „gutartig“ verhält. Seine Idee, nicht die Paarelemente selbst, sondern deren Elemente zur Definition des zugehörigen Paares zu verwenden, hatte aber noch einen ganz anderen Vorteil. Auf diese Weise war es möglich, nicht nur Mengenpaare, sondern sogar Klassenpaare zu definieren. Mehrere Mathematiker, wie z. B. Morse (1965[13]) oder Schmidt (1966[9]) griffen diese Idee auf, und definierten auf diese Weise explizit Klassenpaare.
Ein Nachteil der Idee von Quine ist, dass Urelemente keine Klassen sind und damit keine Elemente enthalten. Das heißt, seine Definition sowie die Definitionen vom Morse, Schmidt und anderen funktionieren nur in Klassenuniversen, in denen es keine Urlemente gibt. Diese Bedingung ist allerdings in den Klassensystemen, die die Autoren verwenden, jeweils erfüllt. Mit Hilfe der leeren Menge und ein paar Mengenbildungsaxiomen lassen sich beliebig viele Mengen erzeugen, die als Repräsentanten für die fehlenden Urelemente dienen können.
1967 schlägt Martin Kühnrich erstmals Klassenpaar-Definitionen vor, die auch für Klassenuniversen mit Urelementen korrekt ist. Im Jahr 1981 geben Arnold Oberschelp und Günter Todt eine Klassenpaar-Definition an, die sogar in Klassenuniversen mit Urelementen und weiteren unspezifischen Objekten korrekt ist.[2] Außerdem wird für den Beweis der „Adäquatheit“ der Definition, d. h. für den Nachweis, dass das Paaraxiom erfüllt ist und dass Paare von Mengen selbst Mengen sind, nur das Paarmengenaxiom benötigt.
Bedeutung des Paarbegriffs
Der Paarbegriff ein ganz fundamentales Werkzeug der Mathematik und der Informatik und steht in dieser Hinsicht der Zahl 0 oder der leeren Menge in keiner Hinsicht nach.
Im Jahr 2003 verfasste Akihiro Kanamori einen sehr schönen Übersichtsartikel über die Geschichte dreier für ihn fundamentaler Begriffe der Mengenlehre. Für ihn sind dies die Begriffe „leere Menge“, „einelementige Menge“ und „geordnetes Paar“:
For the modern set theorist the empty set
Für moderne Mengentheoretiker sind die leere Menge
Gut zwanzig Jahre vorher hatte schon Randall Dipert, C.S. Peirce Professor of American Philosophy, die Bedeutung des geordneten Paars für die präzise Definition des Relations- und des Funktionsbegriffs betont, die für ihn „unabdingbar für das Verständnis der Fundamente der Mathematik sind“:
One of the most significant discoveries of early twentieth century mathematical logic was a workable definition of ´ordered pair´ totally within set theory. [...] A definition of ´ordered pair´ held the key to the precise formulation of the notions of ´relation´ and ´function´ – both of which are probably indispensable for an understanding of the foundations of mathematics. The set-theoretic definition of 'ordered pair' thus turned out to be a key victory for logicism, providing one admits set theory is logic.[6]
Eine der bedeutsamsten Entdeckungen des frühen zwanzigsten Jahrhunderts [auf dem Gebiet der] mathematischen Logik war eine funktionsfähige Definition des ´geordneten Paars´ vollkommen innerhalb der Mengenlehre. [...] Eine Definition des ´geordneten Paars´ war der Schlüssel zur präzisen Formulierung der Begriffe ´Relation´ und ´Funktion´ – welche beide vermutlich unabdingbar für das Verständnis der Fundamente der Mathematik sind. Die mengentheoretische Definition des ´geordneten Paars´ erwies sich folglich als Schlüsselerfolg für den Logizismus, vorausgesetzt, man erkennt an, dass Mengenlehre Logik ist. (Übersetzung des vorangegangen Absatzes)
Allerdings geht es Dipert nicht so sehr um das geordnete Paar an sich, sondern um die Darstellung des geordneten Paars mit Hilfe von ungeordneten Mengen. In seinem Aufsatz möchte er aufzeigen, „wie inadäquat die mengentheoretischen Untersuchungen und Erklärungen von so wichtigen Begriffen wie Relation und Funktion sind“.
I shall attempt to show that the development of a set-theoretic notion of ordered pair was in fact only a pyrrhic victory for logicism, and that all popular, and even all possible, set-theoretic definitions of ´ordered pair´ are flawed. This fact in turn will show how inadequate have been set-theoretic analyses and explications of such important notions as relation and function. I conclude by pointing out that the only philosophically viable route appears to be the approach advocated by Schröder and Peirce a century ago.[6]
Ich werde versuchen zu zeigen, dass die Entwicklung eines mengentheoretischen Begriffs des geordneten Paares tatsächlich nur ein Pyrrhussieg für den Logizismus war und dass alle populären, eventuell sogar alle möglichen mengentheoretischen Definitionen des ´geordneten Paars´ mit Makeln behaftet sind. Diese Tatsache zeigt wiederum, wie inadäquat die mengentheoretischen Untersuchungen und Erklärungen von so wichtigen Begriffen wie Relation und Funktion sind. Ich schließe, indem ich aufzeige, dass der einzig philosophisch gangbare Weg anscheinend der Ansatz ist, den Schröder und Peirce vor einem Jahrhundert verfochten haben. (Übersetzung des vorangegangen Absatzes)
Dieser Kritik an der mengentheoretischen Definition des geordnenten Paares muss deutlich wiedersprochen werden. Aus mathematischer Sicht dient die Reduktion von Grundbegriffen und Axiomen immer nur der Vereinfachung, d. h. der Arbeitserleichterung. Es spricht ansonsten überhaupt nichts dagegen, einen anderen Weg zu gehen:
- Es ist nicht notwendig, Paare als spezielle Mengen aufzufassen. Dies ist nur eine Möglichkeit, Paare auf andere Grundbegriffe zurückzuführen. Diverse andere Möglichkeiten werden im nachfolgenden Abschnitt Integration von geordneten Paaren in formale Systeme aufgezeigt.
- Es ist noch nicht einmal notwendig, den Paarbegriff auf andere Grundbegriffe zurückzuführen. Der Paarbegriff kann und wird in der Mathematik und in der Informatik durchaus auch axiomatisch eingeführt, wie im Abschnitt Axiomatische Definition von geordneten Paaren gezeigt wird.
- Verschiedenen Grundbegriffen, wie „Menge“, „geordnetes Paar“/„Tupel“, „Funktion“, „Relation“ etc., können unterschiedliche „Universen“ zugeordnet werden, wie es z. B. Whitehead und Russell in der Principia Mathematica praktiziert haben.[22]. Diese Vorgehensweise ist in der Informatik sogar noch weiter verbreitet als in der Mathematik. Jede Programmierprache unterscheidet mehr oder weniger scharf zwischen atomaren Typen, Containertypen (Mengen, Multimengen, Listen etc.), Funktionen und weiteren Datentypen.
Dipert hat recht, wenn er aus philosophischer Sicht eine Trennung der
verschiedenen Begriffe für wesentlich hält.
Dies steht jedoch überhaupt nicht im Widerspruch zur mathematischen
Vorgehensweise, aus Vereinfachungsgründen einen Begriff auf einen
anderen zurückzuführen.
Man muss dann nur sauber unterscheiden zwischen Aussagen, die innerhalb
einer speziellen Theorie gültig sind, und Aussagen, die in jeder Theorie
gültig sind, die
bestimmte Grundbegriffe wie „geordnete Paare“, „Funktionen“,
„Relationen“, „Ordinalzahlen“ etc. in Übereinstimmung mit den üblichen
Bedeutungen definiert.
Beispielsweise gilt die Aussage
Integration von geordneten Paaren in formale Systeme
Um geordnete Paare in ein formales System wie ein Mengensystem, ein Klassensystem, eine Programmiersprache oder Ähnliches zu integrieren, gibt es mehrere Möglichkeiten. Die wichtigsten dieser Möglichkeiten sind die funktionale, die relationale, die mengentheoretische, die klassentheoretische und, last, but no least, die axiomatische Definition des Paarbegriffs.
Funktionale Definition von geordneten Paaren
In einem formalen System, in dem Funktionen Basiselemente sind, können geordnete Paare mit Hilfe von (Lambda-)Funktionen definiert werden.
Beispiele
Notation | Definition | GlossarWiki-Definition | |
---|---|---|---|
Frege (1893)[3] | (vgl. Artikel „Geordnetes Paar: Definition von Frege“) | ||
Church (1941)[19] (Lambda-Kalkül) |
Erstaunlicherweise liegt den beiden Definitionen von Frege und Church, zwischen deren Veröffentlichungen mehrere Jahrzehnte liegen, dieselbe Idee zugrunde. Ob sich Church an Freges Definition orientiert hat, ist allerdings unklar.
In beiden Fällen wird ein geordnetes Paar durch eine Funktion
ausgedrückt, die eine „Extraktionsfunktion“ als Argument für den
Parameter
Die eigentlichen Projektionsfunktionen übergeben dem aktuellen geordneten Paar
Relationale Definition von geordneten Paaren
In Systemen, in denen Relationen Basiselemente sind, können geordnete Paare als spezielle Relationen definiert werden.
Beispiele
Whitehead und Russell bezeichnen das kartesische Produkt zweier Mengen
Mengentheoretische Definition von geordneten Paaren
In einem formalen System, in dem Mengen als Basiselemente existieren, können geordnete Paare als spezielle Mengen definiert werden.
Beispiele
Da Mengen ungeordnet sind, d. h. die Elemente keine bestimmte Reihenfolge haben, muss man das erste und das zweite Element eines geordneten Paares anderweitig unterscheiden. Eine Möglichkeit ist es, für jedes Paarelement dessen Position im Paar explizit anzugeben. Diesen Weg schlagen Hausdorff und Quine (1986) ein. Eine andere Möglichkeit ist es, die Reihenfolge der Paarelemente mit Hilfe der Mächtigkeit von Mengen eindeutig festzulegen. Die Definitionen von Wiener, Kuratowski und Quine (1940) basieren allesamt auf der Idee, die Paarlemente anhand einer ein- und einer zweielementigen Menge zu unterscheiden.
Klassentheoretische Definition von geordneten Paaren
In einem formalen System, in dem es neben Mengen auch noch Unmengen gibt, d. h., in dem es Klassen gibt, die nicht Element einer anderen Klasse sein können, können die Mengenpaar-Definitionen von Hausdorff, Wiener, Kurtowski, Quine etc. nicht verwendet werden. In allen diesen Definitionen werden die Paarelemente selbst als Elemente in spezielle Klassen eingefügt.
1940 hatte Quine die Idee, nicht die Paarelemente selbst, sondern die Elemente dieser Klassen zu verwenden, um Paare zu definieren.[29] Jedes Element einer Klasse ist automatisch eine Menge und kann daher auch Element einer anderen Klasse sein, z. B. einer Klasse, die ein geordnetes Paar definiert. Allerdings war Quines Definition von 1940 noch fehlerhaft, wie er selbst kurz drauf feststellen musste.[30]
Ein Nachteil der Idee von Quine ist, dass Urelemente keine Klassen sind und damit keine Elemente enthalten. Das heißt, die im Folgenden aufgelisteten Klassenpaar-Definitionen funktioneren im Gegensatz zu den Mengenpaar-Definitionen des vorangegangen Abschnitts nur in Klassenuniversen, in denen es keine Urlemente gibt. Diese Bedingung ist heute allerdings meist erfüllt. Mit Hilfe der leeren Menge und ein paar Mengenbildungsaxiomen lassen sich beliebig viele Mengen erzeugen, die als Repräsentanten für die fehlenden Urelemente dienen können.
Beispiel 1
Quine definiert einen Operator
Das Paar
Beispiel 2
Morse schlägt einen anderen Weg ein. Er definiert zunächst Mengenpaare
Im letzten Schritt definiert Morse Klassenpaare
Man beachte, dass Morses Definition die Idee von Hausdorff
zugrunde liegt: Er markiert die Elemente des ersten Paarelementes mit
der leeren Menge, die als Zahl 0 interpretiert werden kann, und die
Elemente des zweiten Paarmelementes mit der Menge
Beispiel 3
Schmidt sagt von seiner Definition, sie sei an einen Vorschlag von Quine angelehnt. Er definiert Klassenpaare
Axiomatische Definition von geordneten Paaren
Geordnete Paare können axiomatisch als eigenständige Elemente in ein formales System eingefügt werden. Das wesentliche Axiom für geordnete Paare ist das Paaraxiom.
Beispiele
Notation | |
---|---|
Peano (1897)[20][21] | |
von Neumann (1925)[4] | |
McCarthy (1960, LISP)[5] | (a . b)
|
Oberschelp (1973) [34], Glubrecht, Oberschelp und Todt (1983): |
< |
Peano sowie Glubrecht, Oberschelp und Todt formulieren das Paaraxiom direkt, von Neumann und McCarthy fordern dagegen die Existenz von zwei Projektionsoperatoren, was – wie zuvor gezeigt wurde – ebenfalls die Erfüllung des Paaraxioms zur Folge hat.
Peano würde, wie bereits erwähnt wurde, auf eine axiomatische Defnition des Paarbegriffs gerne verzichten, weiß aber 1887 noch nicht, wie das gehen kann.[20] John von Neumann verzichtet in späteren Arbeiten auf eine axiomatische Definition des Paarbegriffs. Er benutzt spätestens ab 1928 die Definition von Kuratowski.[35][36]
John McCarthy sowie Glubrecht, Oberschelp und Todt sehen dagegen ganz bewusst geordnete Paare als primitive Elemente an, die nicht auf andere Elemente zurückgeführt werden. Für McCarthy sind die geordenten Paare („Cons-Zellen“) sowie die Urelemente („Atome“) die Basis sowohl der Sprache LISP als auch der zugehörigen Daten. Andere komplexe Datenstrukturen als geordnete Paare gibt es in McCarthys LISP nicht (sieh nachfolgenden Abschnitt).
Glubrecht, Oberschelp und Todt definieren so allgemeine klassenlogische Sprachen, dass sie auf eine Axiomatisierung des Paarberiffs nicht verzichten können.[2] In der klassentheoretischen Logik LC unterscheiden sie beispielsweise nicht zwischen Mengen und Unmengen, sondern – allgemeiner – zwischen realen und virtuellen Objekten (S. 163). Klassen können sowohl reale, als auch virtuelle Objekte sein, Mengen sind dagegen reale Klassen, also reale Objekte (S. 187). Daneben gibt es auch Objekte, die weder Klassen oder gar Mengen sind. Individuen (= reale Objekte), die keine Elemente haben, heißen Urelemente (S. 187). Daneben kann es aber auch noch virtuelle Objekte geben, die keine Klassen sind. Ja, es kann sogar reale Objekte geben, die keine Urelemente und keine Klassen sind, und für die Elementbeziehungen bestehen:
Wir weisen noch einmal darauf hin, dass über Nichtklassen und die Elementbeziehung zu ihnen keinerlei Voraussetzungen gemacht werden. (S. 163)
In so einer allgemeinen logischen Sprache kann der Paarbegriff gar nicht auf Klassen oder gar Mengen zurückgeführt werden. Insbesondere virtuelle Nichtklassen könnten dann in keiner Paarbeziehung zu irgendwelchen Objekten stehen.
Noch allgemeiner ist Ausdruckslogik LA von Glubrecht, Oberschelp und Todt. In dieser Logik gibt es stets die beiden Urelemente
Geordnete Paare in der Informatik
Geordnete Paare und deren Verallgemeinerung, die Tupel, sind ein fundamentale Element, um in der Informatik komplexe Datenstrukturen definieren zu können.
Insbesondere in der Programmiersprache LISP sind die geordneten Paar das zentrale, ja sogar das einzige Elemnt, um komplexe Datenstrukturen zu definieren.[5]
Das Universum von LISP besteht aus “S-expressions”. Eine S-expression ist dabei entweder ein Atom (also ein Urelement) oder ein geordnetes Paar (a . b)
, dessen beiden Elemente a
und b
S-expressions sind. Tupel (= geordnete Listen),
Funktionen und Mengen werden später auf Basis dieses Universums eingeführt:
Eine LISP-Liste (a b c)
(a . ( b . (c . NIL)))
ist eine Folge von geordneten Paaren, wobei NIL
ein atomares Element ist. Funktionen sind Lamda-Terme, die mit Hilfe von Listen dargestellt werden (z. B. (lambda (x) (+ x 1))
). Die Semantik dieser Funktionen wird mit Hilfe des Lamda-Kalküls festgelegt. Und Mengen sind Listen, für die spezielle Mengenfunktionen definiert sind (siehe z. B. Common Lisp[37]).
Aber auch in allen anderen Programmiersprachen gibt es Tupel, das heißt geordnete Paare, Tripel, Quadrupel etc. Mit Ausnahme von SQL werden die Tupel jedoch meist anders bezeichnet: Record, Array, Object, Map ...
Die wichtigsten funktionalen Definitionen des geordneten Paars
TO BE DONE
- Diesen Abschnitt in einzelen Seiten auslagern.
Heute werden Paare meist als Mengen- oder Klassenpaare definiert. Aber auch in Mengenlehresystemen, in denen „Funktion“ der unbestimmte Grundbegriff ist, dessen Eigenschaften axiomatisch festgelegt werden und mit dessen Hilfe die übrigen Begriffe, wie „Menge“, „Klasse“, „Relation“ etc. definiert werden, ist es möglich, „geordnete Paare“ einzuführen. Insbesondere Gottlob Frege und Alonzo Church sind diesen Weg gegangen.
Frege benötigt Paare zur Konstruktion von reellen Zahlen (vgl. Frege (1903, §161 ff.)[38], Kutschera (1989, S. 125)[39]). Er war mit seinem strengen Formalismus seiner Zeit weit voraus [16]) und führte daher den Paarbegriff, wie auch alle anderen von ihm verwendeten Begriffe, streng formal ein.
Frege (1893)[3]
Wir definiren nun das Paar so:
Das Semikolon ist hierbei zweiseitiges Functionszeichen. (§144, S. 179[3])
Frege definiert keine Projektionsoperatoren. Folgende Definition stammt von W. Kowarschick (siehe Geordnetes Paar: Definition von Frege):
Anmerkungen
Das Symbol
Wenn man die η-Konversion im Lambda-Kalkül zulässt, kann man den Wertverlauf von
In diesem Fall gilt:
Das heißt, der
Eine detailierte Diskussion von Freges Definition findet sich im Artikel Geordnetes Paar: Definition von Frege.
Freges Definition ist die älteste mir bekannte Definition, die den Paarbegriff auf zuvor definierte Grundbegriffe zurückführt. Allerdings ist diese Definition nicht dazu geeignet, Relationen und Funktionen zu definieren, weil sie den Funktionsbegriff als gegeben voraussetzt. Dies war aber auch nicht die Absicht von Frege. Er benötigte die Paare zur Konstruktion von reellen Zahlen (vgl. Frege (1903, §161 ff.)[40], Kutschera (1989, S. 125)[39]).
Bei
Das Paaraxiom
Frege beweist mit Hilfe der von ihm definerten Axiome mehrere Paareigenschaften. Die wichtigsten dieser Sätze sind (in moderner Notation):
- Wenn ein Gegenstand mit einem zweiten und ein dritter Gegenstand mit einem vierten zusammenfällt, so fällt das aus dem ersten und dritten bestehende Paar zusammen mit dem aus dem zweiten und vierten bestehenden.
- Wenn ein Paar mit einem zweiten zusammenfällt, so fällt das zweite Glied des ersten mit dem zweiten Gliede des zweiten zusammen.
- (ohne weitere Erörterungen von Frege)
Diese Eigenschaften zeigen, dass sein Paarbegriff das Paaraxiom erfüllt, welches explizit erst vier Jahre später von Giuseppe Peano formuliert wurde.[20]
Church (1941)[19]
TO BE DONE
Die wichtigsten Definitionen von Mengenpaaren
Im Folgenden werden wegweisende Definitionen von Mengenpaaren (d. h. Unmengen sind als Paarelemente nicht erlaubt) aufgeführt: die Definitionen von Hausdorff, Wiener, Kuratowski und Quine. Es werden jeweils auch die beiden Projektionsoperatoren angegeben. Gemäß Satz 6.2 („Aus der Existenz der Projektionsoperatoren folgt das Paaraxiom“) ist damit sichergestellt, dass das Paaraxiom erfüllt ist.
Hausdorff (1914)[25]
Felix Hausdorff unterscheidet das erste und das zweite Element eines Paares mit Hilfe zweier spezieller Mengen
Anmerkungen zur Definition von Hausdorff
Bei
Diese Definition hat einen Nachteil. Um den Paarbegriff verwenden zu können, muss man für die Elemente, die
in Paaren gespeichert werden sollen, gemäß der Definition von Hausdorff stets voraussetzen,
dass diese Elemente ungleich
Allerdings ist die von Hausdorff geforderte Bedingung
Es gelte für die folgenden Betrachtungen zunächst noch
Wie man sieht, unterscheiden sich alle Mengen auf der rechten Seite. Es gibt nur drei Mengen, die zwei zweielementige Mengen enthalten (1., 3, und 5.). Diese drei Mengen unterscheiden sich jedoch. Es gibt darüber hinaus zwei wohlunterscheidbare Mengen, die je eine zwei- und eine einelementige Menge enthalten (2. und 4.). Die beiden letzen Mengen sind ebenfalls einmalig: 6. ist eine zweielementige Menge, deren beiden Elemente einelementig sind, und 7. ist eine einelementige Menge, die eine zweielementige Menge enthält.
Verallgemeinerung der Projektionsoperatoren
Wenn man die Projektionsoperatoren auf alle sieben unterschiedlichen Fälle anwendet, stellt man fest, dass jeweils nur in einem Fall ein falsches Ergebnis geliefert wird.
Der Projektionsoperator
Wiener (1914)[24]
Bei der Definition von Norbert Wiener besteht der (vermeindliche) Nachteil der Hausdorff-Paare nicht,
da er das erste und und das zweites Element eines Paares anhand
der Mächtigkeit der zugehörigen Mengen unterscheidet:
Anmerkungen zur Definition von Wiener
Bei
Die Definition von Wiener sorgt dafür,
dass die Menge
Kuratowski (1921)[26]
Kazimierez Kuratowski definiert sieben Jahre später geordnete Mengenpaare deutlich einfacher als Wiener und Hausdorff. (Er geht in seinen Artikel allerdings nur auf die Vorteile seiner Definition gegenüber der Definition von Hausdorff ein.)
La classe
Übersetzung:
Die Klasse
Moderne Schreibweise:
Anmerkungen zur Definition von Kuratowski
Allgemein gilt für Mengen
Kuratowski-Paare haben folgende Eigenschaften, da
Damit kann man zeigen, dass es sich
bei
Alternativ könnte
Die Bedingung
Nelson Goodman merkt an, dass sich die Definition von Kuratowski problemlos für beliebige
Quine (1940)[29]
Willard Quine merkt in seinem Buch „Mathematical Logic“ an, dass Wieners Definition vereinfacht werden kann. (Er verwendet dennoch die Definition von Kuratowski und schlägt außerdem eine erste Klassenpaar-Definition vor, die er allerdings selbst kurz darauf als fehlerhaft erkennt; vgl. Abschnitt „Die Weiterentwicklung des Paarbegriffs“.)
Quine (1986)[33]
Quine definiert Mengenpaare wie folgt, wobei
Anmerkungen zur Definition von Quine
Bei
In den 40er-Jahren hatte Willard Quine eine Klassenpaar-Definition entwickelt (siehe Abschnitt Weiterentwicklung des Paarbegriffs), die sich problemlos zu einer
Definition von
sondern sogar zu einer Definition von
Die Idee hinter Quines Definition ist, dass jedem Paar- bzw. Tupelelement
seine Position im
Quine betont, dass
Allerdings liefern die Projektionsoperatoren auch in diesen Fällen das korrekte Ergebnis, da
Die wichtigsten Definitionen von Klassenpaaren
Wenn Paare nicht nur Mengen, sondern auch Unmengen enthalten können, spricht man von Klassenpaaren.
Die Definitionen von Wiener, Hausdorff und Kuratowski sind für Klassenpaare allerdings ungeeignet,
da diese Definitionen alle darauf basieren, dass die Paarelemente
Und da die Allklasse selbst wieder ein Unmenge ist, pflanzt sich die Unmengeneingeschaft fort, wenn nur ein einziges Element einer beliebigen Klasse eine Unmenge ist.
Auch wenn
Man kann sich das Problem der Unmengen auch anhand der Typtheorie verdeutlichen. Wie im Abschnitt „Die Weiterentwicklung des Paarbegriffs“ beschrieben wurde, liegen die Mengenpaare von Hausdorff, Wiener und Kuratowski auf einer höheren Ebene als ihre Elemente. Eine Unmenge liegt dagegen auf gar keiner Ebene. Für jede Ebene gibt es beliebig viele Elemente der Unmenge, die auf höheren Ebenen liegen. Also kann eine Paardefinition, bei dem jedem Paar eine Ebene zugeordnet werden kann, hier nicht funktionieren.
In einem mengenbasiertes Axiomen-System (wie es z. B. der Zermelo-Fraenkel-Mengenlehre zu Grunde liegt) ist das Paaraxiom
für Mengenpaare uneingeschränkt gültig, da in diesem Fall
Für die Definition von Relationen und Funktionen reicht diese eingeschränkte Form des Paaraxioms aus. Relationen und Funktionen anhalten Paare (oder – allgemeiner – Tupel) als Elemente. Auch wenn eine Relation oder eine Funktion selbst eine Unmenge sein sollte, so sind doch alle ihre Elemente Mengen.
Wenn man allerdings beispielsweise Algebren, wie die Halbgruppe der Ordinalzahlen
Quine (1945)[31][42]
Zunächst wird zur Abkürzung der nachfolgenden Definitionen eine Hilfsoperationen eingeführt (die allerdings jederzeit durch Textersetzung eliminiert werden kann):
Mit Hilfe der Operation
Anmerkungen zu Quines Definition von 1945
Bei
Rosser-Paare
1953 übernimmt J. Barkley Rosser die Definition von Quine.[12] Die oben angegebenen Projektionsoperatoren stammen von ihm. Quine hat nur deren Existenz postuliert (siehe nachfolgenden Abschnitt).
Die Idee hinter Quines Definition
Um Paare
- Es gibt kein
für das gilt; ist dabei die natürliche Zahl „Null“. - Aus
lässt sich eindeutig ermitteln. und liegen auf derselben Ebene in der Typhierachie.
Da der Nachfolger einer jeden natürlichen Zahl ungleich
Die dritte Bedingung zu erfüllen, ist etwas komplizierter. Die Bedingung ist beispielsweise erfüllt, wenn man der Mengenlehre eine Typhierarchie mit natürlichen Zahlen als Urelementen zu Grunde legt.
Quine führt allerdings die natürliche Zahl
Quine-Paare (gemäß der Definition von 1945) sind Klassenpaare
Quines Idee, nicht die Paarelemente
Das Paaraxiom ist also im Falle von Quine-Paare nicht nur für Mengen, sondern auch für Unmengen erfüllt. Das heißt, Quine-Paare sind – sowohl in der Version von 1945 als auch schon in der Version von 1941[30] – Klassenpaare.
Dabei ist es vollkommen unwichtig, auf welche Art die natürlichen Zahlen, die im Operator
Jedes Objekt ist ein Paar
1946 ist Quine eine weitere erstaunliche Eigenschaft seiner Paar-Definition aufgefallen:
Jedes beliebige Objekt ist identisch zu einem geordnetem Paar.[42]
Für jedes Objekt
Beispielsweise gilt, wenn man Quines Definition
( |