Endliche Menge/Numerische Bedingung/Injektive Abbildung/Fakt/Beweis

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

Wir führen Induktion über die Anzahl von , bei ist nach Voraussetzung und man kann ein beliebiges Element aus als Wert an der Stelle festlegen.

Sei nun -elementig und sei die Aussage für jede kleinere Indexmenge (und jede Mengenfamilie, die die numerische Bedingung erfüllt) bewiesen. Wir betrachten zwei Fälle. Erster Fall. Für alle Teilmengen , , gelte sogar die stärkere Bedingung

Wir wählen ein Element und und betrachten , , . Da stets nur das Element herausgenommen wird, gilt die numerische Bedingung für diese neue Situation und wir können darauf die Induktionsvoraussetzung anwenden. Es gibt also eine injektive Abbildung

mit . Diese Abbildung können wir durch zu einer injektiven Abbildung von nach fortsetzen. Zweiter Fall. Es gibt nun eine echte Teilmenge mit

Für gilt die numerische Bedingung nach wie vor. Wir betrachten

und

und setzen

für . Für jede Teilmenge ist

Nach Voraussetzung hat diese Menge zumindest Elemente und hat genau Elemente. Deshalb besitzt zumindest Elemente. D.h. dass und die , , ebenfalls die numerische Bedingung erfüllen. Wir können die Induktionsvoraussetzung auf einerseits und auf andererseits (mit den zugehörigen Zielmengen) anwenden und erhalten injektive Abbildungen

mit und

mit . Da und disjunkt sind, setzen sich diese beiden Abbildungen zu einer injektiven Abbildung mit zusammen.