Wenn f injektiv dann surjektiv, wenn Bild- und Urbildmenge endlich und gleich mächtig. Beweis

Question

Wir haben gerade das Thema Mengenlehre und bekommen dazu jede Woche ein Übungsblatt. Bisher hatten wir schon Aufgaben, wo wir z.B die Bijektivität zeigen mussten. Doch bei dieser Aufgabe wissen wir nicht weiter. Wir scheitern bereits beim Ansatz.

Wir sollen, wenn X und Y endliche Mengen sind mit |X| = |Y| und f: X -> Y eine Abbildung ist, zeigen, dass wenn f injektiv ist, dann ist f auch surjektiv/wenn f surjektiv ist, dann ist f auch injektiv.

Das sind zwei aufgeteilte Aufgaben. Hoffe ihr könnt uns helfen!

Answer 1

Bemerkung: Müsste f nicht eine Funktion sein?

Voraussetzung Bild- und Urbildbereich haben beide die gleiche endliche Anzahl Elemente, sagen wir n. 

Injektiv heisst, dass ein Bildpunkt höchstens ein Urbild hat.

Surjektiv, dass jedes Element des Bildbereichs mindestens ein Urbild hat.

Voraussetzung: f injektiv.

Annahme f nicht surjektiv: Es gibt (mindestens) ein Element des Bildbereichs, das nur kein Urbild hat. Nun sind aber nur noch n-1 Bildpunkte möglich und es gibt n Urbilder, die alle einen andern Bildpunkt haben. Das ist ein Widerspruch: Deshalb: f ist surjektiv.

Voraussetzung: f surjektiv.

Annahme f nicht injektiv: Es gibt (mindestens) ein Element des Bildbereichs, das zwei Urbilder hat. Nun sind aber nur noch n-2 Urbilder übrig und die können nicht n-1 verschiedene Bildpunkte haben. Das ist ein Widerspruch: Deshalb: f ist surjektiv.

Wenn euch das zu wenig ausführlich ist, müsst ihr wohl einen Induktionsbeweis machen. Von einelementigen Bild-und Urbildmengen bis zu n-elementigen.