Zum Inhalt springen

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

Aus Wikiversity
Beweis

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