Natürliche Zahlen/Multiplikation/Selbstaddition/Produktmenge/Einführung/Textabschnitt
Wir geben noch einen zweiten Beweis für die vorstehende Aussage.
Es seien und endliche Mengen mit bzw. Elementen.
Dann besitzt die Produktmenge genau Elemente.
Wir führen Induktion über , also die Anzahl von . Wenn ist, so ist leer und damit ist auch die Produktmenge leer, hat also ebenfalls Elemente, was nach Fakt (1) mit dem Produkt übereinstimmt. Dies sichert den Induktionsanfang. Wenn ist, so besteht aus genau einem Element, sagen wir , und alle Elemente der Produktmenge haben die Form mit diesem einen und einem beliebigen . Somit ist
eine bijektive Abbildung und hat genau so viele Elemente wie , nämlich . Dies stimmt nach Fakt (2) mit dem Produkt überein. Es sei nun die Aussage für alle Mengen mit Elementen (und beliebige endliche Mengen ) bewiesen und es liege eine -elementige Menge vor. Es sei ein fixiertes Element und wir betrachten die disjunkte Zerlegung
Die Menge besitzt dann Elemente, sodass wir auf diese Menge die Induktionsvoraussetzung anwenden können. Ferner ist
und diese Vereinigung ist disjunkt (die erste Komponente eines Paares ist entweder oder nicht ). Daher ist nach Fakt die Anzahl von gleich der Summe der Anzahlen der beiden Bestandteile, also nach der Induktionsvoraussetzung, dem einelementigen Spezialfall und Fakt (3) gleich
Wir behaupten, dass die Abbildung[1]
bijektiv ist. Zum Beweis der Surjektivität sei vorgegeben. Dieses (ganzzahlige) Intervall kann man in die disjunkten Intervalle
unterteilen. Das Element gehört somit zu einem dieser Intervalle, d.h. es gibt ein mit
mit zwischen und . Dann ist
mit einem zwischen und und gehört somit zum Bild. Zum Beweis der Injektivität seien
gegeben, die auf das gleiche Element abbilden. Es gilt also
Da und beide zu gehören, sind die Summen jeweils maximal gleich bzw. . Daher können die Zahlen nur dann gleich sein, wenn
und dann nach der Abziehregel auch
ist.
- ↑ Der Ausdruck bezeichnet hier den Vorgänger von , die Subtraktion haben wir noch nicht eingeführt.