vollständige Induktion < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:15 Do 29.10.2009 | | Autor: | Ersty |
| Aufgabe | Beweisen Sie die folgende Variante der vollständigen Induktion.
"Hat jedes (feste) n eine gegeben Eigenschaft, sofern alle m < n sie haben, dann hat jede natürliche Zahl diese Eigenschaft." |
vollständige Induktion ist so aufgebaut:
Induktionsannahme: "Hat jedes (feste) n eine gegeben Eigenschaft, sofern alle m < n sie haben, dann hat jede natürliche Zahl diese Eigenschaft."
Sie bedeutet für mich, wenn jedes n eine Eigenschaft besitzt, sofern dies die Vorgänger besitzten, dann hat jede natürliche Zahl diese Eigenschaft. Richtig verstanden?
Induktionsanfang: Beweis für den Anfangswert,
was ist das hier: 1? Es gibt eine Zahl mit einer gegeben Eigenschaft..... Das geht nicht......., das kann man nicht so übertragen, wie bei Induktionsaufgaben, wo man Formeln beweisen muss.
Soll im Induktionsanfang der Nachweis erfolgen, dass diese bestimmte Eigenschaft für den Vorgänger, sprich n-1, gilt?
Hilft es mir, wenn ich die Induktionsannahme in eine Formel umwandeln kann?
Wenn ja, habt ihr einen Tipp, wie ich auf die Formel kommen kann? Hab da momentan noch gar keinen Schimmer.
Was ist eine gegeben Eigenschaft, ist das ein Prädikat wie die Aussageform M = {x | p(x) = ich habe eine Eigenschaft}?
Ist die Wahl, welche Eigenschaft ich nehme nicht total willkürlich? Oder soll ich es allgemein halten?
Induktionsvoraussetzung: Gelte dies für n
Induktionsschritt: Zeige dies für n+1
Ich habe diese Frage, in keinem anderen Forum gestellt.
Vielen Dank schon im Voraus!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:28 Do 29.10.2009 | | Autor: | leduart |
Hallo
Ich denke, du sollst die Behauptung dass das ne richtige Möglichkeit der vollst. Induktion ist zeigen.
d.h. du kennst die "normale" vollst Induktion, jetz kannst du die Neue nehmen, und zeigen, dass dann auch die alte gilt. dann bist du fertig.
oder du tust so, als ob du die alte nicht kennst und beweist dass das neue auch beweist, dass etwas für alle natürlichen Zahlen gilt.
Was du NICHT machen sollst ist ne "alte" vollst. Induktion.
also Beh: für alle n gilt, wenn A(n) richtig ist ,unter der Vors dass A(m) richtig ist für alle alle m<n, dann ist es für alle [mm] n\in\IN [/mm] richtig.
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:18 Do 29.10.2009 | | Autor: | piet.t |
Hallo leduart,
So ganz kann ich Dir nicht zustimmen
> Hallo
> Ich denke, du sollst die Behauptung dass das ne richtige
> Möglichkeit der vollst. Induktion ist zeigen.
> d.h. du kennst die "normale" vollst Induktion,
![[ok]](/images/smileys/ok.gif "[ok]") so weit bin ich noch bei dir.
> jetz kannst
> du die Neue nehmen, und zeigen, dass dann auch die alte
> gilt. dann bist du fertig.
> oder du tust so, als ob du die alte nicht kennst und
> beweist dass das neue auch beweist, dass etwas für alle
> natürlichen Zahlen gilt.
Es ist doch eher andersum: man soll zeigen, dass die "neue" Induktion auch funktioniert und das einzige hilfsmittel, das man dazu hat, ist die "alte" vollständige Induktion. Das ist schließlich das einzige Axiom, mit dessen Hilfe man folgern kann, dass etwas "für alle [mm] $n\in\IN$" [/mm] gilt.
Gruß
piet
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:42 Do 29.10.2009 | | Autor: | Ersty |
nur noch mal zur Sicherheit die Nachfrage:
mit "alter Induktion" meint ihr die Beweistechnik "vollständige Induktion"?
Also soll ich mit Hilfe der Beweistechnik, die Beweistechnik beweisen?^^
Grüße, Ersty
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:13 Do 29.10.2009 | | Autor: | leduart |
Hallo
habt ihr die vollständige Induktion als Axiom?
Dann nimm die neue als Axiom und folgere daraus die alte (vollst) und umgekehrt. dann sind sie gleichwertig.
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:40 Do 29.10.2009 | | Autor: | piet.t |
> Hallo
> habt ihr die vollständige Induktion als Axiom?
> Dann nimm die neue als Axiom und folgere daraus die alte
> (vollst) und umgekehrt. dann sind sie gleichwertig.
> Gruss leduart
Wobei hier so wie ich die Aufgabe lese "und umgekehrt" ausreicht.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:52 So 01.11.2009 | | Autor: | Ersty |
Nein, wir haben die vollständige Induktion nicht als Axiom, leider!
Wir haben nur die Addition auf N mit volllständiger Induktion in der VL gehabt.
Ich habe keinen Schimmer, wie ich dann diese Aufgabe lösen soll.
Darf ich das hier schreiben?
Wenn n eine bestimmte Eigenschaft p(x) hat und alle n-m (z.B. (n-(n-1)) (Vorgänger von n), (n-(n-2)), ..., (n-o), also alle natürlichen Zahlen von 0 bis (n-1) ), dann kann man auf jeden Fall durch vollständige Induktion von der 0 ausgehend beweisen, dass p(x) für jedes x aus (1, 2, ..., n) stimmt. Also gilt die Aussage für
0
den Nachfolger von 0, also 1
den Nachfolger von 1, also 2
...
(n-1) und den Nachfolger von (n-1), also n
Die Richtigkeit von p(x) für alle x aus (0, ..., n) ergibt sich aus der Aufgabe.
Nach dem Prinzip der vollständigen Induktion kann diese „Kette“ (trifft p(x) für m zu, dann auch für den Nachfolger, dessen Nachfolger,...) nicht bei n „abreißen“, sondern die Aussage p(x) muss auch für den Nachfolger von n gelten, also für (n+1), den Nachfolger davon usw.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:08 So 01.11.2009 | | Autor: | piet.t |
Hallo,
>
> Darf ich das hier schreiben?
>
> Wenn n eine bestimmte Eigenschaft p(x) hat und alle n-m
> (z.B. (n-(n-1)) (Vorgänger von n), (n-(n-2)), ..., (n-o),
> also alle natürlichen Zahlen von 0 bis (n-1) ), dann kann
> man auf jeden Fall durch vollständige Induktion von der 0
> ausgehend beweisen, dass p(x) für jedes x aus (1, 2, ...,
> n) stimmt.
DAs braucht man ja nicht mehr beweisen, das war eher vorausgesetzt.
> Also gilt die Aussage für
>
> 0
> den Nachfolger von 0, also 1
> den Nachfolger von 1, also 2
> ...
> (n-1) und den Nachfolger von (n-1), also n
>
> Die Richtigkeit von p(x) für alle x aus (0, ..., n) ergibt
> sich aus der Aufgabe.
> Nach dem Prinzip der vollständigen Induktion kann diese
> „Kette“ (trifft p(x) für m zu, dann auch für den
> Nachfolger, dessen Nachfolger,...) nicht bei n
> „abreißen“, sondern die Aussage p(x) muss auch für
> den Nachfolger von n gelten, also für (n+1), den
> Nachfolger davon usw.
So wie ich das verstehe würde das bedeuten: wenn alle natürlichen Zahlen bis n eine bestimmte Eigenschaft haben, dann müssen diese auch alle auf n folgenden Zahlen haben.
Betrachtet man ein vorgegebenes n ist das sicher nicht richtig. Zum Beispiel mit n = 5 und der Eigenschaft "ist kleiner als 6".
Ich denke der richtige Ansatz für diese Aufgabe ist schon ein "klassischer" Induktionsbeweis.
Als Voraussetzung haben wir folgendes Gegeben:
Für jedes n und eine Eigenschaft p(n) gilt: p(m) [mm] \forall [/mm] m<n [mm] \Rightarrow [/mm] p(n)
Und damit kann man nun per Induktion Beweisen, dass p(n) für alle n [mm] \in \IN [/mm] gilt.
Als Beispiel mal den Induktionsanfang:
Bei n=0 ist p(m) [mm] \forall [/mm] m<n sicher erfüllt, denn es gibt kein m<0. Damit gilt p(0).
Die Induktionsannahme muss man wohl etwas abwandeln: p(m) gelte für alle m<n.
Dann kannst Du jetzt zeigen, das p(n+1) gilt.
Das ganze ist noch nicht bis ins letzte Detail durchdacht, aber irgendwie in dieser Richtung müsste es wohl funktionieren.
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:55 So 01.11.2009 | | Autor: | Ersty |
Danke, ich versuchs mal!
Gruß Ersty
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:39 Do 29.10.2009 | | Autor: | piet.t |
> nur noch mal zur Sicherheit die Nachfrage:
> mit "alter Induktion" meint ihr die Beweistechnik
> "vollständige Induktion"?
> Also soll ich mit Hilfe der Beweistechnik, die
> Beweistechnik beweisen?^^
Wenn man eine Beweistechnik nicht postuliert (wie im Induktionsaxiom), dann braucht man wohl eine andere Beweistechnik, um sie zu Beweisen - die meisten Werkzeuge werden ja auch mit Hilfe von anderen Werkzeugen hergestellt.
>
> Grüße, Ersty
|
|
|
|
