Das Schubfachprinzip

Mit Hilfe der natürlichen Zahlen und des Funktionsbegriffs können wir die Endlichkeit einer Menge wie folgt definieren:

Definition (Endlichkeit)

Eine Menge A heißt endlich, falls es eine natürliche Zahl n und eine Bijektion f : { 1, …, n } → A gibt. Andernfalls heißt A unendlich.

Die Definition ist ein wichtiges Beispiel für ein Grundmotiv der Mächtigkeitstheorie: Wir verwenden Bijektionen zur Bestimmung der Größe von Mengen. Eine Bijektion f : { 1, …, n } → A können wir uns als Zählung von A vorstellen. Die endliche Folge f (1), …, f (n) durchläuft alle Elemente von A derart, dass kein Element mehrfach erscheint. Wir nennen die Folge f (1), …, f (n) auch eine Aufzählung (ohne Wiederholungen) der Menge A.

Zählung einer endlichen Menge A durch eine Bijektion f : { 1, …, n } → A. Es gilt A = { f (1), …, f (n) }.

Anschaulich klar, aber dennoch beweisbedürftig ist, dass eine natürliche Zahl n wie in der Definition der Endlichkeit eindeutig ist. Wir zeigen hierzu:

Satz (Dirichletsches Schubfachprinzip, Version I)

Seien n, m  ∈  ℕ, A = { a₁, …, a_n }, B = { b₁, …, b_m } mit a_i ≠ a_j und b_i ≠ b_j für alle i ≠ j. Weiter sei f : A → B bijektiv. Dann gilt n = m.

Anschaulich formuliert:

Schubfachformulierung des Prinzips

Wenn wir paarweise verschiedene Objekte a₁, …, a_n derart in paarweise verschiedene Schubfächer b₁, …, b_m verteilen können, dass jedes Objekt in genau einem Schubfach landet und jedes Schubfach belegt wird, so ist die Anzahl der Objekte gleich der Anzahl der Fächer.

In der Literatur ist auch die Bezeichnung als Taubenschlagprinzip oder kurz als Dirichlet-Prinzip üblich.

Beweis

Wir zeigen die Aussage durch Induktion nach n ≥ 0.

Induktionsanfang n = 0:

Für n = 0 ist A = ∅ und f : ∅ → B bijektiv. Also ist B = ∅, sodass m = 0.

Induktionsschritt von n nach n + 1:

Sei f : { a₁, …, a_n + 1 } → { b₁, …, b_m + 1 } bijektiv. Sei b_k = f(a_n + 1). Wir definieren nun c_j für 1 ≤ j ≤ m durch

$c_{j} = { \begin{matrix} b_{j} & falls 1 \leq j < k, \\ b_{j + 1} & falls k \leq j < m. \end{matrix}$

Dann gilt { c₁, …, c_m } = { b₁, …, b_m + 1 } − { b_k }. Zudem ist die Funktion g : { a₁, …, a_n } → { c₁, …, c_m } mit g(a_i) = f (a_i) für alle 1 ≤ i ≤ n bijektiv, sodass n = m nach I. V. Folglich ist n + 1 = m + 1.

Zur Konstruktion der Funktion g

Korollar (Eindeutigkeit der Mächtigkeit endlicher Mengen)

Sei A eine endliche Menge. Dann gibt es genau ein n  ∈  ℕ derart, dass es eine Bijektion f : { 1, …, n } → A gibt.

Beweis

Seien n, m  ∈  ℕ und f : { 1, …, n } → A, g : { 1, …, m } → A bijektiv. Dann ist g⁻¹ ∘ f : { 1, …, n } → { 1, …, m } bijektiv und damit n = m.

Damit können wir nun definieren:

Definition (Anzahl, Mächtigkeit)

Sei A eine endliche Menge. Dann setzen wir

|A| = „das eindeutige n, für das eine Bijektion f : { 1, …, n } → A existiert.“

Die natürliche Zahl |A| heißt die Anzahl der Elemente oder die Mächtigkeit oder Kardinalität von A. Gilt |A| = n, so sagen wir auch, dass A eine n-elementige Menge oder eine Menge mit genau n Elementen ist.

Durchgehend gebraucht wird:

Satz (Charakterisierung n-elementiger Mengen)

Seien A eine endliche Menge und n  ∈  ℕ. Dann sind äquivalent:

(a)	A ist n-elementig, d. h. \|A\| = n.

(b)	Es gibt paarweise verschiedene a₁, …, a_n mit A = { a₁, …, a_n }.

Elemente a₁, …, a_n wie in (b) bilden eine Aufzählung von A. Wir erinnern noch einmal daran, dass aus A = { a₁, …, a_n } im Allgemeinen nur folgt, dass |A| ≤ n. Dass |A| = n gilt ist äquivalent dazu, dass die a_i paarweise verschieden sind.

Wir notieren das Schubfachprinzip in zwei Varianten. Ihr Beweis mit Hilfe der oben bewiesenen Version sei dem Leser zur Übung überlassen.

Satz (Schubfachprinzip, Version II)

Sei A eine endliche Menge, und sei f : A → A. Dann sind äquivalent:

(a)	f : A → A ist injektiv.

(b)	f : A → A ist surjektiv.

(c)	f : A → A ist bijektiv.

Diese Äquivalenzen werden in der Mathematik an zahlreichen Stellen verwendet, zum Beispiel in der Algebra bei der Untersuchung von Operationen auf endlichen Mengen. Wissen wir, dass eine Menge A endlich ist, so wird der Nachweis, dass eine Funktion f : A → A (eine Transformation auf A) bijektiv ist, durch das Prinzip deutlich einfacher. Es genügt, „injektiv“ oder „surjektiv“ zu zeigen. Für unendliche Mengen sind die Äquivalenzen nicht mehr gültig. Die Funktion f : ℕ → ℕ mit f (n) = n + 1 für alle n ist injektiv, aber nicht surjektiv, und die Funktion g : ℕ → ℕ mit g(2n) = g(2n + 1) = n für alle n ist surjektiv, aber nicht injektiv.

Eine weitere äquivalente Formulierung des Prinzips ist:

Satz (Schubfachprinzip, Version III)

Seien A, B endliche Mengen. Dann gilt:

(i)	\|A\| ≤ \|B\| genau dann, wenn es gibt ein injektives f : A → B,

(ii)	\|A\| ≥ \|B\| genau dann, wenn es gibt ein surjektives f : A → B,

(iii)

|A| = |B| genau dann, wenn es gibt ein bijektives f : A → B.

Auch diese Version ist von großer Bedeutung: Für unendliche Mengen werden wir die Aussagen auf der rechten Seite für eine allgemeine Definition des Größenvergleichs von Mengen verwenden (vgl. hierzu Kapitel 3).