Beweisarchiv: Mengenlehre: Mengenoperation: Assoziativgesetz

Aus Wikibooks

Injektivität Surjektivität Bijektivität: Faktoren - Komposition - Linksinverse - Linkskürzbarkeit - Rechtsinverse - Rechtskürzbarkeit

Mächtigkeiten (Kardinalzahlen): lineare Ordnung - Kardinalität und Bijektionen - Potenzmenge

Deskriptive Mengenlehre: Satz von Young

Rechenregeln für Mengenoperationen: Assoziativgesetze - Distributivgesetze - Differenzgesetze

[Bearbeiten] Durchschnitt und Vereinigung

[Bearbeiten] Voraussetzung

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

[Bearbeiten] Behauptung

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

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

[Bearbeiten] 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 \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.

[Bearbeiten] Symmetrische Differenz

[Bearbeiten] Voraussetzung

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

[Bearbeiten] Behauptung

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

[Bearbeiten] Mengendifferenz (Gegenbeispiel)

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: