www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Navigation
 Startseite...
 Suchen
 Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Funktionen" - Fixpunktfunktion nachweisen
Fixpunktfunktion nachweisen < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Funktionen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Fixpunktfunktion nachweisen: Beweisidee besprechen
Status: (Frage) beantwortet Status 
Datum: 11:06 Mo 06.04.2020
Autor: clemenum

Aufgabe
Sei $f$ eine Funktion, die auf [mm] $\mathbb{N}$ [/mm] definiert ist. Es gelte die Beziehung $f(n+1)>f(f(n))$ [mm] $\forall n\in \mathbb{N} [/mm] $.
Man zeige: $f(n)=n$ [mm] $\forall n\in \mathbb{N}$ [/mm]

Ein Kollege sagte mir, dass er glaubt, dass es sich hier um eine der anspruchsvollsten Aufgaben vom Übungsblatt handelt. Ich sehe aber nicht, wieso die so trickreich sein sollte.

Meine Idee ist die, dass ich einen Widerspruchsbeweis aufstelle.
Setze $f(n)= n+l$ mit $n,l [mm] \in \mathbb{N}.$ [/mm]
Dann habe ich: $f(f(n)) = f(n+l)= n+2l > n+l+1 =f(n+1) >f(f(n))$ und somit ist [mm] $f(f(n))\neq [/mm] f(f(n)).$ Ein Widerspruch zur Funktionsdefinition!

Die einzige Möglichkeit den Widerspruch zu vermeiden, hätten wir, wenn wir $n+2l = n+l+1,$ also l=1 haben. Für alle positiven $l$ ist somit der Beweis doch gezeigt, oder? Also, müsste nur noch zu zeigen sein, was passiert, wenn $f(n)<n$.

Würdet ihr sagen, dass der Beweis für den Fall $f(n)> n$ erfolgreich zum Widerspruch gebracht wurde? Ein wenig Unsicherheit ist schon noch da.

Wäre für kurze Rückmeldung dankbar!

        
Bezug
Fixpunktfunktion nachweisen: Antwort
Status: (Antwort) fertig Status 
Datum: 11:59 Mo 06.04.2020
Autor: Gonozal_IX

Hiho,

> Meine Idee ist die, dass ich einen Widerspruchsbeweis aufstelle.

Das wäre wohl auch mein erster Ansatz…

Ich fasse erstmal deinen Fehler zusammen:

> Setze [mm]f(n)= n+l[/mm] mit [mm]n,l \in \mathbb{N}.[/mm]
> ...
> Ein Widerspruch zur Funktionsdefinition!

Erstmal nur ein Widerspruch zu deiner Annahme.
Wer sagt dir denn, dass deine Funktion die obige Form hat?
Du nimmst nämlich an: Für jedes [mm] $n\in\IN$ [/mm] gibt es (dasselbe!) [mm] $l\in\IN$, [/mm] so dass $f(n) = n+l$ gilt für eine beliebige Funktion.

Das stimmt z.B. schon mal nicht für die Quadratfunktion $f(n) = [mm] n^2$, [/mm] denn offensichtlich ist $f(1) = [mm] 1^2 [/mm] = 1 + 0$ aber $f(2) = [mm] 2^2 [/mm] = 2 + 2$
D.h. es ist im ersten Fall $l = 0$, im zweiten aber $l=2$. D.h. korrekt wäre deine Aussage nur, wenn das $l$ für jedes $n [mm] \in \IN$ [/mm] ein anderes wäre, also korrekterweise ein [mm] $l_n$, [/mm] dann wäre also $f(n) = n + [mm] l_n$. [/mm]

Und schon ist dein Widerspruch keiner mehr, weil deine Gleichung dann lauten würde: $f(f(n)) = f(n+1) [mm] \gdw (n+l_n) [/mm] + [mm] l_{f(n)} [/mm] = [mm] n+1+l_{n+1}$ [/mm] und du kannst nix mehr zusammenfassen…

Vor dem Beweis eine Rückfrage: Gilt bei euch $0 [mm] \in \IN$ [/mm] oder $0 [mm] \not\in \IN$? [/mm]

Gruß,
Gono.


Bezug
                
Bezug
Fixpunktfunktion nachweisen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:39 Mo 06.04.2020
Autor: clemenum

Hallo Gonozal!

Vielen herzlichen Dank, dass du mir das so detailiert zeigst! Du gibst mir echt richtig tiefe Einsicht in dieses Problem!

Bei uns gilt [mm] $0\notin \mathbb{N}$. [/mm]

Bezug
                        
Bezug
Fixpunktfunktion nachweisen: Antwort
Status: (Antwort) fertig Status 
Datum: 08:04 Mi 08.04.2020
Autor: Gonozal_IX

Hiho,

um die Sache mal zu einem Ende zu bringen: Ein (mir bekannter) Beweis ist alles andere als trivial, du kannst ihn dir []hier anschauen. Solltet ihr einen einfacheren präsentiert bekommen, gerne hier posten :-)

Gruß,
Gono

Bezug
                                
Bezug
Fixpunktfunktion nachweisen: Variante
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 01:29 Do 09.04.2020
Autor: HJKweseleit

Aufbauend auf den von dir empfohlenen Beweis habe ich eine Variante gefunden, die eigentlich nur den ersten Beweisschritt f(1)=1 wiederholt. Die Idee ist folgende:
[Dateianhang nicht öffentlich]

Zunächst ist klar, dass alle Punkte (n|f(n)) im Feld rechts oben von der roten Begrenzung liegen müssen. Nachdem man bewiesen hat, dass f(1)=1 ist (roter Punkt) sowie f(k)>1 für k>1, müssen die restlichen Punkte rechts oben von der blauen Begrenzung liegen. Zieht man nun das Bild durch Koordinatentransformation eine Position nach links und nach unten, hat man für die restlichen Punkte die Anfangssituation vor sich und kann dann zeigen, dass der nächste Punkt (blau) nun ebenfalls auf (1|1) liegt, rücktransformiert also auf (2|2) usw.

Zunächst wiederhole ich noch mal die Beweisschritte für n=1 etwas ausführlicher. Außerdem ändere ich die Behauptung für die Vollst. Ind. etwas ab zu

f(k)=n [mm] \gdw [/mm] k=n

I.Anfang für n=1:

Richtung [mm] \Rightarrow [/mm]  
Sei f(k)=1. Annahme: k>1. Dann existiert f(k-1), und es gilt: 1=f(k)=f(k-1+1)>f(f(k-1)) Wegen [mm] f(f(k-1))\in \IN [/mm] muss der Wert aber [mm] \ge [/mm] 1 sein. Also stimmt die Annahme nicht, und k muss 1 sein. Für k=1 ergibt f(k)=1 keinen Widerspruch, da hier k keinen Vorgänger k-1 hat und daher mit f(k-1) nicht argumentiert werden kann.

Richtung [mm] \Leftarrow [/mm]
Sei a der kleinste Funktionswert aus der Menge {f(2), f(3),f(4)...}, dann gibt es ein k>1 mit f(k)=a. Auch hier existiert wieder f(k-1) wegen [mm] k\ge [/mm] 2, und es gilt a=f(k)=f(k-1+1)>f(f(k-1)). Da der Funktionswert <a ist, kann f(k-1) nicht aus der Menge {2, 3, ...} sein, also muss f(k-1)=1 sein. Dann ist aber nach dem ersten Teil dieses Beweises k-1=1, also k=2, und dies nochmals in f(k-1)=1 eingesetzt gibt f(2-1)=f(1)=1.

I.-Schritt von n auf n+1.

Es gelte nun f(k)=t [mm] \gdw [/mm] k=t für t=1, 2, 3, ... n. Das bedeutet aber, dass f(k+n)>n sein muss für alle k [mm] \in \IN [/mm] (deshalb meine Umformulierung; f(t)=t für [mm] t\le [/mm] n reicht nicht, die Umformulierung garantiert auch, dass für alle weiteren t>n die Werte von 1 bis n nicht mehr vorkommen.)
Somit ist f(k+n)-n>0.
Ich bilde nun

                g(k)=f(k+n)-n für k [mm] \in \IN. [/mm]

Das ist die erwähnte Verschiebung. g ist nun - wie vorher f - eine Abbildung von [mm] \IN [/mm] nach [mm] \IN. [/mm]

Außerdem gilt:
g(k+1)=f(k+n+1)-n>f(f(k+n))-n=g(f(k+n)-n)=g(g(k))
Also g(k+1)>g(g(k)).

Damit hat g dieselben Eigenschaften wie f, und nach obigem Beweis muss nun g(1)=1 sein, also f(1+n)-n=1, also f(n+1)=n+1. Außerdem muß für g(k)=1 folgen: k=1, d.h. aus f(k+n)-n=1 folgt k=1 bzw. aus f(k+n)=n+1 folgt k=1, d.h. die Funktionswerte f(n+2), f(n+3)... liegen alle über n+1.

Dateianhänge:
Anhang Nr. 1 (Typ: JPG) [nicht öffentlich]
Bezug
                                        
Bezug
Fixpunktfunktion nachweisen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:24 Do 09.04.2020
Autor: statler

Hallo,
das ist sehr schön aufgeschrieben und macht klar, daß es sich um einen Induktionsbeweis handelt.

Zur Abrundung würde ich im folgenden Absatz noch das Kursive einfügen:

> Richtung [mm]\Leftarrow[/mm]
>  Sei a der kleinste Funktionswert aus der Menge {f(2),
> f(3),f(4)...}, dann gibt es ein k>1 mit f(k)=a. Auch hier
> existiert wieder f(k-1) wegen [mm]k\ge[/mm] 2, und es gilt
> a=f(k)=f(k-1+1)>f(f(k-1)). Da der Funktionswert an der Stelle f(k-1) <a ist,
> kann das Argument f(k-1) nicht aus der Menge {2, 3, ...} sein, also muss
> f(k-1)=1 sein. Dann ist aber nach dem ersten Teil dieses
> Beweises k-1=1, also k=2, und dies nochmals in f(k-1)=1
> eingesetzt gibt f(2-1)=f(1)=1.

Frohe Ostern trotz aller Kalamitäten
Dieter


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Funktionen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]