Formelsammlung Mathematik: Mengenlehre

→ Mächtigkeiten

Definitionen

Aufzählende Angabe

$a\in \{x_1,\dots ,x_n\}:⟺a=x_1\vee a=x_2\vee \dots \vee a=x_n$

Beschreibende Angabe, unbeschränkt

$a\in \{x\mid P(x)\}:⟺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 \mathrm{\exists }x(y=f(x)\wedge P(x))\}$

Teilmenge

$A\subseteq B:⟺\mathrm{\forall }x(x\in A⟹x\in B)$

Gleichheit

$A=B:⟺\mathrm{\forall }x(x\in A⟺x\in B)$

Vereinigungsmenge

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

$\bigcup _{i\in I}{A}_i:=\{x\mid \mathrm{\exists }i\in I(x\in A_i)\}$

Schnittmenge

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

$\bigcap _{i\in I}{A}_i:=\{x\mid \mathrm{\forall }i\in I(x\in A_i)\}$

Differenzmenge (relatives Komplement)

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

Komplementärmenge

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

$G$: Grundmenge

Symmetrische Differenz

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

Kartesisches Produkt

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

Potenzmenge

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

Disjunkte Vereinigung

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

$\underset{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 \bar{A}=\{\}$	$A\cup \bar{A}=G$	Komplementärgesetze
$\overline{A\cap B}=\bar{A}\cup \bar{B}$	$\overline{A\cup B}=\bar{A}\cap \bar{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{\stackrel{‾}{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\vee B}$ (NOR)	$A\cup B=\{\}$
2	0010	$B\setminus A$		$B\wedge \bar{A}$	$B\setminus A=G$
3	0011	$\bar{A}$		$\bar{A}$	$A=\{\}$
4	0100	$A\setminus B$ (Differenz)		$A\wedge \bar{B}$	$A\setminus B=G$
5	0101	$\bar{B}$		$\bar{B}$	$B=\{\}$
6	0110	$A\mathrm{△}B$ (symmetrische Differenz)		$A\oplus B$ (Kontravalenz)	$A\mathrm{△}B=G$
7	0111	$\overline{A\cap B}$		$\overline{A\wedge B}$ (NAND)	$A\cap B=\{\}$
8	1000	$A\cap B$ (Schnitt)		$A\wedge B$ (Konjunktion)	$A\cap B=G$
9	1001	$\overline{A\mathrm{△}B}$		$A\iff B$ (Äquivalenz)	$A=B$
10	1010	$B$ (Projektion)		$B$ (Projektion)	$B=G$
11	1011	$\bar{A}\cup B$		$A\Rightarrow B$ (Implikation)	$A\subseteq B$
12	1100	$A$ (Projektion)		$A$ (Projektion)	$A=G$
13	1101	$\bar{B}\cup A$		$B\Rightarrow A$	$B\subseteq A$
14	1110	$A\cup B$ (Vereinigung)		$A\vee 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,\dots ,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)⟺f_k(A,B)=G⟺G\subseteq f_k(A,B)⟺\mathrm{\forall }x\in G[L_k(x\in A,x\in B)].$

Außerdem gilt

$f_k(A,B)=G⟺\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,A\setminus B,B\setminus A,\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⟺A\subseteq B\wedge B\subseteq A$

Umschreibung der Teilmengenrelation:

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

Kontraposition:

$A\subseteq B⟺\bar{B}\subseteq \bar{A}$

Kontraposition bei Gleichheit:

$A=B⟺\bar{A}=\bar{B}$

Vereinigung und Schnitt

1. $\bigcup _{(i,j)\in I\times J}(A_i\cap B_j)=\left(\bigcup _{i\in I}{A}_i\right)\cap \left(\bigcup _{j\in J}{B}_j\right)$
2. $\bigcap _{(i,j)\in I\times J}(A_i\cup B_j)=\left(\bigcap _{i\in I}{A}_i\right)\cup \left(\bigcap _{j\in J}{B}_j\right)$
3. $\bigcup _{(i,j)\in I\times J}(A_i\times B_j)=\left(\bigcup _{i\in I}{A}_i\right)\times \left(\bigcup _{j\in J}{B}_j\right)$
4. $I\times J\ne \{\}⟹\bigcup _{(i,j)\in I\times J}(A_i\cup B_j)=\left(\bigcup _{i\in I}{A}_i\right)\cup \left(\bigcup _{j\in J}{B}_j\right)$
5. $I\times J\ne \{\}⟹\bigcap _{(i,j)\in I\times J}(A_i\cap B_j)=\left(\bigcap _{i\in I}{A}_i\right)\cap \left(\bigcap _{j\in J}{B}_j\right)$
6. $I\times J\ne \{\}⟹\bigcap _{(i,j)\in I\times J}(A_i\times B_j)=\left(\bigcap _{i\in I}{A}_i\right)\times \left(\bigcap _{j\in J}{B}_j\right)$
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)=\left(\bigcup _{i\in I}{A}_i\right)\cup \left(\bigcup _{i\in I}{B}_i\right)$
10. $\bigcap _{i\in I}(A_i\cap B_i)=\left(\bigcap _{i\in I}{A}_i\right)\cap \left(\bigcap _{i\in I}{B}_i\right)$
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}{\bar{A}}_i$
2. $\overline{\bigcap _{i\in I}{A}_i}=\bigcup _{i\in I}{\bar{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\ne \{\}⟹\bigcup _{i\in I}A=A$
2. $I\ne \{\}⟹\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 \bar{B}$
10. $\overline{A\setminus B}=\bar{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\mathrm{△}B=(A\cup B)\setminus (A\cap B)$
2. $A\mathrm{△}B=(A\setminus B)\cup (B\setminus A)$
3. $A\mathrm{△}B=B\mathrm{△}A$
4. $(A\mathrm{△}B)\mathrm{△}C=A\mathrm{△}(B\mathrm{△}C)$
5. $A\mathrm{△}\{\}=A$
6. $A\mathrm{△}A=\{\}$
7. $\overline{A\mathrm{△}B}=(A\cap B)\cup (\bar{A}\cap \bar{B})=(\bar{A}\cup B)\cap (\bar{B}\cup A)$

Distributivgesetz:

$M\cap (A\mathrm{△}B)=(M\cap A)\mathrm{△}(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=\{\}⟺A=\{\}\vee B=\{\}$

Endliche Mengen

1. $A\subseteq B⟹|A|\le |B|$
2. $|A\cup B|\le |A|+|B|$
3. $\left|\bigcup _{k=1}^n{A}_k\right|\le \sum _{k=1}^n|A_k|$
4. $|A\times B|=|A||B|$
5. $|A^n|=|A{|}^n$
6. $|B^A|=|B{|}^{|A|}$
7. $|𝒫(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|$