Elementare Mächtigkeitsbestimmungen
Wir stellen einige häufig verwendete Mengenbildungen noch einmal tabellarisch zusammen.
Definition (grundlegende Mengenbildungen)
Für beliebige Mengen A, B, A1, …, Ak definieren wir:
| A ∪ B | = { a | a ∈ A oder a ∈ B }, |
| A ∩ B | = { a | a ∈ A und a ∈ B }, |
| A − B | = A \ B = { a | a ∈ A und a ∉ B }, |
| A Δ B | = (A − B) ∪ (B − A) = { a | entweder a ∈ A oder a ∈ B }, |
| A × B | = { (a, b) | a ∈ A und b ∈ B }, |
Ak = { (a1, …, ak) | ai ∈ A für alle i = 1, …, k },
A1 × … × Ak = { (a1, …, ak) | a1 ∈ A1, …, ak ∈ Ak },
AB = { f | f : A → B },
℘(A) = { B | B ⊆ A }.
Sind die beteiligten Mengen A, B, A1, …, Ak endlich, so sind auch alle Mengen der Tabelle endlich. Ihre Mächtigkeiten lassen sich mit Hilfe der folgenden Formeln berechnen:
Satz (grundlegende Mächtigkeitsformeln)
Für alle endlichen Mengen A, B, A1, …, Ak gilt:
| |A ∪ B| | = |A| + |B| − |A ∩ B|, |
| |A ∩ B| | = |A| + |B| − |A ∪ B|, |
| |A − B| | = |A| − |A ∩ B|, |
| |A Δ B| | = |A − B| + |B − A| = |A| + |B| − 2 |A ∩ B|, |
| |A × B| | = |A| · |B|, |
|Ak| = |A|k,
|A1 × … × Ak| = |A1| · … · |Ak|,
|AB| = |B||A|,
|℘(A)| = 2|A|.
Beweis
Wir zeigen zunächst:
(+) Sind A, B disjunkt (d. h. A ∩ B = ∅), so gilt |A ∪ B| = |A| + |B|.
Seien also A, B disjunkt und A = { a1, …, an }, B = { b1, … bm } mit jeweils paarweise verschiedenen Elementen. Wir setzen an + j = bj für alle 1 ≤ j ≤ m. Dann ist A ∪ B = { a1, …, an + m } mit paarweise verschiedenen aj, sodass |A ∪ B| = n + m = |A| + |B|. Dies zeigt (+).
Für alle A, B ist A die disjunkte Vereinigung von A − B und A ∩ B, sodass
|A| = |A − B| + |A ∩ B|
nach (+). Dies zeigt die Formel für die Differenz und weiter die Formel für die symmetrische Differenz. Nun ist aber A ∪ B = (A − B) ∪ B mit disjunkten Mengen auf der rechten Seite. Nach (+) ist also
|A ∪ B| = |A − B| + |B| = |A| − |A ∩ B| + |B|.
Damit sind die Formeln für die Vereinigung und den Schnitt bewiesen.
Die Formel |A × B| = |A| · |B| lässt sich durch Induktion nach n = |B| beweisen. Eine Induktion nach k liefert dann die Formeln |Ak| = |A|k und |A1 × … × Ak| = |A1| · … · |Ak|.
Die Formeln |AB| = |B||A| und |℘(A)| = 2|A| ergeben sich aus den oben konstruierten Bijektionen G bzw. F unter Verwendung von |Bk| = |B|k und |{ 0, 1 }k| = |{ 0, 1 }|k = 2k.
Explizit halten wir auch noch eine Verallgemeinerung von (+) samt Umformulierungen fest:
Satz (Zerlegungssatz)
(a) | Seien A1, …, An paarweise disjunkte endliche Mengen, und sei A = A1 ∪ … ∪ An. Dann gilt |A| = |A1| + … + |An|. |
(b) | Seien A, B endlich, und sei f : A → B. Für alle b ∈ B sei Ab = f −1[ { b } ] = { a ∈ A | f (a) = b } die Faser von b unter f. Dann gilt |A| = ∑b ∈ B |Ab|. |
(c) | Ist ≡ eine Äquivalenz auf einer endlichen Menge A, so gilt |A| = ∑[ a ] ∈ A/≡ |[ a ]|. Haben alle Äquivalenzklassen die gleiche Mächtigkeit, so gilt |A| = |A/≡ | · |[ a ]| für alle a ∈ A. |
Der Beweis sei dem Leser überlassen. Weitere Anzahlformeln werden wir in den Übungen und im folgenden Kapitel kennenlernen.