Rekursionssatz Dedekind, Beweis für vollständige Induktion

Neue Frage »

lOregu Auf diesen Beitrag antworten »
Rekursionssatz Dedekind, Beweis für vollständige Induktion
Meine Frage:
Dedekind Rekursionssatz:

Für M Menge, m Element M und die Abbildung S: M -> M gilt: Es existiert genau eine Abbildung a: IN -> M mit a(0) = m und a(n+1) = S(a(n)).

Das verstehe ich. Es gibt salopp formuliert nur eine einzige Rekusionsvorschrift über S; bzw. diese ist eindeutig bestimmt.

Nun habe ich gesehen, wie jemand basierend auf dem Satz das Prinzip der vollständigen Induktion beweist, verstehe das aber nicht.

"
[p(n) ist eine Aussage über eine natürliche Zahl n]
Aus der Eindeutigkeit im Rekursionssatz folgt übrigens das Prinzip der vollständigen Induktion: Man betrachte hierbei a: IN -> M definiert durch a(n) = 1 <=> p(n). Aus p(0) folgt dann a(0) = 1, und p(n) => p(n+1) besagt a(n)=> a(n+1). Die konstante Abbildung n |-> 1 erfüllt dieselbe Rekursionsvorschrift, sodass also a(n) = 1 für alle n Element IN gilt, d.h. p(n) gilt für alle n Element IN. Der Rekursionssatz ist also stärker als die vollständige Induktion.
"

Meine Ideen:
Was ich verstehe ist die Idee des Beweises, man wendet die Funktion a auf die rekursive Definition des Rekursionssatzes an, zeigt, dass diese auch auf n |-> zutrifft, und da die Rekusion eindeutig ist, sind sie gleich und der Rest ist klar.

Mit fehlt aber die Definition von der Funktion S aus dem Rekursionssatz.
Ich tue mir schwer die Rekursionsdefinition aus dem Rekursionssatz auf a(n) anwenden zu können, ebenso auf n |-> 1.
Denn diese wäre ja n+1 |-> S(a(n)). Was aber ist S hierbei?

Explizit wurde S nicht definiert. Und die Implizite sehe ich vermutlich nicht.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »