Induktion: totale Ordnung < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | $(M, [mm] \le)$ [/mm] sei eine total geordnete Menge.
Es soll mittels Induktion gezeigt werden, dass jede endliche nichtleere Teilmenge $N [mm] \subseteq [/mm] M$ ein Minimum besitzt. |
Hallo,
ich versuche vergeblich mit der allgemeinen Vorgehensweise bei dieser Aufgabe anzusetzen:
Induktionsanfang:
Induktionsschritt
Induktionsvorausssetzung
Für ein ... gelte: Jede nichtleere Teilmenge $N [mm] \subseteq [/mm] M$ besitzt ein Minimum.
Zu zeigen:
Dann folgt:
Meinge Gedanken bisher:
Durch die gegebene Tatsache, dass eine Teilmenge nicht leer ist, also mindestens ein Element vorhanden sein muss, besitzt jede Teilmenge zwangsweise ein Minimum.
Das ist aber noch lange kein Induktionsbeweis und ich zerbreche mir den Kopf darüber, wie ich das anhand von Induktion zeigen kann.
Ich hoffe, es weiß jemand Rat.
Vielen Dank.
Gruß
el_grecco
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:00 Mo 29.11.2010 | | Autor: | fred97 |
> [mm](M, \le)[/mm] sei eine total geordnete Menge.
> Es soll mittels Induktion gezeigt werden, dass jede
> endliche nichtleere Teilmenge [mm]N \subseteq M[/mm] ein Minimum
> besitzt.
> Hallo,
>
> ich versuche vergeblich mit der allgemeinen Vorgehensweise
> bei dieser Aufgabe anzusetzen:
Du mußt die Aufgabe so formulieren:
(*) [mm] \forall [/mm] n [mm] \in \IN [/mm] gilt: jede n-elementige Teilmenge von M besitzt eine Minimum.
>
> Induktionsanfang:
Den Induktionsanfang kriegst Du doch wohl hin ! Es ist n=1.
> Induktionsschritt
> Induktionsvorausssetzung
> Für ein ... gelte: Jede nichtleere Teilmenge [mm]N \subseteq M[/mm]
> besitzt ein Minimum.
Versuchs nochmal, mit (*)
>
> Zu zeigen:
Jede (n+1)- elementige Teilmenge von M besitzt ein Minimum
FRED
>
> Dann folgt:
>
>
> Meinge Gedanken bisher:
> Durch die gegebene Tatsache, dass eine Teilmenge nicht
> leer ist, also mindestens ein Element vorhanden sein muss,
> besitzt jede Teilmenge zwangsweise ein Minimum.
> Das ist aber noch lange kein Induktionsbeweis und ich
> zerbreche mir den Kopf darüber, wie ich das anhand von
> Induktion zeigen kann.
>
> Ich hoffe, es weiß jemand Rat.
>
> Vielen Dank.
>
> Gruß
> el_grecco
>
>
|
|
|
| |
|
| Aufgabe | $(M, [mm] \le)$ [/mm] sei eine total geordnete Menge.
Es soll mittels Induktion gezeigt werden, dass jede endliche nichtleere Teilmenge $N [mm] \subseteq [/mm] M$ ein Minimum besitzt. |
Danke für die rasche Reaktion, Fred. 
Es wäre sehr nett, wenn du kurz drüberlesen kannst (vor allem beim Ende):
(*) [mm]\forall[/mm] [mm]n \in \IN[/mm] gilt: jede n-elementige
Teilmenge von M besitzt ein Minimum.
Induktionsanfang $n=1$: die Teilmenge enthält nur ein einziges Element, welches gleichzeitig auch das Minimum ist.
Induktionsschritt: $n [mm] \to [/mm] n+1$
Induktionsvorausssetzung:
Für ein $n [mm] \in \IN$ [/mm] gelte: jede n-elementige Teilmenge von M besitzt eine Minimum.
Zu zeigen:
Jede (n+1)- elementige Teilmenge von M besitzt ein Minimum
Dann folgt:
Da M eine total geordnete Menge ist, ist auch jede Teilmenge davon eine total geordnete Menge. Jede Teilmenge, die nicht leer ist und somit mindestens ein Element enthält, besitzt deshalb ein Minimum.
Nochmals vielen Dank.
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:37 Mo 29.11.2010 | | Autor: | fred97 |
> [mm](M, \le)[/mm] sei eine total geordnete Menge.
> Es soll mittels Induktion gezeigt werden, dass jede
> endliche nichtleere Teilmenge [mm]N \subseteq M[/mm] ein Minimum
> besitzt.
> Danke für die rasche Reaktion, Fred.
> Es wäre sehr nett, wenn du kurz drüberlesen kannst (vor
> allem beim Ende):
>
> (*) [mm]\forall[/mm] [mm]n \in \IN[/mm] gilt: jede n-elementige
> Teilmenge von M besitzt ein Minimum.
>
> Induktionsanfang [mm]n=1[/mm]: die Teilmenge enthält nur ein
> einziges Element, welches gleichzeitig auch das Minimum
> ist.
O.K.
>
> Induktionsschritt: [mm]n \to n+1[/mm]
>
> Induktionsvorausssetzung:
> Für ein [mm]n \in \IN[/mm] gelte: jede n-elementige Teilmenge von
> M besitzt eine Minimum.
O.K.
>
> Zu zeigen:
> Jede (n+1)- elementige Teilmenge von M besitzt ein
> Minimum
>
> Dann folgt:
> Da M eine total geordnete Menge ist, ist auch jede
> Teilmenge davon eine total geordnete Menge. Jede Teilmenge,
> die nicht leer ist und somit mindestens ein Element
> enthält, besitzt deshalb ein Minimum.
Was ist das denn ???????????
Alles muß man selber machen ....:
Nimm Dir mal eine (n+1)- elementige Teilmenge her. Etwa $A= [mm] \{x_1, ...,x_{n+1}\}$
[/mm]
Setze $B:= [mm] \{x_1, ...,x_{n}\}$
[/mm]
nach IV. hat B ein Minimum, nennen wir es [mm] x_0.
[/mm]
Da " [mm] \le" [/mm] eine Totalordnung ist, gilt [mm] x_0 \le x_{n+1} [/mm] oder [mm] x_{n+1} \le x_0
[/mm]
Was ist dann im ersten Fall das Minimum von A ? Und was im zweiten Fall ?
FRED
>
>
> Nochmals vielen Dank.
>
> Gruß
> el_grecco
>
|
|
|
| |
|
| Aufgabe | $(M, [mm] \le)$ [/mm] sei eine total geordnete Menge.
Es soll mittels Induktion gezeigt werden, dass jede endliche nichtleere Teilmenge $N [mm] \subseteq [/mm] M$ ein Minimum besitzt. |
Hallo Fred,
danke für Deine Mühe.
> Was ist das denn ???????????
>
> Alles muß man selber machen ....:
Ich bitte um Nachsicht.
> Nimm Dir mal eine (n+1)- elementige Teilmenge her. Etwa [mm]A= \{x_1, ...,x_{n+1}\}[/mm]
>
> Setze [mm]B:= \{x_1, ...,x_{n}\}[/mm]
Zur Sicherheit frage ich besser nach. Meinst Du das so $A [mm] \subseteq [/mm] B$ ?
> nach IV. hat B ein Minimum, nennen wir es [mm]x_0.[/mm]
Falls das wirklich so $A [mm] \subseteq [/mm] B$ gemeint ist, verstehe ich es deshalb nicht, denn die IV bezieht sich auf Teilmengen. B wäre dann aber eine Obermenge.
> Da " [mm]\le"[/mm] eine Totalordnung ist, gilt [mm]x_0 \le x_{n+1}[/mm] oder
> [mm]x_{n+1} \le x_0[/mm]
>
> Was ist dann im ersten Fall das Minimum von A ? Und was
> im zweiten Fall ?
Wenn das oben geklärt ist, sollte bei mir endlich der Groschen fallen.
Vielen Dank für die Geduld, Mühe und Nachsicht!
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:34 Di 30.11.2010 | | Autor: | M.Rex |
> [mm](M, \le)[/mm] sei eine total geordnete Menge.
> Es soll mittels Induktion gezeigt werden, dass jede
> endliche nichtleere Teilmenge [mm]N \subseteq M[/mm] ein Minimum
> besitzt.
> Hallo Fred,
>
> danke für Deine Mühe.
>
>
> > Was ist das denn ???????????
> >
> > Alles muß man selber machen ....:
>
> Ich bitte um Nachsicht.
>
>
> > Nimm Dir mal eine (n+1)- elementige Teilmenge her. Etwa [mm]A= \{x_1, ...,x_{n+1}\}[/mm]
>
> >
> > Setze [mm]B:= \{x_1, ...,x_{n}\}[/mm]
>
> Zur Sicherheit frage ich besser nach. Meinst Du das so [mm]A \subseteq B[/mm]
> ?
Genau andersherum. A ist die Obermenge, die ein Element mehr als B hat. Schau dir mal die Definition (vor allem die Indizes) genauer an
>
> > nach IV. hat B ein Minimum, nennen wir es [mm]x_0.[/mm]
>
> Falls das wirklich so [mm]A \subseteq B[/mm] gemeint ist, verstehe
> ich es deshalb nicht, denn die IV bezieht sich auf
> Teilmengen. B wäre dann aber eine Obermenge.
Eben genau andersherum.
>
> > Da " [mm]\le" $="" src="http://teximg.matheraum.de/render?d=108&s=$%5Cle$"> eine Totalordnung ist, gilt ![$x_0 \le x_{n+1}[/mm] oder
</font>
<br>
<font class=]() > > [mm]x_{n+1} \le x_0[/mm]
> >
> > Was ist dann im ersten Fall das Minimum von A ? Und was
> > im zweiten Fall ?
Schau dir mal das Element [mm] x_{n+1} [/mm] an, das ja nur in A enthalten ist.
B hat nach I.V. ein Minimum [mm] x_{min}, [/mm] was kann denn dann für [mm] x_{n} [/mm] gelten? Fall 1: [mm] x_{n+1}
>
> Wenn das oben geklärt ist, sollte bei mir endlich der
> Groschen fallen.
>
> Vielen Dank für die Geduld, Mühe und Nachsicht!
>
> Gruß
> el_grecco
>
Marius
|
|
|
| |
|
| Aufgabe | $(M, [mm] \le)$ [/mm] sei eine total geordnete Menge.
Es soll mittels Induktion gezeigt werden, dass jede endliche nichtleere Teilmenge $N [mm] \subseteq [/mm] M$ ein Minimum besitzt. |
Danke Marius,
damit die Übersicht nicht verloren geht, oben nochmals die Angabe und hier die Induktion bis zum "aktuellen Stand":
(*) [mm]\forall[/mm] [mm]n \in \IN[/mm] gilt: jede n-elementige
Teilmenge von M besitzt ein Minimum.
Induktionsanfang $n=1$: die Teilmenge enthält nur ein einziges Element, welches gleichzeitig auch das Minimum ist.
Induktionsschritt: $n [mm] \to [/mm] n+1$
Induktionsvorausssetzung:
Für ein $n [mm] \in \IN$ [/mm] gelte: jede n-elementige Teilmenge von M besitzt eine Minimum.
Zu zeigen:
Jede (n+1)- elementige Teilmenge von M besitzt ein Minimum
Dann folgt:
$B [mm] \subseteq [/mm] A$
$B := [mm] \{ x_{1},...,x_{n} \}$ [/mm] $A := [mm] \{ x_{1},...,x_{n+1} \}$
[/mm]
> Schau dir mal das Element [mm]x_{n+1}[/mm] an, das ja nur in A
> enthalten ist.
> B hat nach I.V. ein Minimum [mm]x_{min},[/mm] was kann denn dann
> für [mm]x_{n}[/mm] gelten?
> Fall 1: [mm]x_{n+1}
Dieser Fall kann nicht gelten, da eine totale Ordnung [mm] $\le$ [/mm] vorliegt und B eine Teilmenge von A ist.
> oder Fall2: [mm]x_{n+1}\ge x_{min}?[/mm]
Dieser Fall gilt (gleiche Begründung wie oben).
> Was ist dann mit der Menge A. HAt A nun ein Minimum?
Ich dachte im Rahmen dieser Aufgabe muss man nur nachweisen, dass die Teilmenge und nicht die Obermenge ein Minimum besitzt. ![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]")
Ärgerlich, dass mir der Induktionsschluss solche Schwierigkeiten bereitet...
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:20 Di 30.11.2010 | | Autor: | fred97 |
Das ist ja ein Jammer !
Ich wiederhole:
Nimm Dir mal eine (n+1)- elementige Teilmenge her. Etwa $ A= [mm] \{x_1, ...,x_{n+1}\} [/mm] $
Setze $ B:= [mm] \{x_1, ...,x_{n}\} [/mm] $
Dann ist doch klar, dass B Teilmenge von A ist : Du mußt nur hinschauen !
nach IV. hat B ein Minimum, nennen wir es $ [mm] x_0. [/mm] $
Es ist [mm] x_0 \in [/mm] B !! Und damit auch [mm] x_0 \in [/mm] A
Da " $ [mm] \le" [/mm] $ eine Totalordnung ist, gilt $ [mm] x_0 \le x_{n+1} [/mm] $ oder $ [mm] x_{n+1} \le x_0 [/mm] $
Fall 1: $ [mm] x_0 \le x_{n+1} [/mm] $. Dann hat A das Minimum [mm] x_0
[/mm]
Fall 2: $ [mm] x_{n+1} \le x_0 [/mm] $. Dann hat A das Minimum [mm] x_{n+1}
[/mm]
Fertig !!!!
FRED
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:32 Di 30.11.2010 | | Autor: | el_grecco |
Danke für Deine Hilfe, Fred.
> Nimm Dir mal eine (n+1)- elementige Teilmenge her. Etwa [mm]A= \{x_1, ...,x_{n+1}\}[/mm]
>
> Setze [mm]B:= \{x_1, ...,x_{n}\}[/mm]
>
>
> Dann ist doch klar, dass B Teilmenge von A ist : Du mußt
> nur hinschauen !
Es verwirrt mich nur, warum Du den Begriff "Teilmenge" für die Menge A verwendest, obwohl $B [mm] \subseteq [/mm] A$ gilt und A demnach die Obermenge ist?
Abgesehen von den Begrifflichkeiten ist mir der Induktionsschluss aber jetzt klar.
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:37 Di 30.11.2010 | | Autor: | fred97 |
> Danke für Deine Hilfe, Fred.
>
> > Nimm Dir mal eine (n+1)- elementige Teilmenge her. Etwa [mm]A= \{x_1, ...,x_{n+1}\}[/mm]
>
> >
> > Setze [mm]B:= \{x_1, ...,x_{n}\}[/mm]
> >
> >
> > Dann ist doch klar, dass B Teilmenge von A ist : Du mußt
> > nur hinschauen !
>
> Es verwirrt mich nur, warum Du den Begriff "Teilmenge" für
> die Menge A verwendest, obwohl [mm]B \subseteq A[/mm] gilt und A
> demnach die Obermenge ist?
Man glaubt es kaum !
Die Grundmenge in der ganzen Aufgabe ist die Menge M.
A war eine (n+1)-elementige Teilmenge von M
und B Teilmenge von A
FRED
> Abgesehen von den Begrifflichkeiten ist mir der
> Induktionsschluss aber jetzt klar.
>
> Gruß
> el_grecco
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:46 Di 30.11.2010 | | Autor: | el_grecco |
Danke für die Ergänzung, Fred.
> Man glaubt es kaum !
Wie gesagt: ich bitte um Nachsicht.
> Die Grundmenge in der ganzen Aufgabe ist die Menge M.
>
> A war eine (n+1)-elementige Teilmenge von M
>
> und B Teilmenge von A
Der Grund für meine Verständnisschwierigkeiten: ich dachte $B [mm] \subseteq [/mm] A$ wird "synonym" verwendet für $N [mm] \subseteq [/mm] M$. Aber im Nachhinein ist man immer schlauer...
Gruß
el_grecco
|
|
|
|
