Wohlordnungsprinzip Beweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:06 So 13.04.2008 | | Autor: | then3210 |
| Aufgabe | | Wohlordnungsprinzip: Ist A eine nichtleere Teilmenge der natürlichen Zahlen, so gibt es in A ein kleinstes Element. |
Ich weiß einfach nicht wie ich den Beweis beginnen soll.
Ohne Wohlordnung von [mm] \IN [/mm] doch doch keine Induktion oder? Damit hat doch [mm] A\not= \emptyset [/mm] als Teilmenge von [mm] \IN [/mm] auch ein kleinstes Element.
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:43 So 13.04.2008 | | Autor: | Veandune |
Hallo then3210,
also ich habe genau dasselbe Problem wie Du: Der Induktionsbeweis. Normalerweise wird das Wohlordnungsprinzip per Widerspruch bewiesen. Weswegen in der Aufgabe der Induktionsbeweis gefordert wurde, ist mir deshalb schleierhaft.
Leider widerspricht diese Aufgabenstellung nicht sich selbst, weil der allgemeine Induktionsbeweis auf den Peano-Axiomen beruht.
Also versuche ich mal den Induktionsanfang (den Induktionsschluß bekomme ich leider noch nicht hin).
Aufgabenstellung:
Beweisen Sie per Induktion das folgende Wohlordnungsprinzip.
[mm]
M \subset \IN \wedge M\ne \emptyset \Rightarrow\exists x\in M\forall y\in M :x\le y[/mm]
Hierbei ist mir klar, dass ich nacheinander über die Indizes [mm]x[/mm] und [mm]y[/mm] gehen muss:
Induktionsanfang (ich zähle die [mm]0[/mm] nicht zu der Grundmenge der natürlichen Zahlen):
[mm]x=1, y=1: x\le y[/mm]
Aber wie gehe ich nun vor? Wie bekomme ich dort ein [mm]y+1[/mm] rein, welches diesen Sachverhalt weit genug klärt?
Ist der folgende Ansatz akzeptabel?
[mm]x\le y
Vielen Dank
Vean
|
|
|
| |
|
| Status: |
(Antwort) fehlerhaft  | | Datum: | 21:31 So 13.04.2008 | | Autor: | pelzig |
Also kann man nicht einfach über die Anzahl der Elemente von $M$ Induktion machen?
Sei P(n):"Eine Menge [mm] $M\subset\IN$ [/mm] mit $n$ Elementen besitzt ein kleinstes Element".
IA: Für [mm] $M=\{n\}$ [/mm] ist offensichtlich $n$ das kleinste Element.
IS: M hat $n+1$ Elemente, ich kann also ein Element $m$ auswählen und [mm] $M\setminus\{m\}$ [/mm] hat nach Induktionsvoraussetzung ein kleinstes Element [mm] $m_0$. [/mm] Falls [mm] $m\le m_0$ [/mm] ist, so ist (Transitivität von [mm] $\le$) [/mm] $m$ das kleinste Element von $M$, ansonsten [mm] $m_0$.
[/mm]
Betrachte nun die Menge [mm] $A:=\{n\in\IN:P(n)\}$. [/mm] Es ist [mm] $1\in [/mm] A$ und für jedes [mm] $n\in [/mm] A$ folgt [mm] $n+1\in [/mm] A$.
Nach dem Induktionsaxiom der Peano-Axiome ist also [mm] $A=\IN$ $\Box$[/mm]
|
|
|
| |
|
| Status: |
(Korrektur) fundamentaler Fehler  | | Datum: | 22:17 So 13.04.2008 | | Autor: | Merle23 |
> Also kann man nicht einfach über die Anzahl der Elemente
> von [mm]M[/mm] Induktion machen?
>
> Sei P(n):"Eine Menge [mm]M\subset\IN[/mm] mit [mm]n[/mm] Elementen besitzt
> ein kleinstes Element".
>
> IA: Für [mm]M=\{n\}[/mm] ist offensichtlich [mm]n[/mm] das kleinste Element.
> IS: M hat [mm]n+1[/mm] Elemente, ich kann also ein Element [mm]m[/mm]
> auswählen und [mm]M\setminus\{m\}[/mm] hat nach
> Induktionsvoraussetzung ein kleinstes Element [mm]m_0[/mm]. Falls
> [mm]m\le m_0[/mm] ist, so ist (Transitivität von [mm]\le[/mm]) [mm]m[/mm] das kleinste
> Element von [mm]M[/mm], ansonsten [mm]m_0[/mm].
>
> Betrachte nun die Menge [mm]A:=\{n\in\IN:P(n)\}[/mm]. Es ist [mm]1\in A[/mm]
> und für jedes [mm]n\in A[/mm] folgt [mm]n+1\in A[/mm].
> Nach dem
> Induktionsaxiom der Peano-Axiome ist also [mm]A=\IN[/mm] [mm]\Box[/mm]
Mit [mm]A=\IN[/mm] hast du aber (fast) gar nix gezeigt, denn jede Teilmenge der natürlichen Zahlen mit unendlich vielen Elementen (z.B. alle geraden Zahlen) wird nicht von A 'erfasst'.
|
|
|
| |
|
| Status: |
(Korrektur) richtig (detailiert geprüft)  | | Datum: | 23:41 So 13.04.2008 | | Autor: | pelzig |
Ok, die unendlichen Mengen fehlen, da haste recht.
Für unendliche Teilmengen $A$ nimmt man ein beliebiges [mm] $n\in [/mm] A$ und betrachtet [mm] $A_n:=\{m\in A:m\le n\}$. [/mm] Dann ist [mm] $A_n$ [/mm] endlich, da [mm] $A_n\subseteq\{1,...,n\}$, [/mm] und besitzt nach dem oben gezeigen ein kleinstes Element, das offensichtlich auch kleinstes Element von $A$ ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:19 So 13.04.2008 | | Autor: | Merle23 |
Ich versuch' mich mal selber an einem Beweis, wobei ich mir aber nicht sicher bin, ob er richtig ist.
Ausserdem benutze ich hierbei ein etwas abgewandeltes Induktionsprinzip, welches man erstmal selbst beweisen müsste, sofern man es nicht in der Vorlesung hatte.
Wir führen einen Widerspruchsbeweis unter der Annahme, dass [mm] M\subset\IN [/mm] kein kleinstes Element besitzt. Bei der Induktion betrachten wir die Menge [mm]\IN\setminus M[/mm].
Induktionsanfang [mm](n=1)[/mm]: [mm]1\in\IN\setminus M[/mm] ist wahr, denn sonst wäre [mm]1\in M[/mm] und somit kleinstes Element.
Induktionsschritt [mm](1,...,n\Rightarrow n+1)[/mm]: [mm]n+1\in\IN\setminus M[/mm] ist ebenfalls wahr, denn sonst wäre [mm]n+1\in M[/mm] und somit kleinstes Element, da ja weder 1, noch 2, noch ..., noch n [mm]\in M[/mm] ist.
Also gilt nach dem Prinzip der vollständigen Induktion [mm]\IN\setminus M=\IN[/mm] und somit [mm]M=\emptyset[/mm]. Widerspruch.
|
|
|
|
