Dedekind'scher Rekursionssatz < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Satz
Sei [mm] (\IN,S) [/mm] ein Modell der natürlichen Zahlen. Weiterhin sei X eine Menge und f: X [mm] \mapsto [/mm] X und S: [mm] \IN \mapsto \IN [/mm] Nachfolgerfunktion.
Dann existiert zu [mm] x_{0} \in [/mm] X genau eine Abbildung [mm] \phi: \IN \mapsto [/mm] X mit
i) [mm] \phi(0) [/mm] = [mm] x_{0}
[/mm]
ii) [mm] \phi \circ [/mm] S = [mm] f\circ\phi [/mm] |
Hallo zusammen,
mir bereitet der Dedekind'sche Rekursionssatz Schwierigkeiten.
Zwar habe ich die Notwendigkeit für einen Satz verstanden, der das "Rechnen" mit rekursiv definierten Funktionen ermöglicht, aber offensichtlich ist es mir zu formal, sodass ich nicht durchsteige.
Z.B. ist ja die Fakultätsfkt. eine rekursiv definierte Funktion:
3! = 3*2*1
[mm] x_{0} [/mm] stelle ich mir als Startpunkt vor. [mm] \phi [/mm] (0) bildet darauf ab.
Was sagt mir aber nun, dass die Abbildung aller auf 0 folgenden nat. Zahlen gleich einer Komposition von Selbstabbildung und [mm] \phi [/mm] (n) ist? Insbesondere den Zweck von f verstehe ich nicht. Wie kann ich mir den Zusammenhang mit der Fakultätsfkt. erklären?
Ich wäre dankbar für eure Hilfe!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:25 Mo 24.10.2011 | | Autor: | Helbig |
Hallo,
Der Rekursionssatz wird vielleicht verständlicher, wenn Du die Rekursionsgleichungen so schreibst:
(i) [mm] $\phi(0) [/mm] = [mm] x_0$
[/mm]
(ii) [mm] $\phi(n+1)=f(\phi(n))$
[/mm]
Hierbei schreiben wir $n+1$ für $S(n)$.
Eigentlich sollte intuitiv klar sein, daß durch (i) und und (ii) genau eine Funktion [mm] $\phi$ [/mm] gegeben ist: Wegen (i) ist [mm] $\phi(0)$ [/mm] festgelegt, und wegen (ii) ist der Reihe nach [mm] $\phi(1)=f(\phi(0))$, $\phi(2)=f(\phi(1))$ [/mm] und so weiter definiert.
Nun haben wir mit der Fakultätsfunktion ein kleines Problem, denn für [mm] $\phi(n)=n!$ [/mm] ist ja:
(i) [mm] $\phi(0)=1$ [/mm] bzw. $0!=1$.
(ii) [mm] $\phi(n+1)=(n+1)*\phi(n)$ [/mm] bzw. $(n+1)! = (n+1)*n!$.
Hier ist das $f$ des Rekursionssatzes nicht nur eine Funktion von [mm] $\phi(n)$, [/mm] sondern von $n$ und [mm] $\phi(n)$, [/mm] das heißt, wir haben [mm] $f\colon\IN\times\IN\to \IN$ [/mm] mit
$f(n, x)=(n+1) * x$. Damit lautet
(ii) [mm] $\phi(n+1)=f(n, \phi(n)) [/mm] = [mm] (n+1)*\phi [/mm] (n)$ bzw. $(n+1)!=(n+1)*n!$.
In der erweiterten Form des Rekursionssatzes haben wir also
[mm] $f\colon \IN\times X\to [/mm] X$
statt
[mm] $f\colon X\to [/mm] X$.
Ein Beispiel für den Rekursionssatz in der einfachen Form bildet die Addition von $n$
zu einem festen [mm] $m\in \IN$:
[/mm]
(i) [mm] $\phi(0)=m$ [/mm] bzw.: $m+0=m$
(ii) [mm] $\phi(n+1) [/mm] = [mm] \phi(n)+1$ [/mm] bzw.: $m+(n+1)= (m+n)+1$.
Hier ist [mm] $f\colon X\to [/mm] X $, $f(x)=x+1$ und [mm] $X=\IN$.
[/mm]
Vielleicht wird der Rekursionssatz so etwas klarer.
Wolfgang
|
|
|
| |
|
Lieber Wolfgang,
damit habe ich nun ein tolles Beispiel gefunden, wie man offenbar einfache Sachverhalte schwierig darstellen kann.
Mein Knoten ist geplatzt durch diese intuitivere Schreibweise des Rekursionssatzes, vielen Dank dafür. Ich merke, dass ich meine Blicke noch etwas dafür schärfen muss, um mich davon nicht aus der Bahn werfen zu lassen.
Deine Beispiele machen für mich sehr viel Sinn, jetzt kann ich die Aufgabe (hoffentlich) auch lösen :)
Beste Grüße
|
|
|
|
