Endliche Mengen/Natürliche Zahlen/Verknüpfungen/Textabschnitt

Wir überlegen uns, wie die üblichen Verknüpfungen auf den natürlichen Zahlen, die Addition und die Multiplikation, mit mengentheoretischen Verknüpfungen von endlichen Mengen zusammenhängen. Man kann sich darüber streiten, was man als Definition für diese Verknüpfungen nimmt und was dann eine zu beweisende Aussage ist. Für eine axiomatische Behandlung ist es insgesamt vorteilhaft, diese Verknüpfungen auf die Nachfolgerabbildung zurückzuführen und induktiv zu begründen, siehe dazu den Anhang. Die Summe ${}n+m$ ist in diesem Zugang als der ${}m$-te Nachfolger von ${}n$ definiert, das Produkt ${}n\cdot m$ als die ${}n$-fache Summe von ${}m$ mit sich selbst. Die inhaltliche Bedeutung dieser Verknüpfungen wird in den folgenden Aussagen beschrieben.

Lemma

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

Dann besitzt ihre Vereinigung ${}M\cup N$ gerade ${}m+n$ Elemente.

Beweis

Die Voraussetzung besagt, dass es eine bijektive Abbildung

$\psi \colon \{1,\ldots ,m\}\longrightarrow M$

und eine bijektive Abbildung

$\varphi \colon {\{1,\ldots ,n\}}\longrightarrow N$

gibt. Die Abbildung

${\{1,\ldots ,n\}}\longrightarrow \{m+1,\ldots ,m+n\},\,i\longmapsto m+i,$

ist nach Aufgabe bijektiv, sei ${}\theta$ die Umkehrabbildung. Somit ist nach Fakt  (3)

$\varphi \circ \theta \colon \{m+1,\ldots ,m+n\}\longrightarrow N$

ebenfalls bijektiv. Wir definieren nun eine Abbildung

$F\colon \{1,\ldots ,m+n\}\longrightarrow M\cup N$

durch

${}F(k)={\begin{cases}\psi (k),{\text{ falls }}k\in \{1,\ldots ,m\}\,,\\\varphi (\theta (k)),{\text{ falls }}k\in \{m+1,\ldots ,m+n\}\,.\end{cases}}\,$

Diese Abbildung ist surjektiv, da jedes Element aus ${}M$ durch den ersten Fall und jedes Element aus ${}N$ durch den zweiten Fall abgedeckt ist. Die Injektivität sieht man so. Wenn

${}k\neq \ell \,$

gegeben sind, und das eine Element zu ${}\{1,\ldots ,m\}$ und das andere zu ${}\{m+1,\ldots ,m+n\}$ gehört, so ist  ${}F(k)\in M$  und  ${}F(\ell )\in N$  (oder umgekehrt) und sie sind verschieden wegen der Disjunktheit von ${}M$ und ${}N$. Wenn hingegen ${}k$ und ${}\ell$ aus der gleichen Teilmenge des Definitionsbereiches kommen, so ergibt sich die Verschiedenheit von ${}F(k)$ und ${}F(\ell )$ aus der Injektivität von ${}\psi$ bzw. von ${}\varphi \circ \theta$. Insgesamt erhalten wir also eine bijektive Abbildung

$\{1,\ldots ,m+n\}\longrightarrow M\cup N,$

sodass die Anzahl von ${}M\cup N$ gleich ${}m+n$ ist.

$\Box$

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.