1. Endliche Mengen

In diesem und im folgenden Kapitel stehen endliche Mengen und ihre Mächtigkeiten im Zentrum. Wir präzisieren den Begriff der Endlichkeit mit Hilfe von Bijektionen und besprechen das Dirichletsche Schubfachprinzip in verschiedenen Varianten. Danach wenden wir uns dem Problem der Mächtigkeitsberechnung zu: Ist eine endliche Menge A gegeben, so müssen wir eine natürliche Zahl n finden derart, dass sich die Elemente von A in der Form a₁, …, a_n ohne Wiederholungen aufzählen lassen. Zwei Grundtechniken für diese Aufgabe sind:

(1)	Wir zerlegen die Menge A in disjunkte Mengen A₁, …, A_k, deren Mächtigkeiten wir bestimmen können. Dann ist die Mächtigkeit von A die Summe der Mächtigkeiten der Mengen A₁, …, A_k.

(2)	Wir geben eine Bijektion f : A → B an, mit einer Menge B, deren Mächtigkeit bereits bekannt ist. Dann ist die Mächtigkeit von A gleich der Mächtigkeit von B.

Zur Illustration dieser Techniken betrachten wir zwei Mächtigkeitsbestimmungen der Graphentheorie.