Beweisarchiv: Mengenlehre: Mengenoperation: Distributivgesetz

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

und

$x\in (A\cap B)\cup (A\cap C)⟺(x\in A\wedge x\in B)\vee (x\in A\wedge x\in C).$

Die Behauptung folgt daher aus der Distributivität von $\wedge$ über $\vee$, d.h. der allgemeinen Äquivalenz von $p\wedge (q\vee r)$ und $(p\wedge q)\vee (p\wedge 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\wedge \mathrm{\exists }i\in I:x\in B_i$, für die rechte dagegen zu $\mathrm{\exists }i\in I:(x\in A\wedge x\in B_i)$. Aber auf prädikatenlogischer Ebene gilt bereits die allgemeine Äquivalenz von $p\wedge \mathrm{\exists }i:q_i$ mit $\mathrm{\exists }i:(p\wedge q_i)$ - hier mit $p$ für $x\in A$ und $q_i$ für $i\in I\wedge x\in B_i$:

• Aus $p\wedge \mathrm{\exists }i:q_i$ folgt sowohl $p$ als auch $\mathrm{\exists }i:q_i$, aus letzterem $q_i$ für ein geeignetes $i$. Zusammen mit $p$ folgt für dieses $i$ dann $p\wedge q_i$, insbesondere $\mathrm{\exists }i:(p\wedge q_i)$.
• Aus $\mathrm{\exists }i:(p\wedge q_i)$ folgt - für geeignetes $i$ - die Gültigkeit von $p\wedge q_i$, also sowohl $p$ als auch $q_i$. Folglich gilt $q_i$ für dieses $i$, d.h. $\mathrm{\exists }i:q_i$, zusammen mit $p$ also $p\wedge \mathrm{\exists }i: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\vee (q\wedge r)$ und $(p\vee q)\wedge (p\vee 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\vee \mathrm{\forall }i:q_i$ und $\mathrm{\forall }i:(p\vee 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\vee \mathrm{\forall }i:q_i$ wahr als auch $p\vee q_i$ für jedes $i$, also $\mathrm{\forall }i:(p\vee q_i)$.
• Angenommen, $p$ ist falsch.
  • Gilt $p\vee \mathrm{\forall }i:q_i$, so folgt $\mathrm{\forall }i:q_i$. Sei $i$ beliebig. Dann folgt hieraus $q_i$ und erst recht $p\vee q_i$. Da $i$ beliebig war, folgt $\mathrm{\forall }i:(p\vee q_i)$.
  • Gilt $\mathrm{\forall }i:(p\vee q_i)$ und ist $i$ beliebig, so folgt $p\vee q_i$, nach Voraussetzung sogar $q_i$. Da $i$ beliebig war, folgt $\mathrm{\forall }i:q_i$ und erst recht $p\vee \mathrm{\forall }i:q_i$.

Bemerkung

Der vorhergehende Satz läßt sich wieder als Spezialfall hiervon mit zweielementiger Indexmenge auffassen.

Durchschnitt über Symmetrische Differenz

Voraussetzung

$A,B,C$ seien beliebige Mengen.

Behauptung

$A\cap (B\mathrm{△}C)=(A\cap B)\mathrm{△}(A\cap C)$

Beweis

Die Behauptung folgt aus der aussagenlogischen Äquivalenz von $p\wedge (q\leftrightarrow ̸r)$ und $(p\wedge q)\leftrightarrow ̸(p\wedge r)$.

Wikipedia-Verweise

charakteristische Funktion - De Morgansche Gesetze - Distributivgesetz - Restklassenring - Schnittmenge - symmetrische Differenz - Teilmenge - Vereinigungsmenge

---