Abzählbar unendlich/Bijektion zu N/Fakt/Beweis

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

Es sei

eine surjektive Abbildung. Wir definieren induktiv eine streng wachsende Abbildung

derart, dass bijektiv ist. Wir setzen und konstruieren induktiv über die Eigenschaft, dass die kleinste natürliche Zahl ist, für die nicht zu

gehört. Eine solche Zahl gibt es immer, da andernfalls endlich wäre; also gibt es auch eine kleinste solche Zahl. Nach Konstruktion ist , d.h. ist streng wachsend.

Da jedes die Eigenschaft
erfüllt, ist die Gesamtabbildung

injektiv.
Zum Nachweis der Surjektivität sei . Wegen der Surjektivität von ist die Faser nicht leer und daher gibt es auch ein kleinstes Element mit . Da streng wachsend ist, gibt es nur endlich viele Zahlen mit . Daher ist und .

Zur bewiesenen Aussage