Prinzip der vollständigen Induktion beweisen

29.11.2009, 20:36

sebastu91

Prinzip der vollständigen Induktion beweisen

Hay mal wieder!

Zur Aufgabe:

Man beweise das Prinzip der vollständigen Induktion:
Satz 1. Sei $\begin{eqnarray*} S \end{eqnarray*}$ (Teilmenge) $\begin{eqnarray*} \mathbb N \end{eqnarray*}$
Falls
(a) $\begin{eqnarray*} 0 \in S \end{eqnarray*}$
und
(b) für jedes $\begin{eqnarray*} k \in S \end{eqnarray*}$ auch $\begin{eqnarray*} k+1 \in S \end{eqnarray*}$ gilt,
so ist $\begin{eqnarray*} S= \mathbb N \end{eqnarray*}$ .

(Hinweis: Man benutze das Wohlordnungsprinzip und versuche sich an einem Widerspruchsbeweis.)

Ich hab irgendwie keine Ahnung wie man das Prinzip der vollständgen Induktion beweisen soll. Ich wüsste wie man sie anwendet, aber nicht wie man sie selbst beweist. Der tipp hilft mir dadurch auch nicht wirklich weiter. Hat jemand ne Idee?

29.11.2009, 21:05

El_Snyder

Auf diesen Beitrag antworten »

Fehlt da nicht der Bezug zur vollst. Induktion? Du sollst doch jetzt nur zeigen, dass eine Teilmenge der natürlichen Zahlen, die die 0 ( = k ) und jedes k+1 enthält, gleich der Menge der natürlichen Zahlen ist. Das scheint mir aber recht trivial (du kannst zu jedem Element aus S 1 addieren und erhältst ein weiteres Element aus S; da du bei 0 anfangen kannst, hast du also alle natürlichen Zahlen in S).
Zum Beweis der vollst. Induktion muss die Teilmenge doch näher beschrieben werden im Sinne von A(n) = wahr (bzw. hier A(n) = falsch, da du ja den Widerspruchsbeweis führen sollst) für eine Aussage für jedes n aus N. Oder irre ich mich da?

29.11.2009, 21:10

tmo

Auf diesen Beitrag antworten »

Nehme an es sei $\begin{eqnarray*} S \neq \mathbb N \end{eqnarray*}$ .

Betrachte nun $\begin{eqnarray*} M := \mathbb N \setminus S \end{eqnarray*}$ , also alle natürlichen Zahlen die nicht in S liegen.

Nach dem Wohlordnungsprinzip enthält M ein kleinstes Element m.

Nun ist entweder $\begin{eqnarray*} m = 0 \end{eqnarray*}$ oder $\begin{eqnarray*} m-1 \in S \end{eqnarray*}$

29.11.2009, 21:19

sebastu91

Auf diesen Beitrag antworten »

Aber so hab ich doch nicht das Prinzip der vollständigen Induktion bewiesen. Oder doch?
Außerdem versteh ich nicht ganz wieso $\begin{eqnarray*} m-1\in S \end{eqnarray*}$ sein muss. verwirrt

29.11.2009, 21:25

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von sebastu91
Aber so hab ich doch nicht das Prinzip der vollständigen Induktion bewiesen. Oder doch?

Sei A(n) eine Aussage und S die Menge aller n, für die A(n) wahr ist.

Siehst du jetzt, warum man diesen Satz "Prinzip der vollständigen Induktion" nennt?
Denn was man bei der Induktion macht, ist ja gerade $\begin{eqnarray*} 0 \in S \end{eqnarray*}$ und $\begin{eqnarray*} n \in S \Rightarrow n+1 \in S \end{eqnarray*}$ zeigen.

Zitat:

Original von sebastu91
Außerdem versteh ich nicht ganz wieso $\begin{eqnarray*} m-1\in S \end{eqnarray*}$ sein muss. verwirrt

Dann denk nochmal drüber nach.

29.11.2009, 21:52

El_Snyder

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Sei A(n) eine Aussage und S die Menge aller n, für die A(n) wahr ist.

Das habe ich gemeint. Aber für den hier verlangten Widerspruchsbeweis betrachtet man doch eher die Menge S aller n, für die A(n) falsch ist, oder?
Da A(1) nach Induktionsanfang wahr ist, hat diese Menge dann das kleinste Element m > 1. (m-1) ist dann in der Menge der natürlichen Zahlen ohne die Menge S (da m schließlich kleinstes Element von S ist). D.h. dass A(m-1) wahr ist (weil es ja in der anderen Teilmenge der natürlichen Zahlen ist, für die A(n) wahr ist). Nach Induktionsprinzip müsste dann aber auch A(m) wahr sein (da wir im Induktionsschritt von n auf n+1, also hier von m-1 auf m-1+1=m schließen).
Und hier ist dann der Widerspruch dazu, dass m oben schon kleinstes Element der Menge S aller n, für die A(n) falsch ist, war.

Neue Frage »

Antworten »

Prinzip der vollständigen Induktion beweisen

Verwandte Themen