Induktionsbeweis

15.09.2008, 19:03

Felix

Induktionsbeweis

Ich soll folgendes beweisen :
Die Aussage A(n) stimmt für $\begin{eqnarray*} n_0 \in N \end{eqnarray*}$ ; $\begin{eqnarray*} n\geq n_0 \end{eqnarray*}$ . Wenn A für n stimmt so stimmt es auch für n+1.
Daraus folgt A(n) ist für jedes $\begin{eqnarray*} n\geq n_0 \end{eqnarray*}$ richtig.

Diese Aussage soll ich mittels DES wOHLORDNUNGSPRINZIPS UND einem Wiederspruchbeweises verifizieren.

Ich weiß nicht ganz wie unglücklich

Ich habe so argumentiert :

Die Aussage A(n) ist für Elemente der Menge $\begin{eqnarray*} M := \{ n \in N: n \geq n_0\} \end{eqnarray*}$ richtig.

Nach dem Wohlordnungsprinzip ist n0 eindeutig das kleinste Element aus M.

Gilt die Aussage nun für ein $\begin{eqnarray*} k \geq n_0 \end{eqnarray*}$ $\begin{eqnarray*} k \in N \end{eqnarray*}$ nicht so kann k nicht in M sein ---> Wiederspruch ...

Ist der Beweis so richtig geführt? Oder hab ich vieleicht irgendeine Tatsache für selbstverständlich angenommen die aber bewiesen gehört ?

lg

15.09.2008, 19:36

papahuhn

Auf diesen Beitrag antworten »

RE: Beweis für Induktionsbeweis

Zitat:

Original von Felix
Die Aussage A(n) ist für Elemente der Menge $\begin{eqnarray*} M := \{ n \in N: n \geq n_0\} \end{eqnarray*}$ richtig.

Ist der Beweis so richtig geführt? Oder hab ich vieleicht irgendeine Tatsache für selbstverständlich angenommen die aber bewiesen gehört ?
lg

Ja, das ist nämlich das, was du beweisen sollst.

15.09.2008, 19:44

Felix

Auf diesen Beitrag antworten »

Kannst du mir vielleicht einen Ansatz geben ?? Wie beginne ich diesen Beweis ?

15.09.2008, 19:46

papahuhn

Auf diesen Beitrag antworten »

http://de.wikipedia.org/wiki/Wohlordnungssatz

Abschnitt über dem Anwendungsbeispiel.

15.09.2008, 21:43

Felix

Auf diesen Beitrag antworten »

Hmmm

Heißt das ich soll beweisen das die Menge M für die A(n) zutrifft alle natürlichen Zahlen enthält die größer n0 sind?

Um das zu machen gehe ich also davon aus, dass nicht alle n > n0 Element M sind und führe den Wiederspruchbeweis wie im Wikipedia Artikel durch?

Ich gehe also von der Menge N := { $\begin{eqnarray*} n \in N : n>n_0 \end{eqnarray*}$ . Für die Elemente dieser Menge soll gelten :
$\begin{eqnarray*} x \in N \Leftarrow \Rightarrow x ~~(nicht)\in M \end{eqnarray*}$ .

Diese Menge muss ein kleinstes Element haben. Dann muss man zeigen, dass es noch ein kleineres Element gibt, was zum Wiederspruch führt ...

Und von welchem kleinsten Element soll ich ausgehen bzw. wie zeige ich, dass es ein noch kleineres gibt ????

lg

15.09.2008, 22:35

WebFritzi

Auf diesen Beitrag antworten »

Sei $\begin{eqnarray*} n_2 \end{eqnarray*}$ dieses kleinste Element. Sei nun $\begin{eqnarray*} n_2 = n_1 + 1. \end{eqnarray*}$ Kann $\begin{eqnarray*} A(n_1) \end{eqnarray*}$ stimmen?

15.09.2008, 22:40

Felix

Auf diesen Beitrag antworten »

Aso weil A(n1) nicht stimmen kann entsteht ein Wiederspruch ...

Damit sollte der Beweis eigentlich fertig sein, oder verwirrt

Danke für die Hilfe Freude

15.09.2008, 22:49

papahuhn

Auf diesen Beitrag antworten »

Ich sehe noch einiges Durcheinander in deinen Ausführungen: Du definierst N durch sich selbst, M willst du auch irgendwie redefinieren, und wo der Widerspruch jetzt ist, haste uns auch noch nicht erzählt.

Schreib das mal etwas gescheiter hin.

16.09.2008, 08:25

Felix

Auf diesen Beitrag antworten »

Die Menge N für die A(n) nicht gilt ist Teilmenge von M. Nach dem Wohlordnungsprinzip hat N ein kleinstes Element. Nehmen wir an n2 sei dieses Element, wenn aber n2 dass kleinste Element wäre dann dürfte die Aussage eigentlich auch für n1 = n2 - 1 nicht gelten (denn wann immer die Ausage für ein n > n0 dilt gilt sie ja auch für n + 1 was dann ja zu einem Wiederspruch führen würde), das führt zu einem Wiederspruch weil n2 ja das kleinste Element sein sollte.

So korrekt ?

16.09.2008, 10:41

Romaxx

Auf diesen Beitrag antworten »

Hallo,

Zitat:

Die Menge N für die A(n) nicht gilt ist Teilmenge von M

Das kann nicht stimmen. Auch der Rest langt nicht für einen Beweis.

Fang so an:

Annahme:
1.) $\begin{eqnarray*} A(n_0) \end{eqnarray*}$ ist wahr und 2.) $\begin{eqnarray*} A(n)\Rightarrow A(n+1) \end{eqnarray*}$ und 3.) es gibt ein $\begin{eqnarray*} n \geq n_0 \end{eqnarray*}$ für das gilt: $\begin{eqnarray*} A(n) \end{eqnarray*}$ ist falsch.

Sei also $\begin{eqnarray*} X=\{n\in \mathbb N | A(n) \end{eqnarray*}$ ist falsch mit $\begin{eqnarray*} n\geq n_0\} \end{eqnarray*}$
Da $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ wohlgeordnet ist, gibt es ein kleinsten Element $\begin{eqnarray*} n_1\in X \end{eqnarray*}$
Das kleinste Element in $\begin{eqnarray*} X \end{eqnarray*}$ ist nicht $\begin{eqnarray*} n_0 \end{eqnarray*}$ , denn $\begin{eqnarray*} A(n_0) \end{eqnarray*}$ ist wahr.
Sei also $\begin{eqnarray*} n_1\geq n_0+1 \end{eqnarray*}$ das kleinste Element in $\begin{eqnarray*} X \end{eqnarray*}$ .
Es ist $\begin{eqnarray*} n_1-1\in \mathbb N\setminus X \end{eqnarray*}$ , also $\begin{eqnarray*} A(n_1-1) \end{eqnarray*}$ ist wahr.

Folgere nun aufgrund der Annahme einen Widerspuch.

16.09.2008, 19:43

Felix

Auf diesen Beitrag antworten »

Das der erste Teil nicht stimmt ist mir 5 nmin nach dem Post eingefallen unglücklich

Der Rest ist aber eigentlich identisch zu deiner Beweisführung verwirrt

16.09.2008, 21:01

Romaxx

Auf diesen Beitrag antworten »

Zitat:

Der Rest ist aber eigentlich identisch zu deiner Beweisführung

Hallo,

Nicht ganz. Im Großen und Ganzen ist der Schluss enthalten, aber versuche es noch detailierter darzulegen.

Um meinem Beweis einen Schluss zu geben.

... Da $\begin{eqnarray*} A(n_1-1) \end{eqnarray*}$ wahr ist folgt mit 2.) $\begin{eqnarray*} A(n_1) \end{eqnarray*}$ ist wahr.
Also ist $\begin{eqnarray*} n_1 \end{eqnarray*}$ nicht in $\begin{eqnarray*} X \end{eqnarray*}$ . Widerspruch.

17.09.2008, 16:30

Felix

Auf diesen Beitrag antworten »

Ok danke

Neue Frage »

Antworten »

Induktionsbeweis

Verwandte Themen