Einfacher Beweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:19 Di 20.10.2009 | | Autor: | kegel53 |
Hallo Leute,
ich bin im Moment an einem Beweis dran und wollte eigentlich nur kurz was absichern. Also ich hab eine Funktion f [mm] :\IN-->\IN [/mm] und es gilt f(f(n))>f(n).
Kann ich daraus sofort schließen, dass auch f(n)>n ist oder geht das nur unter bestimmten Voraussetzungen?
Besten Dank schon mal.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:30 Di 20.10.2009 | | Autor: | leduart |
Hallo
Du solltest da kurz zeigen. und es gilt natuerlich nur, wenn die beziehung fuer alle n [mm] \in\IN [/mm] gilt.
gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:41 Di 20.10.2009 | | Autor: | kegel53 |
Ja klar sorry hab ich vergessen dazu zu schreiben. Die Ausaage gilt natürlich für alle n [mm] \in\IN. [/mm] Aber wie kann ich das zeigen? Ich bin davon ausgegangen, dass es hier ein einfacher Folgepfeil tut :).
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:25 Di 20.10.2009 | | Autor: | leduart |
Hallo
wenn du davon ausgehst, dass es einfach ist, dann solltest dus auch zeigen koennen !
Aber es ist einfach falsch, drum kann mans auch nicht beweisen.
Merkd dir bei jedem folgt Pfeil, sollte man nen Beweis im Hintergrund haben!
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:37 Di 20.10.2009 | | Autor: | kegel53 |
Okay dann liegt da wohl ein Denkfehler zugrunde. Hättest du dann vielleict ein Tipp parat wie ich stattdessen vorgehen. Also zu zeigen habe ich eigentlich, dass aus f(n+1)>f(f(n)) bereits folgt, dass f(n)=n ist. Wäre für jeden Tipp dankbar.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:17 Mi 21.10.2009 | | Autor: | Merle23 |
Nette Knobelaufgabe.
Ich habe bisher nur ein partielles Resultat, nämlich die Monotonie von f.
Der Beweis läuft über Induktion. Die Aussage, die für jedes n bewiesen wird, ist "n wird von keiner höheren Zahl unter f getroffen", das entspricht [mm]\forall m \in \IN (m > n \Rightarrow f(m) \not= n)[/mm].
[mm]
n=1: \ Wenn \ f(m) = 1 \ mit \ m > 1, \ so \ 1 = f(m) > f(f(m-1)) \ge 1. \ Widerspruch.[/mm]
[mm]n \to n+1: \ Angenommen, \ f(m) = n+1 \ und \ m > n+1. \ So \ gilt \ n+1 = f(m) > \underbrace{f(\underbrace{f(m-1)}_{\ge n+1})}_{\ge n+1} \ge n+1. \ Widerspruch.
[/mm]
edit: Voller Entsetzen muss ich feststellen, dass das ja gar nicht die Monotonie, sondern "nur" die Ungleichung [mm]f(n) \ge n[/mm] ist, die ich gezeigt habe.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:52 Mi 21.10.2009 | | Autor: | pelzig |
Induktiv folgt direkt [mm] $f(n)\ge [/mm] n$ für alle $n$. Wendet auf diese Ungleichung abermals auf beiden Seiten $f$ an (Monotonie) und so hat man [mm] $f(n+1)>f(f(n))\ge [/mm] f(n)$ für alle [mm] $n\in\IN$, [/mm] also ist $f$ sogar streng monoton wachsend, also insbesondere injektiv.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:34 Mi 21.10.2009 | | Autor: | kegel53 |
Es wär halt einfach zu schön, wenn man jetzt sagen könnte das ganze is äquivalent zu [mm] n+1>f(n)\ge [/mm] n. Dann wär man fertig. Wie gesagt wäre und könnte :).
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:00 Do 22.10.2009 | | Autor: | Merle23 |
Hi,
habe meinen Post oben ja schon korrigiert. Monotonie habe ich -nicht- gezeigt. Leider.
Und f kann doch nicht -streng- monoton sein, wenn f=id gelten soll.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:35 Do 22.10.2009 | | Autor: | pelzig |
> habe meinen Post oben ja schon korrigiert. Monotonie habe
> ich -nicht- gezeigt. Leider.
Das ist schlecht, ich schau es mir später nochmal an.
> Und f kann doch nicht -streng- monoton sein, wenn f=id gelten soll.
Die Identität ist streng monoton wachsend... (jaaa, ich musste an dieser Stelle auch erst kurz innehalten  )
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:58 Do 22.10.2009 | | Autor: | Merle23 |
> > Und f kann doch nicht -streng- monoton sein, wenn f=id gelten soll.
> Die Identität ist streng monoton wachsend... (jaaa, ich
> musste an dieser Stelle auch erst kurz innehalten )
Argghhh..... hast Recht. ^^
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:00 Do 22.10.2009 | | Autor: | Merle23 |
Ok, die Monotonie ist eigentlich damit nur eine einfache Folgerung.
[mm] f(m) > f(f(m-1)) \ge f(m-1)[/mm].
Wieso habe ich das nicht schon früher gesehen. Ist echt nicht mehr schwer gewesen. ^^
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:06 Do 22.10.2009 | | Autor: | pelzig |
Alex hat gezeigt, dass $f$ monoton wachsend ist. Mit einem einfachen Induktionsargument erhält man dann zunächst die Ungleichung [mm] $f(n)\ge [/mm] n$ und weiter sogar, dass f streng monoton wachsend ist (siehe meine Mitteilung oben). Damit können wir nun $f(n)=n$ zeigen:
Wegen der Monotonie ist f injektiv, also bijektiv auf seinem Bild. Dann ist aber auch die Umkehrabbildung [mm] $f^{-1}:f(\IN)\to\IN$ [/mm] streng monoton wachsend (!). Betrachte nun die Ungleichung $f(n+1)>f(f(n))$. Linke und rechte Seite sind zweifelsohne Elemente aus [mm] $f(\IN)$, [/mm] also können wir [mm] $f^{-1}$ [/mm] anwenden und erhalten wegen dessen Monotonie $n+1>f(n)$ - für alle [mm] $n\in\IN$. [/mm] Also insgesamt: [mm] $n+1>f(n)\ge [/mm] n$ für alle [mm] $n\in\IN$ [/mm] - und das ist die Behauptung.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:16 Do 22.10.2009 | | Autor: | kegel53 |
Das is ja wahnsinn! Vielen Dank. Wenn du jetzt noch erklären könntest wie du von injektiv auf "bijektiv auf dem Bild" kommst und warum die Umkehrabbildung dann auch streng monoton wachsend sein muss wärs klasse.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:20 Do 22.10.2009 | | Autor: | pelzig |
> Das is ja wahnsinn! Vielen Dank. Wenn du jetzt noch
> erklären könntest wie du von injektiv auf "bijektiv auf
> dem Bild" kommst und warum die Umkehrabbildung dann auch
> streng monoton wachsend sein muss wärs klasse.
Das überlasse ich dem Leser als Übungsaufgabe ![[aetsch]](/images/smileys/aetsch.gif "[aetsch]") . Das eine ist trivial, das andere fast. Denk mal drüber nach!
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:25 Do 22.10.2009 | | Autor: | kegel53 |
Hehe okay ich werd mal ne Nacht drüber schlafen. Dank dir!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:01 Do 22.10.2009 | | Autor: | Merle23 |
Auch hier der Hinweis: -strenge- Monotonie kann man nicht zeigen, wenn man zeigen will, dass f=id gilt.
|
|
|
| |
|
> Aber es ist einfach falsch, drum kann mans auch nicht
> beweisen.
Hallo leduart,
kannst Du mal (D)ein Gegenbeispiel sagen? Ich habe irgendwie keins gefunden - und weiß daher immer noch nicht, ob die Aussage stimmt oder nicht.
Gegeben war [mm] f:\IN \to \IN [/mm] mit der Eigenschaft f(f(n))>f(n), und die Frage war, ob daraus f(n)>n folgt.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:41 Mi 21.10.2009 | | Autor: | pelzig |
> kannst Du mal (D)ein Gegenbeispiel sagen? Ich habe
> irgendwie keins gefunden - und weiß daher immer noch
> nicht, ob die Aussage stimmt oder nicht.
>
> Gegeben war [mm]f:\IN \to \IN[/mm] mit der Eigenschaft f(f(n))>f(n),
> und die Frage war, ob daraus f(n)>n folgt.
Ein Gegenbeispiel ist die Funktion [mm] $$f(n):=\begin{cases}3&\text{für }n=1\\1&\text{für }n=2\\n+1&\text{sonst}\end{cases}$$ [/mm] Für [mm]n\ge 3[/mm] erfüllt sie $f(f(n))=n+2>n+1=f(n)$, für [mm] $n\in\{1,2\}$ [/mm] auch, aber es ist [mm] $f(2)=1\le [/mm] 2$.
Gruß, Robert
|
|
|
| |
|
Hallo Robert,
wie kommt es, dass du das genau gleiche Gegen-
beispiel wie ich gefunden hast ?
Interessant, oder nicht ?
LG Al
|
|
|
| |
|
>> Aber es ist einfach falsch, drum kann mans auch
>> nicht beweisen.
>
> Hallo leduart,
>
> kannst Du mal (D)ein Gegenbeispiel sagen? Ich habe
> irgendwie keins gefunden - und weiß daher immer
> noch nicht, ob die Aussage stimmt oder nicht.
>
> Gegeben war [mm]f:\IN \to \IN[/mm] mit der Eigenschaft f(f(n))>f(n),
> und die Frage war, ob daraus f(n)>n folgt.
>
> Gruß v. Angela
Hallo Angela,
ich hab mir dies auch gerade überlegt. Zur Präzi-
sierung sollte man wohl noch die Quantoren hin-
schreiben. So wie ich's verstanden habe, ist die
Frage die:
Kann man aus [mm] $(\forall [/mm] n)\ f(f(n))>f(n)$
auf [mm] $(\forall [/mm] n)\ f(n)>n$
schließen ?
Ein einfaches Gegenbeispiel wäre etwa:
[mm] f(n)=\begin{cases} 1\quad, & \mbox{ für }\ n=2 \\ 3\quad, & \mbox{ für }\ n=1\\n+1\quad,&\mbox{ sonst} \end{cases}
[/mm]
Die einsame Ausnahme n=2, für welche f(n)<n ist,
ist allerdings wenig gegen die unendliche Überzahl
aller anderen n, für welche f(n)>n ist, genügt aber,
um die All-Aussage [mm] $(\forall [/mm] n)\ f(n)>n$ zu stürzen.
lieben Gruß Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:48 Mi 21.10.2009 | | Autor: | pelzig |
> Die einsame Ausnahme n=2, für welche f(n)<n ist,
> ist allerdings wenig gegen die unendliche Überzahl
> aller anderen n, für welche f(n)>n ist [...]
Das Gegenbeispiel kann leicht so abgewandelt werden, dass die Behauptung [mm]f(n)>n[/mm] genau für eine beliebige, endliche und nichtleere Ausnahmemenge [mm] $A\subset\IN\setminus\{1\}$, [/mm] nicht gilt: [mm] $$f_A(n):=\begin{cases}1&\text{falls }n\in A\\n+\max(A)&\text{sonst}\end{cases}$$ [/mm] Man könnte sich nun fragen, ob es auch für unendliches A ein solches Beispiel finden lässt. Schönen Abend noch...
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:05 Mi 21.10.2009 | | Autor: | leduart |
Hallo an alle interessierten
mein Gegenbeispiel war:
Fuer alle Zahlen, die das doppelte einer durch 3 teilbaren ungeraden Zahl sind, also n=2*3*k=2m , k ungerade
f(n)=m<n
fuer alle anderen Zahlen f(n)=3n oder f(n)=5n
Gruss leduart
|
|
|
| |
|
Hallo,
ich kann natürlich nicht ausschließen, daß ich mich gerade etwas dämlich anstelle, es wäre nicht das erste Mal...
Aber diese Aufgabe kommt nicht aus der Anfängervorlesung, oder etwa doch?
Falls ja: wie lautet die Aufgabenstellung vollständig - mit Vor- und Nachspiel?
Ansonsten: aus welchem Dunstkreis kommt die Aufgabe?
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:54 Mi 21.10.2009 | | Autor: | pelzig |
> ich kann natürlich nicht ausschließen, daß ich mich
> gerade etwas dämlich anstelle, es wäre nicht das erste Mal...
Ich muss zugeben, dass ich mir an der 2. Variante der Behauptung bisher auch glorreich die Zähne ausgebissen habe. Ich würde aber gern wissen, obs denn nun stimmt oder nicht 
Gruß, Robert
|
|
|
| |
|
> > ich kann natürlich nicht ausschließen, daß ich mich
> > gerade etwas dämlich anstelle, es wäre nicht das erste
> Mal...
> Ich muss zugeben, dass ich mir an der 2. Variante der
> Behauptung bisher auch glorreich die Zähne ausgebissen
> habe. Ich würde aber gern wissen, obs denn nun stimmt
> oder nicht
>
> Gruß, Robert
Hallo Robert,
was verstehst du denn nun unter der "2. Variante" ?
Etwa
$ [mm] (\forall [/mm] n)\ [mm] \left(\ f(f(n))>f(n)\quad \Rightarrow\quad f(n)>n\ \right)$ [/mm] ?
Gruß Al
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:51 Mi 21.10.2009 | | Autor: | pelzig |
> was verstehst du denn nun unter der "2. Variante" ?
Diese.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:40 Mi 21.10.2009 | | Autor: | kegel53 |
Hallo angela,
also die Aufgabe stammt wie du richtig erkannt hast nicht aus einer Anfängervorlesung, sondern ist die Einstiegsaufgabe zu Funktionalanalysis, jedoch hat damit eigentlich nix zu tun is hauptsächlich dazu da, um die Zeit bis zu den ersten "richtigen" Aufgaben zu überbrücken.
Die komplette Aufgabe lautete:
Sei [mm] f:\IN-->\IN [/mm] mit f(n+1)>f(f(n)) für alle [mm] n\in \IN. [/mm] Man zeige, dass dann bereits f(n)=n für alle [mm] n\in \IN [/mm] gilt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:33 Mi 21.10.2009 | | Autor: | pelzig |
Er hat genau diese Aufgabenstellung jetzt schon zweimal geschrieben. Warum zweifelst du das denn jetzt immernoch an?
Behauptung: [mm] $f:\IN\to\IN$ [/mm] mit $f(n+1)>f(f(n))$ für alle n [mm] \Rightarrow $f=\operatorname{id}_\IN$
[/mm]
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:45 Mi 21.10.2009 | | Autor: | Herby |
Hallo Robert,
> Er hat genau diese Aufgabenstellung jetzt schon zweimal
> geschrieben. Warum zweifelst du das denn jetzt immernoch
> an?
>
> Behauptung: [mm]f:\IN\to\IN[/mm] mit [mm]f(n+1)>f(f(n))[/mm] für alle n
> [mm]\Rightarrow[/mm] [mm]f=\operatorname{id}_\IN[/mm]
wahrscheinlich, weil in der ersten Frage was anderes stand
Lg
Herby
|
|
|
| |
|
> Hallo Robert,
>
> > Er hat genau diese Aufgabenstellung jetzt schon zweimal
> > geschrieben. Warum zweifelst du das denn jetzt immernoch
> > an?
> >
> > Behauptung: [mm]f:\IN\to\IN[/mm] mit [mm]f(n+1)>f(f(n))[/mm] für alle n
> > [mm]\Rightarrow[/mm] [mm]f=\operatorname{id}_\IN[/mm]
>
> wahrscheinlich, weil in der
> ersten Frage was anderes
> stand
>
>
> Lg
> Herby
Genau. Und weil ich große Zweifel habe, ob jemand
irrtümlich anstelle eines Gleichheitszeichens ein
Größerzeichen schreibt.
Gruß Al
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:12 Mi 21.10.2009 | | Autor: | pelzig |
Ich kann dir zwar auch nicht sagen was kegel gemeint hat, aber die Aussage [mm] $$f:\IN\to\IN [/mm] $ mit $f(n+1)>f(f(n)) $ für alle [mm] $n\in\IN\quad\Rightarrow\quad [/mm] f(n)>n $ für alle [mm] $n\in\IN$$ [/mm] ist offensichtlich falsch. Betrachte z.B. [mm] $f=\opeartorname{id}_\IN$ [/mm]
Gruß, Robert
|
|
|
| |
|
Hallo Robert,
was soll das " " ?
Ich ziehe es einfach vor, mich mit Aufgaben erst
dann ernsthaft zu befassen, wenn ich einigermaßen
sicher sein kann, dass die Aufgabe auch wirklich
so gemeint war, wie sie dasteht.
Es gäbe ja allenfalls noch die Möglichkeit, dass in
Tat und Wahrheit weder ein "=" noch ein ">", sondern
ein [mm] "\ge" [/mm] gemeint war ...
Gruß Al
|
|
|
| |
|
Hallo zusammen,
noch ein später Nachtrag: ich hatte diese Aufgabe
zuerst wirklich ziemlich falsch eingeschätzt. Jetzt
im Rückblick, wenn ich eure raffinierten Argumente
zum Beweis betrachte, dass aus
[mm] $\forall n\in\IN:\ [/mm] f(n+1)>f(f(n))$ tatsächlich [mm] $\forall n\in\IN:\ [/mm] f(n)=n$
folgt, führt mich diese Einsicht zu ein paar tiefer
gehenden Gedanken über die natürlichen Zahlen.
Wie kann es sein, dass eine unendliche Folge
natürlicher Zahlen durch eine scheinbar so harmlos
daherkommende Ungleichung wie $f(n+1)>f(f(n))$
absolut eindeutig festgelegt ist. Wir sind an die
Vielfalt möglicher Zahlenfolgen so sehr gewöhnt,
dass wir auf den ersten Blick (und auch auf den
zweiten und dritten) nicht erkennen, wie streng
diese Forderung $f(n+1)>f(f(n))$ in Tat und Wahrheit
ist. Trotz der unendlichen Reichhaltigkeit der Menge
[mm] \IN [/mm] und der gesamten Zahlentheorie ist die Ordnungs-
struktur von [mm] \IN [/mm] offenbar ein sehr enges Korsett,
so dass es möglich ist, eine Zahlenfolge bis ins letzte
Detail festzulegen, ohne irgend eines der Glieder
wirklich numerisch festzulegen, durch eine simple
Ungleichung mit einem [mm] \forall [/mm] -Quantor dabei.
Ach ja: ich habe mich noch gefragt, was man
wohl erhalten würde, wenn man z.B.
[mm] $\forall n\in\IN:\ [/mm] f(n+1)>f(f(f(n)))$
voraussetzt ...
LG Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:45 Fr 23.10.2009 | | Autor: | pelzig |
Ich finde diese Aussage auch höchst bemerkenswert. Und der Beweis ist eine richtige Perle, finde ich. Eine tolle Übungsaufgabe.
Gruß, Robert
|
|
|
| |
|
Hallo,
ich danke Euch, pelzig, Al Chwarizmi und leduart für Eure Gegenbeispiele.
Ich bin gespannt, wie das zu lösen ist.
Wenn es hier keiner hinbekommt, dann würde ich mich freuen, wenn Du, kegel53, später mal die Lösung posten würdest.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:34 Mi 21.10.2009 | | Autor: | kegel53 |
Also bevor es hier zur allgemeinen Verwirrung kommt nochmal zu meinen Fragen, die ja teilweise schon beantwortet wurden.
Die allererste Frage bezog sich auf eine Beweisidee, die auf meinem Mist gewachsen ist also ob man von f(f(n))>f(n) direkt auf f(n)>n schließen kann.
Das wurde jetzt bereits mehrmals verneint okay.
Die andere Frage ist nun die direkt aus der Aufgabenstellung also ob man von f(n+1)>f(f(n)) bereits schließen kann, dass f(n)=n gilt. Und das scheint wohl schwieriger sein als gedacht.
Ich werde die Lösung natürlich hier darlegen vorausgesetzt wir besprechen die Aufgabe, denn wie gesagt war die Einstiegsaufgabe zur Vorlseung die "richtigen" kommen erst noch.
An alle bisher Beteiligten ers mal recht herzlichen Dank!!
|
|
|
|
![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]"){kind=small}
![[kopfschuettel]](/images/smileys/kopfschuettel.gif "[kopfschuettel]"){kind=small}
