Falscher Induktionsbeweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:50 Di 24.01.2012 | | Autor: | hilado |
| Aufgabe | Welcher Schritt im folgenden Induktionsbeweis ist falsch und warum ist er falsch?
Es bezeichne G [mm] \subseteq \IN [/mm] die Menge der geraden natürlichen Zahlen und U [mm] \subseteq \IN [/mm] der Menger der ungeraden natürlichen Zahlen.
Behauptung: Für jede Teilmenge S [mm] \subseteq \IN [/mm] gilt entweder S [mm] \subseteq [/mm] U oder S [mm] \subseteq [/mm] G.
Induktionsanfang: Die Behauptung ist wahr für alle S [mm] \subseteq [/mm] mit nur einem Element.
Induktionsschritt: Sei S eine Menge mit n + 1 Elementen. Wähle ein Element e aus und setze S' := S \ {e}. S'hat nur n Elemente und nach Induktionsvoraussetung gilt die Behauptung, dass entweder S' [mm] \subseteq [/mm] U oder S' [mm] \subseteq [/mm] G. Nun entfernen wir ein anderes Element e' und erhalten S'' := S \ {e'}. Da auch S'' nur n Elemente besitzt, gilt wiederum, dass entweder S'' [mm] \subseteq [/mm] U oder S'' [mm] \subseteq [/mm] G. Für ein e'' [mm] \in [/mm] S' [mm] \cap [/mm] S'' gilt nun e'' [mm] \in [/mm] U oder e'' [mm] \in [/mm] G. Dann gilt S', S'' [mm] \subseteq [/mm] U (oder S', S'' [mm] \subseteq [/mm] G) und e, e' [mm] \in [/mm] U (oder e, e' [mm] \in [/mm] G). Also gilt die Behauptung auch für die Menge S. Dies vervollständigt den Induktionsbeweis für n + 1 Elemente. |
Ich weiß bei der Aufgabe leider nicht, wo ich genau anfangen soll, weil man da jedes mal auf die Voraussetzung hinweist.
Damit meine ich folgendes: Nimmt man Element e aus der Menge S, ist die Menge S' [mm] \subseteq [/mm] U bzw. S' [mm] \subseteq [/mm] G. Nun kann es ja sein, dass e eben zu der anderen Menge gehört, also wenn S' [mm] \subseteq [/mm] U, dann ist e [mm] \in [/mm] G.
Nun nehmen wir aber ein anderes Element e' und erhalten S'' und S'' [mm] \subseteq [/mm] U bzw. S'' [mm] \subseteq [/mm] G ist. D.h. doch aber auch, dass meine Vermutung falsch ist, dass mein vorheriges e eben nicht zur anderen Menge gehört, sondern schon richtig ist.
Was ich mir hier noch denken könnte, dass wir zwar jedes Mal vermuten, dass eine Menge mit n Elementen entweder Teilmenge von G bzw. U ist, dies aber in keinster Weise nachprüfen. Für mich ist dann aber die Frage, wie schaffe ich das vernünftig zu belegen ...
|
|
| |
|
> Welcher Schritt im folgenden Induktionsbeweis ist falsch
> und warum ist er falsch?
>
> Es bezeichne G [mm]\subseteq \IN[/mm] die Menge der geraden
> natürlichen Zahlen und U [mm]\subseteq \IN[/mm] der Menger der
> ungeraden natürlichen Zahlen.
>
> Behauptung: Für jede Teilmenge S [mm]\subseteq \IN[/mm] gilt
> entweder S [mm]\subseteq[/mm] U oder S [mm]\subseteq[/mm] G.
>
> Induktionsanfang: Die Behauptung ist wahr für alle
> S [mm]\subseteq[/mm] [mm] \IN [/mm] mit nur einem Element.
>
> Induktionsschritt: Sei S eine Menge mit n + 1 Elementen.
> Wähle ein Element e aus und setze S' := S \ {e}. S'hat nur
> n Elemente und nach Induktionsvoraussetung gilt die
> Behauptung, dass entweder S' [mm]\subseteq[/mm] U oder S' [mm]\subseteq[/mm]
> G. Nun entfernen wir ein anderes Element e' und erhalten
> S'' := S \ {e'}. Da auch S'' nur n Elemente besitzt, gilt
> wiederum, dass entweder S'' [mm]\subseteq[/mm] U oder S'' [mm]\subseteq[/mm]
> G. Für ein e'' [mm]\in[/mm] S' [mm]\cap[/mm] S'' gilt nun e'' [mm]\in[/mm] U oder e''
> [mm]\in[/mm] G. Dann gilt S', S'' [mm]\subseteq[/mm] U (oder S', S''
> [mm]\subseteq[/mm] G) und e, e' [mm]\in[/mm] U (oder e, e' [mm]\in[/mm] G). Also gilt
> die Behauptung auch für die Menge S. Dies vervollständigt
> den Induktionsbeweis für n + 1 Elemente.
> Ich weiß bei der Aufgabe leider nicht, wo ich genau
> anfangen soll, weil man da jedes mal auf die Voraussetzung
> hinweist.
>
> Damit meine ich folgendes: Nimmt man Element e aus der
> Menge S, ist die Menge S' [mm]\subseteq[/mm] U bzw. S' [mm]\subseteq[/mm] G.
> Nun kann es ja sein, dass e eben zu der anderen Menge
> gehört, also wenn S' [mm]\subseteq[/mm] U, dann ist e [mm]\in[/mm] G.
>
> Nun nehmen wir aber ein anderes Element e' und erhalten S''
> und S'' [mm]\subseteq[/mm] U bzw. S'' [mm]\subseteq[/mm] G ist. D.h. doch
> aber auch, dass meine Vermutung falsch ist, dass mein
> vorheriges e eben nicht zur anderen Menge gehört, sondern
> schon richtig ist.
>
> Was ich mir hier noch denken könnte, dass wir zwar jedes
> Mal vermuten, dass eine Menge mit n Elementen entweder
> Teilmenge von G bzw. U ist, dies aber in keinster Weise
> nachprüfen. Für mich ist dann aber die Frage, wie schaffe
> ich das vernünftig zu belegen ...
Hallo hilado,
betrachte am besten ein Beispiel mit einer Menge aus
2 Elementen, nämlich einer geraden und einer ungeraden
Zahl, also etwa $\ S\ =\ [mm] \{\,2\,,\,3\,\}$ [/mm] .
Und nun verfolge genau, was der angebliche Induktions-
schritt (für den Fall n=1) mit diesem Beispiel machen
würde. So kommst du wohl darauf, was daran faul ist ...
LG Al-Chw.
|
|
|
|
