Beweisarchiv: Mengenlehre: Mengenoperation: De Morgansche Regeln für Mengen

Sei $X$ eine Menge und seien $A_i$ Mengen für $i\in I$ mit beliebiger Indexmenge $I$. Dann gelten die folgenden Gleichungen:

• $X\setminus \left(\bigcup _{i\in I}{A}_i\right)=\bigcap _{i\in I}(X\setminus A_i)$
• $X\setminus \left(\bigcap _{i\in I}{A}_i\right)=\bigcup _{i\in I}(X\setminus A_i)$

Spezialfall

Seien $A,B,C$ drei Mengen. Dann gelten die beiden Gleichungen

(a) $A\setminus (B\cup C)=(A\setminus B)\cap (A\setminus C)$ und
(b) $A\setminus (B\cap C)=(A\setminus B)\cup (A\setminus C)$.

Beweis

$\begin{array}{cc}X\setminus \left(\bigcup _{i\in I}{A}_i\right)& \stackrel{(1)}{=}\{x\in X\mid x\notin \bigcup _{i\in I}{A}_i\}\\ & \stackrel{(2)}{=}\{x\in X\mid \mathrm{\neg }(x\in \bigcup _{i\in I}{A}_i)\}\\ & \stackrel{(3)}{=}\{x\in X\mid \mathrm{\neg }(\mathrm{\exists }i\in I:x\in A_i)\}\\ & \stackrel{(4)}{=}\{x\in X\mid \mathrm{\forall }i\in I:\mathrm{\neg }(x\in A_i)\}\\ & \stackrel{(2)}{=}\{x\in X\mid \mathrm{\forall }i\in I:x\notin A_i\}\\ & \stackrel{(1)}{=}\{x\in X\mid \mathrm{\forall }i\in I:x\in X\setminus A_i\}\\ & \stackrel{(5)}{=}\bigcap _{i\in I}(X\setminus A_i)\end{array}$

(1): Definition der mengentheoretischen Differenz

(2): Definition von $\notin$

(3): Definition der Vereinigungsmenge

(4): Allaussage ist äquivalent zu verneinter Existenzaussage

(5): Definition der Schnittmenge

Analog gilt für den zweiten Teil:

$\begin{array}{cc}X\setminus \left(\bigcap _{i\in I}{A}_i\right)& =\{x\in X\mid x\notin \bigcap _{i\in I}{A}_i\}\\ & =\{x\in X\mid \mathrm{\neg }(x\in \bigcap _{i\in I}{A}_i)\}\\ & =\{x\in X\mid \mathrm{\neg }(\mathrm{\forall }i\in I:x\in A_i)\}\\ & =\{x\in X\mid \mathrm{\exists }i\in I:\mathrm{\neg }(x\in A_i)\}\\ & =\{x\in X\mid \mathrm{\exists }i\in I:x\notin A_i\}\\ & =\{x\in X\mid \mathrm{\exists }i\in I:x\in X\setminus A_i\}\\ & =\bigcup _{i\in I}(X\setminus A_i)\end{array}$

Beweis des Spezialfalls

(a) Die Menge links des Gleichheitszeichens enthält alle Elemente von $A$, die keine Elemente von $B$ oder $C$ sind, also $x\in A\wedge x\notin B\wedge x\notin C$. Die rechte Menge enthält alle Elemente, für die gilt $x\in A\wedge x\notin B\wedge x\in A\wedge x\notin C$ also ebenfalls $x\in A\wedge x\notin B\wedge x\notin C$, und damit ist die Gleichheit gezeigt.
(b) Die Menge links des Gleichheitszeichens enthält alle Elemente von $A$, die keine Elemente von $B$ und $C$ sind, also $x\in A\wedge (x\notin B\vee x\notin C)$. Die rechte Menge enthält alle Elemente, für die gilt $(x\in A\wedge x\notin B)\vee (x\in A\wedge x\notin C)$, also ebenfalls $x\in A\wedge (x\notin B\vee x\notin C)$, womit die Gleichheit gezeigt ist