Aufgabe:
Nutzen Sie die vollständige Induktion, um das sogenannte Taubenschlagprinzip zu beweisen:
Seien M, N zwei Mengen und sei m := |M| mit m ∈ ℕ \ {1}. Sei weiterhin f : M → N eine
Abbildung. Dann gilt:
|f(M)| ≤ m − 1 ⇔ f nicht injektiv.
Anschaulich bedeutet dies:
”⇒“: Verteilt man m Tauben auf weniger als m − 1 Käfige, so ist mindestens ein Käfig mindestens
doppelt belegt,
”⇐“: Wenn sich von m Tauben mindestens zwei einen Käfig teilen, belegen alle Tauben zusammen
maximal m − 1 Käfige.
Hinweis: Sie dürfen verwenden, dass für eine Abbildung g : X → Y und Teilmengen A, B ⊂ X
die Gleichheit g(A ∪ B) = g(A) ∪ g(B) gilt. Außerdem dürfen Sie benutzen, dass für zwei disjunkte
und endliche Mengen C, D gilt: |C ∪ D| = |C| + |D|.
Ich hoffe es kann mir jemand weiter helfen ^^
