Natürliche Zahlen/Multiplikation/Selbstaddition/Produktmenge/Einführung/Textabschnitt

Satz

Es seien ${}M$ und ${}N$ endliche Mengen mit ${}m$ bzw. ${}n$ Elementen.

Dann besitzt die Produktmenge ${}M\times N$ genau ${}m\cdot n$ Elemente.

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\,.$

$\Box$

Das Distributivgesetz illustriert anhand der Interpretation der Multiplikation als Anzahl einer Produktmenge.

Wir geben noch einen zweiten Beweis für die vorstehende Aussage.

Wir behaupten, dass die Abbildung

$\psi \colon \{1,\ldots ,m\}\times {\{1,\ldots ,n\}}\longrightarrow \{1,2,\ldots ,mn\},\,(i,j)\longmapsto (i-1)n+j,$

bijektiv ist. Zum Beweis der Surjektivität sei ${}z\in \{1,2,\ldots ,mn\}$ vorgegeben. Dieses (ganzzahlige) Intervall kann man in die disjunkten Intervalle

$\{1,\ldots ,n\}\cup \{n+1,\ldots ,2n\}\cup \{2n+1,\ldots ,3n\}\cup \ldots \cup \{(m-1)n+1,\ldots ,mn\}$

unterteilen. Das Element ${}z$ gehört somit zu einem dieser Intervalle, d.h. es gibt ein ${}i$ mit

${}z\in \{(i-1)n+1,\ldots ,in\}\,$

mit ${}i$ zwischen ${}1$ und ${}m$. Dann ist

${}z=(i-1)n+j\,$

mit einem ${}j$ zwischen ${}1$ und ${}n$ und gehört somit zum Bild. Zum Beweis der Injektivität seien

${}(i,j),(k,\ell )\in \{1,\ldots ,m\}\times {\{1,\ldots ,n\}}\,$

gegeben, die auf das gleiche Element abbilden. Es gilt also

${}(i-1)n+j=(k-1)n+\ell \,.$

Da ${}j$ und ${}\ell$ beide zu ${}{\{1,\ldots ,n\}}$ gehören, sind die Summen jeweils maximal gleich ${}in$ bzw. ${}kn$. Daher können die Zahlen nur dann gleich sein, wenn

${}i=k\,$

und dann nach der Abziehregel auch

${}j=\ell \,$

ist.