Voraussetzung

${\displaystyle A,\ B,\ C}$ seien beliebige Mengen.

Behauptung

${\displaystyle A\cap (B\cup C)=(A\cap B)\cup (A\cap C)}$

Beweis

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

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

Alternativ: Es gilt

${\displaystyle x\in A\cap (B\cup C)\iff x\in A\land (x\in B\lor x\in C)}$

und

${\displaystyle 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 ${\displaystyle \land }$ über ${\displaystyle \lor }$, d.h. der allgemeinen Äquivalenz von ${\displaystyle p\land (q\lor r)}$ und ${\displaystyle (p\land q)\lor (p\land r)}$.

Voraussetzung

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

Behauptung

${\displaystyle 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 ${\displaystyle x}$ äquivalent zu ${\displaystyle x\in A\land \exists i\in I\colon x\in B_{i}}$, für die rechte dagegen zu ${\displaystyle \exists i\in I\colon (x\in A\land x\in B_{i})}$. Aber auf prädikatenlogischer Ebene gilt bereits die allgemeine Äquivalenz von ${\displaystyle p\land \exists i\colon q_{i}}$ mit ${\displaystyle \exists i\colon (p\land q_{i})}$ - hier mit ${\displaystyle p}$ für ${\displaystyle x\in A}$ und ${\displaystyle q_{i}}$ für ${\displaystyle i\in I\land x\in B_{i}}$:

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

Voraussetzung

${\displaystyle A,\ B,\ C}$ seien beliebige Mengen.

Behauptung

${\displaystyle A\cup (B\cap C)}$ ${\displaystyle =}$ ${\displaystyle (A\cup B)\cap (A\cup C)}$

Beweis

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

Voraussetzung

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

Behauptung

${\displaystyle 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 ${\displaystyle p\lor \forall i\colon q_{i}}$ und ${\displaystyle \forall i\colon (p\lor q_{i})}$ - hier mit ${\displaystyle x\in A}$ für ${\displaystyle p}$ sowie ${\displaystyle i\in I\Rightarrow x\in B_{i}}$: für q

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

Bemerkung

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

Voraussetzung

${\displaystyle A,\ B,\ C}$ seien beliebige Mengen.

Behauptung

${\displaystyle A\cap (B\triangle C)=(A\cap B)\triangle (A\cap C)}$

Beweis

Die Behauptung folgt aus der aussagenlogischen Äquivalenz von ${\displaystyle p\land (q\not \leftrightarrow r)}$ und ${\displaystyle (p\land q)\not \leftrightarrow (p\land r)}$.