05 Fundiertheit, Paare und Produkte

5. Fundiertheit, geordnete Paare und Produkte

Voraussetzung: 03 Mengenlehre - Grundlagen und Axiome (Paarmengenaxiom, Potenzmenge)

5.1 Fundiertheitsaxiom

Fundiertheit

Zu jeder nichtleeren Menge $A$ existiert ein Element $x\in A$ mit $x\cap A=\varnothing$. Man sagt dann: $x$ und $A$ sind disjunkt (allgemein: zwei Mengen $x,A$ heißen disjunkt, falls $x\cap A=\varnothing$).

Dieses Axiom verhindert “zirkuläre” Mengen — also Mengen, die sich selbst (direkt oder über Umwege) als Element enthalten.

Folgerung 1: Keine Menge enthält sich selbst

Folgerung aus der Fundiertheit

$x\notin x$ für jede Menge $x$.

Beweis (Widerspruch): Annahme: $x\in x$. Die Menge $A:=\{x\}$ (existiert nach dem Paarmengenaxiom) ist nicht leer. Wegen der Fundiertheit muss $A$ ein zu $A$ disjunktes Element enthalten — da $x$ das einzige Element von $A$ ist, kann nur $x$ dieses disjunkte Element sein.

Aber: $x$ ist nicht disjunkt zu $A$, denn nach Annahme ($x\in x$) und Wahl von $A$ ($x\in A$) gilt $x\in x\cap A$ — also ist $x\cap A\ne \varnothing$. WIDERSPRUCH zur Fundiertheit.

Folgerung 2: Keine zyklischen Elementbeziehungen

Auch $a\in b\in a$ (für zwei Mengen $a,b$) tritt nicht ein.

Beweis: Die Menge $\{a,b\}$ muss (nach Fundiertheit) ein zu $\{a,b\}$ disjunktes Element enthalten. Wäre $a\in b\in a$, so kann dieses disjunkte Element nicht $a$ sein, denn $b\in a\cap \{a,b\}$ (da $b\in a$ nach Annahme und $b\in \{a,b\}$ trivial) — also wäre $a$ nicht disjunkt zu $\{a,b\}$. Aber $\{a,b\}$ enthält nur $a$ und $b$ als Elemente — wenn $a$ nicht das disjunkte Element sein kann, müsste es $b$ sein. Durch symmetrisches Argument (mit $a$ und $b$ vertauscht) scheitert auch das. WIDERSPRUCH.

Allgemein gilt: Es gibt keine Menge $\{a_1,\dots ,a_n\}$ mit $a_1\in a_2\in \cdots \in a_n\in a_1$

Intuition

Die Fundiertheit sorgt dafür, dass die $\in$-Beziehung “nach unten terminiert” — man kann nicht endlos (oder zyklisch) immer tiefer in Elemente von Elementen absteigen. Das ist die mengentheoretische Grundlage dafür, dass Induktion und Rekursion überhaupt wohldefiniert sind.

---

5.2 Geordnete Paare nach Kuratowski

Bisher kannten wir nur ungeordnete Paarmengen $\{a,b\}$ (mit $\{a,b\}=\{b,a\}$). Für viele Zwecke (z.B. Koordinaten, Relationen, Funktionen) braucht man aber geordnete Paare, bei denen Reihenfolge zählt.

Definition: Geordnetes Paar (Kuratowski)

Für zwei Mengen $a,b$ definiert man: $(a,b):=\{a,\{a,b\}\}$

Diese Definition baut ausschließlich auf dem Paarmengenaxiom auf — es wird kein neues Axiom benötigt, um geordnete Paare einzuführen.

Warum ist das eine sinnvolle Definition?

Entscheidend ist, dass geordnete Paare die erwartete Eigenschaft erfüllen:

$(a,b)=(c,d)⟺a=c\wedge b=d$

Beweis ”⟸”: Trivial — wenn $a=c$ und $b=d$, dann ist $\{a,\{a,b\}\}=\{c,\{c,d\}\}$ einfach durch Einsetzen.

Beweis ”⟹”: Gelte $(a,b)=(c,d)$, also $\{a,\{a,b\}\}=\{c,\{c,d\}\}$. Da beide Mengen genau zwei “Top-Level”-Elemente haben müssen ($a$ bzw. $\{a,b\}$ links, $c$ bzw. $\{c,d\}$ rechts), gibt es zwei Fälle, wie diese Elemente sich einander zuordnen können:

Fall 1: $a=c\wedge \{a,b\}=\{c,d\}$ $\Rightarrow$ (mit $a=c$ eingesetzt) $\{a,b\}=\{a,d\}$ $\Rightarrow b=d$. Also $a=c\wedge b=d$. ✓

Fall 2: $a=\{c,d\}\wedge c=\{a,b\}$ $\Rightarrow a\in \{a,b\}=c\in \{c,d\}=a$, also $a\in c\in a$. Das ist aber genau die in 5.1 ausgeschlossene zyklische Beziehung — WIDERSPRUCH zur Fundiertheit. Fall 2 kann also nicht eintreten.

Damit bleibt nur Fall 1 übrig, und die Behauptung ist bewiesen. ∎

Warum ist das wichtig?

Dieser Beweis zeigt, wofür die Fundiertheit aus 5.1 tatsächlich gebraucht wird: Ohne sie könnte man nicht ausschließen, dass “entartete” Paare wie in Fall 2 echte, unterschiedliche geordnete Paare erzeugen, die trotzdem gleich aussehen. Die Fundiertheit garantiert also, dass die Kuratowski-Definition wohldefiniert und eindeutig ist.

Man kann (muss hier aber nicht im Detail ausführen) ein Prädikat $p(x,a,b)$ formulieren, das genau dann wahr ist, wenn $x=(a,b)$ gilt — damit ist das geordnete Paar vollständig in der Sprache der Mengenlehre ausdrückbar.

---

5.3 Kartesisches Produkt

Definition: Kartesisches Produkt

Für zwei Mengen $A,B$ ist $A\times B$ die Menge aller Paare $(a,b)$ mit $a\in A$ und $b\in B$: $A\times B:=\{(a,b):a\in A,b\in B\}$

Warum ist $A\times B$ überhaupt eine “gesicherte” Menge?

Diese Frage ist wichtig, weil man (wie in Kapitel 3 gelernt) nicht einfach “alle Paare mit dieser Eigenschaft” als Menge postulieren darf — man muss zeigen, dass sie sich aus bereits gesicherten Mengen aussondern lässt.

• Ein Paar $(a,b)=\{a,\{a,b\}\}$ besteht aus einem Element $a\in A\cup B$ und einer Teilmenge $\{a,b\}$ von $A\cup B$, d.h. einem Element von $\mathfrak{P}(A\cup B)$.
• Das Paar $(a,b)$ ist also selbst eine Teilmenge von $A\cup \mathfrak{P}(A\cup B)$ (seine beiden “Bestandteile” liegen jeweils dort), also ein Element von $\mathfrak{P}(A\cup \mathfrak{P}(A\cup B))$.
• Folglich lassen sich alle Paare $(a,b)$ mit $a\in A,b\in B$ aus der (bereits gesicherten) Menge $\mathfrak{P}(A\cup \mathfrak{P}(A\cup B))$ aussondern.

Damit ist $A\times B$ nach dem (korrigierten) Aussonderungsschema aus Kapitel 3 eine legitime Menge.

Beispiel: $\{1,2,3\}\times \{1,5,7\}=\{(1,1),(1,5),(1,7),(2,1),(2,5),(2,7),(3,1),(3,5),(3,7)\}$

Mengen der Form $A\times B$ heißen auch Rechteckmengen.

Tripel, Quadrupel und das große Mengenprodukt

Aus geordneten Paaren lassen sich rekursiv höhere Tupel konstruieren: $\text{Tripel: }(a,b,c):=(a,(b,c))$ $\text{Quadrupel: }(a,b,c,d):=(a,(b,(c,d)))$ usw. Die entsprechenden Mengen aller Tripel, Quadrupel etc. werden analog mit $A\times B\times C$ usw. bezeichnet.

Großes Mengenprodukt

Für eine Familie $(A_j{)}_{j\in I}$ von Mengen ist das große Mengenprodukt definiert durch: ${\prod }_{j\in I}{A}_j:=\{f:f\text{ ist Funktion von }I\text{ nach }{\bigcup }_j{A}_j\text{ mit }f(j)\in A_j\text{ fu¨r alle }j\}$

Die Idee: Ein Element des großen Produkts ist eine Funktion, die jedem Index $j$ ein Element aus “seiner” Menge $A_j$ zuordnet — das verallgemeinert das Tupel-Konzept auf (eventuell unendlich viele) Faktoren.

Dieses Konzept wird in 06 Relationen gebraucht, wo Relationen als Teilmengen von $A\times B$ definiert werden.