Mengen, Relationen & Funktionen: Übungsaufgaben mit Schritt-für-Schritt-Lösungen

1Mengen und Mengenoperationen

Eine Menge ist eine Sammlung verschiedener Elemente: A = {1, 2, 3}. Reihenfolge und Wiederholung spielen keine Rolle. |A| ist die Anzahl der Elemente, und U ist die Grundmenge, die alles Betrachtete enthält.

• A ∪ B (Vereinigung): die Elemente in A oder B oder beiden.
• A ∩ B (Schnitt): die Elemente in beiden.
• A − B (Differenz): die Elemente von A, die nicht in B liegen.
• A′ (Komplement): die Elemente von U, die nicht in A liegen.

In einem Venn-Diagramm teilen zwei Kreise U in vier Bereiche: nur A, beide, nur B und keine. Jeder Mengenausdruck ist eine Vereinigung einiger dieser Bereiche, du kannst ihn also immer Bereich für Bereich zählen.

Hier ist |A| = 12 + 5 = 17, |A ∩ B| = 5, |A ∪ B| = 12 + 5 + 8 = 25 und |(A ∪ B)′| = 15.

2Zählen mit Inklusion und Exklusion

Addiert man |A| und |B|, wird die Überschneidung doppelt gezählt, also ziehe sie einmal ab:

Bei drei Mengen werden die paarweisen Überschneidungen abgezogen, dann ist die Mitte aber dreimal entfernt worden, also wird sie wieder addiert:

Bei Textaufgaben ist es meist sicherer, ein Venn-Diagramm von der Mitte nach außen zu füllen: zuerst die Elemente in allen drei Mengen, dann jedes Paar abzüglich der Mitte, dann jede einzelne Menge abzüglich dessen, was schon eingetragen ist.

Zwei weitere Zählungen kommen oft vor: Eine Menge mit n Elementen hat 2ⁿ Teilmengen (ihre Potenzmenge 𝒫(A)), und es gibt |A × B| = |A|·|B| geordnete Paare.

3Ein durchgerechnetes Beispiel

Folge jedem Schritt. Versuche, den nächsten vorherzusagen, bevor du ihn öffnest.

4Relationen

Eine Relation R auf einer Menge X ist eine Menge geordneter Paare (x, y) mit x und y aus X. Als gerichteter Graph gezeichnet, ist jedes Paar ein Pfeil und (x, x) eine Schleife.

• Reflexiv: (x, x) ∈ R für jedes x: eine Schleife an jedem Knoten.
• Symmetrisch: Zu (x, y) ∈ R gehört immer (y, x) ∈ R.
• Antisymmetrisch: (x, y) und (y, x) liegen nur dann beide in R, wenn x = y.
• Transitiv: (x, y) und (y, z) in R erzwingen (x, z) ∈ R.

Eine Relation, die reflexiv, symmetrisch und transitiv ist, heißt Äquivalenzrelation. Sie zerlegt X in disjunkte Klassen, etwa die Reste 0, 1 und 2 bei „x ≡ y (mod 3)“. Eine Klasse mit s Elementen liefert s² geordnete Paare.

Um eine Eigenschaft zu widerlegen, genügt ein Gegenbeispiel; um sie zu beweisen, prüfe jedes Paar.

5Funktionen

Eine Funktion f: A → B ordnet jedem Element von A genau ein Bild in B zu.

• Injektiv (eineindeutig): Verschiedene Elemente haben verschiedene Bilder; kein Element von B erhält zwei Pfeile.
• Surjektiv (auf): Jedes Element von B erhält mindestens einen Pfeil.
• Bijektiv: beides. Nur dann hat f eine Umkehrfunktion f⁻¹.

Die Funktion in der Abbildung ist injektiv, aber nicht surjektiv: d erhält keinen Pfeil. Eine Injektion braucht |A| ≤ |B| und eine Surjektion |A| ≥ |B|.

Mit |A| = m und |B| = n gibt es nᵐ Funktionen und n!/(n − m)! injektive. Die Verkettung (g ∘ f)(x) = g(f(x)) wendet zuerst f an.

6Häufige Fehler

• |A| + |B| addieren, ohne die Überschneidung abzuziehen.
• Bei der Inklusion-Exklusion mit drei Mengen vergessen, die Mitte wieder zu addieren.
• mⁿ statt nᵐ für die Anzahl der Funktionen von m Elementen in n Elemente schreiben.
• Denken, eine Relation könne nicht zugleich symmetrisch und antisymmetrisch sein: Die Relation {(1, 1)} ist beides.
• g ∘ f in der falschen Reihenfolge anwenden: Zuerst wirkt f.

7So sehen Prüfungsaufgaben aus

• Leicht: Venn-Diagramme und Teilmengen. Du zählst einen Mengenausdruck anhand eines Venn-Diagramms, klickst den Bereich eines Ausdrucks an oder bestimmst die Größe einer Potenzmenge, eines kartesischen Produkts oder einer Familie von Teilmengen.
• Mittel: Inklusion-Exklusion und Relationen. Du löst Zählaufgaben mit zwei und drei Mengen, zählst Ausdrücke aus Bereichssummen, entscheidest, welche Eigenschaft eine Relation hat, oder zählst die für einen Abschluss nötigen Paare.
• Schwer: Funktionen und Abzählen. Du ordnest eine Funktion als injektiv, surjektiv oder bijektiv ein, zählst Funktionen, Injektionen und Surjektionen, wertest Verkettungen und Umkehrfunktionen aus und zählst Paare in Äquivalenzrelationen.