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 (Brockhaus)

Paar ... 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)$.

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 von Giuseppe Peano erfüllt ist:

Für alle Elemente $a$, $b$, $c$, $d$ gilt, dass die Paare $[a,b]$ genau dann gleich sind (in Zeichen $[a,b] = [c,d]$),

wenn sowohl $a$ und $c$, als auch $b$ und $d$ einander gleich sind ($a=c$ und $b=d$).

Anmerkung

Die Rückrichtung des Paaraxiom („Aus der Gleichheit von $a$ und $c$ sowie von $b$ und $d$ folgt die Gleichheit der beiden Paare $[a,b]$ und $[c,d]$“) ist trivilerweise immer erfüllt, sofern man die Gleichheit mit Hilfe des „Prinzips von der Identität des Ununterscheidbaren“ definiert.

Interessant ist daher vor allem die Aussage, dass aus der Gleichheit zweier Paare die Gleichheit der zugehörigen Elemente folgt. Im Umkehrschluss (logische Kontraposition) heißt dies nämlich, dass aus der Ungleichheit von $a$ und $c$ oder von $b$ und $d$ ($a\not=c$ oder $b\not=d$) stets die Ungleichheit der beiden Paare $[a,b]$ und $[c,d]$ folgt ($[a,b] \not= [c,d]$).

Projektion

Für geordnete Paare kann man – wegen des Paaraxioms – zwei Projektionsoperationen $\pi_1$ und $\pi_2$ definieren, um das erste bzw. das zweite Element des Paars zu extrahieren:

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

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

Satz: Existenz und Eindeutigkeit der Projektionsoperationen

Wenn das Paaraxion von Peano erfüllt ist, gibt es genau eine Operation $\pi_1$ und genau eine Operation $\pi_2$, die die zuvor definierten Eigenschaften haben.

Beweis

[ein-/ausklappen]

Eindeutigkeit:

Angenommen, es gäbe zwei Projektionsoperationen $\pi_1$ und $\pi'_1$ die das erste Paarelement extrahieren. Dann würde aus der zuvor definierten Eigeschaft von $\pi_1$ Folgendes folgen:

Für alle $a$, $b$ gilt $\pi_1([a,b]) = a = \pi'_1([a,b]).$

Das heißt, die beiden Operationen liefern für jedes Paar dasselbe Ergebnis. Damit sind beide Operationen (hinsichtlich des Abbildungsverhaltens von Paaren) identisch.

(Das heißt nicht, dass sich $\pi_1$ und $\pi'_1$ nicht hinsichtlich anderer Aspekte unterscheiden können. Zum Beispiel kann das Abbildungsverhalten hinsichtlich Nicht-Paaren unterschiedlich ausfallen, sofern dies Verhalten für eine oder gar beide Operationen definiert ist, oder die Operationen können mit Hilfe unterschiedlicher Verfahren (Algorithmen) zum selben Ergebnis kommen. Die Eindeutigkeit gilt daher nur, wenn das „Prinzip von der Identität des Ununterscheidbaren“ zum Einsatz kommt und man die Projektionsoperatoren stets nur auf Paare anwendet.)

Für $\pi_2$ zeigt man die Eindetigkeit analog.

Existenz:

Bei $\pi_1$ und $\pi_2$ handelt es sich um Abbildungen, die jedem Element vom Typ „Paar“ einen speziellen Wert zuweisen.

So eine Abbildung kann es nur geben, wenn sich die Paare, denen unterschiedliche Werte zugeweisen werden sollen, selbst unterscheiden. Wenn man beispielsweise $[a,b] := \{a,b\}$ festlegen würde, würden sich die „Paare“ $[2,5]$ und $[5,2]$ nicht untrscheiden, da die Mengen $\{2,5\}$ und $\{5,2\}$ gleich sind. In diesem Fall könnte es keine Abbilung $\pi_1$ geben, die dem „Paar“ $[2,5]$ den Wert $2$ und dem „Paar“ $[5,2]$ den Wert $5$ zuweisen würde.

Wenn allerdings die Paardefinition das Paaraxiom von Peano erfüllt ist, unterscheiden sich alle Paare, die nicht aus denselben Elementen gebildet werden. (z.B. unterscheiden sich in diesem Fall die beiden Paare $[2,5]$ und $[5,2]$). Das Paaraxion fordert, dass aus $a\not=c$ oder $b\not=d$ stets $[a,b] \not= [c,d]$ folgt (siehe Anmerkung im Anschluss an die Definition des Paarbegriffs). Das heißt, man kann beliebige Abbildungen definieren, die jedem Paar einen individuellen Wert zuweisen. Insbesondere kann man also $\pi_1$ und $\pi_2$ definieren.

Satz: Beziehung zwischen Projektion und Paaraxiom

Wenn das Paaraxion von Peano erfüllt ist, gilt für alle Paare $[a,b] = [\pi_1([a,b]),\pi_2([a,b])]$.

Wenn umgekehrt die Projektionsfunktionen $\pi_1$ und $\pi_2$ existieren erfüllt ist, dann ist auch das Paaraxiom erfüllt.

Beweis

[ein-/ausklappen]

Der erste Teil der Aussage folgt sofort aus dem zuvor bewiesenen Satz und dem „Prinzip von der Identität des Ununterscheidbaren“.

Für den zweiten Teil nehmen wir zunächst an, dass $a \not= c$ gilt. Wäre nun $[a,b] = [c,d]$, dann wäre auch $a = \pi_1([a,b]) = \pi_1([c,d]) = c$, was ein Widerspruch zur Annahme ist. Also muss $[a,b] \not= [c,d]$ gelten. Analog zeigt man, dass aus $d \not= d$ ebenfalls $[a,b] \not= [c,d]$ folgt.

Insgesamt gilt also, dass aus $a \not= c$ oder $b \not= d$ stets $[a,b] \not= [c,d]$ folgt. Das heißt, das Paaraxiom ist erfüllt (siehe Anmerkung im Anschluss an die Definition des Paarbegriffs).

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 ein Unmengenpaar sein kann, nennt man es zur Verdeutlichung auch Klassenpaar.

Geschichte des Paarbegriffs

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 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 können, 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/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 Absatz „LISP“) 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 (Konstruktore: {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) mit Hilfe der vorgegebenen Datenstrukturen definiert werden, sofern diese benötigt 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.

Geordnete Mengen- und Klassenpaare

Beispiele

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, 1966 definiert von Schmidt „in Anlehnung an Quine“)

Im Falle der ersten drei Definition ist das Paaraxiom nur für Mengenpaare $[a,b]$, da eine Unmenge $a$ oder $b$ nicht Element irgendeiner Menge oder Klasse sein kann. Im Falle der Definition von Schmidt 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).

Definition und Eigenschaften von Mengen- und Klassenpaaren

Lemma: Projektion

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

Man beachte, dass dieses Lemma zur Folge hat, dass die folgenden drei Definitionen jeweils nur für Mengen korrekt sind, nicht jedoch für Klassen. Bei der Berechnung von $\pi_1([a,b])$ und $\pi_2([a,b])$ wird die Voraussetzung $\rm{Mg}(a)$ bzw. $\rm{Mg}(b)$ jeweils für den letzen Berechnungsschritt benötigt.

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

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.

$\begin{array}{rclr}

 \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
\end{array} 

$

Satz: Hausdorff-Paare erfüllen das Paaraxiom von Peano

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

Beweis

[ein-/ausklappen]

„$\leftarrow$“

$a = c \wedge b = d \rightarrow \{\{a,\boldsymbol{1}\},\{b,\boldsymbol{2}\}\} = \{\{c,\boldsymbol{1}\},\{d,\boldsymbol{2}\}\} \rightarrow [a,b] = [c,d]$

„$\rightarrow$“

$\begin{array}{rclr}

  [a,b] = [c,d] & \;\rightarrow\; & \{\{a,\boldsymbol{1}\},\{b,\boldsymbol{2}\}\} = \{\{c,\boldsymbol{1}\},\{d,\boldsymbol{2}\}\} & \text{(Definition von $=$)}\\
                & \;\rightarrow\; & \{a,\boldsymbol{1}\} \in \{\{c,\boldsymbol{1}\},\{d,\boldsymbol{2}\}\} \\
                & \;\rightarrow\; & \{a,\boldsymbol{1}\} = \{c,\boldsymbol{1}\} 
                                  & \text{(da $\boldsymbol{1} \not= d$ und $\boldsymbol{1} \not=\boldsymbol{2}$)} \\
                & \;\rightarrow\; & a = c  & \text{(da $\boldsymbol{1} \not= a$ und $\boldsymbol{1} \not= c$; Definition von $=$)}
\end{array} 

$

Den zweiten Teil $[a,b] = [c,d] \rightarrow b=d$ beweist man analog.

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.

$\begin{array}{rclclcl}

 \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
\end{array} 

$

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.

$\begin{array}{rclclcl}

 \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\, \bigcap[a,b]) \\
              & =  & \bigcap(\bigcup\{\{a\},\{a,b\}\} \setminus\, \bigcap\{\{a\},\{a,b\}\})  \\
              & =  & \bigcap((\{a\} \cup \{a,b\}) \,\setminus\, (\{a\} \cap\{a,b\})) \\
              & =  & \bigcap(\{a,b\} \setminus \{a\}) \\
              & =  & \bigcap\{b\} \\
              & =  & b \\
\end{array} 

$

Schmidt-Paare

$\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\,\} 
\end{array} 

$

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, aber selbst keine Elemente sein können. Schmidt „verpackt“ daher nicht $a$ und $b$ selbst in ein- bzw. zweielementige Mengen, sondern er macht dies mit den Elementen dieser beiden Klassen.

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

$

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

Grund: Für Unmengen ist, da eine Unmenge nicht Element einer Menge sein kann, ein Mengenpaar nämlich stets gleich der Allklasse $\mathcal{V}$ unabhängig von der Reihenfolge der Elemente. Es gilt: $\forall u: \rm{UMg}(u) \rightarrow \{u\} = \mathcal{V}$ (siehe Definintion von $n$-elementigen Mengen)

Und damit gilt erst recht:

$\forall a, b: \{\{a,\boldsymbol{1}\},\{b,\boldsymbol{2}\}\} = \{\{b,\boldsymbol{1}\},\{a,\boldsymbol{2}\}\} = \mathcal{V}$

$\forall a, b: \{\{\{a\}\},\{\emptyset,\{b\}\}\} = \{\{\{b\}\},\{\emptyset,\{a\}\}\} = \mathcal{V}$

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

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

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

Siehe auch

• Reconsidering Ordered Pairs, Dana Scott und Dominic McCarty