Beweisarchiv: Mengenlehre: Mengenoperation: Distributivgesetz

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 über Vereinigung

Voraussetzung

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

Behauptung

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

Beweis

$\subseteq$ : x sei ein Element der linken Seite, also $x\in A\cap (B\cup C)$ . Dann gilt $x\in A$ und $x\in B\cup C$ . Da x in der Vereinigung von B und C liegt, ist (Fall 1) $x\in B$ oder (Fall 2) $x\in C$ . Im Fall 1 ist $x\in A\cap B$ , im Fall 2 ist $x\in A\cap C$ . Damit liegt x in der Vereinigung $(A\cap B)\cup (A\cap C)$ , ist also Element der rechten Seite.

$\supseteq$ : x sei ein Element der rechten Seite, also $x\in (A\cap B)\cup (A\cap C)$ . Damit gilt (Fall 1) $x\in A\cap B$ oder (Fall 2) $x\in A\cap C$ . In beiden Fällen haben wir $x\in A$ . Außerdem ist $x\in B$ oder $x\in C$ , zusammengefasst also $x\in B\cup C$ . Nach Definition des Durchschnitts liegt x in $A\cap (B\cup C)$ , ist also Element der linken Seite.

Alternativ: Es gilt

x\in A\cap (B\cup C)\iff x\in A\land (x\in B\lor x\in C)

und

x\in (A\cap B)\cup (A\cap C)\iff (x\in A\land x\in B)\lor (x\in A\land x\in C).

Die Behauptung folgt daher aus der Distributivität von $\land$ über $\lor$ , d.h. der allgemeinen Äquivalenz von $p\land (q\lor r)$ und $(p\land q)\lor (p\land r)$ .

Durchschnitt über beliebige Vereinigung

Voraussetzung

Sei $A$ eine Menge, $I$ eine (Index-)Menge und zu jedem $i\in I$ sei $B_{i}$ eine Menge.

Behauptung

$A\cap \bigcup _{i\in I}B_{i}=\bigcup _{i\in I}(A\cap B_{i})$

Beweis

Element der linken Menge zu sein ist für jedes $x$ äquivalent zu $x\in A\land \exists i\in I\colon x\in B_{i}$ , für die rechte dagegen zu $\exists i\in I\colon (x\in A\land x\in B_{i})$ . Aber auf prädikatenlogischer Ebene gilt bereits die allgemeine Äquivalenz von $p\land \exists i\colon q_{i}$ mit $\exists i\colon (p\land q_{i})$ - hier mit $p$ für $x\in A$ und $q_{i}$ für $i\in I\land x\in B_{i}$ :

Aus $p\land \exists i\colon q_{i}$ folgt sowohl $p$ als auch $\exists i\colon q_{i}$ , aus letzterem $q_{i}$ für ein geeignetes $i$ . Zusammen mit $p$ folgt für dieses $i$ dann $p\land q_{i}$ , insbesondere $\exists i\colon (p\land q_{i})$ .
Aus $\exists i\colon (p\land q_{i})$ folgt - für geeignetes $i$ - die Gültigkeit von $p\land q_{i}$ , also sowohl $p$ als auch $q_{i}$ . Folglich gilt $q_{i}$ für dieses $i$ , d.h. $\exists i\colon q_{i}$ , zusammen mit $p$ also $p\land \exists i\colon q_{i}$ .

Bemerkung

Der vorhergehende Satz kann auch als Spezialfall dieses Satzes für den Fall einer zweielementigen Indexmenge angesehen werden.

Vereinigung über Durchschnitt

Voraussetzung

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

Behauptung

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

Beweis

Hier folgt die Gleichheit aus der allgemeinen Äquivalenz von $p\lor (q\land r)$ und $(p\lor q)\land (p\lor r)$

Vereinigung über beliebigen Durchschnitt

Voraussetzung

Sei $A$ eine Menge, $I$ eine (Index-)Menge und zu jedem $i\in I$ sei $B_{i}$ eine Menge.

Behauptung

$A\cup \bigcap _{i\in I}B_{i}=\bigcap _{i\in I}(A\cup B_{i})$

Beweis

Hier folgt die Aussage aus der allgemeinen Äquivalenz von $p\lor \forall i\colon q_{i}$ und $\forall i\colon (p\lor q_{i})$ - hier mit $x\in A$ für $p$ sowie $i\in I\Rightarrow x\in B_{i}$ : für q

Angenommen, $p$ ist wahr. Dann ist sowohl $p\lor \forall i\colon q_{i}$ wahr als auch $p\lor q_{i}$ für jedes $i$ , also $\forall i\colon (p\lor q_{i})$ .
Angenommen, $p$ ist falsch.
- Gilt $p\lor \forall i\colon q_{i}$ , so folgt $\forall i\colon q_{i}$ . Sei $i$ beliebig. Dann folgt hieraus $q_{i}$ und erst recht $p\lor q_{i}$ . Da $i$ beliebig war, folgt $\forall i\colon (p\lor q_{i})$ .
- Gilt $\forall i\colon (p\lor q_{i})$ und ist $i$ beliebig, so folgt $p\lor q_{i}$ , nach Voraussetzung sogar $q_{i}$ . Da $i$ beliebig war, folgt $\forall i\colon q_{i}$ und erst recht $p\lor \forall i\colon q_{i}$ .