Geordnetes Paar

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

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

Umfang: 5 (wesentliche Fakten vorhanden)

Quellenangaben: 5 (vollständig vorhanden)

Quellenarten: 5 (ausgezeichnet)

Konformität: 5 (ausgezeichnet)

Definition (Kowarschick)

Der Term $[a,b]$, wobei $a$ und $b$ zwei Mengen oder Klassen sind, heißt geordnetes Paar oder $2$-Tupel, wenn für den Operator $[\cdot,\cdot]$ das Peanosche Paaraxiom erfüllt ist:

$\forall a, b, c, d: [a,b] = [c,d] \leftrightarrow a = c \wedge b = d$

Projektion

Für geordnete Paare werden folgende beiden Projektions-Operationen definiert, um das erste bzw. das zweite Element des Paars zu extrahieren:

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

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

Mengen-, Unmengen- und Klassenpaare

Ein Paar $[a,b]$ heißt Mengenpaar, wenn $a$ und $b$ mit Sicherheit zwei Mengen sind ($\rm{Mg}(a) \wedge \rm{Mg}(b)$, vgl. Klasse).

Wenn $a$ oder $b$ eine Unmenge ist ($\rm{UMg}(a) \vee \rm{UMg}(b)$, vgl. Klasse), wird $[a,b]$ Unmengenpaar genannt.

Wenn ein Paar entweder ein Mengen- oder eine Unmengenpaar sein kann, nennt man es zur Verdeutlichung auch Klassenpaar.

Anmerkungen

Der Paarbegriff findet sich bereits in der 1898 erschienene Arbeit „Arithmetices principia: nova methodo“ von Giuseppe Peano. Kurz vor Drucklegung des Buches „Formulaire de Mathématiques“, das das Paaraxiom enthält, publiziert Peano laut Hubert Kennedy eine kleine Studie mit Ergebnissen seiner Studien über die Herabsetzung der Zahl der Grundbegriffe auf ein Minimum.

Diese Publikation enthält sieben Festsetzungen. Eine davon steht als (x;y) für den Begriff eines geordneten Zahlenpaars, das sich aus x und y zusammensetzt. Peano bemerkt dazu: ‹Die Idee eines geordneten Zahlenpaars ist von grundsätzlicher Bedeutung. Wir wissen aber nicht, wie wir es durch die obenerwähnten Symbole ausdrücken sollen.›

1914 gelang es Norbert Wiener und Felix Hausdorff unabhängig voneinander, geordnete Paare durch Mengen auszudrücken. (vgl. nachfolgende Beispiele)

Unterschied zwischen Mathematik und Informatik

Sowohl in der Mathematik, als auch in der Informatik ist es von zentraler Bedeutung unterschiedlicge 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 können, wird axiomatisch festgelegt. In diesen Containern sind die Elemente ungeordnet und jeweils höchstens einmal enthalten.
• In einem zweiten Schritt, werden geordnete Paar definiert.
• Auf Basis der geordneten Paar können 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 Tupel 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:
  • C: Verbünde (record, Tupel); Schlüsselwort: struct
  • C++: zu Objekten verallgemeinerte Verbünde; Schlüsselwörter struct, class
  • PASCAL: [Verbund|Verbünde]]; Schlüsselwort: RECORD
  • LISP: geordnete Paar („CONS-Zellen“) sowie aus CONS-Zellen gebildete Listen (Tupel); Konstruktor: (a . b), (CONS A B)
  • JavaScript: Objekte undd Arrays; Konstruktoren: { a: Wert1, b: Wert2, ...} bzw. [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) definiert, sofern dieses benötigt werden.

Ein weiterer wesentlicher Unterschied zwischen Mathematik und Informatik ist die Behandlung von Urelementen: In der Mathematik wird heute i.Allg. auf Urelemente ganz verzichtet. Stattdessen werden bestimmte Mengen (oder Kalssen) als Repräsentanten für die benötigten Urelemente verwendet.

In der Informatik sind Urelemente dagegen von zentraler Bedeutung. Diese werden i. Allg. Werte oder Atome genannt. Beispiele:

• Boolesche Werte
• Numerische Werte
• Zeichenketten
• etc.

Beispiele für geordnete Mengen- oder Klassenpaare

Beispiele für mögliche Definitionen von $[a,b]$ sind:

$[a,b] := \{\{a,\boldsymbol{1}\},\{b,\boldsymbol{2}\}\}$, wobei $\boldsymbol{1}$ und $\boldsymbol{2}$ sowohl voneinander als auch von $a$ und $b$ verschieden sein müssen (Mengenpaare, 1914 entdeckt von Hausdorff)

$[a,b] := \{\{\emptyset,\{a\}\},\{\{b\}\}\}$ (Mengenpaare, 1914 entdeckt von Wiener)

$[a,b] := \{\{a\},\{a,b\}\}$ (Mengenpaare, 1921 entdeckt von Kuratowski)

$[a,b] := \{\{\{x\}\}: x \in a\} \,\cup\, \{\mathcal P(\{x\}): x \in b\}$ (Klassenpaare, Schmidt)

Im Falle der ersten drei Definition ist sas Paaraxiom nur für Mengenpaare $[a,b]$, da eine Unmenge $a$ oder $b$ nicht Element irgendeiner MEnge oder Klasse sein kann. Im Falle der zweiten Definition ist das Paaraxiom dagegen für beliebige Klassenpaare $[a,b]$ erfüllt.

LISP

Es gibt noch diverse weitere Möglichkeiten, Mengen- oder Klassenpaare zu definieren. Interessant ist in diesem Zusammenhang die von John McCarthy entwickelte Programmiersprache LISP, in der sowohl die LISP-Anweisungen, als auch die LISP-Datenstrukturen nur mit Hilfe von so genannten LISP-Atomen (Zeichenketten, Zahlen etc.) und geordneten Paaren gebildet werden (vgl. Typentheorie).

In LISP werden geordnete Paare in der Form $(a \cdot b)$ bzw. (a . b) (ASCII-Schreibweise) notiert und mit der Funktion $\rm{cons}$ erzeugt. Die Operationen $\pi_1$ und $\pi_2$ zur Extraktion der Elemente heißen bei McCarthy $\rm{car}$ und $\rm{cdr}$. Listen werden in LISP als Abkürzung für $\rm{cons}$-Ketten definiert (siehe Tupel).

Reihenfolge der Elemente

Geordnete Paare sind im Gegensatz zu Mengen tatsächlich geordnet:

$\forall a, b: \{a,b\} = \{b,a\}$ (Bei Paarmengen spielt die Reihenfolge der Elemente keine Rolle, ...)

$\forall a, b: [a,b] = [b,a] \leftrightarrow a = b$ (... bei Paaren wegen des „Paaraxioms“ dagegen schon.)

In einem mengebasiertes Axiomen-System (wie es z.B. der Zermelo-Fraenkel-Mengenlehre zu Grunde liegt) ist die vorangehende Formel sowohl für Mengenpaare, als auch für Klassenpaare unbeschränkt gültig, da in diesem Fall $\forall$ 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) ist die Formel allerdings nur im Falle von Klassenpaaren gültig, da hier $\forall$ als „Für alle Klassen, d.h. für alle Mengen und Unmengen innerhalb des Klassenuniversums“ interpretiert wird.. Bei Mengenpaaren gilt lediglich:

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

Für Unmengen ist ein Mengenpaar nämlich stets gleich der Allklasse $\mathcal{V}$ oder stets gleich der leeren Menge, unabhängig von der Reihenfolge der Elemente:

$\forall a, b: \rm{UMg}(a) \vee \rm{UMg}(b) \rightarrow ([a,b] = \{a,\{a,b\}\} = \mathcal{V} \,\rm{bzw.}\, \emptyset = \{b,\{b,a\}\} = [b,a])$

Grund: Eine Unmenge kann nicht Element einer Menge sein. Abhängig von der Art, wie $\{a\}$ definiert ist, gilt daher entweder $\forall a: \rm{UMg}(a) \rightarrow \{a\} = \mathcal{V}$ oder $\forall a: \rm{UMg}(a) \rightarrow \{a\} = \emptyset$.

Fazit: Im Falle eines klassenbasierten Axiomen-Systems sollte man eine Klassenpaar-Definition an Stelle einer Mengenpaar-Definition verwenden.

Projektion

Lemma: $\rm{Mg}(x) \,\leftrightarrow\, \bigcap\{x\} = x$

Hausdorff-Paare

$[a,b] \,=\, \{\{a,\boldsymbol{1}\},\{b,\boldsymbol{2}\}\},\, \rm{Mg}(a),\, \rm{Mg}(b),\, \boldsymbol{1} \notin \{\boldsymbol{2}, a,b\},\, \boldsymbol{2} \notin \{\boldsymbol{1}, a,b\} $

Hasudorf unterscheidet das erste und das zweite Element eines Paares mit Hilfe von zwei speziellen Mengen, die anderweitig nicht verwendet werden.

$\pi_1([a,b]) \,:=\, \bigcap\{x: \{x,\boldsymbol{1}\} \in [a,b]\} \,=\, \bigcap\{a\} \,=\, a $

$\pi_2([a,b]) \,:=\, \bigcap\{x: \{x,\boldsymbol{2}\} \in [a,b]\} \,=\, \bigcap\{b\} \,=\, b $

Wiener-Paare

$[a,b] \,=\, \{\{\{a\}\},\{\emptyset,\{b\}\}\},\, \rm{Mg}(a),\, \rm{Mg}(b) $

Wiener unterscheidet das erste und das zweite Element eines Paares anhand der Mächtigkeit der zugehörigen Mengen. $a$ ist Element einer einelementigen Menge und $b$ ist Element einer zweielementigen Menge. Die Definition von Wiener sorgt dafür, dass die Menge $\{\emptyset,\{b\}\}$ auch im Falle $b = \emptyset$ zweielementig ist. Für $\{\emptyset,b\}$ wäre dies dagegen nicht der Fall.

$\pi_1([a,b]) \,:=\, \bigcap\{x: \{\{x\}\} \in [a,b]\} \,=\, \bigcap\{a\} \,=\, a$

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

Kuratowski-Paare

$[a,b] \,=\, \{\{a\},\{a,b\}\},\, \rm{Mg}(a),\, \rm{Mg}(b) $

Kuratowski geht einen vollkommen anderen Weg als Wiener und Hausdorff. Er kombiniert die beiden Paarelemente $a$ und $b$ so geschickt in einer Menge, dass diese Elemente mit Hilfe von einfachen Mengen-Operationen ($\cup$, $\cap$, $\setminus$) wiedergewonnen werden können.

$\pi_1([a,b]) \,:=\, \bigcap\bigcap [a,b] \,=\, \bigcap\bigcap\{\{a\},\{a,b\}\} \,=\, \bigcap(\{a\} \cap\{a,b\}) \,=\, \bigcap\{a\} = a $

$\pi_2([a,b]) \,:=\, \bigcap(\bigcup [a,b] \setminus \pi_1([a,b])) \,=\, \bigcap(\bigcup\{\{a\},\{a,b\}\} \setminus \{a\}) \,=\, \bigcap(\{a\} \cup \{a,b\}) \setminus \{a\}) \,=\, \bigcap(\{a,b\} \setminus \{a\}) \,=\, \bigcap\{b\} \,=\, b $

Schmidt-Paare

$[a,b] \,=\, \{\,\{\{x\}\}:\ x \in a\,\} \,\cup\, \{\,\mathcal P(\{x\}): x \in b\,\} \,=\, \{\,\{\{x\}\}: x \in a\,\} \,\cup\, \{\,\{\emptyset, \{x\}\}: x \in b\,\} $

Schmidt greift die Idee von Wiener auf. Er unterscheidet die beiden Paarelemente $a$ und $b$ anhand von ein- und zweielementigen Mengen. Allerdings achtet er darauf, dass $a$ und $b$ nur rechts vom Elementzeichen $\in$ vorkommen, da Unmengen zwar Elemente enthalten können, aber nicht Elemente sein können. Schmidt „verpackt“ daher $a$ und $b$ nicht selbst in ein- bzw. zweielementige Mengen, sondern er macht dies mit den Elementen dieser beiden Klassen.

$\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 $

Siehe auch

• Reconsidering Ordered Pairs, Dana Scott und Dominic McCarty