Beweisarchiv: Mengenlehre: Mengenoperation: Assoziativgesetz

Rechenregeln für Mengenoperationen: Assoziativgesetze · Distributivgesetze · Differenzgesetze · Grundeigenschaften der Inklusion · De Morgansche Regeln für Mengen · Bild und Urbild

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

Voraussetzung

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

Behauptung

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

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

Beweis

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\land x\in (B\cap C)\iff x\in A\land (x\in B\land x\in C)

sowie

x\in (A\cap B)\cap C\iff x\in (A\cap B)\land x\in C\iff (x\in A\land x\in B)\land 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\land (q\land r)$ und $(p\land q)\land r$ .

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

Symmetrische Differenz

Voraussetzung

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

Behauptung

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

Beweis

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{aligned}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{aligned}}

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

{\begin{aligned}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{aligned}}

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

Mengendifferenz (Gegenbeispiel)

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