A sei eine endliche Menge, |A|=n. Nun soll durch vollständige Induktion bewiesen werden, dass es eine Funktion n^n von A in sich gibt. (|F(A)=n^n|)
hi anne,
A sei eine endliche Menge, |A|=n. Nun soll durch vollständige
Induktion bewiesen werden, dass es eine Funktion n^n von A in
sich gibt. (|F(A)=n^n|)
so wie der text dasteht, ist er nicht wirklich sinnvoll. „eine funktion n^n“ kanns nur geben, wenn eine rechenoperation „^“ definiert ist. und die betragsstriche in der klammer sind auch unsinn.
gemeint ist vermutlich:
A sei eine endliche Menge, |A|=n. Nun soll durch vollständige Induktion bewiesen werden, dass die anzahl der funktionen von A in sich gleich n^n ist. (|F(A)|=n^n, wenn F(A) die menge aller funktionen von A in sich ist.)
ich finds einfacher, den allgemeineren satz zu zeigen, nämlich A und B seien endliche mengen mit den mächtigkeiten |A| = n und |B| = m. dann ist die anzahl der funktionen von A nach B = m^n.
das kann man gut mit induktion über n zeigen. (das hatten wir übrigens hier vor kurzem schon.)
sei n = 1. d.h. A hat 1 element, B hat n elemente.
dann gibt es m = m^1 funktionen von A nach B. du kannst nämlich auf m verschiedene weisen dem element aus A einen funktionswert zuordnen.
so weit zum induktionsanfang.
nun der induktionsschritt:
sei nun |A| = n und |B| = m und die anzahl der funktionen von A nach B gleich m^n.
erweitere A nun um ein element zur menge A*. (B unverändert!) dann kannst du jede funktion von A nach B auf m arten zu einer funktion von A* nach B erweitern.
die anzahl dieser funktionen ist dann …
überleg dir auch, dass das alle möglichen funktionen von A* nach B sind.
im falle B = A ist m = n und die anzahl der funktionen n^n.
hth
m.
… sei n = 1. d.h. A hat 1 element, B hat n elemente.
soll heißen: B hat m elemente
dann gibt es m = m^1 funktionen von A nach B. …
sorry.
m.