Schaf Problem

    • davidh38
      davidh38
      Bronze
      Dabei seit: 18.01.2005 Beiträge: 833
      Betrachten Sie den folgenden Induktionsbeweis, der zeigen soll, dass alle Schafe einer Herde
      dieselbe Farbe haben.
      Basis f all(Induktionsan f ang) : Es ist klar, dass ein Schaf dieselbe Farbe hat wie es selbst.
      Induktionsschritt :
      Nimm aus einer Herde mit n Schafen ein Schaf a heraus. Die restlichen n1 Schafe haben wegen
      der Induktionsannahme dieselbe Farbe. Nun schicke Schaf a zurück zur Herde und nimm
      ein anderes Schaf b heraus. Durch die Induktionsannahme haben die restlichen n1 Schafe
      (nun wieder mit Schaf a in der Herde) wieder dieselbe Farbe. Also hat a dieselbe Farbe wie alle
      anderen Schafe. Somit haben alle Schafe der Herde dieselbe Farbe.
      Was ist falsch an diesem Beweis?


      Ich habe mir Gedanken gemacht, aber ich komme nicht auf eine präzise Lösung: Ich denke mir, dass der Induktionsanfang lauten sollte: Ein Schaf hat dieselbe Farbe wie eine anderes Schaf. Außerdem ist die Folgerung auch sehr komisch, weil sie folgert, dass alle n-1 Schafe dieselbe Farbe haben, aber aus dem Induktionsanfang geht nur hervor, dass alle Schafe dieselbe Farbe wie sie selbst haben.

      Sind meine Gedanken soweit richtig oder liege ich völlig daneben. Wäre sehr dankbar, wenn mir jemand vielleicht noch ein Tipp gibt, damit ich ein bisschen weiterkomme.
  • 23 Antworten
    • dayero
      dayero
      Bronze
      Dabei seit: 26.02.2005 Beiträge: 1.723
      Original von davidh38

      Basis f all(Induktionsan f ang) : Es ist klar, dass ein Schaf dieselbe Farbe hat wie es selbst.
      Induktionsschritt :
      Nimm aus einer Herde mit n Schafen ein Schaf a heraus. Die restlichen n1 Schafe haben wegen
      der Induktionsannahme dieselbe Farbe.
      lol?
      für mich liest sich das wie:

      alle mäuse sind eingabegeräte.
      sei a eine maus so gilt wegen der induktionsannahme, daß sie horst heißt. folgerung: für alle b gilt frank oder kaffeemaschine.

      wenn dir der beweis nicht einleuchtet, kann ich es auch nochmal für roggenbrote zeigen ;)
    • Faust
      Faust
      Bronze
      Dabei seit: 25.01.2005 Beiträge: 424
      Der Induktionsschritt ist falsch, weil er für n=2 nicht funktioniert. (Erst ab n=3)
    • davidh38
      davidh38
      Bronze
      Dabei seit: 18.01.2005 Beiträge: 833
      Original von Faust
      Der Induktionsschritt ist falsch, weil er für n=2 nicht funktioniert. (Erst ab n=3)
      Ist die Induktionsannahme richtig?
    • gImLi
      gImLi
      Bronze
      Dabei seit: 17.01.2005 Beiträge: 726
      Behauptung: 1 ist die größte natürliche Zahl.
      Beweis durch Widerspruch:
      Sei k eine größere natürliche Zahl als 1 => k^2 > k. Somit kann k nicht die größte natürliche Zahl gewesen sein ...
      ^^

      zum schafproblem:
      ich denke der fehler liegt darin, dass man nicht das schaf "zurückschicken" und ein anderes nehmen darf.
    • Faust
      Faust
      Bronze
      Dabei seit: 25.01.2005 Beiträge: 424
      Original von davidh38
      Ist die Induktionsannahme richtig?
      Ja
    • knobi81
      knobi81
      Bronze
      Dabei seit: 18.03.2005 Beiträge: 9
      die induktionsannahme ist eine richtige annahme.
      der induktionsschritt geht wie du schon geschrieben hast voll am thema vorbei :)


      Die restlichen n1 Schafe haben wegen der Induktionsannahme dieselbe Farbe.
      nein, laut annahme hat das schaf nur die farbe wie es selbst. über die restlichen elemente dieser "schafmenge" kann keine ausssage gemacht werden.
      spiel das mal mit einer bunt angepinselten schafmenge durch, dann ist es sehr schnell offensichtlich ^^

      ein für das problem passender ansatz mit induktion wäre meiner meinung nach sowas wie:


      behauptung: alle schafe habe die gleiche farbe.

      dazu beweist man:

      I) schaf 0 (schaf 1) hat genau eine farbe.

      II) hat schaf n eine farbe so hat auch schaf n+1 genau die gleiche farbe
    • mike1234
      mike1234
      Bronze
      Dabei seit: 31.01.2005 Beiträge: 147
      Original von dayero
      Original von davidh38

      Basis f all(Induktionsan f ang) : Es ist klar, dass ein Schaf dieselbe Farbe hat wie es selbst.
      Induktionsschritt :
      Nimm aus einer Herde mit n Schafen ein Schaf a heraus. Die restlichen n1 Schafe haben wegen
      der Induktionsannahme dieselbe Farbe.
      lol?
      für mich liest sich das wie:

      alle mäuse sind eingabegeräte.
      sei a eine maus so gilt wegen der induktionsannahme, daß sie horst heißt. folgerung: für alle b gilt frank oder kaffeemaschine.

      wenn dir der beweis nicht einleuchtet, kann ich es auch nochmal für roggenbrote zeigen ;)
      Oder das Großvater-Paradoxon nach der Relativitätstheorie. Ein Mann macht eine Zeitreise in die Vergangenheit und erschießt seinen Großvater, bevor sein Vater gezeugt wird. Sein Vater wird also nicht geboren und er selbst damit auch nicht. Wenn er aber nicht geboren wird, wie kann er dann in die Vergangenheit reisen und seinen Großvater erschießen? Schade, daß Einstein nicht mehr lebt, sonst würde ich den mal fragen. :D
    • sammy
      sammy
      Bronze
      Dabei seit: 16.01.2005 Beiträge: 5.315
      Original von mike1234
      Original von dayero
      Original von davidh38

      Basis f all(Induktionsan f ang) : Es ist klar, dass ein Schaf dieselbe Farbe hat wie es selbst.
      Induktionsschritt :
      Nimm aus einer Herde mit n Schafen ein Schaf a heraus. Die restlichen n1 Schafe haben wegen
      der Induktionsannahme dieselbe Farbe.
      lol?
      für mich liest sich das wie:

      alle mäuse sind eingabegeräte.
      sei a eine maus so gilt wegen der induktionsannahme, daß sie horst heißt. folgerung: für alle b gilt frank oder kaffeemaschine.

      wenn dir der beweis nicht einleuchtet, kann ich es auch nochmal für roggenbrote zeigen ;)
      Oder das Großvater-Paradoxon nach der Relativitätstheorie. Ein Mann macht eine Zeitreise in die Vergangenheit und erschießt seinen Großvater, bevor sein Vater gezeugt wird. Sein Vater wird also nicht geboren und er selbst damit auch nicht. Wenn er aber nicht geboren wird, wie kann er dann in die Vergangenheit reisen und seinen Großvater erschießen? Schade, daß Einstein nicht mehr lebt, sonst würde ich den mal fragen. :D
      Na das würde ich ja gerne mal sehen, wo du mir eine Quellenangabe gibst oder nen Zitat wo Einstein behauptet, man kann in die Vergangenheit reisen :rolleyes:
      Die Relativitätstheorie sagt sowas ganz sicher auch nicht aus :P
    • mike1234
      mike1234
      Bronze
      Dabei seit: 31.01.2005 Beiträge: 147
      Original von sammy

      Na das würde ich ja gerne mal sehen, wo du mir eine Quellenangabe gibst oder nen Zitat wo Einstein behauptet, man kann in die Vergangenheit reisen :rolleyes:
      Die Relativitätstheorie sagt sowas ganz sicher auch nicht aus :P
      Das hatte ich auch nicht geschrieben, daß Einstein das behauptet hat. Das Großvater-Paradoxon sagt lediglich aus, welche Komplikationen bei einer solchen Zeitreise entstehen würden. Nach der Relativitätstheorie wären Zeitreisen in die Vergangenheit theoretisch möglich, wenn man ßberlichtgeschwindigkeit erreichen könnte. ßberlichtgeschwindigkeit ist aber nicht möglich, da eine Masse dann durch die Beschleunigung unendlich groß werden würde und somit im gesamten Universum nicht genug Energie vorhanden ist, um eine solche Beschleunigung durchführen zu können.

      Gruß
      Mike
    • sholvar
      sholvar
      Bronze
      Dabei seit: 18.01.2005 Beiträge: 4.826
      Original von davidh38
      Was ist falsch an diesem Beweis?
      Jede Herde hat ein schwarzes Schaf. Folglich kann man die These, welche bewiesen werden soll, verneinen und für falsch erklären. Da is der Fehler. Die These ist falsch. :P
    • gImLi
      gImLi
      Bronze
      Dabei seit: 17.01.2005 Beiträge: 726
      Original von knobi81

      Die restlichen n1 Schafe haben wegen der Induktionsannahme dieselbe Farbe.
      nein, laut annahme hat das schaf nur die farbe wie es selbst. über die restlichen elemente dieser "schafmenge" kann keine ausssage gemacht werden.
      Also nach dem Prinzip der Induktion ist die von dir zitierte Behauptung durchaus noch "richtig".
      Im eigentlichen Sinne "richtig" wird sie natürlich erst, nachdem der Induktionsschritt korrekt vollzogen wurde - aber so funktioniert Induktion nunmal - man darf die Induktionsbehauptung (Aussage gilt für {n-1} beim Induktionsschritt [{n-1}->{n}] benutzen.
    • Korn
      Korn
      Bronze
      Dabei seit: 14.01.2005 Beiträge: 12.511
      Der Fehler liegt darin, dass formal ein Induktionsbeweis eine Beweis über den natürlichen Zahlen N ist. Die natürlichen Zahlen sind ein well-ordered set, also "durchnumeriert". Somit ist das "Zurückschicken" eines Schafs in die Herde nicht gestattet, denn dies würde bedeuten, dass ein n element N existiert so dass n < n - 1 ist ;)

      Wers ganz formal haben will möge in einem Buch zur axiomatischen Mengenlehre unter dem Induktionsprinzip nachsehen.
    • jjacky
      jjacky
      Bronze
      Dabei seit: 17.01.2005 Beiträge: 1.305
      bei den schafen ist der induktionsschritt einfach total falsch. über jede gruppe mit mehr als einem schaf läßt sich nichts algemeines aussagen.

      Original von gImLi
      Behauptung: 1 ist die größte natürliche Zahl.
      Beweis durch Widerspruch:
      Sei k eine größere natürliche Zahl als 1 => k^2 > k. Somit kann k nicht die größte natürliche Zahl gewesen sein ...
      ^^
      das ist kein widerspruch. es wird nur gezeigt, dass k nicht die größte natürliche zahl ist. trotzdem kann sie größer als 1 sein.
    • gImLi
      gImLi
      Bronze
      Dabei seit: 17.01.2005 Beiträge: 726
      Original von jjacky
      bei den schafen ist der induktionsschritt einfach total falsch. über jede gruppe mit mehr als einem schaf läßt sich nichts algemeines aussagen.

      Original von gImLi
      Behauptung: 1 ist die größte natürliche Zahl.
      Beweis durch Widerspruch:
      Sei k eine größere natürliche Zahl als 1 => k^2 > k. Somit kann k nicht die größte natürliche Zahl gewesen sein ...
      ^^
      das ist kein widerspruch. es wird nur gezeigt, dass k nicht die größte natürliche zahl ist. trotzdem kann sie größer als 1 sein.
      natürlich ist das ein Widerspruch :)

      vergleiche dazu den Beweis von Euklid (?) zur Unendlichkeit der Primzahlen ...

      Annahme: Es gäbe eine größte Primzahl k, dann ist p_1 * p_2 ... *k - 1 =: q eine größere Primzahl (oder es gibt eine Primzahl zwischen k und q).

      Ist das gleiche Prinzip ...

      So wirklich kann ich leider auch nciht sagen, worin der Fehler besteht. Muss wohl irgendwas mit der induktiven Definition von N zu tun haben (jede nat Zahl n besitzt per Definition einen "Nachfolger" m, mit m > n)

      Ganz trivial wird es aber auch nicht sein - zumindest steht es im Königsberger Ana II im Kapitel über Variationsrechnung als "Perron'sches Paradoxon"
    • soLidas
      soLidas
      Bronze
      Dabei seit: 16.01.2005 Beiträge: 914
      Korn hats ja im Prinzip schon gesagt:
      Der Fehler bei dem Beweis liegt also quasi darin, daß er eine Annahme macht, die aber gerade bewiesen werden soll.
      Wenn die Indukionsannahme lautet: n-1 Schafe haben dieselbe Farbe, dann kann man natürlich so viele Schafe entfernen wie man will und die Annahme gilt immernoch. Tut man aber nun Schaf a hinzu und entfernt ein anderes Schaf b, dann gilt die Annahme nicht mehr, es sei denn man kann beweisen, daß Schaf a dieselbe Farbe hat, wie Schaf b. Und genau dort beißt sich die Katze dann in den Schwanz ;)
    • jjacky
      jjacky
      Bronze
      Dabei seit: 17.01.2005 Beiträge: 1.305
      Original von gImLi
      Original von jjacky
      bei den schafen ist der induktionsschritt einfach total falsch. über jede gruppe mit mehr als einem schaf läßt sich nichts algemeines aussagen.

      Original von gImLi
      Behauptung: 1 ist die größte natürliche Zahl.
      Beweis durch Widerspruch:
      Sei k eine größere natürliche Zahl als 1 => k^2 > k. Somit kann k nicht die größte natürliche Zahl gewesen sein ...
      ^^
      das ist kein widerspruch. es wird nur gezeigt, dass k nicht die größte natürliche zahl ist. trotzdem kann sie größer als 1 sein.
      natürlich ist das ein Widerspruch :)

      vergleiche dazu den Beweis von Euklid (?) zur Unendlichkeit der Primzahlen ...

      Annahme: Es gäbe eine größte Primzahl k, dann ist p_1 * p_2 ... *k - 1 =: q eine größere Primzahl (oder es gibt eine Primzahl zwischen k und q).

      Ist das gleiche Prinzip ...

      So wirklich kann ich leider auch nciht sagen, worin der Fehler besteht. Muss wohl irgendwas mit der induktiven Definition von N zu tun haben (jede nat Zahl n besitzt per Definition einen "Nachfolger" m, mit m > n)

      Ganz trivial wird es aber auch nicht sein - zumindest steht es im Königsberger Ana II im Kapitel über Variationsrechnung als "Perron'sches Paradoxon"
      nein, schau dir mal den original post an, den ich zitiert habe. darin wird überhaupt nicht angenommen, dass k die größte zahl ist, sondern nur, dass k größer als 1 ist. deswegen führt die tatsache, dass k^2>k ist nicht zum widerspruch. k^2 > k und k > 1 widersprechen sich nun wirklich nicht!
    • gImLi
      gImLi
      Bronze
      Dabei seit: 17.01.2005 Beiträge: 726
      ok, war vielleicht etwas "ungenau" von mir formuliert. Die Widerspruchsannahme müsste lauten "Sei k>1 die größte natürliche Zahl ..."
    • Suspender
      Suspender
      Bronze
      Dabei seit: 31.01.2005 Beiträge: 20
      Naja so falsch ist die Induktion eigentlich gar nicht. Die Induktionsannahme stimmt und der Induktionsschritt im Prinzip ja auch. Das Problem ist einfach, dass der Schritt von einem Schaf auf 2 Schaafe falsch ist. Hier wirds ja auch offensichtlich falsch. Dadurch kippt natüürlich die ganze Induktion...
      Könnte man den Schritt von einem Schaaf auf das zweite Schaf beweisen, dann wäre die Induktion in der Tat richtig und alle Schaafe hätten die gleiche Farbe...(so in der Art ging der Widerspruch, wenn ich mich richtig erinnere)
    • Korn
      Korn
      Bronze
      Dabei seit: 14.01.2005 Beiträge: 12.511
      Ihr habt es immer noch nicht verstanden ;)

      Ein Induktionsbeweis läuft immer über die Menge aller natürlichen Zahlen, d.h. 0, 1, 2, 3, .....

      Zunächst einmal muss man also jedem Schaf eine eindeutige Nummer zuweisen


      Man beweist die Behauptung zunächst für n = 0

      Dann nimmt man die Behauptung für alle n für die gilt n < N und muss nun zeigen, dass daraus die Behauptung für N+1 auch folgt.


      Induktionsschritt:
      Nimm aus einer Herde mit n Schafen ein Schaf a heraus. Die restlichen n1 Schafe haben wegen
      der Induktionsannahme dieselbe Farbe. Nun schicke Schaf a zurück zur Herde und nimm
      ein anderes Schaf b heraus. Durch die Induktionsannahme haben die restlichen n1 Schafe
      (nun wieder mit Schaf a in der Herde) wieder dieselbe Farbe. Also hat a dieselbe Farbe wie alle
      anderen Schafe. Somit haben alle Schafe der Herde dieselbe Farbe.
      Hier liegt der Fehler. Die Annahme ist nämlich, dass alle Schafe mit der Nummer < N nun dieselbe Farbe haben. Für das Schaf mit der Nummer N+1 gilt diese Annahme nicht, auch nicht wenn wir es in die Herde zurückschicken!
    • 1
    • 2