Induktionsbeweis über die Menge der Elemente einer Abbildung

Question

Ich soll dies per Induktion die Anzahl der Elemente herausfinden. Dazu soll eine Induktion über eine Varieable stattfinden. 

Also eine Induktion von 1->m = m Elemente, aber wie stelle ich dies am besten an?

Answer 1

Da brauchst du aber wohl eine doppelte Induktion: Einmal über n und einmal über m.

Über n ist es recht einfach:  Sei M eine m-elementige Menge.  Für n=1 gibt es m Abbildungen; denn jedes der m Elemente von M kann das Bild des einzigen Elementes von N sein.

Wenn es nun für ein n genau mⁿ Abbildungen gibt, und du hast nun eine Menge N mit n+1 Elementen. Und sei x ∈ N,

dann gibt es mⁿ Abbildungen von  N \ {x} nach M und dem x kann man jedes der m Elemente von M zuordnen, also

gibt es m*mⁿ = mⁿ⁺¹ Abbildungen von N nach M.

Über m ist die Induktion etwas kniffliger. Sei also N eine n-elementige Menge und  m=1.

Dann gibt es nur eine Abbildung; denn jedem x∈N muss ja etwas zugeordnet werden, also jedem x dieses eine Element von M.

Gelte die Aussage nun für ein m. Und sei nun M eine (m+1)elementige Menge. Sei nun y ∈ M. Dann kann man die Abbildungen von N nach M danach einteilen wie viele Urbilder das y hat. 

y hat gar kein Urbild.  Davon gibt es so viele Abbildungen wie die von N nach M\{y} , also mⁿ Stück.

y hat genau ein Urbild x. Es gibt m^n-1 Abbildungen von N\{x} nach M und jedes der n Elemente von N kann das Urbild von y sein, also gibt es davon n*m^n-1 Stück.

y hat genau zwei Urbilder x1 und x2. Es gibt m^n-2 Abbildungen von N\{x1;x2} nach M und jede 2-elementige Teilmenge von N  kann das Urbild von y sein, also gibt es davon (n über 2) *m^n-2 Stück.

Entsprechend für Urbildanzahlen 3,4,...,n.   Also ist die Anzahl aller Abbildungen von N nach M dann 

mⁿ + n*n^m-1 + (n über 2)*n^m-2 + ..................+  (n über n) * m^n-n  

und das ist nach dem binomischen Satz gerade (m+1)ⁿ .   

Damit ist auch die zweite Induktion am Ende.