Beweisarchiv: Mengenlehre: Mengenoperation: Assoziativgesetz

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)⟺x\in A\wedge x\in (B\cap C)⟺x\in A\wedge (x\in B\wedge x\in C)$

sowie

$x\in (A\cap B)\cap C⟺x\in (A\cap B)\wedge x\in C⟺(x\in A\wedge x\in B)\wedge 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\wedge (q\wedge r)$ und $(p\wedge q)\wedge 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\mathrm{△}(B\mathrm{△}C)=(A\mathrm{△}B)\mathrm{△}C$

Beweis

Hier folgt die Gleichheit der Mengen aus der logischen Äquivalenz von $p\leftrightarrow ̸(q\leftrightarrow ̸r)$ und $(p\leftrightarrow ̸q)\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{array}{cc}B\mathrm{△}C& =(B\cup C)\setminus (B\cap C)=(B\cup C)\cap (B\cap C{)}^{𝖢}\\ & =(B\cup C)\cap (B^{𝖢}\cup C^{𝖢})=(B\cap C^{𝖢})\cup (C\cap B^{𝖢})\end{array}$

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

$\begin{array}{cc}A\mathrm{△}(B\mathrm{△}C)& =(A\cap (B\mathrm{△}C{)}^{𝖢})\cup ((B\mathrm{△}C)\cap A^{𝖢})\\ & =(A\cap ((B^{𝖢}\cap C^{𝖢})\cup (B\cap C)))\cup (((B\cap C^{𝖢})\cup (C\cap B^{𝖢}))\cap A^{𝖢})\\ & =(A\cap B^{𝖢}\cap C^{𝖢})\cup (A\cap B\cap C)\cup (B\cap C^{𝖢}\cap A^{𝖢})\cup (C\cap B^{𝖢}\cap A^{𝖢})\end{array}$

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)\ne (A\setminus B)\setminus C$, wie ein einfaches Beispiel zeigt:

$\{a\}\setminus (\{a\}\setminus \{a\})=\{a\}\setminus \varnothing =\{a\}$

$(\{a\}\setminus \{a\})\setminus \{a\}=\varnothing \setminus \{a\}=\varnothing$

Wikipedia-Verweise

Assoziativgesetz - charakteristische Funktion - Differenzmenge - Restklassenring - Schnittmenge - symmetrische Differenz - Teilmenge - Vereinigungsmenge

---