Formelsammlung Mathematik: Mengenlehre

Aufzählende Angabe

${\displaystyle a\in \{x_{1},\ldots ,x_{n}\}\;\;{:\Longleftrightarrow }\;\;a=x_{1}\lor a=x_{2}\lor \ldots \lor a=x_{n}}$

Beschreibende Angabe, unbeschränkt

${\displaystyle a\in \{x\mid P(x)\}\;\;{:\Longleftrightarrow }\;\;P(a)}$

Beschreibende Angabe, beschränkt

${\displaystyle \{x\in A\mid P(x)\}:=\{x\mid x\in A\wedge P(x)\}}$

Beschreibende Angabe, Kurzschreibweise für Bildmengen

${\displaystyle \{f(x)\mid P(x)\}:=\{y\mid \exists x(y=f(x)\wedge P(x))\}}$

Teilmenge

${\displaystyle A\subseteq B\;\;{:\Longleftrightarrow }\;\;\forall x\,(x\in A\implies x\in B)}$

Gleichheit

${\displaystyle A=B\;\;{:\Longleftrightarrow }\;\;\forall x\,(x\in A\iff x\in B)}$

Vereinigungsmenge

${\displaystyle A\cup B:=\{x\mid x\in A\lor x\in B\},}$

${\displaystyle \bigcup _{i\in I}A_{i}:=\{x\mid \exists i{\in }I\,(x\in A_{i})\}}$

Schnittmenge

${\displaystyle A\cap B:=\{x\mid x\in A\land x\in B\},}$

${\displaystyle \bigcap _{i\in I}A_{i}:=\{x\mid \forall i{\in }I\,(x\in A_{i})\}}$

Differenzmenge (relatives Komplement)

${\displaystyle A\setminus B:=\{x\mid x\in A\land x\notin B\}}$

Komplementärmenge

${\displaystyle {\overline {A}}:=G\setminus A}$

${\displaystyle G}$: Grundmenge

Symmetrische Differenz

${\displaystyle A\triangle B:=\{x\mid x\in A\oplus x\in B\}}$

Kartesisches Produkt

${\displaystyle A\times B:=\{(x,y)\mid x\in A\land y\in B\}}$

Potenzmenge

${\displaystyle {\mathcal {P}}(A):=\{U\mid U\subseteq A\}}$

Disjunkte Vereinigung

${\displaystyle A\sqcup B:=(\{1\}\times A)\cup (\{2\}\times B),}$

${\displaystyle \bigsqcup _{i\in I}A_{i}:=\bigcup _{i\in I}\,(\{i\}\times A_{i})}$

Schnitt	Vereinigung
${\displaystyle A\cap B=B\cap A}$	${\displaystyle A\cup B=B\cup A}$	Kommutativgesetze
${\displaystyle A\cap (B\cap C)=(A\cap B)\cap C}$	${\displaystyle A\cup (B\cup C)=(A\cup B)\cup C}$	Assoziativgesetze
${\displaystyle A\cap A=A}$	${\displaystyle A\cup A=A}$	Idempotenzgesetze
${\displaystyle A\cap G=A}$	${\displaystyle A\cup \{\}=A}$	Neutralitätsgesetze
${\displaystyle A\cap \{\}=\{\}}$	${\displaystyle A\cup G=G}$	Extremalgesetze
${\displaystyle A\cap {\overline {A}}=\{\}}$	${\displaystyle A\cup {\overline {A}}=G}$	Komplementärgesetze
${\displaystyle {\overline {A\cap B}}={\overline {A}}\cup {\overline {B}}}$	${\displaystyle {\overline {A\cup B}}={\overline {A}}\cap {\overline {B}}}$	De Morgansche Gesetze
${\displaystyle A\cap (A\cup B)=A}$	${\displaystyle A\cup (A\cap B)=A}$	Absorptionsgesetze

${\displaystyle G}$: Grundmenge

Distributivgesetze:

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

Involution:

${\displaystyle {\overline {\overline {A}}}=A}$

Nr.	dcba	Mengenoperation	Venn-Diagramm	logische Funktion	Relation
0	0000	${\displaystyle \{\}}$ (leere Menge)		${\displaystyle 0}$ (Kontradiktion)	${\displaystyle G=\{\}}$
1	0001	${\displaystyle {\overline {A\cup B}}}$		${\displaystyle {\overline {A\lor B}}}$ (NOR)	${\displaystyle A\cup B=\{\}}$
2	0010	${\displaystyle B\setminus A}$		${\displaystyle B\land {\overline {A}}}$	${\displaystyle B\setminus A=G}$
3	0011	${\displaystyle {\overline {A}}}$		${\displaystyle {\overline {A}}}$	${\displaystyle A=\{\}}$
4	0100	${\displaystyle A\setminus B}$ (Differenz)		${\displaystyle A\land {\overline {B}}}$	${\displaystyle A\setminus B=G}$
5	0101	${\displaystyle {\overline {B}}}$		${\displaystyle {\overline {B}}}$	${\displaystyle B=\{\}}$
6	0110	${\displaystyle A\triangle B}$ (symmetrische Differenz)		${\displaystyle A\oplus B}$ (Kontravalenz)	${\displaystyle A\triangle B=G}$
7	0111	${\displaystyle {\overline {A\cap B}}}$		${\displaystyle {\overline {A\land B}}}$ (NAND)	${\displaystyle A\cap B=\{\}}$
8	1000	${\displaystyle A\cap B}$ (Schnitt)		${\displaystyle A\land B}$ (Konjunktion)	${\displaystyle A\cap B=G}$
9	1001	${\displaystyle {\overline {A\triangle B}}}$		${\displaystyle A\Leftrightarrow B}$ (Äquivalenz)	${\displaystyle A=B}$
10	1010	${\displaystyle B}$ (Projektion)		${\displaystyle B}$ (Projektion)	${\displaystyle B=G}$
11	1011	${\displaystyle {\overline {A}}\cup B}$		${\displaystyle A\Rightarrow B}$ (Implikation)	${\displaystyle A\subseteq B}$
12	1100	${\displaystyle A}$ (Projektion)		${\displaystyle A}$ (Projektion)	${\displaystyle A=G}$
13	1101	${\displaystyle {\overline {B}}\cup A}$		${\displaystyle B\Rightarrow A}$	${\displaystyle B\subseteq A}$
14	1110	${\displaystyle A\cup B}$ (Vereinigung)		${\displaystyle A\lor B}$ (Disjunktion)	${\displaystyle A\cup B=G}$
15	1111	${\displaystyle G}$ (Grundmenge)		${\displaystyle 1}$ (Tautologie)	${\displaystyle 1}$

Die Spalten dieser Tabelle hängen wie folgt zusammen. Sei ${\displaystyle k\in \{0,1,\ldots ,15\}}$ die Nr. der Zeile. Es gibt je Zeile eine Mengenoperation ${\displaystyle f_{k}(A,B)}$, eine logische Funktion ${\displaystyle L_{k}(A,B)}$ und eine Relation ${\displaystyle R_{k}(A,B)}$. Dabei gilt

${\displaystyle f_{k}(A,B)=\{x\mid L_{k}(x\in A,x\in B)\}}$

und

${\displaystyle R_{k}(A,B)\iff f_{k}(A,B)=G\iff G\subseteq f_{k}(A,B)\iff \forall x\in G\,[L_{k}(x\in A,x\in B)].}$

Außerdem gilt

${\displaystyle f_{k}(A,B)=G\iff {\overline {f_{k}(A,B)}}=\{\}.}$

Die Binärzahl kodiert die Wertetabelle der logischen Funktion und kodiert außerdem die Partition von ${\displaystyle G}$ in die disjunkten Bereiche

${\displaystyle (A\cap B,\quad A\setminus B,\quad B\setminus A,\quad {\overline {A\cup B}}).}$

Eine Stelle der Binärzahl gibt dabei an, ob der dazugehörige Bereich im Venn-Diagramm rot ausgefüllt ist.

Zerlegung der Gleichheit:

${\displaystyle A=B\iff A\subseteq B\land B\subseteq A}$

Umschreibung der Teilmengenrelation:

${\displaystyle A\subseteq B\iff A\cap B=A\iff A\cup B=B\iff A\setminus B=\{\}}$

Kontraposition:

${\displaystyle A\subseteq B\iff {\overline {B}}\subseteq {\overline {A}}}$

Kontraposition bei Gleichheit:

${\displaystyle A=B\iff {\overline {A}}={\overline {B}}}$

1. ${\displaystyle \bigcup _{(i,j)\in I\times J}(A_{i}\cap B_{j})={\bigg (}\bigcup _{i\in I}A_{i}{\bigg )}\cap {\bigg (}\bigcup _{j\in J}B_{j}{\bigg )}}$
2. ${\displaystyle \bigcap _{(i,j)\in I\times J}(A_{i}\cup B_{j})={\bigg (}\bigcap _{i\in I}A_{i}{\bigg )}\cup {\bigg (}\bigcap _{j\in J}B_{j}{\bigg )}}$
3. ${\displaystyle \bigcup _{(i,j)\in I\times J}(A_{i}\times B_{j})={\bigg (}\bigcup _{i\in I}A_{i}{\bigg )}\times {\bigg (}\bigcup _{j\in J}B_{j}{\bigg )}}$
4. ${\displaystyle I\times J\neq \{\}\implies \bigcup _{(i,j)\in I\times J}(A_{i}\cup B_{j})={\bigg (}\bigcup _{i\in I}A_{i}{\bigg )}\cup {\bigg (}\bigcup _{j\in J}B_{j}{\bigg )}}$
5. ${\displaystyle I\times J\neq \{\}\implies \bigcap _{(i,j)\in I\times J}(A_{i}\cap B_{j})={\bigg (}\bigcap _{i\in I}A_{i}{\bigg )}\cap {\bigg (}\bigcap _{j\in J}B_{j}{\bigg )}}$
6. ${\displaystyle I\times J\neq \{\}\implies \bigcap _{(i,j)\in I\times J}(A_{i}\times B_{j})={\bigg (}\bigcap _{i\in I}A_{i}{\bigg )}\times {\bigg (}\bigcap _{j\in J}B_{j}{\bigg )}}$
7. ${\displaystyle \bigcup _{(i,j)\in I\times I}(A_{i}\cup B_{j})=\bigcup _{i\in I}\,(A_{i}\cup B_{i})}$
8. ${\displaystyle \bigcap _{(i,j)\in I\times I}(A_{i}\cap B_{j})=\bigcap _{i\in I}\,(A_{i}\cap B_{i})}$
9. ${\displaystyle \bigcup _{i\in I}\,(A_{i}\cup B_{i})={\bigg (}\bigcup _{i\in I}A_{i}{\bigg )}\cup {\bigg (}\bigcup _{i\in I}B_{i}{\bigg )}}$
10. ${\displaystyle \bigcap _{i\in I}\,(A_{i}\cap B_{i})={\bigg (}\bigcap _{i\in I}A_{i}{\bigg )}\cap {\bigg (}\bigcap _{i\in I}B_{i}{\bigg )}}$
11. ${\displaystyle \bigcup _{(i,j)\in I\times J}A_{ij}=\bigcup _{i\in I}\bigcup _{j\in J}A_{ij}=\bigcup _{j\in J}\bigcup _{i\in I}A_{ij}}$
12. ${\displaystyle \bigcap _{(i,j)\in I\times J}A_{ij}=\bigcap _{i\in I}\bigcap _{j\in J}A_{ij}=\bigcap _{j\in J}\bigcap _{i\in I}A_{ij}}$
13. ${\displaystyle \bigcup _{i\in I}\bigcap _{j\in J}A_{ij}\subseteq \bigcap _{j\in J}\bigcup _{i\in I}A_{ij}}$

Verallgemeinerte De Morgansche Gesetze:

1. ${\displaystyle {\overline {\bigcup _{i\in I}A_{i}}}=\bigcap _{i\in I}{\overline {A}}_{i}}$
2. ${\displaystyle {\overline {\bigcap _{i\in I}A_{i}}}=\bigcup _{i\in I}{\overline {A}}_{i}}$

Verallgemeinerte Distributivgesetze:

1. ${\displaystyle M\cap \bigcup _{i\in I}A_{i}=\bigcup _{i\in I}\,(M\cap A_{i})}$
2. ${\displaystyle M\cup \bigcap _{i\in I}A_{i}=\bigcap _{i\in I}\,(M\cup A_{i})}$

Verallgemeinerte Idempotenzgesetze:

1. ${\displaystyle I\neq \{\}\implies \bigcup _{i\in I}A=A}$
2. ${\displaystyle I\neq \{\}\implies \bigcap _{i\in I}A=A}$

1. ${\displaystyle A\setminus A=\{\}}$
2. ${\displaystyle A\setminus \{\}=A}$
3. ${\displaystyle \{\}\setminus A=\{\}}$
4. ${\displaystyle (A\setminus B)\setminus C=A\setminus (B\cup C)}$
5. ${\displaystyle A\setminus (B\setminus C)=(A\setminus B)\cup (A\cap C)}$
6. ${\displaystyle A\setminus (A\setminus B)=A\cap B}$
7. ${\displaystyle (A\setminus B)\cap M=(A\cap M)\setminus B=A\cap (M\setminus B)}$
8. ${\displaystyle (A\setminus B)\cup M=(A\cup M)\setminus (B\setminus M)}$
9. ${\displaystyle A\setminus B=A\cap {\overline {B}}}$
10. ${\displaystyle {\overline {A\setminus B}}={\overline {A}}\cup B}$
11. ${\displaystyle (A\setminus B)\cup (A\cap B)=A}$
12. ${\displaystyle (A\setminus B)\cap (A\cap B)=\{\}}$

Distributivgesetze:

1. ${\displaystyle (A\cup B)\setminus M=(A\setminus M)\cup (B\setminus M)}$
2. ${\displaystyle (A\cap B)\setminus M=(A\setminus M)\cap (B\setminus M)}$

Pseudo-Distributivgesetze:

1. ${\displaystyle M\setminus (A\cup B)=(M\setminus A)\cap (M\setminus B)}$
2. ${\displaystyle M\setminus (A\cap B)=(M\setminus A)\cup (M\setminus B)}$

1. ${\displaystyle A\triangle B=(A\cup B)\setminus (A\cap B)}$
2. ${\displaystyle A\triangle B=(A\setminus B)\cup (B\setminus A)}$
3. ${\displaystyle A\triangle B=B\triangle A}$
4. ${\displaystyle (A\triangle B)\triangle C=A\triangle (B\triangle C)}$
5. ${\displaystyle A\triangle \{\}=A}$
6. ${\displaystyle A\triangle A=\{\}}$
7. ${\displaystyle {\overline {A\triangle B}}=(A\cap B)\cup ({\overline {A}}\cap {\overline {B}})=({\overline {A}}\cup B)\cap ({\overline {B}}\cup A)}$

Distributivgesetz:

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

Distributivgesetze:

1. ${\displaystyle M\times (A\cup B)=(M\times A)\cup (M\times B)}$
2. ${\displaystyle M\times (A\cap B)=(M\times A)\cap (M\times B)}$
3. ${\displaystyle M\times (A\setminus B)=(M\times A)\setminus (M\times B)}$
4. ${\displaystyle (A\cup B)\times M=(A\times M)\cup (B\times M)}$
5. ${\displaystyle (A\cap B)\times M=(A\times M)\cap (B\times M)}$
6. ${\displaystyle (A\setminus B)\times M=(A\times M)\setminus (B\times M)}$

Weiterhin gilt:

1. ${\displaystyle (A_{1}\times B_{1})\cap (A_{2}\times B_{2})=(A_{1}\cap A_{2})\times (B_{1}\cap B_{2})}$
2. ${\displaystyle (A_{1}\times B_{1})\cup (A_{2}\times B_{2})\subseteq (A_{1}\cup A_{2})\times (B_{1}\cup B_{2})}$
3. ${\displaystyle A\times B=\{\}\iff A=\{\}\lor B=\{\}}$

1. ${\displaystyle A\subseteq B\implies |A|\leq |B|}$
2. ${\displaystyle |A\cup B|\leq |A|+|B|}$
3. ${\displaystyle {\Big |}\bigcup _{k=1}^{n}A_{k}{\Big |}\leq \sum _{k=1}^{n}|A_{k}|}$
4. ${\displaystyle |A\times B|=|A|\,|B|}$
5. ${\displaystyle |A^{n}|=|A|^{n}}$
6. ${\displaystyle |B^{A}|=|B|^{|A|}}$
7. ${\displaystyle |{\mathcal {P}}(A)|=2^{|A|}}$

Prinzip von Inklusion und Exklusion:

1. ${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}$
2. ${\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|}$