Natürliche Zahlen/Multiplikation/Selbstaddition/Produktmenge/Fakt/Beweis

Beweis

Wir führen Induktion über ${}m$, also die Anzahl von ${}M$. Wenn ${}m=0$ ist, so ist ${}M$ leer und damit ist auch die Produktmenge leer, hat also ebenfalls ${}0$ Elemente, was nach Fakt  (1) mit dem Produkt übereinstimmt. Dies sichert den Induktionsanfang. Wenn ${}m=1$ ist, so besteht ${}M$ aus genau einem Element, sagen wir ${}x$, und alle Elemente der Produktmenge haben die Form ${}(x,y)$ mit diesem einen ${}x$ und einem beliebigen ${}y\in N$. Somit ist

$N\longrightarrow M\times N,\,y\longmapsto (x,y),$

eine bijektive Abbildung und ${}M\times N$ hat genau so viele Elemente wie ${}N$, nämlich ${}n$. Dies stimmt nach Fakt  (2) mit dem Produkt ${}1\cdot n$ überein. Es sei nun die Aussage für alle Mengen ${}M$ mit ${}m$ Elementen (und beliebige endliche Mengen ${}N$) bewiesen und es liege eine ${}(m+1)$-elementige Menge ${}M$ vor. Es sei ${}x\in M$ ein fixiertes Element und wir betrachten die disjunkte Zerlegung

${}M=(M\setminus \{x\})\cup \{x\}\,.$

Die Menge ${}M\setminus \{x\}$ besitzt dann ${}m$ Elemente, sodass wir auf diese Menge die Induktionsvoraussetzung anwenden können. Ferner ist

${}M\times N={\left((M\setminus \{x\})\times N\right)}\cup {\left(\{x\}\times N\right)}\,$

und diese Vereinigung ist disjunkt (die erste Komponente eines Paares ist entweder ${}x$ oder nicht ${}x$). Daher ist nach Fakt die Anzahl von ${}M\times N$ gleich der Summe der Anzahlen der beiden Bestandteile, also nach der Induktionsvoraussetzung, dem einelementigen Spezialfall und Fakt  (3) gleich

${}m\cdot n+n=(m+1)\cdot n\,.$

Zur bewiesenen Aussage