Noethersche Induktion

16.04.2016, 20:17

DQQpy

Noethersche Induktion

Abend,

in Logik hatten wir letztens die noethersche Induktion. Allerdings verstehe ich nicht ganz den Ansatz, den unsere Dozentin uns vermitteln wollte.
Zuerst verallgemeinerte sie die vollständige Induktion so:

$\begin{eqnarray*} p(0) und \\ \forall n \in \mathbb N : p(0) \wedge p(1) \wedge ... \wedge p(n) \rightarrow p(n+1) \end{eqnarray*}$

Das sind die beiden Voraussetzungen für eine Gültigkeit für alle nat. Zahlen.
Dabei verstehe ich schon nicht: Warum setzt man jetzt die Gültigkeit für alle vorherigen Zahlen voraus? Warum reicht es nicht wie bei der vollständigen Induktion die Gültigkeit der einen vorherigen Aussage vorauszusetzen?
Jedenfalls schrieb sie die Voraussetzung dann in diese Form um:

$\begin{eqnarray*} p(0) und \\ \forall n \in \mathbb N : (\forall k \in \mathbb N : (k < n+1 \rightarrow p(k)) \rightarrow p(n+1)) \end{eqnarray*}$

Das habe ich im Prinzip verstanden. Nur dann meinte sie, man könne das p(0) mit der anderen Voraussetzung zusammenfassen zu:

$\begin{eqnarray*} \forall n \in \mathbb N : (\forall k \in \mathbb N : (k < n \rightarrow p(k)) \rightarrow p(n)) \end{eqnarray*}$

Und da frage ich mich warum das p(0) dann verschwindet? Wenn man als beliebiges n die 1 nimmt, lässt sich doch gar keine Aussage treffen, da sich für k keine nat. Zahl < 1 finden lässt ( $\begin{eqnarray*} 0 \notin \mathbb N \end{eqnarray*}$ , richtig?).

MfG

P.S.: Wie erzeugt man in Latex einen Zeilenumbruch, der die erste Zeile nicht rechts anordnet? Hammer

16.04.2016, 21:05

papahuhn

Auf diesen Beitrag antworten »

RE: Noethersche Induktion

Zitat:

Wenn man als beliebiges n die 1 nimmt, lässt sich doch gar keine Aussage treffen, da sich für k keine nat. Zahl < 1 finden lässt

Die Aussage $\begin{eqnarray*} \forall k \in \mathbb{N}: (k < 1 \rightarrow p(k)) \end{eqnarray*}$ ist eben deshalb wahr, weil k < 1 immer falsch ist.

17.04.2016, 00:28

DQQpy

Auf diesen Beitrag antworten »

RE: Noethersche Induktion
Ahh, natürlich! Danke dir.
Hat jemand eine Idee zur anderen Frage?

17.04.2016, 10:37

papahuhn

Auf diesen Beitrag antworten »

RE: Noethersche Induktion
Welche andere?

17.04.2016, 11:32

DQQpy

Auf diesen Beitrag antworten »

RE: Noethersche Induktion

Zitat:

Original von DQQpy
Dabei verstehe ich schon nicht: Warum setzt man jetzt die Gültigkeit für alle vorherigen Zahlen voraus? Warum reicht es nicht wie bei der vollständigen Induktion die Gültigkeit der einen vorherigen Aussage vorauszusetzen?

17.04.2016, 13:12

papahuhn

Auf diesen Beitrag antworten »

RE: Noethersche Induktion
Der Ansatz eurer Dozentin ist nicht dadurch motiviert, dass p(n) nicht "ausreicht", sondern dass es ein Induktionsprinzip gibt, das in der Struktur der natürlichen Zahlen auf die vollständige Induktion vereinfacht werden kann, welches zusätzlich aber in Strukturen funktioniert, in denen die vollständige Induktion als Beweismethode nicht genügt.
Zum anderen, betrachte mal folgende Aufgabe:
Sei $\begin{eqnarray*} f:\mathbb{N} \rightarrow \mathbb{N} \end{eqnarray*}$ mit
$\begin{eqnarray*} f(0) = 0 \end{eqnarray*}$
$\begin{eqnarray*} f(n+1) = \sum_{k=0}^n~\frac{f(k)}{n+k+1} \end{eqnarray*}$
Beweise mit vollständiger Induktion: $\begin{eqnarray*} f(n) = 0 \end{eqnarray*}$ für alle $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$ . Sieht doch recht einfach aus, wenn man den Induktionsschritt noethersch durchführen kann, oder?

18.04.2016, 08:57

DQQpy

Auf diesen Beitrag antworten »

Achso, alles klar.
Vielen Dank!

Neue Frage »

Antworten »

Noethersche Induktion

Verwandte Themen