Geordnetes Paar

Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nur teilweise:

Korrektheit: 4 (großteils überprüft)

Umfang: 3 (einige wichtige Fakten fehlen)

Quellenangaben: 5 (vollständig vorhanden)

Quellenarten: 5 (ausgezeichnet)

Konformität: 5 (ausgezeichnet)

Ein geordnetes Paar $(a,b)$ bezeichnet die Zusammenfassung zweier nicht notwendigerweise verschiedener Objekte $a$ und $b$ zu einer Einheit. Die beiden Elemente sind dabei angeordnet. Das heißt, die beiden Paare $(a,b)$ und $(b,a)$ sind dann und nur dann gleich, wenn $a$ und $b$ gleich sind.

„Geordnetes Paar“ ist ein elementarer Grundbegiff der Mathematik. Sie sind ein zentrales Hilfsmittel der Mathematik und der Informatik, um z.B. Beziehungen zwischen Objekten herstellen 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, 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 $\{a,b\}$ (wobei $a \neq b$ gelten muss, damit die Menge wirklich zwei Elemente enthält) sind nur die Elemente von Bedeutung, die Reihenfolge der Elemente spielt dagegen keine Rolle:

$\forall a,b: \{a,b\} = \{b,a\}$

Im Gegensatz dazu sind bei „geordneten Paaren“ $[a,b]$ (wobei auch $a = b$ erlaubt ist) nicht nur deren Elemente von Bedeutung, sondern zusätzlich noch deren Reihenfolge:

$\forall a,b: [a,b] = [b,a] \Leftrightarrow a = b\quad$

Das Paaraxiom von Peano

$\forall a,b: [a,b] = [c,d] \Leftrightarrow a=c \;\&\;b=d $

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 $\in$ definiert, verwendet man einen Operator, der selbst schon zwei Elemente anordnet: $a \in b$ bedeutet etwas anderes als $b \in a$. Diese Problem ist philosophischer Natur und besteht in der Mathematik prinzipiell. Um eine Objektsprache zu definieren, benötigt man eine Metasprache, in der viele der auf Objektebene zu definierenden oder beweisenden Eigenschaften schon als gültig angesehen werden. Zur Definition der Metasprache benötigt man eine Metametasprache etc. pp.

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.

Definitionen

Brockhaus (1991): Band 16, S. 414

Definition (Brockhaus (1991))

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: $(a,b)$ ist i.a. verschieden von $(b,a)$. P. lassen sich als Punkte im kartes. Produkt der zugrundeliegenden Menge mit sich selbst auffassen.

Definition von Randall Dipert, Dipert (1982), S. 354

Definition (Dipert (1982))

Ein geordnetes Paar ist, grob gesprochen, (a) eine Entität die zwei andere Entitäten enthält und (b) zwar so, dass eines von diesen beiden Entitäten als das 'erste' identifiziert werden kann und das andere als das 'zweite'. Genauer gesagt, das unverwechselbar machenende Kriterium von geordneten Paaren ist: zwei geordnete Paare sind identisch, genau dann wenn die entsprechenden Elemente identisch sind. Das heißt, wenn $< A, B >$ und $< C,D >$ geordnete Paare mit den Elementen $A$, $B$, $C$, und $D$ sind, dann möchten wir Folgendes haben:

$< A,B > \;=\; < C, D>$ genau dann wenn $A = C$ und $B = D$.

Anmerkung (von Dipert)

Von keiner anderen Eigenschaft geordneter Paare wurde jemals gezeigt, dass sie notwendig oder wünschenswert wäre. Diese eine Eigenschaft ist ausreichend.

Definition (Kowarschick (2014))

Der Term $[a,b]$ heißt geordnetes Paar, wenn für den Operator $[\cdot,\cdot]$ das Paaraxiom erfüllt ist:

$\forall a,b: [a,b] = [c,d] \Leftrightarrow a=c \;\&\;b=d $

(Zwei Paare $[a,b]$ und $[c,d]$ sind genau dann gleich, wenn sowohl $a$ und $c$ als auch $b$ und $d$ gleich sind.)

Mengenpaare

Ein geordnetes Paar $[a,b]$ heißt Mengenpaar, wenn sowohl $a$ als auch $b$ eine Menge oder ein Urelement ist.

Klassenpaare

Ein geordnetes Paar $[a,b]$ heißt Klassenpaar, wenn sowohl $a$ als auch $b$ eine Menge, eine Unmenge oder ein Urelement ist.

Anmerkung zur Definition von Mengen- und Klassenpaaren

Ein geordnetes Paar kann an Stelle von Mengen, Unmengen und Urelmenten auch noch andere Arten von Elementen $a$ und $b$ enthalten. Gottlob Frege erlaubt beispielsweise „Gegenstände“, „Funktionen“ und „Werthverläufe“.. John von Neumann erlaubt „Argumente“ (und damit insbesondere auch spezielle Funktionen, die sogenannten „Argument-Funktionen“) und in LISP sind nur Atome (Urelemente) und Paare als Elemente erlaubt.

Projektionsoperatoren

Für geordnete Paare gibt es – wegen des Paaraxioms – zwei Projektionsoperatoren $\pi_1$ und $\pi_2$, die das erste bzw. das zweite Element des Paars extrahieren. Bei $\pi_1$ und $\pi_2$ handelt es sich normalerweise nicht um Funktionen, da der Funktionsbegriff überlicherweise erst nachträglich mit Hilfe des Paarbegriffs definiert wird. Es handelt sich häufig um abkürzende Schreibweisen, die durch die sie definierenden Terme (siehe nachfolgende explizite Mengen-/Klassenpaar-Definitionen) ersetzt werden können. Daher werden $\pi_1$ und $\pi_2$ hier Operatoren genannt.

Definition (Kowarschick (2014))

Operatoren $\pi_1$ und $\pi_2$, die das erste bzw. das zweite Element eines jeden Paars (des zugehörigen Universums) extrahieren

$\forall a,b: \pi_1([a,b]) = a\quad$ (das erste Element des jeweiligen Paars)

$\forall a,b: \pi_2([a,b]) = b\quad$ (das zweite Element des jeweiligen Paars)

heißen Projektionsoperatoren.

Anmerkung

Die hier verwendeten Bezeichnungen $\pi_1$ und $\pi_2$ für die Projektionsoperatoren gehen auf Edgar Codd zurück, den Begründer der Relationalen Algebra.

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): $Q_1$ und $Q_2$
• McCarthy (1960): car und cdr
• Morse (1965): $\rm{crd}'$ und $\rm{crd}$
• Schmidt (1966): $\mathfrak{G}$ und $\mathfrak{G}'$
• Ebbinghaus (2003): $\pi_l$ und $\pi_r$

Eigenschaften der Projektionsorperatoren

Da die Projektionsoperatoren zuvor nur metasprachlich definiert wurden, kann man Eigenschaften von $\pi_1$ und $\pi_2$ zunächst auch nur auf Metaebene beweisen. Wenn man später den Paarbegriff und gegebenenfalls den Funktionsbegriff objektsprachlich formalisiert hat, kann man anschließend auch Projektionsoperatoren oder sogar Projektionsfunktionen definieren und dann für diese analoge Aussagen mit Hilfe einer Objektsprache beweisen.

Existenz und Eindeutigkeit der Projektionsoperatoren

Wenn das Paaraxiom gilt, gibt es genau einen auf den zugehörigen Paaren definierten Operator $\pi_1$ und genau einen auf den zugehörigen Paaren Operator $\pi_2$, die die in der Definition geforderten Eigenschaften erfüllen.

Insbesondere gilt damit für jedes Paar $p$ die Beziehung $p = [\pi_1(p),\pi_2(p)]$.

Beweis

siehe Satz „Existenz und Eindeutigkeit der Projektionsoperatoren“

Anmerkung

Der Satz sagt nicht aus, dass es nicht zwei Operatoren $\pi_1$ und $\pi'_1$ bzw. $\pi_2$ und $\pi'_2$ geben kann, die auch für Nicht-Paare $\overline p$ definiert sind und für derartige Elemente evtl. unterschiedliche Ergebnisse liefern: $\pi_1(\overline p)\neq\pi'_1(\overline p)$ bzw. $\pi_2(\overline p)\neq\pi'_2(\overline p)$.

Aus der Existenz der Projektionsoperatoren folgt das Paaraxiom

Wenn zwei Projektionsoperatoren $\pi_1$ und $\pi_2$ existieren, die in der Definition geforderten Eigenschaften 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 die beiden Projektionsoperatoren eindeutig sind, sofern sie überhaupt existieren.

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 axiomatische, die funktionale, die relationale, die mengentheoretische und die klassentheoretische Definition des Paarbegriffs.

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)	$(a;b)$
von Neumann (1925)	$(a,b)$
McCarthy (1960, LISP)	$(a \cdot b)$ bzw. (a . b)

Peano formuliert das Paaraxiom direkt, von Neumann und McCarthy fordern dagegen die Existenz von zwei Projektionsoperatoren, was ebenfalls die Erfüllung des Paaraxioms zur Folge hat.

Funktionale Definition von geordneten Paaren

In einem formalen System, in dem Funktionen axiomatisch eingeführt werden, können geordnete Paare als spezielle Funktionen eingeführt werden.

Beispiele:

	Notation	Definition	„moderne Form“ der Definition
Frege (1893)	$a; b$	$\Vdash \acute{\epsilon}(a \frown (b \frown \epsilon)) = a; b$	$ a; b := \lambda x . x b a\quad$ (vgl. Artikel „Geordnetes Paar: Definition von Frege“)
Church (1941) (Lambda-Kalkül)	$[a, b]$	$[a, b] \rightarrow \lambda x. x a b$	$ [a, b] := \lambda x . x a b\quad$

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 mir allerdings unbekannt.

Relationale Definition von geordneten Paaren

In Systemen, in denen Relationen axiomatisch eingeführt werden, können geordnete Paare als spezielle Relationen definiert werden.

Beispiel:

	Notation	Definition	„moderne Form“ der Definition
Whitehead, Russell (1910)	$(x,y)$	... an ordinal couple (geordnetes Paar) ... is defined as a relation $\iota`x \uparrow \iota`y$ ...	$(x,y) := \{x\}\times\{y\}$

Bei der Definition von Whitehead und Russell ist $a \uparrow b$ das kartesische Produkt zweier Mengen $a$ und $b$. Der Term $\iota`x $ bezeichnet die einmelementige Menge, die $x$ als einziges Element enthält. Whitehead und Russell definieren zuerst den Begriff „Relation“, darauf aufbauend das „kartesisches Produkt“ (wenn auch nicht unter diesem Namen) und darauf aufbauend den Begriff „geordnetes Paar“. In mengen- oder klassenbasierten Systemen (siehe nachfolgende Abschnitte) geht man genau umgekehrt vor.

Mengentheoretische Definition von geordneten Paaren

In einem formalen System, in dem Mengen axiomatisch eingeführt werden, können geordnete Paare als spezielle Mengen eingeführt werden.

Beispiele:

	Notation	Definition	„moderne Form“ der Definition
Hausdorff (1914)	$(a,b)$	$ \{\{a,1\},\{b,2\}\}$	$ (a,b) := \{\{a,1\},\{b,2\}\}$
Wiener (1914)	kein spezieller Term	$ \iota`(\iota`\iota`x \cup \iota`\Lambda) \cup \iota`\iota`\iota`y$	$[x,y] := \{\{\{x\},\emptyset\},\{\{y\}\}\} $
Kuratowski (1921)	kein spezieller Term	La classe $((a,b),(a))$ est une „paire ordonnée dont $a$ est le premier élément et $b$ est le second“	$[a,b] := \{\{a,b\},\{a\}\}$
Quine (1940)	$x;y$	$ \iota(\iota x \cup \iota\Lambda) \cup \iota\iota y$	$x;y := \{\{x,\emptyset\},\{y\}\}$
Quine (1986)			$[a,b] := \{\{\{a\},1\},\{\{b\},2\}\}$

Klassentheoretische Definition von geordneten Paaren

TO BE DONE

Geschichte des Paarbegriffs

Peirce (1870), S. 359

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.

Erste Definition des geordneten Paares, allerdings noch ohne Paaraxiom und ohne explizite Bezeichnung „Paar“, Peano (1889), S. XII6

Die symbolische Schreibweise $(x,y)$ für geordnete Paare verwendet Giuseppe Peano erstmals in der 1889 erschienen Arbeit „Arithmetices principia: nova methodo“:

Es seien $x$, $y$ beliebige Entitäten; das System, das aus Entität $x$ und aus Entität $y$ zusammengesetzt ist, fassen wir als neue Entität auf und bezeichnen es mit dem Zeichen $(x,y)$: $\ldots$

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 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)). Allerdings blieb die Wirkung von Frege gering, „auch wegen seiner Verwendung zahlreicher und ungewöhnlicher Symbole“, wie Wußing in seiner „kurturhistorischen Zeitreise“ anmerkt.

In zwei Veröffentlichungen von 1897 formuliert Giuseppe Peano erstmals das Paaraxiom. 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 zur von ihm zuvor definierten Symbole ausdrücken könne. 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ührte Peano übrigens kurz nach dem Paaraxiom auch noch den Existenzoperator $\exists$ als zweite bedeutende Neuerung ein.)

1914 gelingt es Felix Hausdorff und Norbert Wiener unabhängig voneinander, erstmals geordnete (Mengen-)Paare durch Mengen auszudrücken (siehe Abschnitte Hausdorff (1914) und Wiener (1914)). 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, weil eine Relation – wie von Peirce bereits 1870 erkannt wurde (siehe oben) – als Menge bzw. Klasse von Paaren oder – allgemeiner – von Tupeln aufgefasst werden kann. Das heißt, man konnte von 1914 an auf spezielle Typisierung von und spezielle Axiome für Relationen und Funktionen verzichten. Beispielsweise hatten Whitehead und Russell 1910 in der Principa Mathmatica noch drei Typhierachien für Mengen, Funktionen und Relationen definiert, um die Russellsche Antinomie zu vermeiden.

Die Weiterentwicklung des Paarbegriffs

TO BE DONE

Wenn man irgendeinen Grundbegriff mit Hilfe anderer Grundbegriffe definiert, hat der so definierte Grundbegriff zusätzliche Eigenschaften, die der ursprüngliche Grundbegriff nicht hat.

Wenn man beispielsweise die Ordinalzahlen auf die von John von Neumann vorgeschlagene Weise definiert, gilt für alle Ordinalzahlen $m$ und $n$:

$m<n \leftrightarrow m \in n$

Diese Eigenschaft hat sich als vorteilhaft erwiesen, gilt aber nicht im Axiomensystem der natürlichen Zahlen von Peano, da dort der Elementoperator für natürliche Zahlen gar nicht definiert ist.

Dass alle Hausdorff-Paare $[a,b]$ folgende Eigenschaft haben,

$\{\boldsymbol{1},\boldsymbol{2}\}\subseteq\bigcup[a,b]$

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 hat Willard Quine Ende der 30er-Jahre und in den 40er-Jahren beschäftigt. 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 war dies sehr unpraktisch.

Vorschlag für ein Klassenpaar, Quine (1940), S. 202

Eine weiteres Problem der Kuratowski-Paare ist, dass sie nur Mengen, aber keine Unmengen als Paarelemente enthalten können. Quine hat in seinem Lehrbuch „Mathematical Logic“ von 1940 zwar noch die Kuratowski-Paare verwendet, aber bereits eine alternative Paar-Definition angegeben, bei der geordnete Paare auch Unmengen enthalten können.

Anmerkungen von Goodman zu Quines Vorschlag, Goodman (1941), S. 150

The alternative version adopted in D23 is due to Kuratowski. In the present system simplicity would have gained in some directions, and lost in others, by construing $x,y$ in still a third way: $\hat z(\exists w)(w \in z \;. z = \iota w \;. \vee \;. w \in y \;. z = \overline{\iota w})$. This version has the advantage of rendering the antecedent ‘$x, y, w \in V$’ superfluos in †417.

Allerdings hat er bald erkannt, dass diese Definition fehlerhaft ist, und über dieses Problem mit Nelson Goodman diskutiert:

[...] Quine suggested an alternative to the definition of ordered couple [...], but later discoverd that this alternative definition would fail to distinguish $x,y$ from $y,x$ when $x\subset y$. In a later discussion between us he proposed the first satisfactory definition of the ordered couple as a class only one type higher than its components.

Goodman merkt jedoch kritisch an, dass diese Definition nicht problemlos verallgemeinert werden kann, um „längere Sequenzen“ (d.h. $n$-Tupel mit $n>2$) zu definieren. Er verbessert daher Quines Definition so, dass – erstens – ein Paar weiterhin nur um eine Ebene höher liegt als seine Elemente und – zweitens – diese Definition problemlos für $n$-Tupel verallgemeinert werden kann.

Dies wiederum stachelt Quine an, Goodmans Definition zu verbessern. 1945 präsentiert er eine Paar-Definition, bei der jedes Paar auf derselben Ebene liegt wie ihre Elemente und die für beliebige $n$-Tupel verallgemeinert werden kann. Diese $n$-Tupel liegen dann ebenfalls auf derselben Ebene wie ihre Elemente.

Bedeutung des Paarbegriffs

Randall Dipert hält die „funktionsfähige“ Definition des Paarbegriffs innerhalb der Mengenlehre für eine der „bedeutsamsten Entdeckungen“ des frühen 20. Jahrhunderts auf dem Gebiet der Mathematischen Logik:

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. The definition also was instrumental in achieving the appearance of ontological economy - since it seemed only sets were needed - although this feature was emphasized only later.

Akihiro Kanamori schlägt 20 Jahre später in dieselbe Kerbe:

For the modern set theorist the empty set $0$, the singleton $\{a\}$, and the ordered pair $<x, y>$ are at the beginning of the systematic, axiomatic development of set theory, both as a field of mathematics and as a unifying framework for ongoing mathematics. These notions are the simplest building blocks in the abstract, generative conception of sets advanced by the initial axiomatization of Ernst Zermelo [l908a] [...]

Auf der andere Seite sieht Dipert die Definition des geordneten Paars und damit die Definition von Relation und Funktion mit Hilfe von Mengen oder Klassen – zumindest aus philosophischer Sicht – sehr kritisch:

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.

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:

1. Es muss nicht unbedingt die „Menge“ als dasjenige Grundelement gewählt werden, mit deren Hilfe die anderen Grundbegriffe definiert werden.
2. Verschiedenen Grundbegriffen, wie „Menge“, „geordnetes Paar“/„Tupel“, „Funktion“, „Relation“ etc. können durchaus unterschiedliche „Universen“ zugeordnet werden.

Für beide Vorgehensweisen finden sich vor allem in der Informatik Beispiele. Beispielsweise basiert die Programmiersprache LISP auf einem Universum 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).

Die zweite Vorgehensweise ist in der Informatik sogar noch weiter verbreitet. Jede Programmierprache unterscheidet mehr oder weniger scharf zwischen atomaren Typen, Containertypen (Mengen, Multimengen, Listen etc.), Funktionen und weiteren Datentypen.

Das heißt, 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.

Die wichtigsten funktionalen Definitionen des geordneten Paars

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.), Kutschera (1989, S. 125)). Er war mit seinem strengen Formalismus seiner Zeit weit voraus Quine (1989): Willard Van Orman Quine; Peirce's Logic; in: Selected Logic Papers; Auflage: Enlarged Edition; Verlag: Harvard University Press; Adresse: Cambridge, London; 1995; Quellengüte: 5 (Buchartikel)</ref>) und führte daher den Paarbegriff, wie auch alle anderen von ihm verwendeten Begriffe, streng formal ein.

Definition des geordneten Paars, Frege (1893), §144, S. 179

Frege (1893)

Wir definiren nun das Paar so:

$\Vdash\acute{\epsilon}(o \frown (a \frown \epsilon)) = o;a$

Das Semikolon ist hierbei zweiseitiges Functionszeichen. (§144, S. 179)

Frege definiert keine Projektionsoperatoren. Folgende Definition stammt von W. Kowarschick (siehe Geordnetes Paar: Definition von Frege):

$\begin{array}{lclclcl}

 \Vdash \acute{p}(p(\acute{x}(\acute{y}y))) = \pi_1 \\
 \Vdash \acute{p}(p(\acute{x}(\acute{y}x))) = \pi_2 \\

\end{array} $

Anmerkungen

$\Vdash$ ist bei Frege der „Definitionsdoppelstrich“ und $\acute{\epsilon}\phi(\epsilon)$ der „Werthverlauf“ einer Funktion $\phi$, wobei man den Wertverlauf-Operator als Lambda-Operator vorstellen kann:

$\acute{\epsilon}\phi(\epsilon) \;\hat\approx\; \lambda \epsilon .\phi(\epsilon)$

$\frown$ ein ein Operator, der den Funktionsaufruf für Wertverläufe nachbildet:

Satz 1 und Satz 2: Der Wertverlauf von ein- und zweistelligen Funktionen, Frege (1893), S. 75

$\vdash f(a) = a \frown \acute{\epsilon}f(\epsilon)$ (Frege: Satz 1, §54, S. 75)

Das Symbol $\vdash$ ist dabei der „Inferenzoperator“, der schon bei Frege die heute noch übliche Bedeutung „Aus den Axiomen kann die nachfolgende Formel logisch hergeleitet werden.“ hatte.

Wenn man die η-Konversion im Lambda-Kalkül zulässt, kann man den Wertverlauf von $\phi$ mit $\phi$ identifizieren (Frege unterscheidet allerdings streng zwischen Funktion und zugehörigem Wertverlauf):

$\lambda \epsilon .\phi(\epsilon) \;=\; \phi$

In diesem Fall gilt:

$(\lambda \epsilon .\phi(\epsilon))(x) \;=\; \phi(x)$

Das heißt, der $\frown$-Oerator entspricht im Prinzip der $\beta$-Konversion. Freges Paar-Definition kann also folgendermaßen im Lambda-Kalkül nachgebildet werden:

$o;a \,:= \; \lambda \epsilon . \epsilon a o$

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.), Kutschera (1989, S. 125)).

Bei $\pi_1$ und $\pi_2$ handelt es sich tatsächlich um Projektionsoperatoren. Der Beweis des Satzes basiert im Wesentlichen auf Satz 1 von Frege.

$\begin{array}{lcll}

 \pi_1(a;b) & = & \acute{p}(p(\acute{x}(\acute{y}y)))(a;b)          & (\rm{Def. von}\;\pi_1)    \\ 
            & = & (a;b) \frown \acute{p}(p(\acute{x}(\acute{y}y)))  & (\rm{Frege: Satz 1})      \\ 
            & = & (a;b)(\acute{x}(\acute{y}y))                      & (\rm{Frege: Satz 1})      \\ 
            & = & \acute{x}(\acute{y}y) \frown (a;b)                & (\rm{Frege: Satz 1})      \\ 
            & = & \acute{x}(\acute{y}y) \frown (\acute{\epsilon}(a \frown (b \frown \epsilon)) & (\rm{Def. von}\;a;b) \\
            & = & a \frown (b \frown \acute{x}(\acute{y}y))         & (\rm{Frege: Satz 1})      \\
            & = & a \frown \acute{y}y                               & (\rm{Frege: Satz 1})      \\ 
            & = & a                                                 & (\rm{Frege: Satz 1})     

\\

 \pi_2(a;b) & = & \acute{p}(p(\acute{x}(\acute{y}x)))(a;b)          & (\rm{Def. von}\;\pi_2)    \\
            & = & (a;b) \frown \acute{p}(p(\acute{x}(\acute{y}x)))  & (\rm{Frege: Satz 1})      \\ 
            & = & (a;b)(\acute{x}(\acute{y}x))                      & (\rm{Frege: Satz 1})      \\
            & = & \acute{x}(\acute{y}x) \frown (a;b)                & (\rm{Frege: Satz 1})      \\ 
            & = & \acute{x}(\acute{y}x) \frown (\acute{\epsilon}(a \frown (b \frown \epsilon))  & (\rm{Def. von}\;a;b) \\ 
            & = & a \frown (b \frown \acute{x}(\acute{y}x))         & (\rm{Frege: Satz 1})      \\
            & = & a \frown \acute{y}b                               & (\rm{Frege: Satz 1})      \\
            & = & b                                                 & (\rm{Frege: Satz 1})        

\end{array} $

Das Paaraxiom

Freges Paar-Begriff erfüllt das Paaraxiom, Frege (1893), Tafel der wichtigeren Lehrsätze, S. 248

Frege beweist mit Hilfe der von ihm definerten Axiome mehrere Paareigenschaften. Die wichtigsten dieser Sätze sind (in moderner Notation):

$\vdash a = i \;\rightarrow\; (o = e \;\rightarrow\; o ; a = e ; i)\quad$ (Frege (1893), §155, Satz Nr. 251; Tafel der wichtigeren Lehrsätze, S. 248)

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.

$\vdash m; x = c; d \;\rightarrow\; x = d\quad$ (Frege (1893), §149, Satz Nr. 219; Tafel der wichtigeren Lehrsätze, S. 248)

Wenn ein Paar mit einem zweiten zusammenfällt, so fällt das zweite Glied des ersten mit dem zweiten Gliede des zweiten zusammen.

$\vdash m; x = c; d \;\rightarrow\; m = c\quad$ (Frege (1893), §149, Satz Nr. 220; Tafel der wichtigeren Lehrsätze, S. 248)

(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.

Church (1941)

TO BE DONE

Die wichtigsten axiomatischen Definitionen

Peano (1897)

Definition des geordneten Paars und Paaraxiom, Peano (1897a), S. 580

$(x ; y)$ indica la coppia formata dagli oggetti $x$ ed $y$.

Questa coppia è considerata come un nuovo oggetto. [...]

L'idea di coppia è fondamentale, cioè noi non la sappiamo esprimere mediante i simboli precedenti. Però possiamo definire l'eguaglianza di due coppie:

[...]$\quad(x ; y) = (a ; b) \;\;.\,=\;.\;\; x=a \;.\; y=b \quad$ Def.

“ la coppia $(x ; y)$ dicesi eguale alla $(a ; b)$, quando i loro elementi sono ordinatamente eguali „.

Übersetzung und angepasste Symbolik (Kowarschick)

$(x;y)$ bezeichnet das Paar, das aus den Objekten $x$ und $y$ gebildet wird.

Dieses Paar wird als neues Objekt betrachtet. [...]

Die Idee eines geordneten Zahlenpaars ist von grundlegender Bedeutung. Wir wissen aber nicht, wie wir es durch die [im Aufsatz] zuvor erwähnten Symbole ausdrücken können. Aber wir können die Gleichheit von zwei Paaren definieren:

[...]$\quad(x;y) = (a;b) \;:\Leftrightarrow\; x=a \,\,\&\,\, y=b$

Das Paar $(x;y)$ ist gleich $(a;b)$, wenn ihre Elemente gemäß ihrer Anordnung gleich sind.

Anmerkungen zur Definition von Peano

Definition des geordneten Paars und Paaraxiom, Peano (1897b), S. 6

Peano hat in seinem Aufsatz „Studii de Logica Matematica“ und kurz darauf in Band 2 seines Buchs „Formulaire de Mathématiques“ erstmals explizit das „Paaraxiom“ formuliert.

Neumann (1925)

TO BE DONE

McCarthy (1960)

In LISP werden geordnete Paare in der Form $(a \cdot b)$ bzw. (a . b) (ASCII-Schreibweise) notiert und mit der Funktion cons erzeugt. Die Operatoren $\pi_1$ und $\pi_2$ zur Extraktion der Elemente heißen bei McCarthy car und cdr.

Listen werden in LISP als Abkürzung für cons-Ketten definiert (siehe Tupel).

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 Frege, 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.

Definition des geordneten Paars mit Hilfe von Mengen, Hausdorff (1914), S. 32

Hausdorff (1914)

Felix Hausdorff unterscheidet das erste und das zweite Element eines Paares mit Hilfe zweier spezieller Mengen $\boldsymbol{1}$ und $\boldsymbol{2}$, die anderweitig nicht verwendet werden. Es sei $\{a,b\} \cap \{\boldsymbol{1},\boldsymbol{2}\} = \emptyset \,\wedge\, \boldsymbol{1} \not= \boldsymbol{2}$ erfüllt.

$\begin{array}{lclclcl}

 [a,b]    & := & \{\{a,\boldsymbol{1}\},\{b,\boldsymbol{2}\}\} \\
 \pi_1(p) & := & \bigcap\{x: \{x,\boldsymbol{1}\} \in p\} \\ 
 \pi_2(p) & := & \bigcap\{x: \{x,\boldsymbol{2}\} \in p\} 

\end{array} $

Anmerkungen zur Definition von Hausdorff

Bei $\pi_1$ und $\pi_2$ handelt es sich tatsächlich um Mengenpaar-Operatoren:

$\begin{array}{lcld}

 \pi_1([a,b]) & = & \bigcap\{x: \{x,\boldsymbol{1}\} \in [a,b]\} \\
              & = & \bigcap\{x: \{x,\boldsymbol{1}\} \in \{\{a,\boldsymbol{1}\},\{b,\boldsymbol{2}\}\}\, \} \\
              & = & \bigcap\{a\} & \mbox{(da } b \not= \boldsymbol{1}\mbox{ und da } a,b \mbox{ Mengen sind)}\\
              & = & a & \mbox{(da } a \mbox{ eine Menge ist)} \\ 
 \pi_2([a,b]) & = & \bigcap\{x: \{x,\boldsymbol{2}\} \in [a,b]\} \\
              & = & \bigcap\{x: \{x,\boldsymbol{2}\} \in  \{\{a,\boldsymbol{1}\},\{b,\boldsymbol{2}\}\}\, \} \\
              & = & \bigcap\{b\} & \mbox{(da } a \not= \boldsymbol{2}\mbox{ und da } a,b \mbox{ Mengen sind)}\\
              & = & b & \mbox{(da } b \mbox{ eine Menge ist)}

\end{array} $

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 $\boldsymbol{1}$ und ungleich $\boldsymbol{2}$ sind. Derartige Fallunterscheidungen blähen die zugehörigen Beweise unnötig auf.

Allerdings ist die von Hausdorff geforderte Bedingung $\{a,b\} \cap \{\boldsymbol{1},\boldsymbol{2}\} = \emptyset$ unnötig. Es reicht aus, wenn $\boldsymbol{1} \not= \boldsymbol{2}$ erfüllt ist.

Es gelte für die folgenden Betrachtungen zunächst noch $\{a,b\} \cap \{\boldsymbol{1},\boldsymbol{2}\} = \emptyset$. Dann kann man folgende Fälle unterscheiden:

$\begin{array}{rlclclcl}

 1. & [a,\boldsymbol{1}]              & = & \{\{a, \boldsymbol{1}\},\{\boldsymbol{1},\boldsymbol{2}\}\}              & = & \{\{\boldsymbol{1},\boldsymbol{2}\},\{a, \boldsymbol{1}\}\} \\
 2. & [a,\boldsymbol{2}]              & = & \{\{a, \boldsymbol{1}\},\{\boldsymbol{2},\boldsymbol{2}\}\}              & = & \{\{a,\boldsymbol{1}\},\{\boldsymbol{2}\}\} \\
 3. & [a,b]                           & = & \{\{a,\boldsymbol{1}\},\{b,\boldsymbol{2}\}\}                            & = & \{\{a,\boldsymbol{1}\},\{b,\boldsymbol{2}\}\} \\
 4. & [\boldsymbol{1},b]              & = & \{\{\boldsymbol{1}, \boldsymbol{1}\},\{b,\boldsymbol{2}\}\}              & = & \{\{\boldsymbol{1}\},\{b,\boldsymbol{2}\}\} \\
 5. & [\boldsymbol{2},b]              & = & \{\{\boldsymbol{2}, \boldsymbol{1}\},\{b,\boldsymbol{2}\}\}              & = & \{\{\boldsymbol{1},\boldsymbol{2}\},\{b,\boldsymbol{2}\}\} \\
 6. & [\boldsymbol{1},\boldsymbol{2}] & = & \{\{\boldsymbol{1}, \boldsymbol{1}\},\{\boldsymbol{2},\boldsymbol{2}\}\} & = & \{\{\boldsymbol{1}\},\{\boldsymbol{2}\}\} \\
 7. & [\boldsymbol{2},\boldsymbol{1}] & = & \{\{\boldsymbol{2}, \boldsymbol{1}\},\{\boldsymbol{1},\boldsymbol{2}\}\} & = & \{\{\boldsymbol{1},\boldsymbol{2}\}\} \\

\end{array} $

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.

$\begin{array}{rlclclclclclcl}

 1. & \pi_1([a,\boldsymbol{1}])              & = & \bigcap\{x: \{x,\boldsymbol{1}\} \in \{\{\boldsymbol{1},\boldsymbol{2}\},\{a,\boldsymbol{1}\}\}\} & = & \emptyset      
   && \pi_2([a,\boldsymbol{1}])              & = & \bigcap\{x: \{x,\boldsymbol{2}\} \in \{\{\boldsymbol{1},\boldsymbol{2}\},\{a,\boldsymbol{1}\}\}\} & = & \boldsymbol{1} \\
 2. & \pi_1([a,\boldsymbol{2}])              & = & \bigcap\{x: \{x,\boldsymbol{1}\} \in \{\{a,\boldsymbol{1}\},\{\boldsymbol{2}\}\}\}                & = & a              
   && \pi_2([a,\boldsymbol{2}])              & = & \bigcap\{x: \{x,\boldsymbol{2}\} \in \{\{a,\boldsymbol{1}\},\{\boldsymbol{2}\}\}\}                & = & \boldsymbol{2} \\
 3. & \pi_1([a,b])                           & = & \bigcap\{x: \{x,\boldsymbol{1}\} \in \{\{a,\boldsymbol{1}\},\{b,\boldsymbol{2}\}\}\}              & = & a              
   && \pi_2([a,b])                           & = & \bigcap\{x: \{x,\boldsymbol{2}\} \in \{\{a,\boldsymbol{1}\},\{b,\boldsymbol{2}\}\}\}              & = & b              \\
 4. & \pi_1([\boldsymbol{1},b])              & = & \bigcap\{x: \{x,\boldsymbol{1}\} \in \{\{\boldsymbol{1}\},\{b,\boldsymbol{2}\}\}\}                & = & \boldsymbol{1} 
   && \pi_2([\boldsymbol{1},b])              & = & \bigcap\{x: \{x,\boldsymbol{2}\} \in \{\{\boldsymbol{1}\},\{b,\boldsymbol{2}\}\}\}                & = & b              \\
 5. & \pi_1([\boldsymbol{2},b])              & = & \bigcap\{x: \{x,\boldsymbol{1}\} \in \{\{\boldsymbol{1},\boldsymbol{2}\},\{b,\boldsymbol{2}\}\}\} & = & \boldsymbol{2}
   && \pi_2([\boldsymbol{2},b])              & = & \bigcap\{x: \{x,\boldsymbol{2}\} \in \{\{\boldsymbol{1},\boldsymbol{2}\},\{b,\boldsymbol{2}\}\}\} & = & \emptyset      \\
 6. & \pi_1([\boldsymbol{1},\boldsymbol{2}]) & = & \bigcap\{x: \{x,\boldsymbol{1}\} \in \{\{\boldsymbol{1}\},\{\boldsymbol{2}\}\}\}                  & = & \boldsymbol{1} 
   && \pi_2([\boldsymbol{1},\boldsymbol{2}]) & = & \bigcap\{x: \{x,\boldsymbol{2}\} \in \{\{\boldsymbol{1}\},\{\boldsymbol{2}\}\}\}                  & = & \boldsymbol{2} \\
 7. & \pi_1([\boldsymbol{2},\boldsymbol{1}]) & = & \bigcap\{x: \{x,\boldsymbol{1}\} \in \{\{\boldsymbol{1},\boldsymbol{2}\}\}\}                      & = & \boldsymbol{2} 
   && \pi_2([\boldsymbol{2},\boldsymbol{1}]) & = & \bigcap\{x: \{x,\boldsymbol{2}\} \in \{\{\boldsymbol{1},\boldsymbol{2}\}\}\}                      & = & \boldsymbol{1} \\

\end{array} $

Der Projektionsoperator $\pi_1$ liefert nur im ersten Fall ein fehlerhaftes Ergebnis. Analog ist das Ergebnis von $\pi_2$ im fünften Fall falsch. Dies kann aber problemlos behoben werden:

$\begin{array}{lclclcl}

 \pi_1(p) & := & \bigcap(\{x: \{x,\boldsymbol{1}\} \in p\} \;\cup\; \{x: x \not\in \{\boldsymbol{1},\boldsymbol{2}\} \wedge \bigvee y: \{x,y\}\in p \wedge y = \boldsymbol{1}\}) \\ 
 \pi_2(p) & := & \bigcap(\{x: \{x,\boldsymbol{2}\} \in p\} \;\cup\; \{x: x \not\in \{\boldsymbol{1},\boldsymbol{2}\} \wedge \bigvee y: \{x,y\}\in p \wedge y = \boldsymbol{2}\})  

\end{array} $

Wiener (1914)

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: $a$ ist Element einer einelementigen Menge und $b$ ist Element einer zweielementigen Menge.

$\begin{array}{lclclcl}

 [a,b]    & := & \{\,\{\{a\}\},\{\emptyset,\{b\}\}\,\} \\ 
 \pi_1(p) & := & \bigcap\{x: \{\{x\}\} \in p\} \\ 
 \pi_2(p) & := & \bigcap\{x: \{\emptyset,\{x\}\} \in p\}

\end{array}$

Anmerkungen zur Definition von Wiener

Bei $\pi_1$ und $\pi_2$ handelt es sich tatsächlich um Mengenpaar-Operatoren:

$\begin{array}{lclclclcl}

 \pi_1([a,b]) & = & \bigcap\{x: \{\{x\}\} \in [a,b]\} \\           
              & = & \bigcap\{x: \{\{x\}\} \in  \{\,\{\{a\}\},\{\emptyset,\{b\}\}\,\}\,\} \\            
              & = & \bigcap\{a\} & \mbox{(da } a,b \mbox{ Mengen sind)}\\ 
              & = & a            & \mbox{(da } a \mbox{ eine Menge ist)} \\ 
 \pi_2([a,b]) & = & \bigcap\{x: \{\emptyset,\{x\}\} \in [a,b]\} \\  
              & = & \bigcap\{x: \{\emptyset,\{x\}\} \in  \{\,\{\{a\}\},\{\emptyset,\{b\}\}\,\}\,\} \\  
              & = & \bigcap\{b\} & \mbox{(da } a,b \mbox{ Mengen sind)}\\ 
              & = & b            & \mbox{(da } b \mbox{ eine Menge ist)}

\end{array}$

Die Definition von Wiener sorgt dafür, dass die Menge $\{\emptyset,\{b\}\}$ auch im Fall $b = \emptyset$ zweielementig ist. Für $\{\emptyset,b\}$ wäre dies dagegen nicht der Fall.

Geordnetes Paar mit Hilfe von Menge, Kuratowski (1921), S. 171

Kuratowski (1921)

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 $((a,b),(a))$ est une „paire ordonnée dont $a$ est le premier élément et $b$ est le second“.

Übersetzung:

Die Klasse $((a,b),(a))$ ist ein „geordnetes Paar, wobei $a$ das erste Element ist und $b$ das zweite“.

Moderne Schreibweise:

$\begin{array}{lclclcl}

 [a,b]    & := & \{\{a\},\{a,b\}\} \\
 \pi_1(p) & := & \bigcap\bigcap p   & = & \bigcup\bigcap p\\
 \pi_2(p) & := & \bigcap(\{x \in \bigcup p: \bigcup p \not= \bigcap p \rightarrow x \not\in \bigcap p\})
          &  = & \bigcup(\{x \in \bigcup p: \bigcup p \not= \bigcap p \rightarrow x \not\in \bigcap p\})\\

\end{array} $

Anmerkungen zur Definition von Kuratowski

Allgemein gilt für Mengen $a$:

$\begin{array}{lclclcl}

 \bigcap\{a\} & = & \bigcup\{a\} & =& a   \\

\end{array} $

Kuratowski-Paare haben folgende Eigenschaften, da $a$ und $b$ Mengen sind:

$\begin{array}{lclclcl}

 \bigcap[a,b] & = & \bigcap\{\{a\},\{a,b\}\} & =& \{a\}   \\
 \bigcup[a,b] & = & \bigcup\{\{a\},\{a,b\}\} & =& \{a,b\} \\

\end{array} $

Damit kann man zeigen, dass es sich bei $\pi_1$ und $\pi_2$ tatsächlich um Paaroperatoren handelt:

$\begin{array}{lcll}

 \pi_1([a,b]) & = & \bigcap\bigcap [a,b] \\
              & = & \bigcap\{a\} & \mbox{(anstelle von } \bigcap \mbox{ könnte man auch } \bigcup \mbox{ verwenden)} \\
              & = & a            & \mbox{(da } a \mbox{ eine Menge ist)} \\ 
 \pi_2([a,b]) & = & \bigcap(\{x \in \bigcup[a,b]: \bigcup[a,b] \not= \bigcap[a,b] \rightarrow x \not\in \bigcap [a,b]\}) \\
              & = & \bigcap(\{x \in \{a,b\}: \{a,b\} \not= \{a\} \rightarrow x \not\in \{a\}\}) \\
              & = & \bigcap\{b\}  & \mbox{(anstelle von } \bigcap \mbox{ könnte man auch } \bigcup \mbox{ verwenden)}  \\
              & = & b             & \mbox{(da } b \mbox{ eine Menge ist)}\\

\end{array} $

Alternativ könnte $\pi_2$ folgendermaßen definiert werden:

$\begin{array}{lclclcl}

 \pi_2(p) & := & \begin{cases} 
                    \bigcap\bigcup p                     & \mbox{falls } \bigcup p     = \bigcap p \\
                    \bigcap(\bigcup p\setminus\bigcap p) & \mbox{falls } \bigcup p \not= \bigcap p 
                  \end{cases} \\

\end{array} $

Die Bedingung $\bigcup p \not= \bigcap p$ bei der Definition von $\pi_2$ wird benötigt, damit $\pi_2$ auch für Paare der Art $[a,a]$ das korrekte zweite Element $a$ berechnet. Würde man diese Bedingung weglassen, würde $\pi_2([a,a]) = \emptyset$ gelten.

Nelson Goodman merkt an, dass sich die Definition von Kuratowski problemlos für beliebige $n$-Tutpel (wobei $n$ eine natürliche, d.h. endliche Zahl ist) verallgemeinern lässt. Er gibt allerdings kein allgemeines Konstruktionsprinzip, sondern nur folgendes Beispiel an:

$\begin{array}{lclclcl}

 [a,b,c] & := & \{\{\{a\}\},\{\{a,b\}\},\{\{a,b\},\{c\}\}\} \\

\end{array}$

Anmerkungen zim geordneten Paar, Quine (1940), S. 201 und S. 202

Quine (1940)

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“.)

$\begin{array}{lclclcl}

 [a,b]    & := & \{\,\{a\},\{\emptyset,b\}\,\} \\ 
 \pi_1(p) & := & \bigcap\{x: \{x\} \in p\} \\ 
 \pi_2(p) & := & \bigcap\{x: \{\emptyset,x\} \in p\}

\end{array}$

Quine (1986)

Quine definiert Mengenpaare wie folgt, wobei $0 := \emptyset$, $1 := 0 \cup \{0\} = \{\emptyset\}$ und $2 := 1 \cup \{1\} = \{\emptyset, \{\emptyset\}\}$:

$\begin{array}{rclr}

 [a,b]    & := & \{\{\{a\},1\},\{\{b\},2\}\} \\
 \pi_1(p) & := & \bigcap\{x: \{\{x\},1\} \in p\} \\ 
 \pi_2(p) & := & \bigcap\{x: \{\{x\},2\} \in p\}

\end{array}$

Anmerkungen zur Definition von Quine

Bei $\pi_1$ und $\pi_2$ handelt es sich tatsächlich um Paaroperatoren, da $a$ und $b$ Mengen sind:

$\begin{array}{rclr}

 \pi_1([a,b]) & = & \bigcap\{x: \{\{x\},1\} \in [a,b]\} & = &  \bigcap\{a\} & = & a \\ 
 \pi_2([a,b]) & = & \bigcap\{x: \{\{x\},2\} \in [a,b]\} & = &  \bigcap\{b\} & = & b

\end{array}$

In den 40er-Jahren hatte Willard Quine eine Klassenpaar-Definition entwickelt (siehe Abschnitt Weiterentwicklung des Paarbegriffs), die sich problemlos zu einer Definition von $n$-Tupeln ($n \in \mathbb N$) verallgemeinern lässt, wobei $n \in \omega$ eine natürliche Zahl ist. 1986 schlägt er die obige Mengenpaar-Definition vor, bei der es sich um eine leicht modifizierte Version der Hausdorff-Paare handelt. Diese ist zwar nicht für Unmengen definiert, lässt sich dafür aber nicht nur zu einer Definition von $n$-Tupeln verallgemeinern,

$[a_1,\ldots, a_n] \,\,:=\,\, \{\{\{a_1\},1\},\ldots,\{\{a_n\},n\}\} $

sondern sogar zu einer Definition von $o$-Tupeln, wobei $o \in \Omega$ eine beliebige Ordinalzahl ist. Diese werden gemäß dem Vorschlag von John von Neumann folgendermaßen definiert:

$0 := \{\}$

$1 := 0 \cup \{0\} = \{\{\}\}$

$2 := 1 \cup \{1\} = \{0, 1\} = \{\{\}, \{\{\}\}\}$

$3 := 2 \cup \{2\} = \{0, 1, 2\} = \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}\}$

$\vdots$

$\omega := \{0, 1, 2, \ldots\}$

$\omega+1 := \omega \cup \{\omega\}$

$\omega+2 := \omega+1 \cup \{\omega+1\}$

$\vdots$

Die Idee hinter Quines Definition ist, dass jedem Paar- bzw. Tupelelement seine Position im $o$-Tupel mit Hilfe einer Ordinalzahl $p$ zugeordnet wird. Dabei werden nicht die Mengenpaare $\{x,p\}$ gebildet, sondern die Mengenpaare $\{\{x\},p\}$, da es anderenfalls zu Mehrdeutigkeiten im Falle von $x \in \Omega$ kommen würde. Beim Mengenpaar $\{2,3\}$ wäre beispielsweise nicht klar, ob es sich um die Zahl $2$ an der Postion $3$ handelt oder um die Zahl $3$ an der Position $2$. Beim $\{\{2\},3\}$ ist dagegen eindeutig bestimmt, dass es sich um die Zahl $2$ an der Postion $3$ handelt.

Quine betont, dass $1 = \{0\} $ die einzige einelementige (John-von-Neumann-)Ordinalzahl ist. Also könnte es nur im Zusammenhang mit der Ordinalzahl $0$ zu Mehrdeutigkeiten kommen:

$\begin{array}{rclclcl}

 [a,0]        & = & \{\{\{a\},1\},\{\{0\},2\}\} & = & \{\{\{a\},1\},\{1,2\}\} \\
 [0,b]        & = & \{\{\{0\},1\},\{\{b\},2\}\} & = & \{\{1,1\},\{\{b\},2\}\} & = & \{\{1\},\{\{b\},2\}\}
\end{array} 

$

Allerdings liefern die Projektionsoperatoren auch in diesen Fällen das korrekte Ergebnis, da $2 = \{0,1\}$ zweielementig ist:

$\begin{array}{rclclcl}

 \pi_1([a,0]) & = & \bigcap\{x: \{\{x\},1\} \in \{\{\{a\}, 1\}, \{\{0\},2\}\} & = & \bigcap\{a\} & = & a \\
 \pi_1([0,b]) & = & \bigcap\{x: \{\{x\},1\} \in \{\{\{0\}, 1\}, \{\{b\},2\}\} & = & \bigcap\{0\} & = & 0 \\
 \pi_2([a,0]) & = & \bigcap\{x: \{\{x\},2\} \in \{\{\{a\}, 1\}, \{\{0\},2\}\} & = & \bigcap\{0\} & = & 0 \\
 \pi_2([0,b]) & = & \bigcap\{x: \{\{x\},2\} \in \{\{\{0\}, 1\}, \{\{b\},2\}\} & = & \bigcap\{b\} & = & b \\
\end{array} 

$

Klassenpaare

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 $a$ und $b$ Elemente von ein- und/oder zweielementigen Mengen sind. Unmengen können jedoch – gemäß ihrer Definition – nicht Elemente von irgendwelchen Mengen sein:

$\bigwedge u: \rm{UMg}(u) \rightarrow \{u\} = \mathcal{V}$ (siehe Definition von $n$-elementigen Mengen)

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 $\{u\}$ für Unmengen anders definiert werden sollte (wie z.B. $\{u\} = \emptyset$; siehe Alternative Definition einer einelementigen Menge), wäre nichts gewonnen. Da sich Klassen, die Unmengen als Elemente enthalten, für verschiedene Unmengen nicht voneinander unterscheiden, unterscheiden sich auch die entsprechenden Mengenpaar-Definitionen auch nicht.

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

$\bigwedge a, b: [a,b] = [b,a] \leftrightarrow a = b$

für Mengenpaare uneingeschränkt gültig, da in diesem Fall $\bigwedge$ als „Für alle Mengen innerhalb des Mengenuniversums“ interpretiert wird. In einem klassenbasierten Axiomen-System (wie es z.B. der Neumann-Bernays-Gödel-Mengenlehre zu Grunde liegt) wird $\bigwedge$ jedoch als „Für alle Klassen, d.h. für alle Mengen und Unmengen innerhalb des Klassenuniversums“ interpretiert. Für die bislang definierten Mengenpaare gilt in derartigen Systemen lediglich:

$\bigwedge a, b: \rm{Mg}(a) \wedge \rm{Mg}(b) \rightarrow ([a,b] = [b,a] \leftrightarrow a = b)$

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 $\Omega$ mit Addition $+$ als $2$-Tupel, d.h. als geordnetes Paar $[\Omega, +]$ definieren will, reicht das eingeschränkte Paaraxiom nicht mehr aus. Die Klasse der Ordinalzahlen $\Omega$ ist eine Unmenge.

Quine (1945)

Zunächst wird zur Abkürzung der nachfolgenden Definitionen eine Hilfsoperationen eingeführt (die allerdings jederzeit durch Textersetzung eliminiert werden kann):

$\begin{array}{lclcl}

 \theta(z) & := &  \{v: v \in z \wedge v \not\in \N\} \,\cup\, \{v+1: v \in z \wedge v \in \N\} & = & (z \setminus \N) \cup \{n+1 : n \in (z \cap \N) \}

\end{array}$

Mit Hilfe der Operation $\theta$ definiert Willard Quine geordnete Paare wie folgt:

$\begin{array}{rclcl}

 [a,b]    & := & \{\theta(x):x\in a\} \cup \{\theta(x)\cup \{0\}:x\in b\}\\ 
 \pi_1(p) & := & \{x: \theta(x) \in p\}  \\ 
 \pi_2(p) & := & \{x: \theta(x)\cup \{0\} \in p\} 

\end{array}$

Anmerkungen zu Quines Definition von 1945

Bei $\pi_1$ und $\pi_2$ handelt es sich tatsächlich um Paaroperatoren:

$\begin{array}{rclcl}

 \pi_1([a,b]) & = & \{x: \theta(x) \in [a,b]\} & = & a \\ 
 \pi_2([a,b]) & = & \{x: \theta(x)\cup \{0\} \in [a,b]\} & = & b

\end{array}$

Rosser-Paare

1953 übernimmt J. Barkley Rosser die Definition von Quine. Die oben angegebenen Projektionsoperatoren stammen von ihm. Quine hat nur deren Existenz postuliert (siehe nachfolgenden Abschnitt).

Die Idee hinter Quines Definition

Um Paare $[a,b]$ auf dieselbe Ebene zu legen wie ihre Elemente $a$ und $b$, fügt Willard Quine nicht $a$ und $b$ selbst, sondern deren Elemente in die zugehörige Paarmenge ein. Dazu definiert er zunächst die Operation $\theta(z)$ (er spricht nicht von „operator“ sondern von „notion“), die die Elemente der Menge $z$ leicht modifiziert, indem sie alle natürlichen Zahlen, die in $z$ enthalten sind, um eins erhöht. Man beachte, dass es sich bei $\theta(z)$ um keine Funktion handelt, da Funktionen erst in einem zweiten Schritt mit Hilfe von geordneten Paaren definiert werden. Es handelt sich vielmehr um eine abkürzende Schreibweise, die jederzeit durch Ersetzung eliminiert werden kann.

$\theta(z)$ hat laut Quine folgende Eigenschaften:

1. Es gibt kein $z$ für das $0 \in \theta(z)$ gilt; $0$ ist dabei die natürliche Zahl „Null“.
2. Aus $\theta(z)$ lässt sich $z$ eindeutig ermitteln.
3. $z$ und $\theta(z)$ liegen auf derselben Ebene in der Typhierachie.

Da der Nachfolger einer jeden natürlichen Zahl ungleich $0$ ist, enthält $\theta(z)$ mit Sicherheit nicht die Zahl $0$, erfüllt also die erste Bedingung. Die zweite Bedingung ist ebenfalls erfüllt, da sich $z$ problemlos aus $\theta(z)$ ableiten lässt. Man braucht nur jede natürliche Zahl in $\theta(z)$ um eins zu veringern.

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 $0$, die Nachfolgeroperation $n+1$ und die Menge aller natürlichen Zahlen $\mathbb N$ (er wählt in beiden Fällen andere Symbole) induktiv ein. Er macht dies so geschickt, dass eine natürliche Zahl $n$ und ihr Nachfolger $n+1$ – bezüglich der vom ihm definierten Typhierarchie – stets vom selben Typ sind, d.h. stets auf derselben Ebene liegen.

Quine-Paare (gemäß der Definition von 1945) sind Klassenpaare

Quines Idee, nicht die Paarelemente $a$ und $b$ selbst, sondern deren Elemente in der Paarklasse zu „speichern“, hat insbesondere zur Folge, dass auch Unmengen als Paarelemente fungieren können. Unmengen enhalten zwar ausschließlich Elemente, können selbst aber keine Elemente sein. Das heißt, Unmengen können nur rechts vom Elementzeichen $\in$ vorkommen. Und das ist bei Quines Definition gegeben: $a$ und $b$ stehen nur rechts vom Element-Operator.

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 – Klassenpaare.

Dabei ist es vollkommen unwichtig, auf welche Art die natürlichen Zahlen, die im Operator $\theta$ verwendet werden, repräsentiert werden. Heute verwendet man überlicherweise die Repräsentation, die John von Neumann vorgeschlagen hat (siehe Abschnitt „Anmerkungen zur Definition von Quine“). Und es ist auch unwichtig, ob die Bedingung „$z$ und $\theta(z)$ liegen auf derselben Ebene in der Typhierachie“ erfüllt ist oder nicht. Quine-Paare können auch in typfreien Mengenlehre-Systemen als Klassenpaare fungieren.

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. Für jedes Objekt $o$ gilt folgende Beziehung:

$\begin{array}{rcl}

 o &  = & \{\theta(z): \theta(z) \in o\} \cup  \{\theta(z)\cup \{0\}: \theta(z) \cup \{0\} \in o\} \\
   &  = & \{\theta(z): z\in \{z: \theta(z) \in o\}\} \cup  \{\theta(z)\cup \{0\}: z\in \{z: \theta(z) \cup \{0\} \in o\}\} \\
   &  = & [\,\{z: \theta(z) \in o\}, \{z: \theta(z) \cup \{0\} \in o\}\,]
\end{array} 

$

Beispielsweise gilt, wenn man Quines Definition $0 := \{\emptyset\}$ zugrunde legt:

$\emptyset$	$=$	$[\emptyset,\emptyset]$
$0$	$=$	$[0,\emptyset]$	($0 = \{\emptyset\} = [\{\emptyset\},\emptyset] = [0,\emptyset]$, da $\theta(\emptyset) = \emptyset \in \{\emptyset\}$)
$\{0\}$	$=$	$[\emptyset, 0]$	($\{0\} = \{\{\emptyset\}\} =[\emptyset, \{\emptyset\}] = [\emptyset, 0]$, da $\theta(\emptyset) \cup 0 = \emptyset \cup \{\emptyset\} = \{\emptyset\} \in \{\{\emptyset\}\}$)

Quine merkt dazu an, dass alles eins wird:

Indeed, everything comes to be at once an ordered pair, a class, and a relation.

Ob das eine wirklich vorteilhafte Zusatzeigenschaft dieser Paardefinition ist, sei dahingestellt.

Morse (1965)

Morse definiert geordnete Paare in zwei Schritten.

Zunächst definiert er die klassischen Kuratowski-Paare (d.h. Mengenpaare) samt zugehörigem kartesischem Produkt und einem speziellen Operator $s(\cdot)$:

$\begin{array}{rclp}

  (x,y)       & := & \{\{x\},\{x,y\}\}                       & \text{(2.56.0)}\\
   a \times b & := & \{(x,y):x \in a, y \in b\}              & \text{(S. 60; eine explizite Definition fehlt)} \\
   s(a)       & := & \{\emptyset \} \cup \{\{x\} : x \in a\} & \text{(2.57.0)}\\
\end{array} 

$

Im zweiten Schritt definiert er die eigentlichen Klassenpaare und die zugehörigen Projektionsoperatoren:

$\begin{array}{rclp}

 [a,b]    & := & (\{0\} \times s(a)) \cup (\{\{0\}\}\times s(b))   & \text{(2.57.1)}\\
          & = & \{(0,x): x \in s(a) \} \cup \{(1,x): x \in s(b) \} & \text{(2.131.0, 2.92.6,}\; 1 := \{0\}\text{)}\\
 \pi_1(p) & := & \bigcup \{x: (0,x) \in p\}                        & \text{(2.57.6, 2.1.28, 2.56.4, 2.33.2)}\\
 \pi_2(p) & := & \bigcup \{x: (1,x) \in p\}                        & \text{(2.57.9, 2.1.28, 2.56.4, 2.33.2)}\\

\end{array}$

Anmerkungen zur Definition von Morse

Bei $\pi_1$ und $\pi_2$ handelt es sich tatsächlich um Paaroperatoren:

$\begin{array}{rclp}

 \pi_1([a,b]) & = & \bigcup \{x: (0,x) \in [a,b]\} \\
              & = & \bigcup \{x: (0,x) \in \{(0,x): x \in s(a) \}\} \\
              & = & \bigcup \{x \in s(a) \}\} \\
              & = & \bigcup s(a) \\
              & = & a                                                 & \text{(2.61.1)} \\ 
 \pi_2([a,b]) & = & \bigcup \{x: (1,x) \in [a,b]\} \\
              & = & \bigcup \{x: (1,x) \in \{(1,x): x \in s(b) \}\} \\
              & = & \bigcup \{x \in s(b) \}\} \\
              & = & \bigcup s(b) \\
              & = & b                                                 & \text{(2.61.1)}  

\end{array}$

Das Paaraxiom

Morses Definition erfüllt wie Quines Definition das Paaraxiom für alle Klassen (siehe Morse (1965), 2.61.2), d.h. für Mengen und für Unmengen, da die Paarelemente $a$ und $b$ nur rechts vom Elementsymbol $\in$ vorkommen. Kuratowski-Paare sind zwar nur für Mengen definiert, aber das zugehörige kartesische Produkt ist auch für Klassen definiert (beispielsweise ist $\Omega \times \Omega = \{(o_1,o_2): o_1,o_2\in\Omega\}$ die Klasse aller Ordinalzahlpaare). Und auch der Operator $s$ ist für beliebige Klassen definiert.

Morses Symbole

Morse verwendet etwas andere Symbole, als zuvor angegeben:

• Anstelle von $(\cdot,\cdot)$ und $[\cdot,\cdot]$ notiert er $(\cdot _´ \cdot)$ und $(\cdot,\cdot)$.
• Die zugehörigen kartesischen Produkte notiert er jeweils zwei Kommas $(\cdot {_´}{_´} \cdot)$ und $(\cdot,\!,\cdot)$.
• Die runden Klammern lässt er bei Paaren und kartesischen Produkten teilweise weg.
• Die Projektionsoperatoren heißen bei ihm $\rm{crd}'$ und $\rm{crd}$.
• Die große Vereinigung bezeichnet er mit $\raise.45ex\bigtriangledown$, den großen Durchschnitt mit $\bigtriangleup$.

Die Idee hinter Morses Definition

Morse hat erkannt, dass sich das kartesische Produkt von klassischen Mengenpaaren zur Definition von geordneten Klassenpaaren eignet. (Er spricht – wie einige andere Mathematiker auch – von Wiener-Paaren, meint und verwendet jedoch Kuratowski-Paare.) Während $(a,b)$ nur für Mengen $a$ und $b$ definiert ist, ist $a \times b$ auch für Klassen definiert. Ein Problem ist allerdings, dass stets $a \times \emptyset = \emptyset \times b = \emptyset$ gilt. Das heißt, das kartesische Produkt erfüllt das Paaraxiom für die leere Menge nicht.

J. W. Weihe, ein Ph.D.-Student von Morse, schlägt laut Morse 1949 vor, die Potenzmengen von $a$ und $b$ mittels des kartesischen Produktes zu verknüpfen, da die Potenzmenge nie leer ist:

$\begin{array}{rcl}

 [a,b] & := & \mathcal P(a) \times \mathcal P(b) 
 \end{array}

$

1965 haben Morse und D. C. Peterson diese Idee verfeinert und anstelle von $\mathcal P(a)$ und $\mathcal P(b)$ die Klassen $s(a)$ und $s(b)$ verwendet. Der Operator $s$ ersetzt jedes Element $x$ der Klasse $a$ bzw. $b$ durch die einelementige Menge $\{x\}$. Damit $s(a)$ und $s(b)$ nicht leer sind, fügt Morse außerdem die leere Menge als Element hinzu. Die leere Menge ist das einzige nicht-einelementige Element von $s(a)$ und $s(b)$. Daher können $a$ und $b$ stets aus $s(a)$ und $s(b)$ rekonstruiert werden:

$\begin{array}{lclp}

 \bigcup s(a) & = & a & \text{(2.60.1)}\\ 
 \bigcup s(b) & = & b & \text{(2.60.1)}\\ 
 \end{array}

$

Einheit von Logik und Mengenlehre

In der obigen Definition und in den nachfolgenden Erklärungen werden jeweils in Klammern die Nummern bzw. Seiten der zugehörigen Definitionen von Morse (1965) angegeben. Der Grund ist, dass Anthony P. Morse Logik und Mengenlehre als Einheit auffasst und daher seine Formeln etwas schwerer zu lesen sind. Jede von Morse verwendete Formel kann sowohl prädikatenlogisch als auch mengentheoretisch interpretiert werden. Beispielsweise kann das Symbol $a \wedge b$ sowohl als logische Konjunktion der Aussagen $a$ und $b$, als auch als Durchschnitt der Klassen $a$ und $b$ interpretiert werden.

Auf den ersten Blick stimmen daher die obigen Definitionen nicht mit den Definitionen von Morse überein. Morse definiert $s(a)$ beispielsweise folgendermaßen (er verwendet überdies $ss$ an Stelle von $s$):

$\begin{array}{rclp}

 s(a) \equiv (\rm{sng}\, 0 \cup \bigvee x(x \in a \wedge \rm{sng}\,\rm{sng}\,x)) & \text{(2.57.0)}

\end{array}$

Dass diese Definition von Morse mit der oben angegeben Definition übereistimmt, sieht man folgendermaßen:

Das Symbol $\equiv$ bedeutet bei Morse „definitionsgemäß äquivaltent zu“ (“Foreword”, S. xii). Es kann aber auch als $=$, d.h. als „(definitionsgemäß) gleich zu“ aufgefasst werden (2.4, “axiom of definition for set theory”), wobei $=$ für Klassen auf die übliche Weise definiert wird:

$\begin{array}{rp}

  (x=y)  \equiv ((x \subset y)\wedge(y \subset x)) & \text{(2.3.1)}

\end{array}$

Für eine Menge $x$ (d.h. $x \in U$, wobei $U$ bei Morse die Allklasse ist) gilt $\rm{sng}\,x = \{x\}$ (2.55.0, 2.54.1). $\rm{sng}\,x$ bezeichnet also die einelementige Menge. Das heißt, Morses Definition ist äquivalent zu:

$\begin{array}{rclp}

 s(a) = \{0\} \cup \bigvee x(x \in a \wedge \{\{x\}\})

\end{array}$

Die Zusammenfassung aller Mengen $x$, die das Prädikat $ux$ erfüllen, definiert Morse folgendermaßen:

$\begin{array}{rclp}

  \{x: ux\} & \equiv & {\sf{E}}x\,ux & \rm{(2.33.2)} \\
            & \equiv & \bigvee x(0 \in ux \wedge \rm{sng}\,x) & \text{(2.33.0)} \\
            & \equiv & \bigvee x(ux \wedge \{x\})             & \text{(2.5.0, 2.55.0, 2.54.1)} \\

\end{array}$

Die Klasse aller $x$, die $ux$ erfüllen, ist laut Morse also die große Vereinigung (vgl. 2.1.28, 2.1.29) aller einelementigen Mengen $\{x\}$, für die $x$ zusätzlich die Bedingung $ux$ erfüllt. Entsprechend ist $\bigvee x(x \in a \wedge \{\{x\}\})$ die Vereinigung aller $\{\{x\}\}$, für die $x$ die Bedingung $x \in a$ erfüllt. (Eine explizite Definition für diese Art der Verallgemeinerung des Mengenoperators $\{\cdot:\cdot\}$ hat Morse allerdings nicht angegeben.) Es gilt also:

$\begin{array}{l}

 \bigvee x(x \in a \wedge \{\{x\}\}) = \{\{x\} : x \in a\} \\

\end{array}$

und damit nicht nur in moderner Schreibweise, sondern auch in der Notation von Morse:

$\begin{array}{l}

 s(a) = \{\emptyset \} \cup \{\{x\} : x \in a\}

\end{array}$

Schmidt (1966)

Jürgen Schmidt definiert seine Klassenpaare „in Anlehnung an Quine“. Er kombiniert die Definition von Wiener mit der Idee von Quine, nicht $a$ und $b$, sondern deren Elemente im Paar zu vereinen:

$\begin{array}{rclclcl}

 [a,b] & = & \{\,\{\{x\}\}: x \in a\,\} \,\cup\, \{\,\mathcal P(\{x\}): x \in b\,\} 
       & = & \{\,\{\{x\}\}: x \in a\,\} \,\cup\, \{\,\{\emptyset, \{x\}\}: x \in b\,\} \\
 \pi_1(p) & = & \{x: \{\{x\}\} \in p\} \\
 \pi_2(p) & = & \{x: \{\emptyset,\{x\}\} \in p\} \\

\end{array}$

Anmerkungen zur Definition von Schmidt

Bei $\pi_1$ und $\pi_2$ handelt es sich tatsächlich um Paaroperatoren:

$\begin{array}{rclclcl}

 \pi_1([a,b]) & = & \{x: \{\{x\}\} \in [a,b]\} \\
              & = & \{x: \{\{x\}\} \in (\{\,\{\{x\}\}: x \in a\,\} \,\cup\, \{\,\{\emptyset, \{x\}\}: x \in b\,\})\,\} \\
              & = & \{x: \{\{x\}\} \in \{\,\{\{x\}\}: x \in a\,\} \,\}\\
              & = & \{x: x \in a\} \\
              & = & a \\ 
 \pi_2([a,b]) & = & \{x: \{\emptyset,\{x\}\} \in [a,b]\} \\
              & = & \{x: \{\emptyset,\{x\}\} \in (\{\,\{\{x\}\}: x \in a\,\} \,\cup\, \{\,\{\emptyset, \{x\}\}: x \in b\,\})\;\} \\
              & = & \{x: \{\emptyset,\{x\}\} \in \{\,\{\emptyset, \{x\}\}: x \in b\,\}\,\} \\
              & = & \{x: x \in b\}  \\
              & = & b \\

\end{array}$

Man beachte, dass auch in der Definition von Schmidt $a$ und $b$ nur rechts von $\in$ stehen. Für Schmidt-Paare gilt daher das Paaraxiom ebenso wie für Quine- und Morse-Paare uneingeschränkt sowohl für Mengen als auch für Unmengen.

Oberschelp und Todt (1981)

TO BE DONE

Paare und Tupel in der Informatik

Sowohl in der Mathematik als auch in der Informatik ist es von zentraler Bedeutung, unterschiedliche Objekte in „Containern“ zusammenzufassen.

In der Mathematik wird i. Allg. folgender Weg gewählt:

• Als „Basis-Container“ werden Mengen oder Klassen benutzt. Wie diese erzeugt werden, wird axiomatisch festgelegt. In diesen Containern sind die Elemente ungeordnet und jeweils höchstens einmal enthalten.
• In einem zweiten Schritt werden „geordnete Paare“ definiert.
• Auf Basis der geordneten Paar können in einem dritten Schritt Tupel definiert werden: In diesen Containern sind die Elemente geordnet und evtl. auch mehrfach enthalten.

In der Informatik wird dagegen i. Allg. der umgekehrte Weg gewählt:

• Als „Basis-Container“ werden geordnete Paare oder Tupel bzw. Arrays, die als Verallgemeinerung des Paar-Begriffs aufgefasst werden können, benutzt. Wie diese erzeugt werden können, wird algorithmisch festgelegt. In diesen Containern sind die Elemente geordnet und evtl. auch mehrfach enthalten. Beispiele für derartige Basis-Container sind:
  • LISP: geordnete Paare („CONS-Zellen“, siehe den nachfolgenden Abschnitt „McCarthy (1960)“) sowie aus CONS-Zellen gebildete Listen (siehe den Absatz „Ursprung und Varianten der Vektornotation“ im Dokument Tupel); Konstruktoren: (a . b), (CONS A B)
  • C: Verbünde (record, Tupel; Schlüsselwort: struct) und Arrays
  • C++: zu Objekten verallgemeinerte Verbünde (Schlüsselwörter: struct, class) und Arrays
  • PASCAL: Verbünde (Schlüsselwort: RECORD) und Arrays
  • JavaScript: Objekte (Konstruktor: {a: Wert1, b: Wert2, ...}) und Arrays (Konstruktor: [a, b, c, ...])
  • etc.
• In einem zweiten Schritt können Mengen und auch Multimengen (das sind Container ohne Ordnung, in denen ein Element mehrfach enthalten sein kann) algorithmisch mit Hilfe der durch dies Sprache vorgegebenen Datenstrukturen definiert werden.

Eine Ausnahme bildet die Sprache SQL. Hier sind Tupel und Mengen (genauer: Multimengen) die zentralen Datenstrukturen zur Speicherung von Daten. In diesem Fall werden weder Mengen mit Hilfe von Tupeln noch Tupel mit Hilfe von Mengen nachgebildet.

Tupel als Mengen- oder Klassenpaare (Kowarschick (1991))

Der Tupelbegiff ist eine Verallgemeinerung des Paarbegriffs, der es ermöglicht, beliebig viele Elemente in einer geordneten Liste zusmmenzufassen. Wenn bereits der Tupelbegriff eingeführt wurde, kann man anschließend eine altenative Definition für geordnete Paare angeben:

$[a,b] := (a,b)$ wobei $(a,b)$ ein $2$-Tupel ist.

Diese Definition klingt wie ein „circulus vitiosus“, da Tupel häufig mit Hilfe von Paaren definiert werden. Es liegt allerdings kein unzulässiger Ringschluss vor, da es für die Definition von Relationen, Funktionen etc. nur darauf ankommt, dass der gewählte Paaroperator das Paaraxiom erfüllt. Wie genau der Paaroperator definiert wurde, ist dabei ohne Belang.

Beispielsweise kann man $n$-Tupel – wie von John McCarthy für die Programmiersprache LISP vorgeschlagen – folgendermaßen definieren:

$0$-Tupel: $():=\emptyset$

$1$-Tupel: $(a):= [a, \emptyset]$

$2$-Tupel: $(a,b) := [a, [b, \emptyset]]$

$3$-Tupel: $(a,b,c) := [a, [b, [c, \emptyset]]]$

etc.

Kowarschick schlägt daher 1991 folgende induktive Definition für $n$-Tupel vor:

$0$-Tupel: $():=\emptyset$

$n$-Tupel: $(a_1,\ldots,a_n) := [a_1, (a_2,\ldots,a_n)]$ für $n > 0$

Dabei kann $[\cdot,\cdot]$ ein beliebiger Paaroperator sein (Kowarschick verwendet Schmidt-Paare). Falls es sich um einen Klassenpaar-Operator handelt, sind die $n$-Tupel ebenfalls sowohl für Mengen als auch für Unmengen definiert.

Insbesondere wird auf diese Weise ein neuer Paaroperator definiert: der $2$-Tupel-Operator $(\cdot,\cdot)$. Er unterscheidet sich i.Allg. vom Paaroperator $[\cdot,\cdot]$, da $(a,b) = [a,[b,\emptyset]] \not= [a,b]$ (zumindest sofern der Paar-Operator so definiert wurde, dass $[b, \emptyset] \not= b$; dies ist bei den in diesem Artikel vorgestellten Paar-Operatoren nur bei den Quine-1945-Paaren nicht der Fall). Aber der $2$-Tupel-Operator erfüllt das Paaraxiom. Und dies ist – wie Dipert betont hat – die einzige Eigenschaft, auf die es beim Paarbegriff ankommt.

Daher geht man bei der Formalisierung der Mathematik sinnvollerweise folgendermaßen vor:

Entweder, man wählt eine Paar-Definition, die sich problemlos für beliebige Tupel verallgemeinern lässt (dies ist z.B. bei Quine- oder Morse-Paaren der Fall), oder man beschreitet folgenden Weg:

1. Man wählt eine beliebige Definition für Klassen- bzw. Mengenpaare (je nach dem benutzten Axiomensystem) zur Definition des Paaroperators $[\cdot,\cdot]$.
2. Man definiert $n$-Tupel (a_1,...,a_n) mit Hilfe dieser Paardefinition.
3. Man ignoriert ab nun den ursprünglichen Paaroperator $[.,.]$ und verwendet stattdessen den Paaroperator $(.,.)$ oder – allgemeiner – die Tupeloperatoren $(.,\cdots,.)$, um weitere Grundbegriffe wie Kartesisches Produkt, Relation, Funktion etc. zu definieren.

Dass dieser Weg gangbar ist, hat Morse gezeigt, dessen Paardefinition ebenfalls zweistufig ist.

Siehe auch

• Projektion
• Scott, McCarty (2008): Dana Scott und Dominic McCarty; Reconsidering Ordered Pairs; in: The Bulletin of Symbolic Logic; Band: 14; Nummer: 3; Seite(n): 150-153; Verlag: Association for Symbolic Logic; Web-Link; 2008; Quellengüte: 5 (Artikel)