Geordnetes Paar

Paardarstellungen für Mengen und Urelemente

• ${\displaystyle (a,b)_{\mathrm {K} }:=\{\{a\},\{a,b\}\}}$, gängigste Darstellung nach Kazimierz Kuratowski (1921).^[2] Eine Variante gibt die Definition ${\displaystyle (a,b)_{\text{reverse}}:=\{\{b\},\{a,b\}\}}$

– in einer Typentheorie nach Bertrand Russell möglich bei gleichem Typ von a und b.^[3]

– nicht möglich, wenn a oder b eine echte Klasse ist.

• ${\displaystyle (a,b)_{\text{short}}:=\{a,\{a,b\}\}}$, so genannte kurze Darstellung

– nicht erlaubt in einer Typentheorie nach Bertrand Russell.

• ${\displaystyle (a,b)_{\text{EM}}:=\{\{\emptyset ,\{a\}\},\{b\}\}}$, zum Tupel-Begriff generalisierbare Darstellung^[4]
• ${\displaystyle (a,b)_{\text{W}}:=\{\{\emptyset ,\{a\}\},\{\{b\}\}\}}$, nach Norbert Wiener (1914)^[5]

– in einer Typentheorie nach Bertrand Russell möglich bei gleichem Typ von a und b, wenn als Leermenge die der nächsthöheren Typstufe gewählt wird.^[6]

• ${\displaystyle (a,b)_{\text{H}}:=\{\{a,{\boldsymbol {1}}\},\{b,{\boldsymbol {2}}\}\}}$, wobei ${\displaystyle {\boldsymbol {1}}}$ und ${\displaystyle {\boldsymbol {2}}}$ voneinander verschiedene Objekte sind, beide auch verschieden von ${\displaystyle a}$ und ${\displaystyle b}$, nach Felix Hausdorff (1914)^[7]

Klassenpaare nach Schmidt

${\displaystyle (a,b):=\{\{\{x\}\}\,{\boldsymbol {\mid }}\,x\in a\}\;{\boldsymbol {\cup }}\;\{\{\emptyset ,\{x\}\}\,{\boldsymbol {\mid }}\,x\in b\}}$, nach Jürgen Schmidt (1966)^[8] in Anlehnung an Quine. Eine an die Darstellung von Wiener angelehnte Variante gibt die Definition ${\displaystyle (a,b):=\{\{\emptyset ,\{x\}\}\,{\boldsymbol {\mid }}\,x\in a\}\;{\boldsymbol {\cup }}\;\{\{\{x\}\}\,{\boldsymbol {\mid }}\,x\in b\}}$

– ${\displaystyle a,b}$ können hier auch echte Klassen sein, aber keine 'echten' Urelemente (d. h. von ∅ verschiedene Urelemente).

Der Vergleich der Darstellung von Wiener mit der Variante nach Schmidt zeigt, wie aus einer Paardarstellung ${\displaystyle (a,b)}$ für Mengen und ('echte') Urelemente eine Paardarstellung ${\displaystyle (a,b)_{\text{Schmidt}}}$ für Mengen und echte Klassen erzeugt werden kann:

${\displaystyle (a,b)_{\text{Schmidt}}:=\bigcup _{x\in a}\bigcup _{y\in b}(x,y)}$

Falls a und b Mengen (keine echten Klassen) sind, lässt sich der obige Ausdruck auch wie folgt darstellen:

${\displaystyle (a,b)_{\text{Schmidt}}=\bigcup \{(x,y)|x\in a\land y\in b\}=\bigcup \;(a\times b)}$ ^[9]

Das geschilderte Verfahren lässt sich auch einseitig nur links oder nur rechts anwenden. Dabei könnte genauso gut auch eine andere Paardarstellung wie die von Kuratowski zugrunde gelegt werden.

Paardarstellung nach Quine–Rosser

Bei der Paardarstellung nach Kuratowski liegen die Koordinaten der Paare in der Enthaltenseinsrelation zwei Stufen unter den Paaren (${\displaystyle a,b\in ^{2}(a,b)}$), bei Wiener sind es gar drei Stufen (${\displaystyle a,b\in ^{3}(a,b)}$). Mit dem Schmidtschen Verfahren wird dieser Abstand lediglich um 1 reduziert.

Rosser hat 1953 eine Paardarstellung nach Quine verwendet,^[10] welche eine mengentheoretische Darstellung (oder auch axiomatische Definition) der natürlichen Zahlen ${\displaystyle \mathbb {N} }$ voraussetzt. Dafür befinden sich die Paare auf derselben Stufe wie ihre Koordinaten. Dazu benötigen wir zunächst folgende Hilfsdefinition:^[11]

${\displaystyle \sigma (x):=\left\{{\begin{matrix}x,&{\text{für }}x\not \in \mathbb {N} \\x+1,&{\text{für }}x\in \mathbb {N} .\end{matrix}}\right.}$

${\displaystyle \sigma }$ inkrementiert das Argument (um 1), wenn es eine natürliche Zahl ist, und belässt es ansonsten wie es ist – die Zahl 0 tritt nicht als Funktionswert von ${\displaystyle \sigma }$ auf. Weiter setzen wir:

${\displaystyle \varphi (x):=\sigma [x]=\{\sigma (\alpha )|\alpha \in x\}=(x\setminus \mathbb {N} )\cup \{n+1|n\in (x\cap \mathbb {N} )\}.}$

Dabei ist ${\displaystyle x\setminus \mathbb {N} }$ die Menge der Elemente von ${\displaystyle x}$ die nicht in ${\displaystyle \mathbb {N} }$ liegen. ${\displaystyle \varphi (x)}$ bezeichnet das Bild einer Menge ${\displaystyle x}$ unter der Abbildung ${\displaystyle \sigma }$, und wird manchmal auch mit ${\displaystyle \sigma ''x}$ bezeichnet. Die Anwendung dieser Funktion auf eine Menge inkrementiert alle in ihr enthaltenen natürlichen Zahlen. Insbesondere enthält ${\displaystyle \varphi (x)}$ niemels die Zahl 0, für beliebige Mengen ${\displaystyle x,y}$ gilt also

${\displaystyle \varphi (x)\not =\{0\}\cup \varphi (y).}$

Weiter wird definiert

${\displaystyle \psi (x):=\sigma [x]\cup \{0\}=\varphi (x)\cup \{0\}}$.

Damit enthält ${\displaystyle \psi (x)}$ stets die Zahl 0 als Element.

Schließlich definieren wir das geordnete Paare als die folgende disjunkte Vereinigung:

${\displaystyle (A,B)_{QR}:=\varphi [A]\cup \psi [B]=\{\varphi (a)|a\in A\}\cup \{\varphi (b)\cup \{0\}|b\in B\}.}$

(in anderer Notation auch ${\displaystyle \varphi ''A\cup \psi ''B}$).

Wenn man alle Elemente des so definierten Paares extrahiert, die nicht die 0 enthalten, und ${\displaystyle \varphi }$ umkehrt, erhält man A. In derselben Weise kann B aus den Elementen des Paares, die ihrerseits die 0 enthalten, zurückgewonnen werden.^[12]

Die Definition setzt die abzählbar unendliche Menge der natürlichen Zahlen voraus. Das ist in ZF und NF der Fall, nicht aber in NFU. J. Barkley Rosser konnte zeigen, dass die Existenz solcher geordneter Paare auf derselben Stufe wie ihre Koordinaten das Unendlichkeitsaxiom voraussetzt. Für eine ausführliche Diskussion geordneter Paare im Rahmen von Quine-Menegentheorien siehe Holmes (1998).^[13]