Beweisarchiv: Mengenlehre: Mengenoperation: Assoziativgesetz

Ordinalzahlen: Ordinalzahlen enthalten sich nicht selbst als Element - Elemente von Ordinalzahlen sind Ordinalzahlen - Durchschnitte von Ordinalzahlen sind Ordinalzahlen - Wohlordnung der Klasse aller Ordinalzahlen - Ordinalzahlen bilden eine echte Klasse - Der Nachfolger einer Ordinalzahl ist Ordinalzahl - Vereinigungen von Ordinalzahlen sind Ordinalzahlen - Limes- und Nachfolgerzahlen - Äquivalenz verschiedener Definitionen

Sätze die in ZF Äquivalent zum Auswahlaxiom sind: Alternative Darstellung des Auswahlaxioms - Wohlordnungssatz - Lemma von Zorn

Durchschnitt und Vereinigung [Bearbeiten]

Voraussetzung [Bearbeiten]

$A,\ B,\ C$ seien beliebige Mengen.

Behauptung [Bearbeiten]

$A \cap (B \cap C) = (A \cap B) \cap C$

$A \cup (B \cup C) = (A \cup B) \cup C$

Beweis [Bearbeiten]

Zwei Mengen sind genau dann gleich, wenn sie genau dieselben Elemente enthalten. Nun gilt

$x\in A\cap(B\cap C) \iff x\in A \and x\in(B\cap C) \iff x\in A \and (x\in B \and x\in C)$

sowie

$x\in (A\cap B)\cap C \iff x\in (A\cap B) \and x\in C \iff (x\in A \and x\in B) \and x\in C.$

Die Gleichheit $A\cap(B\cap C)=(A\cap B)\cap C$ folgt also wegen der Assoziativität der logischen und-Verknüpfung, d.h. aus der Äquivalenz von $p\and(q\and r)$ und $(p\and q)\and r$ .

Die Aussage für die Vereinigung folgt entsprechend aus der Assoziativität der logischen oder-Verknüpfung.

Symmetrische Differenz [Bearbeiten]

Voraussetzung [Bearbeiten]

$A,\ B,\ C$ seien beliebige Mengen.

Behauptung [Bearbeiten]

$A \triangle (B \triangle C) = (A \triangle B) \triangle C$

Hier folgt die Gleichheit der Mengen aus der logischen Äquivalenz von $p\not\leftrightarrow(q\not\leftrightarrow r)$ und $(p\not\leftrightarrow q)\not\leftrightarrow r$ . Beide sind genau dann wahr, wenn genau eine oder alle drei Teilaussagen wahr sind. Der Beweis wird im Folgenden direkt für Mengen geführt. Für die symmetrische Differenz gilt:

$\begin{align} B \triangle C &= (B \cup C) \setminus (B \cap C) = (B \cup C) \cap (B \cap C)^{\mathsf C} \\ &= (B \cup C) \cap (B^{\mathsf C} \cup C^{\mathsf C}) = (B \cap C^{\mathsf C}) \cup (C \cap B^{\mathsf C}) \end{align}$

Die letzen beiden Ausdrücke benutzt man in der folgenden Rechnung.

$\begin{align} A \triangle (B \triangle C) &= \left(A \cap (B \triangle C)^{\mathsf C}\right) \cup \left((B \triangle C) \cap A^{\mathsf C}\right) \\ &= \left(A \cap \left((B^{\mathsf C} \cap C^{\mathsf C}) \cup (B \cap C)\right)\right) \cup \left(\left((B \cap C^{\mathsf C}) \cup (C \cap B^{\mathsf C})\right) \cap A^{\mathsf C}\right) \\ &= (A \cap B^{\mathsf C} \cap C^{\mathsf C}) \cup (A \cap B \cap C) \cup (B \cap C^{\mathsf C} \cap A^{\mathsf C}) \cup (C \cap B^{\mathsf C} \cap A^{\mathsf C}) \end{align}$

Dieser Ausdruck ist invariant unter Permutationen von $A,\ B,\ C$ . Daher gilt das Assoziativgesetz.

Mengendifferenz (Gegenbeispiel) [Bearbeiten]

Die Mengendifferenz ist natürlich nicht assoziativ, es gilt also im allgemeinen $A \setminus (B \setminus C) \ne (A \setminus B ) \setminus C$ , wie ein einfaches Beispiel zeigt: