Natürliche Zahlen/Multiplikation/Selbstaddition/Produktmenge/Fakt/Beweis/Aufgabe/Lösung

Wir behaupten, dass die Abbildung

$\psi :\{1,\dots ,m\}\times \{1,\dots ,n\}⟶\{1,2,\dots ,mn\},(i,j)⟼(i-1)n+j,$

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

$\{1,\dots ,n\}\cup \{n+1,\dots ,2n\}\cup \{2n+1,\dots ,3n\}\cup \dots \cup \{(m-1)n+1,\dots ,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,\dots ,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,\dots ,m\}\times \{1,\dots ,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,\dots ,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.

Zur gelösten Aufgabe