Beweisarchiv: Mengenlehre: Mengenoperation: Assoziativgesetz

Aus Wikibooks
Wechseln zu: Navigation, Suche

Beweisarchiv: Mengenlehre

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


Inhaltsverzeichnis

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

Beweis [Bearbeiten]

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:

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

Wikipedia-Verweise [Bearbeiten]

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


Beweisarchiv: Mengenlehre

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