Formelsammlung Mathematik: Mengenlehre

↑ Formelsammlung Mathematik

→ Mächtigkeiten

Definitionen

Aufzählende Angabe

$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

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

Beschreibende Angabe, beschränkt

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

Beschreibende Angabe, Kurzschreibweise für Bildmengen

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

Teilmenge

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

Gleichheit

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

Vereinigungsmenge

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

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

Schnittmenge

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

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

Differenzmenge (relatives Komplement)

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

Komplementärmenge

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

$G$: Grundmenge

Symmetrische Differenz

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

Kartesisches Produkt

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

Potenzmenge

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

Disjunkte Vereinigung

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

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

Boolesche Algebra

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

$G$: Grundmenge

Distributivgesetze:

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

Involution:

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

Zweistellige Mengenoperationen

A	B	Wert
0	0	a
0	1	b
1	0	c
1	1	d

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

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

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

und

$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

$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 $G$ in die disjunkten Bereiche

$(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.

Teilmengenrelation

Zerlegung der Gleichheit:

$A=B\iff A\subseteq B\land B\subseteq A$

Umschreibung der Teilmengenrelation:

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

Kontraposition:

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

Kontraposition bei Gleichheit:

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

Vereinigung und Schnitt

1. $\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. $\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. $\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. $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. $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. $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. $\bigcup _{(i,j)\in I\times I}(A_{i}\cup B_{j})=\bigcup _{i\in I}\,(A_{i}\cup B_{i})$
8. $\bigcap _{(i,j)\in I\times I}(A_{i}\cap B_{j})=\bigcap _{i\in I}\,(A_{i}\cap B_{i})$
9. $\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. $\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. $\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. $\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. $\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. ${\overline {\bigcup _{i\in I}A_{i}}}=\bigcap _{i\in I}{\overline {A}}_{i}$
2. ${\overline {\bigcap _{i\in I}A_{i}}}=\bigcup _{i\in I}{\overline {A}}_{i}$

Verallgemeinerte Distributivgesetze:

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

Verallgemeinerte Idempotenzgesetze:

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

Differenzmenge

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

Distributivgesetze:

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

Pseudo-Distributivgesetze:

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

Symmetrische Differenz

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

Distributivgesetz:

$M\cap (A\triangle B)=(M\cap A)\triangle (M\cap B)$

Kartesisches Produkt

Distributivgesetze:

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

Weiterhin gilt:

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

Endliche Mengen

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

Prinzip von Inklusion und Exklusion:

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