Einfache Operationen mit Mengen
(Öde für Leser und Autor ist die Einführung der Schnitt- und Vereinigungsmenge und ähnlicher Dinge. Die elementaren Lehrbücher sind voll von Listen von Gleichungen in größter Allgemeinheit. Hierauf wollen wir ganz verzichten, und hinsichtlich der Beweise solcher Gleichungen raten wir dem Leser, bewehrt mit Papier und Bleistift, sich anhand der bekannten Mengen-Diagramme bestehend aus sich überlappenden Kreisen von der Richtigkeit der Identitäten zu überzeugen. In den folgenden Kapiteln wird es wesentlich spannender …)
Beim Umgang mit Mengen tauchen die Operationen der Vereinigung, des Durchschnitts und der Subtraktion (oder Differenzbildung) zweier Mengen besonders häufig auf.
Definition (Vereinigung, Schnitt, Differenz und Disjunktheit)
Seien a und b zwei Mengen. Die Vereinigung a ∪ b [a vereinigt b], der Schnitt a ∩ b [a geschnitten b] und die Differenz a − b [a minus b oder a ohne b] von a und b sind definiert durch:
| a ∪ b | = { x | x ∈ a oder x ∈ b }. |
| a ∩ b | = { x | x ∈ a und x ∈ b }. |
| a − b | = { x | x ∈ a und x ∉ b } = { x ∈ a | x ∉ b }. |
Zwei Mengen a, b heißen disjunkt, falls a ∩ b = ∅.
Die Symbole „lateinischer Klarheit“ ∩ und ∪ tauchen zuerst auf in einer Arbeit von Peano aus dem Jahr 1888, diesmal in Italienisch verfasst:
Peano (1888):
„2. Colla scrittura A ∩ B ∩ C …, ovvero A B C …, intenderemo la massima classe contenuta nelle classi A, B, C, … ossia la classe formata da tutti gli enti che sono ad un tempo A e B e C, ecc. Il segno ∩ si leggerà e…
3. Colla scrittura A ∪ B ∪ C …, intenderemo la minima classe che contiene le classi A, B, C, …, ossia la classe formata dagli enti che sono o A o B o C, ecc. Il segno ∪ si leggerà o…“
Das Algebrabuch von Bartel van der Waerden 1930 hat die Zeichenreihe ∈ , ⊆, ∩, ∪ populär gemacht. Zudem verwendete man lange Zeit Zeichen wie 𝔊, 𝔇 für den Schnitt und 𝔖, 𝔙, 𝔐 für die Vereinigung.
Hausdorff (1914):
„A und B seien zwei beliebige Mengen. Unter ihrer Summe
S = 𝔖(A, B)
verstehen wir die Menge der Elemente, die mindestens einer der beiden Mengen angehören; unter ihrem Durchschnitt
D = 𝔇(A, B)
die Menge der Elemente, die beiden Mengen zugleich angehören.“
Beispiele
| { 1, 2 } ∪ { 1, 3 } | = { 1, 2, 3 } , | { } ∪ { 1 } | = { 1 } , |
| { 1, 2 } ∩ { 1, 3 } | = { 1 } , | { } ∩ { 1 } | = { } , |
| { 1, 2 } − { 1, 3 } | = { 2 } , | { } − { 1 } | = { }. |
Für die Subtraktion a − b ist b ⊆ a nicht vorausgesetzt. Oft findet man auch die Schreibweise a\ b für a − b. (Die englische Lesart „a take away b“ beschreibt sehr gut, was passiert.)
Um die Disjunktheit oder eine disjunkte Vereinigung auszudrücken, stehen einige sprachliche Tricks zur Verfügung, etwa „a zerfällt in b und c“, „a spaltet sich in b und c“ oder „b und c zerlegen a“ für „a = b ∪ c und b ∩ c = ∅“. Ähnliches gilt für Zerfällungen/Spaltungen/Zerlegungen einer Menge a in mehrere paarweise disjunkte Mengen a1, …, an, d. h.
a = (...((a1 ∪ a2) ∪ a3) ∪ … ∪ an − 1) ∪ an, ai ∩ aj = ∅
für alle i ≠ j, 1 ≤ i, j ≤ n. Häufig wird man hier auch fordern, dass keines der ai die leere Menge ist.
Übung
Seien a, b, c Mengen. Dann gilt:
(i) | a − b = a − (a ∩ b), |
(ii) | a − b = a gdw a ∩ b = ∅, |
(iii) | a − b = ∅ gdw a ⊆ b, |
(iv) | a − (b − c) = (a − b) ∪ (a ∩ c), |
(v) | (a − b) − c = a − (b ∪ c). |
Zur Veranschaulichung sind Diagramme hilfreich; zum (strengeren) Beweis kann man sich am Beweis von (iii) im Satz unten orientieren.
Übung (Assoziativgesetze für Vereinigung und Durchschnitt)
Seien a, b, c Mengen. Dann gilt:
(i) | (a ∪ b) ∪ c = a ∪ (b ∪ c), |
(ii) | (a ∩ b) ∩ c = a ∩ (b ∩ c). |
Wir können also Klammern oft weglassen. So schreibt sich etwa
a = (...((a1 ∪ a2) ∪ a3) ∪ … ∪ an − 1) ∪ an
viel übersichtlicher als a = a1 ∪ … ∪ an. Dagegen ist die Differenzbildung nicht assoziativ, wie (iv) und (v) der vorangehenden Übung zeigen.
Definition (relative Komplemente)
Seien a, b Mengen und a ⊆ b. Dann heißt b − a das relative Komplement von a in b. Ist b fixiert, so nennen wir b − a kurz das Komplement von a, und setzen ac = b − a.
Satz (Eigenschaften der relativen Komplemente)
Sei d eine Menge. Weiter seien a, b ⊆ d.
Dann gilt für die relativen Komplemente in d:
(i) | a ∪ ac = d, |
(ii) | a ∩ ac = ∅, |
(iii) | (a ∩ b)c = ac ∪ bc, |
(iv) | (a ∪ b)c = ac ∩ bc. |
Die beiden letzten Aussagen werden auch als de Morgansche Regeln bezeichnet.
Beweis
zu (i) und (ii): Nach Definition von ac = d − a.
zu (iii): (Beweistechnik nach dem bekannten Motto:
If it’s madness, there is some method in it.)
zu ⊆: Sei x ∈ (a ∩ b)c.
Also gilt (1) x ∈ d und (2) x ∉ a oder x ∉ b.
Im ersten Fall von (2) x ∉ a ist wegen (1) x ∈ d − a = ac.
Im zweiten Fall von (2) x ∉ b ist wegen (1) x ∈ d − b = bc.
Also gilt immer: x ∈ ac oder x ∈ bc, also x ∈ ac ∪ bc.
zu ⊇: Sei x ∈ ac ∪ bc. Dann gilt x ∈ d − a oder x ∈ d − b.
Im ersten Fall x ∈ d − a ist x ∈ d − (a ∩ b) wegen d − a ⊆ d − (a ∩ b).
Im zweiten Fall x ∈ d − b ist x ∈ d − (a ∩ b) wegen d − b ⊆ d − (a ∩ b).
Also in beiden Fällen x ∈ d − (a ∩ b) = (a ∩ b)c.
Also gilt (a ∩ b)c ⊆ ac ∪ bc und (a ∩ b)c ⊇ ac ∪ bc.
Nach dem Gleichheitskriterium folgt die Behauptung.
zu (iv): Analog zu (iii).
Spät, aber nicht ungelegen kommen an dieser Stelle die Distributivgesetze.
Übung (Distributivgesetze)
Für alle Mengen a, b, c gilt:
(i) | (a ∪ b) ∩ c = (a ∩ c) ∪ (b ∩ c), |
(ii) | (a ∩ b) ∪ c = (a ∪ c) ∩ (b ∪ c). |
Allgemeinere Formeln zu finden, etwa für (a ∪ b) ∩ (c ∪ d), sei dem Leser als eine Art „open end“-Übung überlassen.
Dem Leser ist vielleicht die Symmetrie zwischen (i) und (ii) aus dem Satz oben, den de Morganschen Regeln und den beiden Distributivgesetzen aufgefallen. Anstelle einer umständlichen Diskussion zitieren wir zur Auflockerung des in dieser Umgebung begrenzt aufregenden Stoffs noch einmal Hausdorff, nämlich über die Dualität von ∪/∩, alles/nichts und ⊆/⊇. Hierbei sind
𝔖(A1, A2, … , Am) = A1 ∪ … ∪ Am,
𝔇(A1, … , Am) = A1 ∩ … ∩ Am,
A = Ac = M − A.
Das Zeichen „+“ steht für die disjunkte Vereinigung.
Hausdorff (1914):
„Sind A1, … , Am Teilmengen einer Menge M und A1, … , Am ihre Komplemente in M, also
M = Ai + Ai
so ist
M = 𝔖(A1, A2, … , Am) + 𝔇(A1, … , Am)
= 𝔇(A1, A2, … , Am) + 𝔖(A1, … , Am);
denn die Elemente von M gehören entweder mindestens einem Ai oder keinem, d. h. entweder der Summe der Ai oder dem Durchschnitt der Ai an, und das gleiche gilt, wenn man die Ai mit den Ai vertauscht. Wir können diese Formeln kurz so aussprechen: das Komplement einer Summe ist der Durchschnitt der Komplemente, das Komplement eines Durchschnitts die Summe der Komplemente. Ist also P eine Menge, die aus den Mengen Ai durch wiederholte Summen- und Durchschnittsbildung entsteht, so erhält man ihr Komplement P, indem man die Ai durch ihre Komplemente Ai, das Zeichen 𝔖 durch 𝔇 und das Zeichen 𝔇 durch 𝔖 ersetzt. Da ferner aus P = Q, P ⊂ Q, P ⊃ Q resp. P = Q, P ⊃ Q, P ⊂ Q folgt, so bleibt jede Gleichung zwischen Mengen richtig, wenn man alle Mengen durch ihre Komplemente ersetzt und die Zeichen 𝔖 und 𝔇 vertauscht; jede Ungleichung bleibt richtig, wenn man außerdem noch die Zeichen ⊂ und ⊃ vertauscht [Dualitätsprinzip]. Eine identische, d. h. für beliebige Mengen richtige Relation liefert eine zweite solche auch ohne Übergang zu den Komplementen, also durch bloße Vertauschung der Zeichen 𝔖, 𝔇 und eventuell der beiden Ungleichheitszeichen. Z. B. folgt auf diese Weise die zweite Formel des assoziativen oder distributiven Gesetzes unmittelbar aus der ersten. Als Beispiel für eine Ungleichung zitieren wir die einfache A ⊆ 𝔖(A, B), aus der durch Dualität A ⊇ 𝔇(A, B) folgt.“
Weitere einfache Operationen mit Mengen und zugehörige Gleichungen, die gelegentlich in der Mengenlehre und anderswo auftauchen, sind die Themen der folgenden beiden Übungen. Hierzu:
Definition (symmetrische Differenz)
Seien a, b Mengen. Dann ist die symmetrische Differenz von a und b, in Zeichen a Δ b, definiert durch:
a Δ b = (a − b) ∪ (b − a).
Ist ∩ ein „und“, ∪ ein „oder“, so ist Δ ein „entweder oder“.
Übung (symmetrische Differenz)
Für alle Mengen a, b, c gilt:
(i) | a Δ b = b Δ a = (a ∪ b) − (a ∩ b), |
(ii) | a Δ (b Δ c) = (a Δ b) Δ c, |
(iii) | (a Δ b) ∩ c = (a ∩ c) Δ (b ∩ c). |
In der nächsten Übung betrachten wir geschachtelte Anwendungen der Differenzenbildung. Wir vereinbaren zur Vereinfachung der Notation Rechtsklammerung, d. h. a − b − c = a − (b − c), a − b − c − d = a − (b − c − d), usw.
Differenzenketten sind von Hausdorff untersucht worden und spielen in der deskriptiven Mengenlehre eine Rolle. Hier sind sie lediglich ein hübsches Übungsmaterial, das viel attraktiver ist als etwa die Distributivgesetze:
Übung (Differenzenketten aus absteigenden Mengen)
Sei n ∈ ℕ, und seien a1, …, an Mengen mit a1 ⊇ a2 ⊇ … ⊇ an.
Dann gilt:
(i) | Für n gerade: a1 − … − an = (a1 − a2) ∪ … ∪ (an − 1 − an). |
(ii) | Für n ungerade: a1 − … − an = (a1 − a2) ∪ … ∪ (an − 2 − an − 1) ∪ an. |
Differenzenkette der Länge 4.
Der Leser kann sich also Differenzenketten beliebiger Länge visualisieren: Man wirft einen Stein ins Wasser und sammelt, je nachdem ob die Länge n der Kette gerade ist oder ungerade, die Ringe bestehend aus Wellenbergen oder Wellentälern.