injektiv--bijektiv < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:47 Fr 24.10.2008 | | Autor: | gigi |
Sei [mm] A_n= [/mm] {k [mm] \in \IN [/mm] / 1 [mm] \le [/mm] k [mm] \le [/mm] n}.
| Aufgabe | | Zeige (durch Induktion): f: [mm] A_n \to A_n [/mm] injektiv [mm] \Rightarrow [/mm] f ist bijektiv |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
hallo,
um zu zeigen, dass f bijektiv ist, muss ich ja zeigen, dass f auch surjektiv ist, wenn es injektiv ist. Also, dass zu jedem bild ein urbild existiert (=surjektiv)
Und was genau bedeutet [mm] A_n, [/mm] ist es eine menge von natürlichen zahlen von 1 bis n?
soviel zu meinem aufgabenverständnis...wie gehe ich bei dem beweis vor?
IA: n=1: [mm] A_1 \to A_1
[/mm]
[mm] A_1 \to [/mm] {1}
{1} [mm] \to [/mm] {1} dies ist injektiv, surjektiv und damit auch bijektiv
IS: [mm] A_{n+1} \to A_{n+1}
[/mm]
kann ich so anfangen? wie gehts dann weiter? und was schreibe ich zwischen die einzelnen abbildungen, = oder [mm] \gdw??
[/mm]
gruß und dank!
|
|
| |
|
> Sei [mm]A_n=[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{k [mm]\in \IN[/mm] / 1 [mm]\le[/mm] k [mm]\le[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
n}.
>
> Zeige (durch Induktion): f: [mm]A_n \to A_n[/mm] injektiv
> [mm]\Rightarrow[/mm] f ist bijektiv
> um zu zeigen, dass f bijektiv ist, muss ich ja zeigen, dass
> f auch surjektiv ist, wenn es injektiv ist. Also, dass zu
> jedem bild ein urbild existiert (=surjektiv)
Hallo,
ja.
> Und was genau bedeutet [mm]A_n,[/mm] ist es eine menge von
> natürlichen zahlen von 1 bis n?
Ja, die Menge die alle natürlichen Zahlen von 1 bis n enthält.
Ist Dir die Aussage klar? Findest Du sie "logisch"? Dann ist's gut.
(Ansonsten mach Dir mal ein Bildchen.)
> soviel zu meinem aufgabenverständnis...wie gehe ich bei dem
> beweis vor?
Steht irgendwo, daß man das per Induktion machen soll?
Ich würd's ohne machn.
Nimm an, daß die Funktion injektiv ist und nicht surjektiv ist. (Beweis durch Widerspruch)
Was bedeutet das?
Gruß v. Angela
>
> IA: n=1: [mm]A_1 \to A_1[/mm]
> [mm]A_1 \to[/mm] {1}
> {1} [mm]\to[/mm] {1} dies ist injektiv, surjektiv
> und damit auch bijektiv
>
> IS: [mm]A_{n+1} \to A_{n+1}[/mm]
>
> kann ich so anfangen? wie gehts dann weiter? und was
> schreibe ich zwischen die einzelnen abbildungen, = oder
> [mm]\gdw??[/mm]
>
> gruß und dank!
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:25 Fr 24.10.2008 | | Autor: | gigi |
ja, steht ja explizit in der aufgabe, das induktion verwendet werden soll!
|
|
|
| |
|
Hallo gigi,
also ich würde den Induktionsschritt folgendermaßen erläutern:
[mm] \left|A_n\right|=n [/mm]. Wenn [mm] f:A_n \to\ A_n [/mm], werden n-Elemente auf n-Elemente abgebildet. D.h. alle Werte auf der x-Achse haben ein Urbild, da [mm] A_n [/mm] mit sich selbst gleichmächtig ist.
=> Bijektivität und somit auch Injektivität
=> [mm] A_n_+_1 [/mm] muss mit sich slebst auch bijektiv sein, da die Abbildung nun [mm] f:A_n_+_1 \to\ A_n_+_1 [/mm] heißt und eine Mächtigkeit von [mm] \left|A_n_+_1\right|=n+1 [/mm]
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 11:38 Sa 25.10.2008 | | Autor: | gigi |
hallo und danke,
also kann ich meinen induktionsanfang so schreiben wie oben?
>
> also ich würde den Induktionsschritt folgendermaßen
> erläutern:
>
> [mm]\left|A_n\right|=n [/mm]. Wenn [mm]f:A_n \to\ A_n [/mm], werden
> n-Elemente auf n-Elemente abgebildet. D.h. alle Werte auf
> der x-Achse haben ein Urbild,
wieso alle werte auf der x-achse? wo liegen dann die urbilder? auf der y-achse?? oder wieder auf der x-achse?
>
> da [mm]A_n[/mm] mit sich selbst
> gleichmächtig ist.
>
> => Bijektivität
hier wenden wir die definiton an: X~Y [mm] \gdw [/mm] ex. Bijektion f:X [mm] \to [/mm] Y. oder?
> => [mm]A_n_+_1[/mm] muss mit sich slebst auch bijektiv sein, da die
> Abbildung nun [mm]f:A_n_+_1 \to\ A_n_+_1[/mm] heißt und eine
> Mächtigkeit von [mm]\left|A_n_+_1\right|=n+1[/mm]
>
für meine begriffe ist das so aber noch kein vollständiger induktionsbeweis, oder? irgendwo müssen wir ja die voraussetzung einsetzen und somit dann von n auf n+1 schließen, oder?! und für [mm] A_n [/mm] müssen wir eigentlich gar nichts beweisen, oder--ist ja vorausgesetzt, dass bei der abbildung bijektivität gilt.
gruß und besten dank
|
|
|
| |
|
> für meine begriffe ist das so aber noch kein vollständiger
> induktionsbeweis, oder?
Hallo,
ja, das hast Du richtig bemerkt.
Den Fahrplan für den Induktionsbeweis findest Du in meiner anderen Antwort.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Korrektur) fundamentaler Fehler  | | Datum: | 12:47 Sa 25.10.2008 | | Autor: | angela.h.b. |
> also ich würde den Induktionsschritt folgendermaßen
> erläutern:
>
> [mm]\left|A_n\right|=n [/mm]. Wenn [mm]f:A_n \to\ A_n [/mm], werden
> n-Elemente auf n-Elemente abgebildet. D.h. alle Werte auf
> der x-Achse haben ein Urbild, da [mm]A_n[/mm] mit sich selbst
> gleichmächtig ist.
>
> => Bijektivität und somit auch Injektivität
> => [mm]A_n_+_1[/mm] muss mit sich slebst auch bijektiv sein, da die
> Abbildung nun [mm]f:A_n_+_1 \to\ A_n_+_1[/mm] heißt und eine
> Mächtigkeit von [mm]\left|A_n_+_1\right|=n+1[/mm]
Hallo,
mehrererlei:
1. Schau Dir nochmal genau an, wie das Prinzip der Induktion funktioniert.
Wenn Du im Induktionsschritt (oder: - schluß) den Übergang von n nach n+1 vollziehst, ist die Richtigkeit der Aussage für n überhaupt nicht zu begründen.
Die Richtigkeit wird in der Induktionsvoraussetzung einfach angenommen, das ist ein wesentliches Element der Induktion.
2. f: [mm] A_n \to A_n [/mm] bedeutet, daß jedem Element aus [mm] \{1,2,...,n\} [/mm] eines aus [mm] \{1,2,...,n\} [/mm] zugewiesen wird. Der Funktionswert eines jeden Elementes liegt also in [mm] \{1,2,...,n\}.
[/mm]
Daß die Abbildung von [mm] A_n \to A_n [/mm] geht, bedeutet nicht, daß jedes Element aus [mm] A_n [/mm] auch getroffen wird:
Eine Abbildung von [mm] A_n \to A_n [/mm] wäre auch die durch f(x):=1 für alle [mm] x\in A_n [/mm] definierte.
Aus f: [mm] A_n\to A_n [/mm] folgt also nicht die Injektivität.
Die Injektivität ist in der zu beweisenden Behauptung vorausgesetzt: wir betrachten überhaupt nur solche Funktionen von [mm] A_n [/mm] nach [mm] A_n, [/mm] welche injektiv sind.
Von diesen soll gezeigt werden, daß sie auch bijektiv sind.
3.
=> $ [mm] A_n_+_1 [/mm] $ muss mit sich slebst auch bijektiv sein
Bijektiv können Funktionen sein. Bijektive Mengen gibt's nicht.
Allerdings gibt es gleichmächtige Mengen.
Und: zwischen zwei gleichmächtigen Mengen gibt's ne Bijektion.
> da die
> Abbildung nun [mm]f:A_n_+_1 \to\ A_n_+_1[/mm] heißt und eine
> Mächtigkeit von [mm]\left|A_n_+_1\right|=n+1[/mm]
Eine Abbildung hat keine Mächtigkeit.
Der wahre Kern: im Induktionsschritt betrachtet man nun eine beliebige injektive Abbildung zwischen den Mengen [mm] A_{n+1} [/mm] und [mm] A_{n+1}, [/mm] also zwischen zwei Mengen, die die Mächtigkeit n+1 haben.
Das Vertrackte am Beweis: dieses f, welches wir im Induktionsschritt betrachten, hat mit dem f aus der Induktionsvoraussetzung wenig gemeinsam. Der Bogen zur Induktionsvoraussetzung ist erst zu schlagen, s. meine Antwort an gigi.
Die Induktionsbehauptung ist eine Behauptung, welche für völlig beliebige injektive Abbildungen von der Menge [mm] A_n [/mm] in die Menge [mm] A_n [/mm] gemacht wird.
Gruß v. Angela
|
|
|
| |
|
> Sei [mm] A_n={k \in \IN/ 1\le k \le n}.
[/mm]
>
> Zeige (durch Induktion): f: [mm]A_n \to A_n[/mm] injektiv
> [mm]\Rightarrow[/mm] f ist bijektiv
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> hallo,
>
> um zu zeigen, dass f bijektiv ist, muss ich ja zeigen, dass
> f auch surjektiv ist, wenn es injektiv ist. Also, dass zu
> jedem bild ein urbild existiert (=surjektiv)
> Und was genau bedeutet [mm]A_n,[/mm] ist es eine menge von
> natürlichen zahlen von 1 bis n?
> soviel zu meinem aufgabenverständnis...wie gehe ich bei dem
> beweis vor?
>
> IA: n=1: [mm]A_1 \to A_1[/mm]
> [mm]A_1 \to[/mm] {1}
> {1} [mm]\to[/mm] {1} dies ist injektiv, surjektiv
> und damit auch bijektiv
>
> IS: [mm]A_{n+1} \to A_{n+1}[/mm]
>
> kann ich so anfangen? wie gehts dann weiter? und was
> schreibe ich zwischen die einzelnen abbildungen, = oder
> [mm]\gdw??[/mm]
Hallo,
schreib Dir auch die Induktionsvoraussetzung ganz genau auf.
Induktionsvoraussetzung: für ein bestimmtes n [mm] \in \IN [/mm] sei bereits gezeigt, daß jede injektive Abbildung, die von [mm] A_n [/mm] nach [mm] A_n [/mm] abbildet, bijektiv ist, dh.
es gilt
f: [mm]A_n \to A_n[/mm] injektiv [mm] \Rightarrow[/mm] [/mm] f ist bijektiv für ein [mm] n\in \IN.
[/mm]
Induktionsschluß [mm] n\to [/mm] n+1:
Hier ist zu zeigen, daß die Behauptung auch für n+1 gilt, d.h. daß jede injektive Abbildung, die von [mm] A_n [/mm] nach [mm] A_n [/mm] abbildet, bijektiv ist, daß also
[mm] f:A_{n+1}\to A_{n+1} [/mm] injektiv ==> f ist bijektiv.
Beweis:
Sei [mm] f:A_{n+1}\to A_{n+1} [/mm] injektiv.
Hier können nun zwei Falle auftreten, entweder wird kein k aus [mm] A_n [/mm] auf die n+1 abgebildet, oder es wird ein k aus [mm] A_n [/mm] auf die n+1 abgebildet.
Die Fälle sind getrennt zu untersuchen.
1. Fall:
Der ist leicht. Schau die Einschränkung g von f auf [mm] A_n [/mm] an. Überlege Dir, warum g in die Menge [mm] A_n [/mm] abbildet und injektiv ist.
Was weißt Du mit der Induktionsvoraussetzung über g?
Begründe dann die Bijektivität von f.
2. Fall: es gibt ein k aus [mm] A_n, [/mm] welches auf n+1 abgebildet wird, für welches also f(k)=n+1 ist.
Der ist viel schwieriger.
Überleg Dir erstmal, warum es nicht noch ein anderes k' geben kann, welches auch auf n+1 abgebildet wird.
Nun kannst Du eine Funktion g: [mm] A_n \to [/mm] ... definieren mit
g(x):= f(x) für [mm] x\not=k
[/mm]
g(k):=f(n+1).
Überlege Dir, in welche Menge g abbidldet.
Überlege Dir, warum diese Abbildung injektiv ist.
Folgere mit der Induktionsvoraussetzung, daß die Abbildung bijektiv ist.
Überlege Dir, daß die Einschränkungen von g und f auf die Menge [mm] A_n [/mm] \ [mm] \{k\} [/mm] = [mm] (A_{n+1} [/mm] \ [mm] \{n+1,k\}) [/mm] gleich sind.
Und am Ende mußt Du noch die Kurve zur Bijektivität von f bekommen durch Betrachtung der Funktionswerte von n+1 und k.
Viel Erfolg!
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:14 Sa 25.10.2008 | | Autor: | gigi |
> > Sei [mm]A_n={k \in \IN/ 1\le k \le n}.[/mm]
> >
> > Zeige (durch Induktion): f: [mm]A_n \to A_n[/mm] injektiv
> > [mm]\Rightarrow[/mm] f ist bijektiv
> > Ich habe diese Frage in keinem Forum auf anderen
> > Internetseiten gestellt.
> >
> > hallo,
> >
> > um zu zeigen, dass f bijektiv ist, muss ich ja zeigen, dass
> > f auch surjektiv ist, wenn es injektiv ist. Also, dass zu
> > jedem bild ein urbild existiert (=surjektiv)
> > Und was genau bedeutet [mm]A_n,[/mm] ist es eine menge von
> > natürlichen zahlen von 1 bis n?
> > soviel zu meinem aufgabenverständnis...wie gehe ich bei dem
> > beweis vor?
> >
> > IA: n=1: [mm]A_1 \to A_1[/mm]
> > [mm]A_1 \to[/mm] {1}
> > {1} [mm]\to[/mm] {1} dies ist injektiv,
> surjektiv
> > und damit auch bijektiv
> >
> > IS: [mm]A_{n+1} \to A_{n+1}[/mm]
> >
> > kann ich so anfangen? wie gehts dann weiter? und was
> > schreibe ich zwischen die einzelnen abbildungen, = oder
> > [mm]\gdw??[/mm]
>
> Hallo,
>
> schreib Dir auch die Induktionsvoraussetzung ganz genau
> auf.
>
> Induktionsvoraussetzung: für ein bestimmtes n [mm]\in \IN[/mm] sei
> bereits gezeigt, daß jede injektive Abbildung, die von [mm]A_n[/mm]
> nach [mm]A_n[/mm] abbildet, bijektiv ist, dh.
> es gilt
> f: [mm]A_n \to A_n[/mm] injektiv [mm]\Rightarrow[/mm][/mm] f ist bijektiv für ein
> [mm]n\in \IN.[/mm]
>
> Induktionsschluß [mm]n\to[/mm] n+1:
>
> Hier ist zu zeigen, daß die Behauptung auch für n+1 gilt,
> d.h. daß jede injektive Abbildung, die von [mm]A_n[/mm] nach [mm]A_n[/mm]
> abbildet, bijektiv ist, daß also
> [mm]f:A_{n+1}\to A_{n+1}[/mm] injektiv ==> f ist bijektiv.
>
> Beweis:
>
> Sei [mm]f:A_{n+1}\to A_{n+1}[/mm] injektiv.
>
> Hier können nun zwei Falle auftreten, entweder wird kein k
> aus [mm]A_n[/mm] auf die n+1 abgebildet, oder es wird ein k aus [mm]A_n[/mm]
> auf die n+1 abgebildet.
> Die Fälle sind getrennt zu untersuchen.
>
> 1. Fall:
> Der ist leicht. Schau die Einschränkung g von f auf [mm]A_n[/mm] an.
> Überlege Dir, warum g in die Menge [mm]A_n[/mm] abbildet und
> injektiv ist.
> Was weißt Du mit der Induktionsvoraussetzung über g?
> Begründe dann die Bijektivität von f.
g ist doch dann wieder die gleich abbildung wie f in der voraussetzung, oder? wir bilden ja nur von [mm] A_n [/mm] auf [mm] A_n [/mm] ab, n+1 besitzt kein urbild. also folgt ja schon aus der IV, dass auch g injektiv und bijektiv ist, oder!
>
> 2. Fall: es gibt ein k aus [mm]A_n,[/mm] welches auf n+1 abgebildet
> wird, für welches also f(k)=n+1 ist.
> Der ist viel schwieriger.
> Überleg Dir erstmal, warum es nicht noch ein anderes k'
> geben kann, welches auch auf n+1 abgebildet wird.
>
> Nun kannst Du eine Funktion g: [mm]A_n \to[/mm] ... definieren mit
> g(x):= f(x) für [mm]x\not=k[/mm]
> g(k):=f(n+1).
>
> Überlege Dir, in welche Menge g abbidldet.
> Überlege Dir, warum diese Abbildung injektiv ist.
> Folgere mit der Induktionsvoraussetzung, daß die Abbildung
> bijektiv ist.
>
> Überlege Dir, daß die Einschränkungen von g und f auf die
> Menge [mm]A_n[/mm] \ [mm]\{k\}[/mm] = [mm](A_{n+1}[/mm] \ [mm]\{n,k\})[/mm] gleich sind.
>
> Und am Ende mußt Du noch die Kurve zur Bijektivität von f
> bekommen durch Betrachtung der Funktionswerte von n+1 und
> k.
>
> Viel Erfolg!
>
> Gruß v. Angela
>
>
|
|
|
| |
|
> > Beweis:
> >
> > Sei [mm]f:A_{n+1}\to A_{n+1}[/mm] injektiv.
> >
> > Hier können nun zwei Falle auftreten, entweder wird kein k
> > aus [mm]A_n[/mm] auf die n+1 abgebildet, oder es wird ein k aus [mm]A_n[/mm]
> > auf die n+1 abgebildet.
> > Die Fälle sind getrennt zu untersuchen.
> >
> > 1. Fall:
> > Der ist leicht. Schau die Einschränkung g von f auf [mm]A_n[/mm] an.
> > Überlege Dir, warum g in die Menge [mm]A_n[/mm] abbildet und
> > injektiv ist.
> > Was weißt Du mit der Induktionsvoraussetzung über g?
> > Begründe dann die Bijektivität von f.
>
> g ist doch dann wieder die gleich abbildung wie f in der
> voraussetzung, oder? wir bilden ja nur von [mm]A_n[/mm] auf [mm]A_n[/mm] ab,
Hallo,
ja, die Abbildung geht in die Menge [mm] A_n.
[/mm]
> also folgt ja schon aus der IV,
> dass auch g injektiv und bijektiv ist, oder!
Nein. Die Induktionsvoraussetzung setzt eine injektive Funktion voraus.
Bevor Du auf g die Induktionsvoraussetzung anwwenden kannst, mußt Du noch zeigen, daß die Funktion überhaupt injektiv ist.
Gruß v. Angela
> >
> > 2. Fall: es gibt ein k aus [mm]A_n,[/mm] welches auf n+1 abgebildet
> > wird, für welches also f(k)=n+1 ist.
> > Der ist viel schwieriger.
> > Überleg Dir erstmal, warum es nicht noch ein anderes k'
> > geben kann, welches auch auf n+1 abgebildet wird.
> >
> > Nun kannst Du eine Funktion g: [mm]A_n \to[/mm] ... definieren mit
> > g(x):= f(x) für [mm]x\not=k[/mm]
> > g(k):=f(n+1).
> >
> > Überlege Dir, in welche Menge g abbidldet.
> > Überlege Dir, warum diese Abbildung injektiv ist.
> > Folgere mit der Induktionsvoraussetzung, daß die
> Abbildung
> > bijektiv ist.
> >
> > Überlege Dir, daß die Einschränkungen von g und f auf die
> > Menge [mm]A_n[/mm] \ [mm]\{k\}[/mm] = [mm](A_{n+1}[/mm] \ [mm]\{n,k\})[/mm] gleich sind.
> >
> > Und am Ende mußt Du noch die Kurve zur Bijektivität von f
> > bekommen durch Betrachtung der Funktionswerte von n+1 und
> > k.
> >
> > Viel Erfolg!
> >
> > Gruß v. Angela
> >
> >
>
|
|
|
| |
|
| Aufgabe | 1. Fall:
> > Der ist leicht. Schau die Einschränkung g von f auf an.
> > Überlege Dir, warum g in die Menge abbildet und
> > injektiv ist.
> > Was weißt Du mit der Induktionsvoraussetzung über g?
> > Begründe dann die Bijektivität von f.
>
> g ist doch dann wieder die gleich abbildung wie f in der
> voraussetzung, oder? wir bilden ja nur von auf ab,
|
Wi ebekomme ich die Funktion g her? Wir haben doch nur die Funktion f. Weleche Einschränkungen hat g?
|
|
|
| |
|
> 1. Fall:
> > > Der ist leicht. Schau die Einschränkung g von f auf an.
> > > Überlege Dir, warum g in die Menge abbildet und
> > > injektiv ist.
> > > Was weißt Du mit der Induktionsvoraussetzung über g?
> > > Begründe dann die Bijektivität von f.
> >
> > g ist doch dann wieder die gleich abbildung wie f in der
> > voraussetzung, oder? wir bilden ja nur von auf ab,
>
> Wi ebekomme ich die Funktion g her? Wir haben doch nur die
> Funktion f. Weleche Einschränkungen hat g?
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
wir haben [mm] f:A_{n+1}\to A_{n+1} [/mm] gegeben, und ich betrachte die Funktion
[mm] g:A_n \to A_{n+1} [/mm] mit
g(x):=f(x) für alle [mm] x\in A_n.
[/mm]
Das ist die Funktion, die ich erhalte wenn ich mir die Funktion f nur auf der Menge [mm] A_n [/mm] anschaue, desahlb "Einschränkung".
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:58 Sa 25.10.2008 | | Autor: | gigi |
> > > Die Fälle sind getrennt zu untersuchen.
> > >
> > > 1. Fall:
> > > Der ist leicht. Schau die Einschränkung g von f auf [mm]A_n[/mm] an.
> > > Überlege Dir, warum g in die Menge [mm]A_n[/mm] abbildet und
> > > injektiv ist.
> > > Was weißt Du mit der Induktionsvoraussetzung über
> g?
> > > Begründe dann die Bijektivität von f.
>
> Nein. Die Induktionsvoraussetzung setzt eine injektive
> Funktion voraus.
> Bevor Du auf g die Induktionsvoraussetzung anwwenden
> kannst, mußt Du noch zeigen, daß die Funktion überhaupt
> injektiv ist.
tut mir leid, aber ich komme schon in diesem "einfachen" 1.fall nicht mit! wenn ich eine einschränkung vornehme, dann muss diese doch wieder den gleichen regeln folgen, wie auch f, also wär g auch injektiv. ich habe keine ahnung, wie ich beweisen soll, dass g auch injektiv ist!
>
> Gruß v. Angela
>
>
> > >
> > > 2. Fall: es gibt ein k aus [mm]A_n,[/mm] welches auf n+1 abgebildet
> > > wird, für welches also f(k)=n+1 ist.
> > > Der ist viel schwieriger.
> > > Überleg Dir erstmal, warum es nicht noch ein anderes
> k'
> > > geben kann, welches auch auf n+1 abgebildet wird.
und welche abbildung betrachten wir hier? f ohne einschränkung? dann wäre ja wieder die injektivität vorausgesetzt und es könnten nicht mehrere k existieren.
> > >
> > > Nun kannst Du eine Funktion g: [mm]A_n \to[/mm] ... definieren mit
> > > g(x):= f(x) für [mm]x\not=k[/mm]
> > > g(k):=f(n+1).
wozu brauche ich die nun?
> > > Überlege Dir, in welche Menge g abbidldet.
> > > Überlege Dir, warum diese Abbildung injektiv ist.
> > > Folgere mit der Induktionsvoraussetzung, daß die
> > Abbildung
> > > bijektiv ist.
> > >
> > > Überlege Dir, daß die Einschränkungen von g und f auf die
> > > Menge [mm]A_n[/mm] \ [mm]\{k\}[/mm] = [mm](A_{n+1}[/mm] \ [mm]\{n,k\})[/mm] gleich sind.
> > >
> > > Und am Ende mußt Du noch die Kurve zur Bijektivität von f
> > > bekommen durch Betrachtung der Funktionswerte von n+1 und
> > > k.
> > >
> > > Viel Erfolg!
sorry, ic versuche wirklich, das zu verstehen, aber irgendwo klemmt es gewaltig!
> > > Gruß v. Angela
> > >
> > >
> >
>
|
|
|
| |
|
> > > > Die Fälle sind getrennt zu untersuchen.
> > > >
> > > > 1. Fall:
> > > > Der ist leicht. Schau die Einschränkung g von f auf [mm]A_n[/mm] an.
> > > > Überlege Dir, warum g in die Menge [mm]A_n[/mm] abbildet und
> > > > injektiv ist.
> > > > Was weißt Du mit der Induktionsvoraussetzung über
> > g?
> > > > Begründe dann die Bijektivität von f.
>
>
> >
> > Nein. Die Induktionsvoraussetzung setzt eine injektive
> > Funktion voraus.
> > Bevor Du auf g die Induktionsvoraussetzung anwwenden
> > kannst, mußt Du noch zeigen, daß die Funktion überhaupt
> > injektiv ist.
>
> tut mir leid, aber ich komme schon in diesem "einfachen"
> 1.fall nicht mit! wenn ich eine einschränkung vornehme,
> dann muss diese doch wieder den gleichen regeln folgen, wie
> auch f, also wär g auch injektiv.
Hallo,
das wäre doch eine gute Begründung.
Aber Du mußt die Injektivität von g unbedingt erwähnen.
Wenn Du sie "rechnerisch" beweisen willst ist das auch nicht schwer. Du weißt doch, daß für jedes [mm] x\in A_n [/mm] g(x)=f(x) ist.
> > > > 2. Fall: es gibt ein k aus [mm]A_n,[/mm] welches auf n+1 abgebildet
> > > > wird, für welches also f(k)=n+1 ist.
> > > > Der ist viel schwieriger.
> > > > Überleg Dir erstmal, warum es nicht noch ein
> anderes
> > k'
> > > > geben kann, welches auch auf n+1 abgebildet wird.
> und welche abbildung betrachten wir hier? f ohne
> einschränkung? dann wäre ja wieder die injektivität
> vorausgesetzt und es könnten nicht mehrere k existieren.
> > > >
> > > > Nun kannst Du eine Funktion g: [mm]A_n \to[/mm] ... definieren mit
> > > > g(x):= f(x) für [mm]x\not=k[/mm]
> > > > g(k):=f(n+1).
>
>
> wozu brauche ich die nun?
Du brauchst zum Verwenden der Induktionsvoraussetzung eine injektive Abbildung von [mm] A_n \to A_n.
[/mm]
> > > > Überlege Dir, in welche Menge g abbidldet.
> > > > Überlege Dir, warum diese Abbildung injektiv
> ist.
> > > > Folgere mit der Induktionsvoraussetzung, daß die
> > > Abbildung
> > > > bijektiv ist.
> > > >
> > > > Überlege Dir, daß die Einschränkungen von g und f auf die
> > > > Menge [mm]A_n[/mm] \ [mm]\{k\}[/mm] = [mm](A_{n+1}[/mm] \ [mm]\{n,k\})[/mm] gleich sind.
> > > >
> > > > Und am Ende mußt Du noch die Kurve zur Bijektivität von f
> > > > bekommen durch Betrachtung der Funktionswerte von n+1 und
> > > > k.
> > > >
> > > > Viel Erfolg!
>
> sorry, ic versuche wirklich, das zu verstehen, aber
> irgendwo klemmt es gewaltig!
Versuch es doch erstmal auf dem Papier an einem konkreten Beispiel herauszufinden, wie man solch eine Induktion machen könnte.
Nimm an, Du hättest es für n=4 gezeigt, und nun hättest Du . B. die Funktion f vorliegen mit
[mm] 1\mapsto [/mm] 3
[mm] 2\mapsto [/mm] 2
[mm] 3\mapsto [/mm] 5
[mm] 4\mapsto [/mm] 1
[mm] 5\mapsto [/mm] 4.
Ich mache das immer so, wenn ich mich auf Ideen bringen will oder nicht mehr weiterweiß.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:34 So 26.10.2008 | | Autor: | gigi |
> > > > > Begründe dann die Bijektivität von f.
> >
> >
> > >
> Hallo,
>
> das wäre doch eine gute Begründung.
> Aber Du mußt die Injektivität von g unbedingt erwähnen.
>
> Wenn Du sie "rechnerisch" beweisen willst ist das auch
> nicht schwer. Du weißt doch, daß für jedes [mm]x\in A_n[/mm]
> g(x)=f(x) ist.
>
kann man dann auf die injektivität von g direkt die IV anwenden und folgern, dass g bijektiv ist?
>
> > > > > 2. Fall: es gibt ein k aus [mm]A_n,[/mm] welches auf n+1 abgebildet
> > > > > wird, für welches also f(k)=n+1 ist.
> > > > > Der ist viel schwieriger.
> > > > > Überleg Dir erstmal, warum es nicht noch ein
> > anderes
> > > k'
> > > > > geben kann, welches auch auf n+1 abgebildet wird.
und welche abbildung betrachten wir hier? f ohne
einschränkung? dann wäre ja wieder die injektivität vorausgesetzt und es könnten nicht mehrere k existieren.
> > > > >
> > > > > Nun kannst Du eine Funktion g: [mm]A_n \to[/mm] ... definieren mit
> > > > > g(x):= f(x) für [mm]x\not=k[/mm]
> > > > > g(k):=f(n+1).
> >
>
> > > > > Überlege Dir, in welche Menge g abbidldet.
g bildet doch in [mm] A_{n+1} [/mm] ab, oder?
> > > > > Überlege Dir, warum diese Abbildung injektiv
> > ist.
g(x) ist ja durch f(x) definiert, also nach vor. injektiv. was genau ist nun mein k: irgendein element aus der urbildmenge [mm] A_n [/mm] oder genau das element n+1? g(k) bildet ja dann eigentlich auch nur einen wert auf n+1 ab, der noch nicht durch g(x) erfasst worden ist, so ist wieder jedem bild höchstens ein urbild zugeordnet, oder?
wie beweise ich genau die injektivität?
> > > > > Folgere mit der Induktionsvoraussetzung, daß
> die
> > > > Abbildung
> > > > > bijektiv ist.
> > > > >
> > > > > Überlege Dir, daß die Einschränkungen von g und f auf die
> > > > > Menge [mm]A_n[/mm] \ [mm]\{k\}[/mm] = [mm](A_{n+1}[/mm] \ [mm]\{n,k\})[/mm] gleich sind.
beweis?
> > > > >
> > > > > Und am Ende mußt Du noch die Kurve zur Bijektivität von f
> > > > > bekommen durch Betrachtung der Funktionswerte von n+1 und
> > > > > k.
f(k)=n+1=f(n+1) ??
> > > > >
> > > > > Viel Erfolg!
> >
>
> Nimm an, Du hättest es für n=4 gezeigt, und nun hättest Du
> . B. die Funktion f vorliegen mit
>
> [mm]1\mapsto[/mm] 3
> [mm]2\mapsto[/mm] 2
> [mm]3\mapsto[/mm] 5
> [mm]4\mapsto[/mm] 1
> [mm]5\mapsto[/mm] 4.
>
erklären wir das k etc an diesem bsp:
wäre k hier die 5 auf der linken seite?
gruß und dank
|
|
|
| |
|
> kann man dann auf die injektivität von g direkt die IV
> anwenden und folgern, dass g bijektiv ist?
Hallo,
ja, wenn Du im Fall 1 hast, daß die Funktion bijektiv ist und von [mm] A_n [/mm] nach [mm] A_n [/mm] geht, lieefert Dir die Induktionsvoraussetzung die Bijektivität.
> >
> > > > > > 2. Fall: es gibt ein k aus [mm]A_n,[/mm] welches auf n+1 abgebildet
> > > > > > wird, für welches also f(k)=n+1 ist.
> > > > > > Der ist viel schwieriger.
> > > > > > Überleg Dir erstmal, warum es nicht noch
> ein
> > > anderes
> > > > k'
> > > > > > geben kann, welches auch auf n+1 abgebildet wird.
>
> und welche abbildung betrachten wir hier? f ohne
> einschränkung?
Ja.
> dann wäre ja wieder die injektivität
> vorausgesetzt und es könnten nicht mehrere k existieren.
Genau.
>
> > > > > >
> > > > > > Nun kannst Du eine Funktion g: [mm]A_n \to[/mm] ... definieren mit
> > > > > > g(x):= f(x) für [mm]x\not=k[/mm]
> > > > > > g(k):=f(n+1).
> > >
>
> >
> > > > > > Überlege Dir, in welche Menge g abbidldet.
>
> g bildet doch in [mm]A_{n+1}[/mm] ab, oder?
Was anderes bleibt ihr ja nicht übrig.
Aber schau mal genauer hin: dem einzigen Element k, welches durch f auf n+1 abgebildet wird, wird doch durch g ein anderer Funktionswert zugewiesen.
Also bildet G in die Menge [mm] A_n [/mm] ab!
> > > > > > Überlege Dir, warum diese Abbildung injektiv
> > > ist.
>
> g(x) ist ja durch f(x) definiert, also nach vor. injektiv.
Hm. Ich meine, daß Du das genauer zeigen mußt:
Für [mm] x\in A_n [/mm] \ [mm] \{k} [/mm] sind f und g gleich, und folglich ist g eingeschränkt auf [mm] A_n [/mm] \ [mm] \{k} [/mm] auch injektiv, das ist eigentlich klar.
Zeigen mußt Du aber, da g ja auf ganz [mm] A_n [/mm] definiert ist, daß auch aus g(k)=g(x) folgt: k=x. (Ist sehr einfach.
> was genau ist nun mein k: irgendein element aus der
> urbildmenge [mm]A_n[/mm] oder genau das element n+1?
Es ist ein bestimmtes Element der Urbildmenge: nämlich das Element, welches auf n+1 abgebildet wird.
> g(k) bildet ja
> dann eigentlich auch nur einen wert auf n+1 ab, der noch
> nicht durch g(x) erfasst worden ist,
Nein. g ist doch gerade so definiert, daß kein(!!!) Wert auf n+1 abgebildet wird.
> so ist wieder jedem
> bild höchstens ein urbild zugeordnet, oder?
> wie beweise ich genau die injektivität?
Wie immer. Du mußt zeigen, daß aus "Funktionswerte gleich" folgt "Argumente gleich".
>
> > > > > > Folgere mit der Induktionsvoraussetzung, daß
> > die
> > > > > Abbildung
> > > > > > bijektiv ist.
> > > > > >
> > > > > > Überlege Dir, daß die Einschränkungen von g und f auf die
> > > > > > Menge [mm]A_n[/mm] \ [mm]\{k\}[/mm] = [mm](A_{n+1}[/mm] \ [mm]\{n,k\})[/mm] gleich sind.
>
> beweis?
Klar muß das bewiesen oder begründet werden.
Wann sind zwei Funktionen gleich? Wenn sie an jeder Selle denselben Funktionswert haben.
> > > > > >
> > > > > > Und am Ende mußt Du noch die Kurve zur Bijektivität von f
> > > > > > bekommen durch Betrachtung der Funktionswerte von n+1 und
> > > > > > k.
>
> f(k)=n+1=f(n+1) ??
Ganz sicher nicht. Sonst wäre ja f nicht injektiv.
> f(k)=n+1 stimmt.
Worauf n+1 abgebildet wird, weiß man ja nicht genau. Man weiß nur, worauf es nicht abgebildet wird.
> > Nimm an, Du hättest es für n=4 gezeigt, und nun hättest Du
> > . B. die Funktion f vorliegen mit
> >
> > [mm]1\mapsto[/mm] 3
> > [mm]2\mapsto[/mm] 2
> > [mm]3\mapsto[/mm] 5
> > [mm]4\mapsto[/mm] 1
> > [mm]5\mapsto[/mm] 4.
> >
>
> erklären wir das k etc an diesem bsp:
> wäre k hier die 5 auf der linken seite?
Nein, die 3. Die 3 wird ja auf n+1=4+1 abgebildet.
Gruß v. Angela
>
>
> gruß und dank
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:55 So 26.10.2008 | | Autor: | gigi |
>
>
> > >
> > > > > > > 2. Fall: es gibt ein k aus [mm]A_n,[/mm] welches auf n+1 abgebildet
> > > > > > > wird, für welches also f(k)=n+1 ist.
> > > > > > > Der ist viel schwieriger.
> > > > > > > Überleg Dir erstmal, warum es nicht noch
> > ein
> > > > anderes
> > > > > k'
> > > > > > > geben kann, welches auch auf n+1 abgebildet wird.
> >
> > > > > > >
> > > > > > > Nun kannst Du eine Funktion g: [mm]A_n \to[/mm] ... definieren mit
> > > > > > > g(x):= f(x) für [mm]x\not=k[/mm]
> > > > > > > g(k):=f(n+1).
> > > >
> >
> > >
> > > > > > > Überlege Dir, in welche Menge g abbidldet.
> >
> > g bildet doch in [mm]A_{n+1}[/mm] ab, oder?
>
> Was anderes bleibt ihr ja nicht übrig.
>
> Aber schau mal genauer hin: dem einzigen Element k,
> welches durch f auf n+1 abgebildet wird, wird doch durch g
> ein anderer Funktionswert zugewiesen.
>
> Also bildet G in die Menge [mm]A_n[/mm] ab!
ich verstehe einfach nicht, warum wir diese funktion g im 2.fall benötigen, warum weisen wir dem wert k einen anderen funktionswert zu? und warum gerade f(n+1)
>
>
> > > > > > > Überlege Dir, warum diese Abbildung injektiv
>
>
> Zeigen mußt Du aber, da g ja auf ganz [mm]A_n[/mm] definiert ist,
> daß auch aus g(k)=g(x) folgt: k=x. (Ist sehr einfach.
achja?? aus g(k)=g(x) folgt ja, dass auch f(n+1)=f(x), da ja f injektiv ist, muss gelten n+1=x und folglich gilt auch x=k ???
folglich ist also auch g injektiv und nach IV bijektiv.
> > > > > > >
> > > > > > > Überlege Dir, daß die Einschränkungen von g und f auf die
> > > > > > > Menge [mm]A_n[/mm] \ [mm]\{k\}[/mm] = [mm](A_{n+1}[/mm] \ [mm]\{n,k\})[/mm] gleich sind.
> >
> > beweis?
>
> Klar muß das bewiesen oder begründet werden.
> Wann sind zwei Funktionen gleich? Wenn sie an jeder Selle
> denselben Funktionswert haben.
>
> > > > > > >
> > > > > > > Und am Ende mußt Du noch die Kurve zur Bijektivität von f
> > > > > > > bekommen durch Betrachtung der Funktionswerte von n+1 und
> > > > > > > k.
> >
> > f(k)=n+1=f(n+1) ??
>
> Ganz sicher nicht. Sonst wäre ja f nicht injektiv.
>
> > f(k)=n+1 stimmt.
>
> Worauf n+1 abgebildet wird, weiß man ja nicht genau. Man
> weiß nur, worauf es nicht abgebildet wird.
>
>
> > >
> >
grüße.
>
|
|
|
| |
|
> > Also bildet G in die Menge [mm]A_n[/mm] ab!
>
> ich verstehe einfach nicht, warum wir diese funktion g im
> 2.fall benötigen, warum weisen wir dem wert k einen anderen
> funktionswert zu? und warum gerade f(n+1)
Hallo,
hast Du den Beweisgang denn mal für n=4 ---> n=4+1=5 durchgespielt?
Ich hatte es schon an anderer Stelle erwähnt. Um die Induktionsvoraussetzung anwenden zu können, benötigen wir ja eine injektive Funktion, welche vom [mm] A_n [/mm] in den [mm] A_n [/mm] abbildet. Dies Funktion soll natürlich mit f möglichst viel zu tun haben, und sie wird eben aufgrund einer guten Idee auf diese Weise konstruiert.
Das k muß einen anderen Funktionswert bekommen, weil f(k)=n+1 ist, wir aber eine Funktion brauchen, die nach [mm] A_n [/mm] abbildet.
> >
> >
> > > > > > > > Überlege Dir, warum diese Abbildung injektiv
> >
>
> >
> > Zeigen mußt Du aber, da g ja auf ganz [mm]A_n[/mm] definiert ist,
> > daß auch aus g(k)=g(x) folgt: k=x. (Ist sehr einfach.
>
> achja??
Ja.
Angenommen, es gibt ein [mm] x\in A_n [/mm] mit
> g(k)=g(x)
==> x=k oder (!!!)
> f(n+1)=f(x), da
> ja f injektiv ist, muss gelten
> n+1=x oder x=k.
Wegen [mm] x\in A_n [/mm] ist ersteres nicht möglich.
> und folglich gilt auch
> x=k ???
Wie Du siehst: ja. Aber aus n+1=x kannst Du das natürlich nicht folgern.
> folglich ist also auch g injektiv und nach IV bijektiv.
Ja.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:52 So 26.10.2008 | | Autor: | gigi |
>Überlege Dir, daß die Einschränkungen von g und f auf die Menge $ [mm] A_n [/mm] $ \ $ [mm] \{k\} [/mm] $ = $ [mm] (A_{n+1} [/mm] $ \ $ [mm] \{n,k\}) [/mm] $ gleich sind.
die erste einschränkung ist die vom fall 1. die 2. verstehe ich nicht! und was genau ist nun gleich und wieso?
>Und am Ende mußt Du noch die Kurve zur Bijektivität von f bekommen durch Betrachtung der Funktionswerte von n+1 und k.
und wie kommt man von g wieder zu f? wie schreib ich denn auf, dass aus der bijektivität von g die bijektivität von [mm] A_{n+1} [/mm] folgt?
|
|
|
| |
|
> >Überlege Dir, daß die Einschränkungen von g und f auf die
> Menge [mm]A_n[/mm] \ [mm]\{k\}[/mm] = [mm](A_{n+1}[/mm] \ [mm]\{n,k\})[/mm] gleich sind.
>
>
> die erste einschränkung ist die vom fall 1. die 2. verstehe
> ich nicht!
> und was genau ist nun gleich und wieso?
Hallo,
oh, entschuldige, ein Tippfehler: [mm]A_n[/mm] \ [mm]\{k\}[/mm] ist natürlich [mm] A_{n+1}[/mm] [/mm] \ [mm][mm] \{n\red{+1},k\}.
[/mm]
Das war aber nicht der Grund fürs Unverständnis, oder?
Da steht (bzw. sollte stehen), daß Du, sofern Du die Funktionen f und g eingeschränkt auf die Menge [mm]A_n[/mm] \ [mm]\{k\}[/mm] , welche gleich der Menge [mm] A_{n+1} [/mm] \ [mm] \{n+1,k\} [/mm] ist, betrachtest, feststellen kannst, daß die beiden Funktionen auf diesem eingeschränkten Definitionsbereich gleich sind.
>
> >Und am Ende mußt Du noch die Kurve zur Bijektivität von f
> bekommen durch Betrachtung der Funktionswerte von n+1 und
> k.
>
> und wie kommt man von g wieder zu f?
> wie schreib ich denn
> auf, dass aus der bijektivität von g die bijektivität von
> [mm]A_{n+1}[/mm] folgt?
Du hast
f(x)=g(x) für alle [mm] x\in A_{n+1} [/mm] \ [mm] \{n+1,k\} [/mm]
f(n+1)=g(k)
f(k)=n+1
und Du weißt, daß g bijektiv ist.
Gruß v. Angela
|
|
|
| |
|
Hm.. und ich habe mir so den Kopf zermatert :-(
|
|
|
|
