Aufgabe mit langer Induktion

Question

Aufgabe:

Text erkannt:

(1) (.,Kurze Induktion" impliziert, „Lange Induktion") Es genüge \( (N, e, \nu) \) mit \( e \in N \) und \( \nu: N \rightarrow N \backslash\{e\} \) den Peano Axiomen. Seien \( A_{n}, n \in N \), die eindeutig bestimmten Teilmengen von \( N \) für die gilt \( A_{e}=\{e\} \) und \( A_{\nu(n)}=A_{n} \cup\{\nu(n)\} \). Seien weiterhin Aussagen \( B(n), n \in N \), gegeben. Zeigen Sie, dass \( B(n) \) für alle \( n \in N \) wahr ist, falls das Folgende gilt:
- \( B(e) \) ist wahr.
- Für alle \( n \in N \) gilt: Gilt \( B(k) \) für alle \( k \in A_{n} \), so folgt dass \( B(\nu(n)) \) wahr ist.

Problem/Ansatz:

Hallo! Kann mir jemand bei dieser Aufgabe helfen? Was genau ist eine lange Induktion?

Dankeschön!

Answer 1

Beweis von \(\varphi(n)\) mittels kurzer Induktion:

1. Induktionsanfang: Zeige dass \(\varphi(1)\) gilt.
2. Induktionsvoraussetzung: Sei \(n\in \mathbb{N}\), so dass \(\varphi(n)\) gilt.
3. Induktionsschluss: Zeige dass \(\varphi(n+1)\) gilt.
   

Beweis von \(\varphi(n)\) mittels langer Induktion:

1. Induktionsanfang: Zeige dass \(\varphi(1)\) gilt.
2. Induktionsvoraussetzung: Sei \(n\in \mathbb{N}\), so dass \(\varphi(i)\) für alle \(i\leq n\) gilt.
3. Induktionsschluss: Zeige dass \(\varphi(n+1)\) gilt.
   

(.,Kurze Induktion" impliziert, „Lange Induktion")

Die Aufgabe lautet: Zeige dass wenn kurze Induktion ein korrektes Beweisverfahren ist, dann auch lange Induktion ein korrektes Beweisverfahren ist.