Endliche Menge/Numerische Bedingung/Injektive Abbildung/Fakt/Beweis/Aufgabe/Lösung

Wir führen Induktion über die Anzahl von ${}I$, bei ${}I=\{i\}$ ist nach Voraussetzung ${}M_{i}\neq \emptyset$ und man kann ein beliebiges Element aus ${}M_{i}$ als Wert an der Stelle ${}i$ festlegen.

Es sei nun ${}I$ ${}n$-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 ${}J\subseteq I$, ${}J\neq \emptyset ,I$, gelte sogar die stärkere Bedingung

${}{\#\left(M_{J}\right)}\geq {\#\left(J\right)}+1\,.$

Wir wählen ein Element ${}i_{0}\in I$ und ${}m_{0}\in M_{i_{0}}$ und betrachten ${}I':=I\setminus \{i_{0}\}$, ${}M'=M\setminus \{m_{0}\}$, ${}M_{i}'=M_{i}\setminus \{m_{0}\}$. Da stets nur das Element ${}m_{0}$ 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

$g\colon I'\longrightarrow M'$

mit ${}g(i)\in M_{i}'$. Diese Abbildung können wir durch ${}i_{0}\mapsto m_{0}$ zu einer injektiven Abbildung von ${}I$ nach ${}M$ fortsetzen. Zweiter Fall. Es gibt nun eine echte Teilmenge ${}\emptyset \subset J\subset I$ mit

${}{\#\left(J\right)}={\#\left(M_{J}\right)}\,.$

Für ${}J$ gilt die numerische Bedingung nach wie vor. Wir betrachten

${}K:=I\setminus J\,$

und

${}N:=M\setminus M_{J}\,$

und setzen

${}N_{k}:=M_{k}\cap N\,$

für ${}k\in K$. Für jede Teilmenge ${}T\subseteq K$ ist

${}{\begin{aligned}\bigcup _{k\in T\cup J}M_{k}&={\left({\left(\bigcup _{k\in T}M_{k}\right)}\setminus {\left(\bigcup _{k\in J}M_{k}\right)}\right)}\cup {\left(\bigcup _{k\in J}M_{k}\right)}\\&={\left(\bigcup _{k\in T}N_{k}\right)}\uplus {\left(\bigcup _{k\in J}M_{k}\right)}\\&={\left(\bigcup _{k\in T}N_{k}\right)}\uplus M_{J}.\end{aligned}}$

Nach Voraussetzung hat diese Menge zumindest ${}{\#\left(T\right)}+{\#\left(J\right)}$ Elemente und ${}M_{J}$ hat genau ${}{\#\left(J\right)}$ Elemente. Deshalb besitzt ${}\bigcup _{k\in T}N_{k}$ zumindest ${}{\#\left(T\right)}$ Elemente. D.h. dass ${}K$ und die ${}N_{k}$, ${}k\in K$, ebenfalls die numerische Bedingung erfüllen. Wir können die Induktionsvoraussetzung auf ${}J$ einerseits und auf ${}K$ andererseits (mit den zugehörigen Zielmengen) anwenden und erhalten injektive Abbildungen

$g\colon J\longrightarrow M_{J}$

mit ${}g(j)\in M_{j}$ und

$h\colon K\longrightarrow N$

mit ${}h(k)\in N_{k}\subseteq M_{k}$. Da ${}M_{J}$ und ${}N$ disjunkt sind, setzen sich diese beiden Abbildungen zu einer injektiven Abbildung ${}f\colon I\rightarrow M$ mit ${}f(i)\in M_{i}$

zusammen.

Zur gelösten Aufgabe