Zeige f ist die identität

04.12.2011, 15:50

fayfie

Zeige f ist die identität

es sei f: N->N eine Abbildung mit der Eigenschaft f(n+1)>f(f(n))
Zeige f ist die Identität

Hallo smile

Ich habe jetzt schon einige Zeit an dieser Aufgabe herumgebastelt und versucht abzuleiten, Funktionen zu komibieren etc aber bis jetzt hat nichts wirklich zur Erleuchtung geführt.

Hätte jemand vill einen Tip für mich? Schon mal danke Augenzwinkern

04.12.2011, 17:11

HAL 9000

Auf diesen Beitrag antworten »

Ich kann zumindest erstmal die Aufgabe identifizieren:

Das ist die sechste Aufgabe der IMO 1977. Augenzwinkern

04.12.2011, 17:12

fayfie

Auf diesen Beitrag antworten »

auf der seite gibts nicht zufällig auch ne lösung zu?^^

04.12.2011, 17:13

Ungewiss

Auf diesen Beitrag antworten »

Sollte mich das beruhigen, denn ich kriegs auch nach ner Weile nachdenken nicht hin? verwirrt

Mein Ansatz war Induktion, und beim Induktionsanfang aus f(1)>1 nen Widerspruch basteln, was mir aber nicht wirklich gelingt.

04.12.2011, 17:15

HAL 9000

Auf diesen Beitrag antworten »

Lösungsidee: Weise zunächst die strenge Monotonie der Folge $\begin{eqnarray*} f(n) \end{eqnarray*}$ nach, also $\begin{eqnarray*} f(n)<f(n+1) \end{eqnarray*}$ .

Die eigentliche Behauptung ist dann eine leichte Folgerung daraus.

04.12.2011, 17:29

fayfie

Auf diesen Beitrag antworten »

@HAL 9000
Hat das bei dir schon geklappt mit zeige f ist streng monoton steigend?

Bin grade am Rumbasteln, müsste dazu ja herleiten, dass f(n)<n+1 also f(n)<=n

...aber wie ... bin noch am ausprobieren Augenzwinkern

04.12.2011, 17:31

HAL 9000

Auf diesen Beitrag antworten »

Ehrlich gesagt habe ich den Beweis vorliegen, und er ist nicht auf meinem Mist gewachsen. Aber er ist mit diesem Ansatz sehr gut verständlich.

04.12.2011, 17:42

fayfie

Auf diesen Beitrag antworten »

Ich überlege die ganze Zeit ob man auf die Aussage

f(n+1) > f(f(n)) die Umkehrfunktion von f loslassen könnte und dann daraus
n+1 >f(n) ableiten kann. was ja bedeuten würde, dass f streng monoton steigend ist.
aber ich bezweifle dass ich das darf, zumal weiß ich ja gar nich ob f ne Umkehrfunktion hat ...

kriege ich noch einen Tipp bitte?

04.12.2011, 17:50

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von fayfie
Ich überlege die ganze Zeit ob man auf die Aussage

f(n+1) > f(f(n)) die Umkehrfunktion von f loslassen könnte und dann daraus
n+1 >f(n) ableiten kann

Wenn f streng monoton steigend ist, darfst du das - das ist ja eben die Kernidee des Beweises! Aber diese Monotonie ist eben zuerst mal nachzuweisen.

04.12.2011, 17:54

fayfie

Auf diesen Beitrag antworten »

ja stimmt macht sinn... dachte mir das das nich geht

leider komm ich hier so nich weiter. kannst du mir noch einen Tipp geben wie ich die strenge monotonie daraus herleite, vill die erste umformung oder so, die in dem Beweis vor dir vorgenommen wurde?
Danke

04.12.2011, 17:57

tmo

Auf diesen Beitrag antworten »

Das, was du da machen willst, kannst du doch gerade dann machen, wenn du die Monotonie nachgewiesen hast. Das müssen wir also noch tun und könnten wir so angehen (ich fange mit den nat. Zahlen mal bei 1 an, also die 0 sei nicht drin)

Betrachte die Mengen $\begin{eqnarray*} M_n := \{f(m) | m \geq n \} \end{eqnarray*}$

$\begin{eqnarray*} M_1 \end{eqnarray*}$ enthält als Teilmenge der nat. Zahlen ein kleinstes Element. Wegen der Vorraussetzung kann dies nur f(1) sein.

Folglich gilt schonmal $\begin{eqnarray*} f(n) > f(1) \end{eqnarray*}$ für alle $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$ . Unser Induktionsanfang.

Nun nehmen wir im Induktionsschritt an, dass $\begin{eqnarray*} f(l) \end{eqnarray*}$ kleinstes Element (und zwar wie im Induktionsanfang echt kleiner als alle anderen) von $\begin{eqnarray*} M_{l} \end{eqnarray*}$ sei für alle $\begin{eqnarray*} l < n \end{eqnarray*}$ und betrachten die Menge $\begin{eqnarray*} M_n \end{eqnarray*}$ . Ihr Minimum sei c.
Nun gilt für $\begin{eqnarray*} k \geq n \end{eqnarray*}$ : $\begin{eqnarray*} f(k+1) > f(f(k)) \end{eqnarray*}$ . Wegen $\begin{eqnarray*} k \geq n \end{eqnarray*}$ gilt $\begin{eqnarray*} f(k) > f(n-1) \geq n-1 \end{eqnarray*}$ , also $\begin{eqnarray*} f(k) \geq n \end{eqnarray*}$ .

Foglich ist $\begin{eqnarray*} f(f(k)) \in M_n \end{eqnarray*}$ , also folgt $\begin{eqnarray*} f(k+1) > f(f(k) \geq c \end{eqnarray*}$ und der Induktionsschritt ist geschafft, weil das Minimum wieder nur f(n) sein kann.

04.12.2011, 17:58

HAL 9000

Auf diesen Beitrag antworten »

Die Kernidee für den Monotoniebeweis: Man weist die zur Monotonie de facto gleichbedeutend Aussage

$\begin{eqnarray*} A_n \end{eqnarray*}$ : Es ist $\begin{eqnarray*} f(n)\geq n \end{eqnarray*}$ sowie $\begin{eqnarray*} f(n) \end{eqnarray*}$ das eindeutige Minimum der Menge $\begin{eqnarray*} M_n:=\{f(n),f(n+1),f(n+2),\ldots \} \end{eqnarray*}$ .

per Vollständiger Induktion nach.

EDIT: Etwas spät.

04.12.2011, 18:00

fayfie

Auf diesen Beitrag antworten »

Zitat:

Original von tmo

Betrachte die Mengen $\begin{eqnarray*} M_n := \{f(m) | m \geq n \} \end{eqnarray*}$

$\begin{eqnarray*} M_1 \end{eqnarray*}$ enthält als Teilmenge der nat. Zahlen ein kleinstes Element. Wegen der Vorraussetzung kann dies nur f(1) sein.

warum musst das kleinste Element f(1) sein? Wir haben die Monotonie ja noch nicht nachgewiesen, also kann es jedes belibiege Element sein. oder etwa nicht?

04.12.2011, 18:15

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von fayfie
warum musst das kleinste Element f(1) sein?

Weil $\begin{eqnarray*} f(m) \end{eqnarray*}$ für $\begin{eqnarray*} m>1 \end{eqnarray*}$ nicht das kleinste Element sein kann, wegen $\begin{eqnarray*} f(m) > f(f(m-1)) \end{eqnarray*}$ . Bleibt also nur $\begin{eqnarray*} f(1) \end{eqnarray*}$ übrig.

04.12.2011, 18:51

fayfie

Auf diesen Beitrag antworten »

mom

04.12.2011, 18:58

fayfie

Auf diesen Beitrag antworten »

okaaaaay schon mal vielen Dank. Ich hab jetzt mal versucht alles was ihr so geschrieben habt mit meinen eigenen Worten wieder zugeben:

Wir betrachten die Menge $\begin{eqnarray*} M_{n} := \end{eqnarray*}$ { $\begin{eqnarray*} f(m)|m\geq n \end{eqnarray*}$ }

Annahme: $\begin{eqnarray*} f(m) \in M_{k} \end{eqnarray*}$ ist kleinstes Element der Menge
Es gilt nach VAS: f(m)>f(f(m-1) mit $\begin{eqnarray*} f(m-1) \in \end{eqnarray*}$ N, da f: N->N
$\begin{eqnarray*} \Rightarrow \exists n \in N mit f(m)>n \end{eqnarray*}$
WIDERSPRUCH!
$\begin{eqnarray*} \Rightarrow f(k) ist kleinstes Element in M_{k} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow f(n+1)>f(n) \forall n \in N \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ f ist injektik
$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ Es existiert eine Umkehrfunktion
$\begin{eqnarray*} \Rightarrow n+1 > f(n) > 1 \forall n \in N \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ f(n) = n

04.12.2011, 19:03

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von fayfie
$\begin{eqnarray*} \Rightarrow n+1 > f(n) > 1 \forall n \in N \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ f(n) = n

Also an diesem Schluss - so aufgeschrieben - könnte man schon noch etwas herumkritteln.

04.12.2011, 19:24

fayfie

Auf diesen Beitrag antworten »

Ja da hast du Recht das werde ich noch etwas ausführlicher aufschreiben smile

Aber VIELEN VIELEN DANK für eure Hilfe smile

)) Die AUfgabe ist geschafft!

04.12.2011, 23:51

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von fayfie
Wir betrachten die Menge $\begin{eqnarray*} M_{n} := \end{eqnarray*}$ { $\begin{eqnarray*} f(m)|m\geq n \end{eqnarray*}$ }

Annahme: $\begin{eqnarray*} f(m) \in M_{k} \end{eqnarray*}$ ist kleinstes Element der Menge
Es gilt nach VAS: f(m)>f(f(m-1) mit $\begin{eqnarray*} f(m-1) \in \end{eqnarray*}$ N, da f: N->N
$\begin{eqnarray*} \Rightarrow \exists n \in N mit f(m)>n \end{eqnarray*}$
WIDERSPRUCH!
$\begin{eqnarray*} \Rightarrow f(k) ist kleinstes Element in M_{k} \end{eqnarray*}$

Diese Folgerung geht so übrigens auch nicht direkt.

Das klappt so nur beim Induktionsanfang, also bei $\begin{eqnarray*} M_1 \end{eqnarray*}$ .

Für $\begin{eqnarray*} M_n \end{eqnarray*}$ im Allgemeinen hat man ja das Problem, dass man nur $\begin{eqnarray*} f(m) > f(f(m-1)) \end{eqnarray*}$ kriegt, aber ad hoc noch gar nicht sichergehen kann, dass die Zahl auf der rechten Seite überhaupt in $\begin{eqnarray*} M_n \end{eqnarray*}$ liegt, d.h. ein Widerspruch zur Minimalität von $\begin{eqnarray*} f(m) \end{eqnarray*}$ gefunden ist.

Das muss man sich ja erst im Induktionsschritt erarbeiten. Deswegen ja auch der Induktionsbeweis und kein "direkter".

Übrigens wie ich finde ein schönes Beispiel, wie eine Aussage (die Monotonie) durch geschicktes Umformulieren per Induktion bewiesen werden kann, während man sich an der klassischen Formulierung - $\begin{eqnarray*} f(n+1)>f(n) \end{eqnarray*}$ - per Induktion aber sowas von die Zähne ausbeißen würde.
Einfach nur, weil man eben im Induktionsschritt auch eine ganz andere Annahme zur Verfügung hat, nämlich die Aussage $\begin{eqnarray*} f(k) > f(n) \end{eqnarray*}$ für alle $\begin{eqnarray*} k > n \end{eqnarray*}$ und nicht nur $\begin{eqnarray*} f(n+1)>f(n) \end{eqnarray*}$

Neue Frage »

Antworten »

Zeige f ist die identität

Verwandte Themen