Lemma - Umwandeln beliebiger Vereinigungen von Mengen in eine paarweise disjunkte Vereinigung

• Involvierte Definitionen:
  • Vereinigung von Mengen
  • Paarweise Disjunktheit von Mengen
  • Disjunkte Vereinigung
  • Komplement
  • Differenzmenge
  • Mengensystem
• Veranstaltung: EiS
• Referenz: Eigener Inhalt

⠀

Lemma: Umwandeln beliebiger Vereinigungen von Mengen in eine paarweise disjunkte Vereinigung

Sei eine Grundmenge.
Sei ein Mengensystem über .
Seien .

Dann gilt:

Anmerkung

Wie sieht das eigentlich ausgeschrieben aus?

In der Beschreibung des Lemmas habe ich mich etwas kurz gehalten, um es (vertikal) nicht so aufzublähen. Das holen wir hier jetzt nach. Es gilt:

Kombinationsmöglichkeit

Dieses Lemma lässt sich hervorragend mit Differenzmenge in Halbringen als disjunkte Vereinigung und Differenzmenge in Halbringen als Schnitt von Komplementen kombinieren.

Insgesamt gilt damit:

Sei eine Grundmenge.
Sei ein Halbring über .
Sei eine Vereinigung beliebiger Mengen.

Mit dem Lemma über das umwandeln beliebiger Vereinigungen von Mengen in eine paarweise disjunkte Vereinigung gilt:

Mit den beiden Propositionen Mengendifferenz in Halbringen als Schnitt von Komplementen und Mengendifferenz in Halbringen als disjunkte Vereinigung gilt weiter:

Es existieren paarweise disjunkte , sodass

Das ist hierbei keine Rechenoperation, sondern dient zur Unterscheidung der , die zu den verschiedenen Indizes , bzw. Mengen gehören.

Insbesondere gilt

Beweis

Wir führen den Beweis per vollständiger Induktion über .

Induktionsanfang

Sei . Dann gilt:

Damit hält der IA.

Induktionsvoraussetzung

Die Induktionsannahme

halte für ein .

Induktionsschritt

Es ist zu zeigen, dass

Es gilt:

Umformungsschritt gilt, da der Schnitt von mit den Komplementen aller vorangegangenen Mengen, also , genau diejenigen Mengen, die zwar in , aber nicht in liegen.

Mit der Proposition Differenzmenge als Durchschnitt und der Regeln von De Morgan in der Mengenlehre gilt nämlich:

Umformungsschritte und sind direkte Folgerungen hieraus. Damit hält der Induktionsschritt. Wie vermutet gilt:

Induktionsschluss

Da wir die Aussage im Induktionsschritt zeigen konnten, gilt die Behauptung

für alle , was zu zeigen war.