Induktion

Neue Frage »

Cordovan Auf diesen Beitrag antworten »
Induktion
Hallo Community!

Mir wurde letztens eine lustige Aufgabe für Erstsemester gezeigt. Ich wollte euch mal teilhaben lassen, auch wenn nur wenige es nicht sofort rauskriegen ^^

Satz: Sind mit und , dann folgt .

Beweis (per Induktion):
Induktionsanfang für n=1: Ist und , dann folgt offenbar und , damit also .

Annahme: Es gelte für ein : Aus und folgt .

Schritt:
Seien , dann sind und . Nach Voraussetzung ist dann und damit . QED

Wo liegt der Fehler?
lgrizu Auf diesen Beitrag antworten »
RE: Induktion
mit vollständiger induktion kann man nur eigenschaften nat. zahlen beweisen, es dürfen also nur aussagen über eine nat. zahl getroffen werden, hier ist ein vergleich zweier zahlen, der durch induktion bewiesen werden soll.
Leopold Auf diesen Beitrag antworten »

Das stimmt nicht. Induktion ist möglich bei All-Aussagen über natürliche Zahlen:



Dabei kann eine beliebige Eigenschaft einer natürlichen Zahl sein. Und da dürfen auch andere Objekte als lokale Variable (das ist meine vorübergehende Bezeichnung, ich weiß nicht, wie die Logiker das nennen) drin vorkommen.

Offenbar beginnen hier die natürlichen Zahlen mit :



Und in der folgenden Aussage fungieren als lokale Variable



Äußerlich stimmt hier alles. Der Beweis enthält einen inhaltlichen Fehler, und zwar im Induktionsschluß.
tmo Auf diesen Beitrag antworten »

Fermat wäre zurecht zutiefst beleidigt von so einem Beweis, ist er doch ein Widerspruch zu seiner Methode des unendlichen Abstiegs Augenzwinkern
Eierkopf Auf diesen Beitrag antworten »

Zitat:
Original von Leopold
Das stimmt nicht. Der Beweis enthält einen inhaltlichen Fehler, und zwar im Induktionsschluß.


In der Tat!

Es wird ja wohl gar kein Induktionsschluss i.S.d. VI durchgeführt geführt, sondern allein, ohne Bezug zu A(n) die Aussage A(n+1) umgeformt.
Wieso hält sich im übrigen immer noch irgend wo der alte Zopf, dass A(n) als wahr angenommen werden müsste. Das zerstört doch den Grundgedanken der Induktion in den beiden erforderlicchen Schritten.
Cordovan Auf diesen Beitrag antworten »

Ich kann mich Leopolds Beitrag nur vollständig anschließen!

@Eierkopf:
Das verstehe ich nicht so ganz - die Voraussetzung wird doch benutzt. Und was meinst du mit "dass A(n) als wahr angenommen werden muss"? Ist die Induktion formal falsch?

Cordovan
 
 
Lord Pünktchen Auf diesen Beitrag antworten »
RE: Induktion
Zitat:
Original von Cordovan
Annahme: Es gelte für ein : Aus und folgt .


Hier müsste es für alle und nicht für ein heißen.


Zitat:
Original von Cordovan
Schritt:
Seien , dann sind und . Nach Voraussetzung ist dann und damit . QED

Wo liegt der Fehler?


Ein Fehler liegt in der Annahme, dass aus folgt, dass weil hier in keinster Weise sichergestellt wurde, dass a-1 überhaupt noch eine natürliche zahl ist. (Und damit die auf den natürlichen Zahlen definierte Kleinergleichrelation erst garnicht definiert ist)
Ein anderer Fehler besteht wie bereits gesagt im Induktionsschluss ... eben weil nicht sichergestellt wurde, dass a-1 und b-1 natürliche zahlen sind


Sieht man ja schon beim Beispiel n=2, a=1 und b=2 ... also das "Rätsel" ist in meinen Augen ein klassisches Beispiel für "Glaubt nicht jeden unsinn sondern denkt mal mit und villeicht sogar einen halben schritt weiter als es auf der tafel steht"
jester. Auf diesen Beitrag antworten »
RE: Induktion
Zitat:
Original von Lord Pünktchen
Zitat:
Original von Cordovan
Annahme: Es gelte für ein : Aus und folgt .


Hier müsste es für alle und nicht für ein heißen.


Wenn man annimmt, dass die Aussage für alle stimmt, wozu sollte man dann noch einen Beweis führen? verwirrt
Lord Pünktchen Auf diesen Beitrag antworten »
RE: Induktion
Tja ... jetzt hast du mich verwirrt ...

Induktionen mach ich meistens ohne Induktionsannahme ... nur mit Induktionsverankerung und Induktionsschritt ....


Nimmt man an, es existiert ein n für das die Induktionsannahme gilt, was bringt einem das?
Wo wird das verwendet? Und wieso annehmen ... für n=1 wurde es ja bewiesen ... ich nehme an etwas bewiesenes wäre wahr ?????? oO

Nimmt man an, es gilt für alle n ... dann braucht man nicht weitermachen ... es gilt ja die Reflexivität A=>A =/


da muss ich leider kapitulieren ... verwirrt
aber es wäre schön wenn du mir das erklären könntest Jester, denn das häufig eine induktionsannahme gemacht wird ist mir bekannt ... nur wie weiß ich jetzt nichtmehr Hammer

Edith: Die Induktionshypothese bezieht sich auf A(n) und wird auch im Induktionsschritt verwendet ... dann beweist man A(n+1) ... sowas ... ein komplett verwirrtes pünktchen geschockt

Edith2: Leserlichkeit
induktionist Auf diesen Beitrag antworten »

Man nimmt schon an es gilt für ein , und man nimmt nicht an, dass es für alle gilt, das würde m.M.n keinen Sinn machen. Denn man beweist mit dem Induktionsschritt schließlich nur folgendes:

"Wenn die Aussage für ein n gilt, gilt sie auch für n+1."

Weil man weiß, dass sie für n=1 stimmt, stimmt sie somit auch für n=2. Damit auch für n=3 etc. ... , somit für alle natürlichen Zahlen.

Der Induktionsschritt hier ist aber falsch, weil eben nicht sichergestellt wird, dass a,b natürliche Zahlen sind. Mir gefällt der "Beweis" aber trotzdem gut, da der Fehler nicht zu offensichtlich ist.
Eierkopf Auf diesen Beitrag antworten »

Zitat:
Original von Cordovan

Das verstehe ich nicht so ganz - die Voraussetzung wird doch benutzt. Und was meinst du mit "dass A(n) als wahr angenommen werden muss"? Ist die Induktion formal falsch?



Sorry, aber ich schrieb "müsste" und nicht muss.

Die vollstandige Induktion sieht so aus:
Ich mache einen Induktionsanfang, beispielsweise durch den Nachweis A(1) ist wahr. Gelingt dies nicht, so versuche ich den entsprechenden Nachweis für A(2), usw., bis ich eine wahre Anfangsaussage gefunden habe.
Ich zweige im zweiten Schritt, dem Induktionsschluss, formal,dass aus A(n) die Aussage A(n+1) folgt. Man beachte hierbei, dass der Induktionsschluss selbst keine Aussage über der Wahrheitswert eines konkretisierten A(n) oder A(n+1) macht.
Es ergibt sich aber aus dem korrekten Induktionaschluss und dem Induktionsanfang, dass da A(1) wahr ist, wegen der gültigen Forderung auch A(2) wahr sein muss, usw.

@Lord Püntchen
Du hast an der Stelle den Erstbeitrag missverstanden. Es sollte nicht die zu beweisende Aussage sein, sondern die von mir kritisierte "induktionsannahme", dass die Aussage für ein einzelnes n wahr sein soll. Das mach aber (s.o.) keinen Sinn.

Gruß
Ei
Lord Pünktchen Auf diesen Beitrag antworten »

Danke für die Erklärung ... bei mir hat sich die Verwirrung auch wieder gelegt Freude
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »