Wohlordnungsprinzip < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es sei [mm] $\emptyset \neq [/mm] A [mm] \subset \IN$ [/mm] eine nicht-leere Teilmenge natürlicher Zahlen.
Sie werden in dieser Aufgabe zeigen, dass $A$ ein minimales Element besitzt. Dabei heißt $x [mm] \in [/mm] A$ minimal, falls $x [mm] \leq [/mm] y$ für alle $y [mm] \in [/mm] A$ gilt.
Gehen Sie dazu wie folgt vor:
1. Nehmen Sie an, dass die Behauptung falsch ist, das heißt, A besitzt kein minimales Element.
2. Definieren Sie [mm] $B:=\IN \setminus [/mm] A$ und zeigen Sie mittels vollständiger Induktion, dass für alle $n [mm] \in \IN$ [/mm] schon [mm] $\{1,..,n\} \subset [/mm] B$ gilt.
3. Folgern Sie: [mm] $B=\IN$. [/mm] Warum liefert dies die Behauptung? |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Also, es gilt zu zeigen:
[mm] $\forall [/mm] y [mm] \exists [/mm] x: x [mm] \leq [/mm] y$.
Das heißt es gibt ein universelles $x [mm] \in [/mm] A$, das kleiner oder gleich jedem $y [mm] \in [/mm] A$ ist, eben ein Minimum.
Bei dem Beweis durch Kontraposition, der hier gefordert wird, muss ich von der Negation ausgehen:
[mm] $\exists [/mm] y [mm] \forall [/mm] x: y < x$
Soll heißen ich gehe davon aus, dass ich zu jedem $x [mm] \in [/mm] A$ ein $y [mm] \in [/mm] A$ finden kann, das echt kleiner ist.
Nur wie geht es jetzt weiter?
Nachher werde ich offensichtlich auf den Schluss kommen, dass [mm] $A=\emptyset$, [/mm] was einen Widerspruch darstellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:35 Do 24.10.2013 | | Autor: | fred97 |
> Es sei [mm]\emptyset \neq A \subset \IN[/mm] eine nicht-leere
> Teilmenge natürlicher Zahlen.
>
> Sie werden in dieser Aufgabe zeigen, dass [mm]A[/mm] ein minimales
> Element besitzt. Dabei heißt [mm]x \in A[/mm] minimal, falls [mm]x \leq y[/mm]
> für alle [mm]y \in A[/mm] gilt.
>
> Gehen Sie dazu wie folgt vor:
> 1. Nehmen Sie an, dass die Behauptung falsch ist, das
> heißt, A besitzt kein minimales Element.
>
> 2. Definieren Sie [mm]B:=\IN \setminus A[/mm] und zeigen Sie mittels
> vollständiger Induktion, dass für alle [mm]n \in \IN[/mm] schon
> [mm]\{1,..,n\} \subset B[/mm] gilt.
>
> 3. Folgern Sie: [mm]B=\IN[/mm]. Warum liefert dies die Behauptung?
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Also, es gilt zu zeigen:
>
> [mm]\forall y \exists x: x \leq y[/mm].
Nein. Das stimmt nicht. Zu zeigen ist:
$ [mm] \exists [/mm] x [mm] \in [/mm] A [mm] \quad \forall [/mm] y [mm] \in [/mm] A : x [mm] \le [/mm] y$
>
> Das heißt es gibt ein universelles [mm]x \in A[/mm], das kleiner
> oder gleich jedem [mm]y \in A[/mm] ist, eben ein Minimum.
>
> Bei dem Beweis durch Kontraposition, der hier gefordert
> wird, muss ich von der Negation ausgehen:
>
> [mm]\exists y \forall x: y < x[/mm]
Das ist doch nicht die Negation !!!
>
> Soll heißen ich gehe davon aus, dass ich zu jedem [mm]x \in A[/mm]
> ein [mm]y \in A[/mm] finden kann, das echt kleiner ist.
Ja:
(*) zu jedem x [mm] \in [/mm] A ex. ein y [mm] \in [/mm] A mit: y<x
>
> Nur wie geht es jetzt weiter?
Na, das steht doch oben unter 2.
Ausgehend von (*) zeige induktiv, dass $ [mm] \{1,..,n\} \subset [/mm] B $ ist für jedes n [mm] \in \IN.
[/mm]
Probiers mal.
>
> Nachher werde ich offensichtlich auf den Schluss kommen,
> dass [mm]A=\emptyset[/mm], was einen Widerspruch darstellt.
Ja, das ist die Antwort auf die Frage in 3.
FRED
|
|
|
| |
|
Vor der Induktion nochmal eine kleine Nachfrage:
[mm] $\exists [/mm] x [mm] \forall [/mm] y: [mm] x\leq [/mm] y$
Heißt für mich, dass ich zu jedem y ein x angeben kann, dass kleiner/gleich y ist.
[mm] $\forall [/mm] y [mm] \exists [/mm] x: [mm] x\leq [/mm] y$
Heißt für mich, dass ein universelles x existiert, dass unabhängig von der Wahl meines y kleiner/gleich y ist.
Hab ich da was falsch verstanden?
Nun zur Induktion.
Okay, sei [mm] $B:=\IN \setminus [/mm] A$.
$A(n): = [mm] \{1,..,n\} \subset [/mm] B$
Induktionsanfang (n=1):
[mm] $\{1\} \subset [/mm] B$
Kann ich sagen, dass das richtig ist, da 1 in [mm] $\IN$ [/mm] liegt, aber nicht in A, da in der Menge [mm] \{1\} [/mm] kein $y$ gefunden werden kann, sodass $y<x$?
Induktionsvoraussetzung:
Es gelte $A(n)$ für ein $n [mm] \in \IN$.
[/mm]
Induktionsschluss ($n [mm] \mapsto [/mm] n+1$):
[mm] $\{1,..,n,n+1\}=\{1,..,n\} \cup\{n+1\}$
[/mm]
Gut, [mm] $\{1,..,n\} \subset [/mm] B$ nach Induktionsvoraussetzung. Außerdem ist [mm] $\{n+1\} \subset [/mm] B$ aufgrund derselben Argumentation wie beim Induktionsanfang. Demzufolge ist auch [mm] $\{1,..,n,n+1\} \subset [/mm] B$, womit [mm] $B=\IN$.
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:39 Do 24.10.2013 | | Autor: | fred97 |
> Vor der Induktion nochmal eine kleine Nachfrage:
>
> [mm]\exists x \forall y: x\leq y[/mm]
> Heißt für mich, dass ich zu
> jedem y ein x angeben kann, dass kleiner/gleich y ist.
Nein. Das bedeutet: es ex. ein x mit der Eigenschaft: x [mm] \le [/mm] y für alle y.
> [mm]\forall y \exists x: x\leq y[/mm]
> Heißt für mich, dass ein
> universelles x existiert, dass unabhängig von der Wahl
> meines y kleiner/gleich y ist.
Nein. Das bedeutet: zu jedem y ex. ein x mit: x [mm] \le [/mm] y. I.a. wird x von y abhängen.
>
> Hab ich da was falsch verstanden?
So ist es.
>
> Nun zur Induktion.
>
> Okay, sei [mm]B:=\IN \setminus A[/mm].
>
> [mm]A(n): = \{1,..,n\} \subset B[/mm]
>
> Induktionsanfang (n=1):
>
> [mm]\{1\} \subset B[/mm]
>
> Kann ich sagen, dass das richtig ist, da 1 in [mm]\IN[/mm] liegt,
> aber nicht in A, da in der Menge [mm]\{1\}[/mm] kein [mm]y[/mm] gefunden
> werden kann, sodass [mm]y
Nimm mal an, es wäre 1 [mm] \notin [/mm] B. Dann wäre doch 1 [mm] \in [/mm] A.
Unsere Annahme war doch:
(*) zu jedem x $ [mm] \in [/mm] $ A ex. ein y $ [mm] \in [/mm] $ A mit: y<x .
Wegen (*) gibt es dann ein y [mm] \in [/mm] A mit: y<1. Aber das ist Quatsch. Also ist 1 [mm] \in [/mm] B.
>
> Induktionsvoraussetzung:
> Es gelte [mm]A(n)[/mm] für ein [mm]n \in \IN[/mm].
Nein. Korrekt:
Es gelte [mm]A(n)[/mm] [mm] \subset [/mm] B für ein [mm]n \in \IN[/mm].
>
> Induktionsschluss ([mm]n \mapsto n+1[/mm]):
>
> [mm]\{1,..,n,n+1\}=\{1,..,n\} \cup\{n+1\}[/mm]
>
> Gut, [mm]\{1,..,n\} \subset B[/mm] nach Induktionsvoraussetzung.
> Außerdem ist [mm]\{n+1\} \subset B[/mm] aufgrund derselben
> Argumentation wie beim Induktionsanfang.
Na, na, nicht so voreilig ! Wäre n+1 [mm] \notin [/mm] B, so wäre n+1 [mm] \in [/mm] A. Wieder nach (*), gäbe es dann ein y [mm] \in [/mm] A mit y<n+1
Warum ist das Murks ?
Also n+1 [mm] \in [/mm] B.
> Demzufolge ist
> auch [mm]\{1,..,n,n+1\} \subset B[/mm], womit [mm]B=\IN[/mm].
Ja
FRED
>
|
|
|
| |
|
> > Induktionsvoraussetzung:
> > Es gelte [mm]A(n)[/mm] für ein [mm]n \in \IN[/mm].
>
> Nein. Korrekt:
>
> Es gelte [mm]A(n)[/mm] [mm]\subset[/mm] B für ein [mm]n \in \IN[/mm].
$A(n)$ sollte hier "Aussage in Abhängigkeit von n" heißen. Meine Notation lies wohl den Schluss zu, dass $A(n)$ die Menge [mm] $\{1,..,n\}$ [/mm] ist. Sollte ich da besser Klammern setzen?
> >
> > Induktionsschluss ([mm]n \mapsto n+1[/mm]):
> >
> > [mm]\{1,..,n,n+1\}=\{1,..,n\} \cup\{n+1\}[/mm]
> >
> > Gut, [mm]\{1,..,n\} \subset B[/mm] nach Induktionsvoraussetzung.
> > Außerdem ist [mm]\{n+1\} \subset B[/mm] aufgrund derselben
> > Argumentation wie beim Induktionsanfang.
>
> Na, na, nicht so voreilig ! Wäre n+1 [mm]\notin[/mm] B, so wäre
> n+1 [mm]\in[/mm] A. Wieder nach (*), gäbe es dann ein y [mm]\in[/mm] A mit
> y<n+1
>
> Warum ist das Murks ?
>
Das ist Murks, da alle möglichen $y < n+1$ nach Induktionsvoraussetzung in B liegen.
Also sähe der vollständige Beweis so aus (ich hoffe mal, dass keine Fehler mehr darin sind).
Sei [mm] $\emptyset \neq [/mm] A [mm] \subset \IN$.
[/mm]
zz: [mm] $\exists [/mm] x [mm] \in [/mm] A [mm] \forall [/mm] y [mm] \in [/mm] A: x [mm] \leq [/mm] y $
Beweis durch Kontraposition:
[mm] $\forall [/mm] x [mm] \in [/mm] A [mm] \exists [/mm] y [mm] \in [/mm] A: y < x$ (*)
Sei [mm] $B=\IN \setminus [/mm] A$.
Behauptung: [mm] $\left(\{1,..,n\} \subset B \right)$ [/mm] für alle $n [mm] \in \IN$
[/mm]
Beweis durch Induktion:
Induktionsanfang (n=1):
[mm] $\{1\} \subset [/mm] B$
$1 [mm] \notin [/mm] A$, da nach (*) ein $y<1$ in $A$ existieren müsste, was offensichtlich nicht der Fall ist. Also: $1 [mm] \in [/mm] B [mm] \Rightarrow \{1\} \subset [/mm] B$.
Induktionsvoraussetzung:
Es gelte [mm] $\left(\{1,..,n\} \subset B \right)$ [/mm] für ein $n [mm] \in \IN$.
[/mm]
Induktionsschluss ($n [mm] \mapsto [/mm] n+1$):
[mm] $\{1,..,n,n+1} [/mm] = [mm] \{1,..,n\} \cup \{n+1\}$
[/mm]
[mm] $\{1,..,n\} \subset [/mm] B$ nach Induktionsvoraussetzung. Außerdem ist $(n+1) [mm] \notin [/mm] A$, da nach (*) ein $y<n+1$ existieren müsste, dass in $A$ liegt, diese liegen jedoch nach Induktionsvoraussetzung in B. Also gilt [mm] $\{n+1\} \subset [/mm] B$ und somit auch [mm] $\{1,..,n,n+1\} \subset [/mm] B$, sodass nach dem Induktionsprinzip [mm] $B:=\IN$.
[/mm]
Mit [mm] $B=\IN \setminus [/mm] A$ folgt, dass $A [mm] =\emptyset$, [/mm] was einen Widerspruch darstellt. Somit besitzt jede Teilmenge der natürlichen Zahlen ein Minimum.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:45 Fr 25.10.2013 | | Autor: | fred97 |
> > > Induktionsvoraussetzung:
> > > Es gelte [mm]A(n)[/mm] für ein [mm]n \in \IN[/mm].
> >
> > Nein. Korrekt:
> >
> > Es gelte [mm]A(n)[/mm] [mm]\subset[/mm] B für ein [mm]n \in \IN[/mm].
>
> [mm]A(n)[/mm] sollte hier "Aussage in Abhängigkeit von n" heißen.
> Meine Notation lies wohl den Schluss zu, dass [mm]A(n)[/mm] die
> Menge [mm]\{1,..,n\}[/mm] ist. Sollte ich da besser Klammern
> setzen?
> > >
> > > Induktionsschluss ([mm]n \mapsto n+1[/mm]):
> > >
> > > [mm]\{1,..,n,n+1\}=\{1,..,n\} \cup\{n+1\}[/mm]
> > >
> > > Gut, [mm]\{1,..,n\} \subset B[/mm] nach Induktionsvoraussetzung.
> > > Außerdem ist [mm]\{n+1\} \subset B[/mm] aufgrund derselben
> > > Argumentation wie beim Induktionsanfang.
> >
> > Na, na, nicht so voreilig ! Wäre n+1 [mm]\notin[/mm] B, so wäre
> > n+1 [mm]\in[/mm] A. Wieder nach (*), gäbe es dann ein y [mm]\in[/mm] A mit
> > y<n+1
> >
> > Warum ist das Murks ?
> >
> Das ist Murks, da alle möglichen [mm]y < n+1[/mm] nach
> Induktionsvoraussetzung in B liegen.
>
>
> Also sähe der vollständige Beweis so aus (ich hoffe mal,
> dass keine Fehler mehr darin sind).
>
> Sei [mm]\emptyset \neq A \subset \IN[/mm].
> zz: [mm]\exists x \in A \forall y \in A: x \leq y[/mm]
>
> Beweis durch Kontraposition:
>
> [mm]\forall x \in A \exists y \in A: y < x[/mm] (*)
>
> Sei [mm]B=\IN \setminus A[/mm].
>
> Behauptung: [mm]\left(\{1,..,n\} \subset B \right)[/mm] für alle [mm]n \in \IN[/mm]
>
> Beweis durch Induktion:
>
> Induktionsanfang (n=1):
>
> [mm]\{1\} \subset B[/mm]
>
> [mm]1 \notin A[/mm], da nach (*) ein [mm]y<1[/mm] in [mm]A[/mm] existieren müsste,
> was offensichtlich nicht der Fall ist. Also: [mm]1 \in B \Rightarrow \{1\} \subset B[/mm].
>
> Induktionsvoraussetzung:
> Es gelte [mm]\left(\{1,..,n\} \subset B \right)[/mm] für ein [mm]n \in \IN[/mm].
>
> Induktionsschluss ([mm]n \mapsto n+1[/mm]):
>
> [mm]\{1,..,n,n+1} = \{1,..,n\} \cup \{n+1\}[/mm]
>
> [mm]\{1,..,n\} \subset B[/mm] nach Induktionsvoraussetzung.
> Außerdem ist [mm](n+1) \notin A[/mm], da nach (*) ein [mm]y
> existieren müsste, dass in [mm]A[/mm] liegt, diese liegen jedoch
> nach Induktionsvoraussetzung in B. Also gilt [mm]\{n+1\} \subset B[/mm]
> und somit auch [mm]\{1,..,n,n+1\} \subset B[/mm], sodass nach dem
> Induktionsprinzip [mm]B:=\IN[/mm].
>
> Mit [mm]B=\IN \setminus A[/mm] folgt, dass [mm]A =\emptyset[/mm], was einen
> Widerspruch darstellt. Somit besitzt jede Teilmenge der
> natürlichen Zahlen ein Minimum.
Jetzt passt es
FRED
|
|
|
|
