Rekursionssatz Dedekind, Beweis für vollständige Induktion |
16.01.2019, 15:29 | lOregu | Auf diesen Beitrag antworten » |
Rekursionssatz Dedekind, Beweis für vollständige Induktion 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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |