Es sei M eine endliche Menge mit n ist element von N Elementen. Zeigen Sie: das k-fache cartesische Produkt X^{k} = Xx....x X ist eine endliche Menge mit n^{k} Elementen.
Induktion über k
Induktionsanfang: k=1 X^1 = X haben beide n^1 = n Elemente.
Sei es wahr für k
Xk+1 wäre bei sauberer Definition X^k x X das cartesische Produkt
von X^k und X, also alle Paare mit 1. Komponente in X^k und 2. Komponente
in X. X^k hat nach Ind.vor n^k Elemente und jedes davon bildet mit einer
2. Komponente aus X ein Paar. Es gibt also (n^k) * n = n k+1 Elemente.
q.e.d.