0 Daumen
296 Aufrufe

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 ^^

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community