Mengenlehre-Beweise verstehen: Die 3-Schritte-Methode, die immer funktioniert

Warum scheitern 90% an Mengenbeweisen?

Du sitzt in der Klausur. Aufgabe: "Beweisen Sie: $u \subseteq v \Rightarrow u \cup v = v$".

Dein Kopf: Leere.

Das Problem ist nicht, dass du nicht weißt, was Teilmengen sind. Das Problem: Du weißt nicht, wie man formal aufschreibt, was offensichtlich ist.

Die Anatomie eines Mengenbeweises

Jeder Mengenbeweis folgt demselben Schema:

Formell: Ein Beweis ist eine Kette logischer Implikationen von der Voraussetzung zur Behauptung.

Unformell: Du nimmst dir ein beliebiges Element und zeigst, dass es tut, was es soll.

Die 3-Schritte-Methode für jeden Mengenbeweis

Schritt 1: Teilmengenbeweise aufteilen

$A = B$ beweisen heißt: $A \subseteq B$ UND $B \subseteq A$ zeigen

Behauptung: $u \cup v = v$

(i) Zeige: $u \cup v \subseteq v$ (ii) Zeige: $v \subseteq u \cup v$

Schritt 2: Element-für-Element arbeiten

Nimm ein beliebiges $x$ aus der ersten Menge:

Sei $x \in u \cup v$ beliebig.

→ $x \in u$ oder $x \in v$ (Definition $\cup$) → Falls $x \in u$: Da $u \subseteq v$ gilt $x \in v$ → Falls $x \in v$: Bereits fertig → Also $x \in v$ ✓

Schritt 3: Rückrichtung nicht vergessen

Auch wenn's trivial scheint – aufschreiben!

Sei $x \in v$ beliebig.

→ $x \in v \subseteq u \cup v$ ($v$ ist Teilmenge der Vereinigung) → Also $v \subseteq u \cup v$ ✓

Aus (i) und (ii) folgt: $u \cup v = v$ ■

Beispiel 1: Vereinigung und Teilmenge

Aufgabe: Beweise $u \subseteq v \Rightarrow u \cup v = v$

Beispiel 2: Komplement-Beziehungen

Aufgabe: Beweise $u \subseteq v \Rightarrow \bar{v} \subseteq \bar{u}$

Das ist kniffliger! Hier brauchst du die Kontraposition.

Beweis-Skizze:

1. Annahme: $u \subseteq v$
2. Zeige: $\bar{v} \subseteq \bar{u}$
3. Sei $x \in \bar{v}$, also $x \notin v$
4. Annahme (Widerspruch): $x \in u$
5. Da $u \subseteq v$ folgt $x \in v$
6. Widerspruch zu $x \notin v$!
7. Also $x \notin u$, d.h. $x \in \bar{u}$ ■

Das Schubfachprinzip (Pigeonhole Principle)

Jetzt wird's interessant. Das Schubfachprinzip ist einer der mächtigsten Tricks in der Diskreten Mathematik.

Das Absurdistan-Problem

"In Absurdistan haben alle Bauern weniger Schafe als es Bauern gibt. Jeder Bauer hat mindestens ein Schaf. Gibt es zwei Bauern mit gleich großen Herden?"

Lösung mit Schubfachprinzip (Konkret: 5 Bauern):

Die Logik:

• 5 Bauern müssen auf 4 mögliche Werte (1, 2, 3, 4 Schafe) verteilt werden
• Nach 4 Bauern sind im Best Case alle 4 Werte belegt
• Bauer 5 muss zwangsläufig einen bereits belegten Wert nehmen
• → Mindestens 2 Bauern haben gleich viele Schafe!

Allgemein: $n$ Bauern, $n-1$ mögliche Schafanzahlen → Kollision garantiert

Typische Klausur-Fallen bei Beweisen

Transfer: So kommen Beweise in der Klausur

Die Beweis-Checkliste für die Klausur

1. Start: "Sei $x \in ...$ beliebig"
2. Definitionen: Alle verwendeten Begriffe ausschreiben
3. Fallunterscheidungen: Markant kennzeichnen (Fall 1:, Fall 2:)
4. Ende: ■ oder QED nicht vergessen

Key Takeaways

• Element-Methode – Bei Mengenbeweisen immer "Sei $x \in ...$" starten
• Beide Richtungen – Bei Gleichheit beide Teilmengen-Beziehungen zeigen
• Schubfachprinzip – $n+1$ Objekte auf $n$ Fächer = mindestens 2 im selben
• Definitionen hinschreiben – Auch wenn's trivial scheint
• Fallunterscheidung – Bei "oder" immer beide Fälle betrachten

Das komplette Cheatsheet mit allen Standard-Beweismustern gibt's als PDF! 👆

Nächste Lesson