Vollständige Induktion, andere Formulierung

08.08.2007, 12:23

way

Auf diesen Beitrag antworten »

Vollständige Induktion, andere Formulierung

Hi, ich komm mit folgender Formulierung der vollständigen Induktion nicht zurecht:

"Um für eine Eigenschaft E, die für natürliche Zahlen sinnvoll formuliert werden kann, den Nachweis zu führen, dass E für alle natürlichen Zahlen richtig ist, brauch man nur zu zeigen:
E ist für 1 richtig.
E richtig für n => E richtig für n+1.

Begründung: Dann ist nämlich {n€N | E ist richtig für n} eine induktive Teilmenge und damit gleich N."

Der erste Teil sagt doch nur aus, dass wenn man eine Eigenschaft, die für ein paar natürliche Zahlen gilt, auch für alle natürliche Zahlen zeigen will, macht man einfach die vollständige Induktion, seh ich das richtig?

Die Begründung versteh ich gar nicht, was das soll.
In der Mengenklammer stehen doch die natürlichen Zahlen, und das ist doch dann klar, dass das eine induktive Teilmenge ist. Und man sieht doch sowieso dass das N ist, wieso dann zum Schluss nochmal " und damit gleich N" ???

08.08.2007, 12:34

tigerbine

Auf diesen Beitrag antworten »

RE: Vollständige Induktion, andere Formulierung
http://de.wikipedia.org/wiki/Nat%C3%BCrliche_Zahl

Hier gilt also $\begin{eqnarray*} \mathbb N = \{1,2,3,... \} \end{eqnarray*}$

Um Nachzuweisen, dass alle $\begin{eqnarray*} n \in n \end{eqnarray*}$ eine Egenschaft E erfüllen sind 3 Schritte notwendig:

1. Nachweis für n=1.
2. Annahme, dass n die Eigenschaft E besitzt
3. Beweis, dass dann auch (n+1) die Eigenschaft E besitzt

Es muss aber nicht immer ab n=1 stimmen, dennoch kann man mit Induktion arbeiten, wenn ab einem minimalen n alle weiteren natürlichen Zahlen diese Eigenschaft haben. (Dominokette)

Die Begründung? verwirrt

verwirrt

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

Erklärt dann doch nur nochmal, wie wir mit den Eigenschften auf die Menge kommen. Aber das muss nicht immer IN sein. Sondern alle natürlichen Zahlen ab dem Induktionsanfang.

08.08.2007, 12:52

way

Auf diesen Beitrag antworten »

tigerbine, danke,
aber Du hast eigentlich einfach nochmal die vollständige Induktion erklärt, die ist mir völlig klar, nur die andere Formulierung versteh ich nicht.
Meine Frage hast du auch nicht verstanden, trotzdem danke für Deine Mühe.
Grüsse.

08.08.2007, 12:59

tigerbine

Auf diesen Beitrag antworten »

Die andere Formulierung, war doch die, oder?

Zitat:

E ist für 1 richtig.
E richtig für n => E richtig für n+1.

Mein Kommentar:

Es muss nicht immer bei 1 begonnen werden. Aber nur so bekommt am Ende die Gültigkeit für alle natürlichen Zahlen.
Hier stecken 2 Schritte drin. Linke Seite ist die Induktionsbehauptung (Annahme), rechts steht dann der Induktionsschluss

Was ist daran nun unklar? verwirrt

verwirrt

(Bevor wir zur Begründung kommen)

08.08.2007, 13:02

way

Auf diesen Beitrag antworten »

ok, das ist mir schon völlig klar, aber der komische Satz am Anfang:

"Um für eine Eigenschaft E, die für natürliche Zahlen sinnvoll formuliert werden kann, den Nachweis zu führen, dass E für alle natürlichen Zahlen richtig ist, brauch man nur zu zeigen:"

Vielleicht leg ich da auch viel zu viel Wert drauf, am besten ich vergess das und merk mir nur:

E ist für 1 richtig.

E richtig für n => E richtig für n+1.

denn das ist völlig klar.

08.08.2007, 13:08

tigerbine

Auf diesen Beitrag antworten »

Es ist zwar vielleicht etwas "gestochenes" Deutsch, dennoch kann ich in dem Satz keinen Fehler finden. "Sinnvoll formuliert" könnte auch "wohl definiert" heißen. Sprich wir dürfen ohne weiteres jedes natürliche n einsetzen.

Ob es dann auch für jedes n stimmt, kann eben "einfach" mittels v-Induktion gezeigt (oder widerlegt) werden

Anzeige

08.08.2007, 13:11

way

Auf diesen Beitrag antworten »

Ok, kannst Du vielleicht noch was zur Begründung sagen...

08.08.2007, 13:18

zeusosc

Auf diesen Beitrag antworten »

So wie ich es verstehe:
Die "Vollständige Induktion" (jedenfalls den Satz den ich kenn') sagt, daß wenn eine Eigenschaft E auf eine Teilmenge von IN zutrifft, und diese Teilmenge induktiv ist, dann muss sie gleich der natürlichen Zahlen sein, denn die natürlichen Zahlen sind die kleinste induktive Menge.

Daher ist es wichtig zu unterscheiden:
a) W Teilmenge von IN mit der Eigenschaft E
b) a in W mit Eigenschaft E
c)
c.1) ex. ein a+1 in IN die nicht die eigenschaft E hat,
so ist a+1 nicht in W
=> ist ein a+1 nicht in W so ist W nicht induktiv
c.2) ex. kein a+1 in IN das nicht die Eigenschaft E hat,
so ist a+1 in W
=>da alle a+1 in W, so ist W induktiv

d.h.: währe die Folgerung am Schluss nicht das W=IN ist, hätten wir keine Aussage, daß die Eigenschaft E auf ALLE Elemente zuträfe.

Hat das Deine Frage beantwortet??

grüüße

08.08.2007, 13:23

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Begründung: Dann ist nämlichM:= {n $\begin{eqnarray*} \in \end{eqnarray*}$ IN | E ist richtig für n } eine induktive Teilmenge und damit gleich N."

Hatte ich ja eigentlich auch schon.

Wir starten bei 1 (Induktionsanfang). Mit der IV und dem IS folgt doch dann die Gültigkeitskette

1 -> 2 -> 3 -> 4 -> 5 -> etc.

also für alle natürlichen Zahlen. Wenn dich das Wort Teilmenge stört, welche Beziehungen können denn hier auftreten? Da die n alle natürlich sind, gilt für M sicherlich:

$\begin{eqnarray*} M \subseteq \mathbb N \end{eqnarray*}$

aufgrund ihrer Gestalt (Induktiv und Startwert 1) gilt dann eben auch noch

$\begin{eqnarray*} M = \mathbb N \end{eqnarray*}$

Würde es erst ab n=2 eine wahre Aussage geben, so eben

$\begin{eqnarray*} M \subset \mathbb N \end{eqnarray*}$

@zeusocs:

Wie habt ihr "Induktive Teilmenge definiert", d.h. was ist Euer Startwert?

Gruß,
tigerbine Wink

Wink

08.08.2007, 13:28

way

Auf diesen Beitrag antworten »

Irgendwie check ich das nicht.
Ich betrachte mal nur {n€IN | E ist richtig für n }.
Da steht doch eigentlich völlig klar, dass die Eigenschaft E für alle n aus N gilt oder nicht???

08.08.2007, 13:36

Airblader

Auf diesen Beitrag antworten »

Nein, es ist die Menge aller n, für die E gilt. Das bedeutet nicht, dass diese Menge gleich N ist.

air

08.08.2007, 13:36

tigerbine

Auf diesen Beitrag antworten »

Nein, das steht da nicht. Da steht, dass "M", die (Teil)Menge der natrülichen Zahlen ist, die die Eigenschaft E besitzen. Beispiel

$\begin{eqnarray*} M:=\{n \in \mathbb N~|~n^2 \text{ ist gerade} \} \end{eqnarray*}$

08.08.2007, 13:39

way

Auf diesen Beitrag antworten »

Aah, jetzt wird einiges klarer. Ich mach mir nochmal Gedanken und meld mich später nochmal.
Vielen dank euch!

08.08.2007, 14:03

zeusosc

Auf diesen Beitrag antworten »

Hi nochmal,
zwar steht das schon da, aber @tigerbine:
es wurde keine induktive teilmenge definiert, sondern nur eine teilmenge von IN,
WENN diese aber induktiv ist, dann muss diese gleich der Natürlichen Zahlen sein.,...

grüüüße

09.08.2007, 10:37

way

Auf diesen Beitrag antworten »

Hi tigerbine,

aber irgendwie stimmt doch wieder was nicht.
Das Beispiel das Du genannt hast, also die n€N mit der Eigenschaft n^2 ist gerade, haut doch gar nicht hin, da dass doch gar keine induktive Menge ist, aber in der Begründung steht, das ist eine?!?!?!

09.08.2007, 10:45

way

Auf diesen Beitrag antworten »

Hi tigerbine, ich glaub ich hab meinen Denkfehler.
Die Eigenschaft muss natürlich richtig für 1 sein und, wenn richtig für n, dann richtig für n+1.
Jetzt wirds glaube ich klarer. Die Eigenschaft in der geschweiften Klammer ist natürlich die gleiche wie oben.

09.08.2007, 10:57

tigerbine

Auf diesen Beitrag antworten »

Das Beispiel war dazu gedacht zu verstehen, dass mit $\begin{eqnarray*} M:= \{n \in \mathbb N |~E\} \end{eqnarray*}$ nicht automatisch M=IN folgt.

Es war nicht dazu gedacht, die Menge M hier mittels Induktion zu bestimmen.

Bei der Induktiven Menge wollte ich darauf aufmerksam machen, dass es nicht ausreicht, dass auch gilt für n -> n+1 folgt, sondern es auch auf den Startwert ankommt.

Meine Rückfrage wurde diesbezgl. nicht ganz beanwortet. Ich wollte eure formale Definition gerne einmal hören. Bei Wiki wird bei 0 gestartet, das ist es jetzt wieder Ansichtssache, ob die zu IN gehört oder nicht. Wenn nicht, müßte meiner Meinung nach die Bedingung Startwert 1 gelten, damit die Menge Induktiv ist.

Gruß Wink

Wink

09.08.2007, 11:04

way

Auf diesen Beitrag antworten »

Bei uns wird bei 1 gestartet. Aber irgendwie bin ich jetzt ganz durcheinander :-(
Bzw. vielleicht hab ich es ja auch versanden.
Kannst Du mir eine Frage dazu stellen, ob ich es wirklich verstanden habe?

09.08.2007, 11:05

tigerbine

Auf diesen Beitrag antworten »

Wieso denn?

09.08.2007, 11:06

way

Auf diesen Beitrag antworten »

Kannst Du mir eine Frage vielleicht dazu stellen ob ich es wirklich verstanden habe?

09.08.2007, 11:13

tigerbine

Auf diesen Beitrag antworten »

Lol^^ Formuliere/Beweise mit eigenen Worten, für welche natürlichen Zahlen gilt:

$\begin{eqnarray*} \sum_{k=1}^n~k=\frac{n(n+1)}{2} \end{eqnarray*}$
$\begin{eqnarray*} n^2 \leq 2^n \end{eqnarray*}$

sind die Lösungsmengen induktiv? Wenn nein, warum darf man dennoch das Prinzip der vollständigen Induktion anwenden?

09.08.2007, 11:29

way

Auf diesen Beitrag antworten »

Ich mach mal erst das zweite Beispiel.
Für n=1, n=2 passt es, für n=3 passt es nicht.
Die Lösungsmenge ist nicht induktiv, sonst müsste 3,4,5,6... auch passen.
Vollständige Induktion hat ja nichts mit induktiver Lösungsmenge zu tun.

Bei dem ersten Beispiel passt es für 1, für 2 nicht.
Hier kann man die Lösungsmenge nicht festellen, da man alle Zahlen einsetzen müsste.

09.08.2007, 11:36

tigerbine

Auf diesen Beitrag antworten »

Nö, also ich hatte oben ein k vergessen. Aber deine Antworten passen nicht

Aufgabe 2:

Tabelle machen. Wann stimmt die Behauptung?

n=1: $\begin{eqnarray*} 1^2 \leq 2^1 \end{eqnarray*}$ passt

n=2: $\begin{eqnarray*} 2^2 \leq 2^2 \end{eqnarray*}$ passt

n=3: $\begin{eqnarray*} 3^2 \leq 2^3 \end{eqnarray*}$ passt nicht

n=4: $\begin{eqnarray*} 4^2 \leq 2^4 \end{eqnarray*}$ passt

n=5: $\begin{eqnarray*} 5^2 \leq 2^5 \end{eqnarray*}$ passt

Vermutung, ab n=4 passt es. Kann man das beweisen?

09.08.2007, 13:57

zeusosc

Auf diesen Beitrag antworten »

*Zensiert* Kommentar siehe unten.

09.08.2007, 14:09

WebFritzi

Auf diesen Beitrag antworten »

@zeusosc: Komplettlösungen sind hier nicht gerne gesehen.

09.08.2007, 14:27

zeusosc

Auf diesen Beitrag antworten »

@webfritzi: ja sry,
ich versuch mir die Lösungsmethode der Vollständigen Induktion begreiflich zu machen, da ich schon sehr lange probleme damit habe, daher sehe ich den begriff "Komplettlösung" mal als kompliment. *g*
Ich versuchs zukünftig zu vermeiden...

Zitat:

Original von tigerbine
sind die Lösungsmengen induktiv? Wenn nein, warum darf man dennoch das Prinzip der vollständigen Induktion anwenden?

Da habe ich auch noch meine probleme mit,
aber ich denke das die Lösungsmenge als bildmenge zu verstehen ist,
also (bzgl. des obigen beispiels):
$\begin{eqnarray*} \sum_{\cdot =1}(\cdot) : W\subseteq\mathbb{N}\rightarrow \mathbb{K} \end{eqnarray*}$
$\begin{eqnarray*} n \mapsto \frac{n(n+1)}{2} \end{eqnarray*}$
daher, wird nur überprüft ob die Urbildmenge bzgl. der bildvorschrif induktiv ist,
das würde erklären das die lösungsmenge als bildmenge nicht undbedingt induktiv sein muss,..

------------------------------------------------
bitte bestätigen oder aufklären Big Laugh

Big Laugh

------------------------------------------------

grüüüße

09.08.2007, 14:34

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von zeusosc
@webfritzi: ja sry,
ich versuch mir die Lösungsmethode der Vollständigen Induktion begreiflich zu machen, da ich schon sehr lange probleme damit habe, daher sehe ich den begriff "Komplettlösung" mal als kompliment. *g*

OK, aber das hier ist ways Thread. Wenn dir nicht klar ist, ob dein Lösungsvorschlag OK ist, dann solltest du dafür einen eigenen Thread eröffnen. In diesem Thread hier soll way auf die Lösung gebracht werden und nicht du.

09.08.2007, 15:20

tigerbine

Auf diesen Beitrag antworten »

zeusosc:

way hatte mich um Übungsfragen gebeten. Warum löst Du das Komplett für ihn? unglücklich

unglücklich

Da bin ich ehrlich etwas angesäuert. Ich zensiere das nun auch. du bekommst deine Lösung an PN, kannst einen Eigenen Thread damit machen.

Lies dir bitte mal http://de.wikipedia.org/wiki/Vollst%C3%A...und_Variationen

durch, dann weißt Du auch,was ich mit Beispiel 2 bezwecke. Das Beweisprinzip geht auch, wenn nicht alle nat. Zahlen die Eigenschaft E besitzen.

Induktiv heißt die Menge aber nur, wenn der Startwert 0 bzw. 1 ist.

09.08.2007, 16:28

tensor07

Auf diesen Beitrag antworten »

RE: Vollständige Induktion, andere Formulierung

Zitat:

Original von tigerbine

Zitat:

E ist für 1 richtig.
E richtig für n => E richtig für n+1.

Mein Kommentar:

Es muss nicht immer bei 1 begonnen werden. Aber nur so bekommt am Ende die Gültigkeit für alle natürlichen Zahlen.
Hier stecken 2 Schritte drin. Linke Seite ist die Induktionsbehauptung (Annahme), rechts steht dann der Induktionsschluss

Richtig, aber die Induktionsannahme dient nur zum Beweis von

Zitat:

Für alle natürlichen n: E richtig für n => E richtig für n+1

Also

Zitat:

Original von tigerbine
Um Nachzuweisen, dass alle $\begin{eqnarray*} n \in n \end{eqnarray*}$ eine Egenschaft E erfüllen sind 3 Schritte notwendig:

1. Nachweis für n=1.
2. Annahme, dass n die Eigenschaft E besitzt
3. Beweis, dass dann auch (n+1) die Eigenschaft E besitzt

bezieht sich auf den Beweis.

Man nimmt nicht einfach als Bedingung an, dass E für ein n gilt. Das n wäre völlig willkürlich, und man würde nicht weit kommen. Das n ist wirklich nur ein "dummy" Index, quantifiziert in der zweiten Bedingung von way.

09.08.2007, 18:38

WebFritzi

Auf diesen Beitrag antworten »

RE: Vollständige Induktion, andere Formulierung

Zitat:

Original von tensor07
Das n ist wirklich nur ein "dummy" Index

Ich bin mir sicher, dass tigabiene das auch so meinte.

09.08.2007, 20:21

way

Auf diesen Beitrag antworten »

Hi tigerbine,
klar, bei Deinem 2ten Beispiel könnte man es mit vollständiger Induktion Beweisen, dass es für n grössergleich 4 gilt. Es sei denn, man sieht dann während der vollständigen Induktion dass es doch nicht passt. Dann wäre aber das Gegenteil bewiesen.
Aber irgendwie seh ich da keinen Zusammenhang mit meinem ursprünglichen Problem.

Grüsse...

09.08.2007, 21:15

tigerbine

Auf diesen Beitrag antworten »

Danke, Fritz Mit Zunge

Mit Zunge

@ way:

Ich weiß jetzt echt nicht wo du noch hängst. unglücklich

unglücklich

wir sind nun die Formulierung der VI von Anfang durchgegangen und haben auch erklärt, was es mit der Menge, die im Beweis angeführt wird, auf sich hat.

Als "Ausblick" wollte ich Dir eben noch zeigen, dass die VI als Beweis mittel nicht an den Startwert n=1 gebunden ist. Man kann das vom Anfang analog formulieren, nur dass es eben nicht für alle n in IN gilt sondern erst für alle n ab dem Startwert.

Desweiteren zeigt der Wikipedia Link, dass man sogar Werte "überspringen" kann. Damit wären wir bei dem Beispiel mit den Geraden Quadraten. Denn nur jede 2 Zahl besitzt ein Gerades Quadrat.

09.08.2007, 21:46

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
Danke, Fritz Mit Zunge

Mit Zunge

Uhhh, ich liebe deine Küsse. Big Laugh

Big Laugh

Big Laugh

Big Laugh

10.08.2007, 05:41

way

Auf diesen Beitrag antworten »

Hi tigerbine,

ich betrachte jetzt doch nocheinmal die Begründung:
Seh ich das richtig, dass die Menge {n€N|E ist richtig für N}, diejenige Menge ist, die auf
1. E ist richtig für 1 und
2. E richtig für n=> n richtig für n+1
geprüft wurde und deswegen eine induktive Teilmenge ist?

Ich kann es leider nicht besser ausdrücken, aber ich denke, dass ich es jetzt dank Deiner Hilfe (einigermassen) verstanden habe.

Am Anfang hatte ich vergessen die Def. induktiver Mengen hinzuschreiben, so wie sie hier im Buch definiert ist:

Def.: Sei M* das Stystem der induktiven Teilmengen von K (K Körper). Wir definieren dann N:=Durchschnitt M* und nennen N die Menge der natürlichen Zahlen.

Grüsse...

10.08.2007, 11:08

tigerbine

Auf diesen Beitrag antworten »

Ja und nein. Hier, da wir bei dem "Test" mit der kleinsten natürlichen Zahl beginnen ist das richtig.

Wir wollen zeigen, dass alle nat. Zahlen die Eigenschaft E besitzen. Da IN induktiv ist, kann m an das wie folgt zeigen. 1 hat die Eigenschaft E und es muss mit einem "Dummy" n aus IN auch n+1 die Eigenschaft E besitzen.

Fertig.

Wir kennen die Menge im Vorfeld ja nicht. Mit der Induktion zeigen wir eben, es ist IN oder es ist nicht IN.

10.08.2007, 11:43

way

Auf diesen Beitrag antworten »

Hi tigerbine,
ok, jetzt ist es einges klarer geworden. Ich denke mehr sollte man darüber auch nicht sagen, weil es wahrscheinlich nichts mehr zu sagen gibt. Ich werde das Thema erst mal eine Weile ruhen lassen und es mir dann nochmal anschauen.
Vielen Dank Dir nochmal für die Geduld!
Grüsse.

10.08.2007, 11:54

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Ich denke mehr sollte man darüber auch nicht sagen, weil es wahrscheinlich nichts mehr zu sagen gibt.

Ich denke das können wir so sehen lassen Augenzwinkern

Augenzwinkern

Gruß

Wink

10.08.2007, 15:38

tensor07

Auf diesen Beitrag antworten »

Zitat:

Original von way
Def.: Sei M* das Stystem der induktiven Teilmengen von K (K Körper). Wir definieren dann N:=Durchschnitt M* und nennen N die Menge der natürlichen Zahlen.

Soll hier K ein Zahlkörper sein?

10.08.2007, 17:33

way

Auf diesen Beitrag antworten »

Hi tensor07,

http://de.wikipedia.org/wiki/K%C3%B6rper_%28Algebra%29

Grüsse.

11.08.2007, 04:44

tensor07

Auf diesen Beitrag antworten »

Es darf kein allgemeiner Körper sein, da es auch endliche gibt: und dann wäre $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ offensichtlich nicht drin enthalten.

12 nächste Seite »

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »